www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8550] New: std.container.InlinedArray

reply d-bugmail puremagic.com writes:
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: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



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: -------
Aug 15 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8550


Daniel Cousens <daniel350 bigpond.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |daniel350 bigpond.com



PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 15 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8550


Dmitry Olshansky <dmitry.olsh gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dmitry.olsh gmail.com



11:35:56 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 15 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8550






 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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 15 2012