Re: Small Buffer Optimization for string and friends

[Per Nordlöw via Digitalmars-d]

On Sunday, 8 April 2012 at 05:56:36 UTC, Andrei Alexandrescu 
wrote:
Walter and I discussed today about using the small string 
optimization in string and other arrays of immutable small 
objects.

I put together SSOString at
https://github.com/nordlow/phobos-next/blob/967eb1088fbfab8be5ccd811b66e7b5171b46acf/src/sso_string.d

that uses small-string-optimization on top of a normal D string 
(slice).

I'm satisfied with everything excepts that -dip1000 doesn't 
vorbids `f` from compiling.

I also don't understand why `x[0]` cannot be returned by ref in 
the function `g`.

Comments are welcome.

Contents of sso_string.d follows:

module sso_string;

/** Small-size-optimized string.
 *
 * Store on the stack if constructed with <= `smallCapacity` 
number of
 * characters, otherwise on the GC heap.
 */
struct SSOString
{
    private alias E = immutable(char); // immutable element type
    private alias ME = char;           // mutable element type

    pure nothrow:

    /** Construct from `elements`, with potential GC-allocation 
(iff
     * `elements.length > smallCapacity`).
     */
    this()(scope ME[] elements) @trusted // template-lazy
    {
        if (elements.length <= smallCapacity)
        {
            small.data[0 .. elements.length] = elements;
            small.length = 
cast(typeof(small.length))(2*elements.length);
        }
        else
        {
            large = elements.idup; // GC-allocate
            raw.length *= 2;  // shift up
            raw.length |= 1;  // tag as large
        }
    }

    @nogc:

    // TODO add @nogc overload to construct from mutable static 
array <= smallCapacity

    /** Construct from `elements` without any kind of heap 
allocation.
     */
    this()(immutable(E)[] elements) @trusted // template-lazy
    {
        if (elements.length <= smallCapacity)
        {
            small.data[0 .. elements.length] = elements;
            small.length = 
cast(typeof(small.length))(2*elements.length);
        }
        else
        {
            large = elements;   // @nogc
            raw.length *= 2;    // shift up
            raw.length |= 1;    // tag as large
        }
    }

    @property size_t length() const @trusted
    {
        if (isLarge)
        {
            return large.length/2; // skip first bit
        }
        else
        {
            return small.length/2; // skip fist bit
        }
    }

    scope ref inout(E) opIndex(size_t index) inout return @trusted
    {
        return opSlice()[index]; // automatic range checking
    }

    scope inout(E)[] opSlice() inout return @trusted
    {
        if (isLarge)
        {
            union RawLarge
            {
                Raw raw;
                Large large;
            }
            RawLarge copy = void;
            copy.large = cast(Large)large;
            copy.raw.length /= 2; // adjust length
            return copy.large;
        }
        else
        {
            return small.data[0 .. small.length/2]; // scoped
        }
    }

    private @property bool isLarge() const @trusted
    {
        return large.length & 1; // first bit discriminates small 
from large
    }

private:
    struct Raw                  // same memory layout as `E[]`
    {
        size_t length;          // can be bit-fiddled without GC 
allocation
        E* ptr;
    }

    alias Large = E[];

    enum smallCapacity = Large.sizeof - Small.length.sizeof;
    static assert(smallCapacity > 0, "No room for small elements 
for E being " ~ E.stringof);
    version(LittleEndian) // see: 
http://forum.dlang.org/posting/zifyahfohbwavwkwbgmw
    {
        struct Small
        {
            ubyte length;
            E[smallCapacity] data;
        }
    }
    else
    {
        static assert(0, "BigEndian support and test");
    }

    union
    {
        Raw raw;
        Large large;
        Small small;
    }
}

///
@safe pure nothrow @nogc unittest
{
    import container_traits : mustAddGCRange;
    alias S = SSOString;

    static assert(S.sizeof == 2*size_t.sizeof); // two words
    static assert(S.smallCapacity == 15);
    static assert(mustAddGCRange!S); // `Large large.ptr` must be 
scanned

    auto s0 = S.init;
    assert(s0.length == 0);
    assert(!s0.isLarge);
    assert(s0[] == []);

    const s7 = S("0123456");
    static assert(is(typeof(s7[]) == string));
    assert(!s7.isLarge);
    assert(s7.length == 7);
    assert(s7[] == "0123456");
    // TODO assert(s7[0 .. 4] == "0123");

    const s15 = S("012345678901234");
    static assert(is(typeof(s15[]) == string));
    assert(!s15.isLarge);
    assert(s15.length == 15);
    assert(s15[] == "012345678901234");

    const s16 = S("0123456789abcdef");
    static assert(is(typeof(s16[]) == string));
    assert(s16.isLarge);
    assert(s16.length == 16);
    assert(s16[] == "0123456789abcdef");
    assert(s16[0] == '0');
    assert(s16[10] == 'a');
    assert(s16[15] == 'f');

    // TODO static assert(!__traits(compiles, { auto _ = 
S((char[]).init); }));

    string f() @safe pure nothrow @nogc
    {
        S x;
        return x[];             // TODO should fail with -dip1000
    }

    // TODO activate
    // ref char g() @safe pure nothrow @nogc
    // {
    //     S x;
    //     return x[0];             // TODO should fail with 
-dip1000
    // }
}