std.container.InlinedArray

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2012-08-15T06:09:32Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=8550

CC List

• daniel350
• dmitry.olsh (@DmitryOlshansky)

Description

I suggest to add a collection like this to Phobos.

Two use cases:
- Inside a critical loop you have to build a dynamic array many times over, most times this array is very small, but once in a while it grows longer and you don't want to set a max length.
- You have thousands or millions of struct instances that need to contain a dynamic array, most of those arrays will contain only a very small number of items, but once in a while they will need to contain more items.

In those case replacing a dynamic array with an InlinedArray has some advantages:
- In most cases the local memory is enough, avoiding slow heap allocations and deallocations managed by the GC, and reducing total memory used.
- In most cases the data is stored locally, avoiding indirect access and increasing cache coherence.

There are some disadvantages:
- To replace a dynamic array with an InlinedArray you need to know that the dynamic array doesn't grow too much in your program. To do this you have to add some instrumentation to your program to measure the mode of the length of the arrays. It's not too much hard to add such instrumentation to InlinedArray to manually tune the staticLen value.
- It's not always a drop-in replacement for a dynamic array.


This is a minimal implementation, it lacks most methods. I've replaced two dynamic arrays with InlinedArrays inside a struct allocated many times by a real program, speeding up the program almost 10%:


struct InlinedArray(T, size_t staticLen, Tlen=uint) {
    enum isUsingDynamic = Tlen.max;
    union {
        T[staticLen] static_items;
        T[] dynamic_items;
    }
    private Tlen len;

    @property size_t length() const pure nothrow {
        return (len == isUsingDynamic) ? dynamic_items.length : len;
    }

    T[] opSlice() pure nothrow {
        return (len == isUsingDynamic) ? dynamic_items : static_items[0 .. len];
    }

    void opOpAssign(string op:"~")(T item) pure nothrow {
        if (len == isUsingDynamic) {
            dynamic_items ~= item;
        } else {
            if (len < staticLen) {
                static_items[len] = item;
                len++;
            } else {
                dynamic_items = static_items ~ item;
                len = isUsingDynamic;
            }
        }
    }
}

pragma(msg, InlinedArray!(int, 2).sizeof); // 12 bytes
pragma(msg, InlinedArray!(int, 1).sizeof); // 12 bytes, using 1 wastes space
pragma(msg, InlinedArray!(char, 11, ubyte).sizeof); // only 12 bytes!

void main() {
    import std.stdio;

    InlinedArray!(int, 2) a;
    writeln(a.len, " ", a.static_items, " ", a[]);
    a ~= 5;
    writeln(a.len, " ", a.static_items, " ", a[]);
    a ~= 3;
    writeln(a.len, " ", a.static_items, " ", a[]);
    a ~= 7;
    writeln(a.len, " ", a.static_items, " ", a.dynamic_items, " ", a.length, " ", a[]);
    a ~= 11;
    writeln(a.len, " ", a.static_items, " ", a.dynamic_items, " ", a.length, " ", a[]);
}


Output:

12u
12u
12u
0 [0, 0] []
1 [5, 0] [5]
2 [5, 3] [5, 3]
4294967295 [3, 27140064] [5, 3, 7] 3 [5, 3, 7]
4294967295 [4, 27144160] [5, 3, 7, 11] 4 [5, 3, 7, 11]

[dlangBugzillaToGithub]

daniel350 commented on 2012-08-15T06:30:37Z

This is a very cool idea. 

The concept put simply is just your typical dynamic array with a pre-allocated buffer that it *can* use up until it surpasses that buffer, in which case that buffer is then ignored (at the cost of the size of the buffer, which is probably negligible in most cases).

The only problems I can foresee is perhaps little 'gotchas' in that union of a dynamic array and static array. I'd have to investigate to know for sure on that. 
Lots of unit tests for this I think, and definitely some information needed from those in the know about the compiler back end.

[dlangBugzillaToGithub]

dmitry.olsh (@DmitryOlshansky) commented on 2012-08-15T11:35:56Z

This is called small array optimization except for size of array is hardwired so that the whole struct fits a couple of words. I suggest to just add it to std.container.Array.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2012-08-15T15:34:34Z

(In reply to comment #2)
> This is called small array optimization except for size of array is hardwired
> so that the whole struct fits a couple of words. I suggest to just add it to
> std.container.Array.

Yes, this is similar to small array optimization, but this variant of the idea allows you to tune how much space you want to save locally.

Beside staticLen, this InlinedArray also optionally takes the Tlen type. If you are using something very small, like ubytes or chars or shorts, and you want to pack as many of them as possible in the local static array, you are allowed to define Tlen as ubyte (or ushort) instead of uint or size_t. So InlinedArray!(int,1) takes 12 bytes and stores up to 11 ubytes/chars.