http://d.puremagic.com/issues/show_bug.cgi?id=8550
Summary: std.container.InlinedArray Product: D Version: D2 Platform: All OS/Version: All Status: NEW Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nob...@puremagic.com ReportedBy: bearophile_h...@eml.cc --- Comment #0 from bearophile_h...@eml.cc 2012-08-15 06:09:32 PDT --- 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] -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------