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: -------
