www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Small-size-optimized Appender

reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
Would appreciated feedback on this small-size-optimized Appender

/** Small-Size-Optimized (SSO) `Appender`.
  */
struct SSOAppender(T, size_t smallCapacity)
if (smallCapacity >= 1)
{
     import std.array : Appender;
     import fixed_array : FixedArray;

     void put(T x)  trusted
     {
         if (_isLarge)
             _large.put(x);
         else if (_small.full)
         {
             import std.algorithm.mutation : moveEmplaceAll;
             T[smallCapacity] tmp = void;
             moveEmplaceAll(_small[], tmp[0 .. _small.length]);
             import core.lifetime : emplace;
             emplace!Large(&_large);
             _large.put(tmp[]);
             _large.put(x);
             _isLarge = 1;
         }
         else
             _small.put(x);
     }

     inout(T)[] data() inout return scope
     {
         if (_isLarge)
             return _large.data[];
         else
             return _small[];
     }

private:
     alias Small = FixedArray!(T, smallCapacity);
     alias Large = Appender!(T[]);
     union
     {
         Small _small;
         Large _large;
     }
     bool _isLarge;
}

I can inline `FixedArray` into a static array if wanted. It's 
basically a static array with a length that provides a put API.

Source: 
https://github.com/nordlow/phobos-next/blob/e914975613e9a5153313acf29b1b183326823ca3/src/nxt/sso_appender.d
Oct 16 2020
next sibling parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 16 October 2020 at 19:06:33 UTC, Per Nordlöw wrote:

 Would appreciated feedback on this small-size-optimized Appender


Perhaps this could be integrated into

     Appender(A, size_t smallCapacity)

that behaves like existing `Appender` when smallCapacity is 0.
Oct 16 2020
prev sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Friday, 16 October 2020 at 19:06:33 UTC, Per Nordlöw wrote:

 Would appreciated feedback on this small-size-optimized Appender

 /** Small-Size-Optimized (SSO) `Appender`.
  */
 struct SSOAppender(T, size_t smallCapacity)
 if (smallCapacity >= 1)
 {
     import std.array : Appender;
     import fixed_array : FixedArray;

     void put(T x)  trusted
     {
         if (_isLarge)
             _large.put(x);


This will call a  system postblit or copy constructor in  safe 
code.

[...]

     union
     {
         Small _small;
         Large _large;
     }
     bool _isLarge;
 }


If you're using a union, you need to define a copy constructor 
and a destructor, because the compiler will not automatically 
insert calls to these functions for your union members.

You could also use a library like sumtype or taggedalgebraic that 
handles these details for you, which would be my recommended 
approach.


 I can inline `FixedArray` into a static array if wanted. It's 
 basically a static array with a length that provides a put API.

 Source: 
 https://github.com/nordlow/phobos-next/blob/e914975613e9a5153313acf29b1b183326823ca3/src/nxt/sso_appender.d


FixedArray [1] suffers from the safety issue explained here:

https://gist.github.com/pbackus/39b13e8a2c6aea0e090e4b1fe8046df5#example-short-string

The short version is: because the compiler does not consider an 
integer to be an unsafe type, it will freely allow  safe code to 
corrupt the _length variable, so you must include bounds-checking 
in all of your  trusted code (that is, you must use _store[i] 
instead of _store.ptr[i]).

[1] 
https://github.com/nordlow/phobos-next/blob/e914975613e9a5153313acf29b1b183326823ca3/src/nxt/fixed_array.d#L101
Oct 16 2020
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 16 October 2020 at 20:32:43 UTC, Paul Backus wrote:

             _large.put(x);




Should I use

     import core.lifetime : move;
     _large.put(x.move);

instead?
Oct 16 2020
parent reply Paul Backus <snarwin gmail.com> writes:
On Friday, 16 October 2020 at 20:36:57 UTC, Per Nordlöw wrote:

 On Friday, 16 October 2020 at 20:32:43 UTC, Paul Backus wrote:

             _large.put(x);




 Should I use

     import core.lifetime : move;
     _large.put(x.move);

 instead?


Just remove the  trusted annotation from the function and wrap 
the calls to  system functions in  trusted lambdas. Attribute 
inference will take care of the rest.
Oct 16 2020
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 16 October 2020 at 20:45:24 UTC, Paul Backus wrote:

 Just remove the  trusted annotation from the function and wrap 
 the calls to  system functions in  trusted lambdas. Attribute 
 inference will take care of the rest.


Thanks. Will that be inlined by default or only in release mode?
Oct 16 2020
parent reply Paul Backus <snarwin gmail.com> writes:
On Friday, 16 October 2020 at 20:52:48 UTC, Per Nordlöw wrote:

 On Friday, 16 October 2020 at 20:45:24 UTC, Paul Backus wrote:

 Just remove the  trusted annotation from the function and wrap 
 the calls to  system functions in  trusted lambdas. Attribute 
 inference will take care of the rest.


 Thanks. Will that be inlined by default or only in release mode?


Immediately-called lambdas are always inlined, even by DMD in 
non-release mode.
Oct 16 2020
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 16 October 2020 at 20:55:07 UTC, Paul Backus wrote:

 Immediately-called lambdas are always inlined, even by DMD in 
 non-release mode.


Nice. Thanks. I still believe

      trusted { ... }

would be more appreciated, though. I always forget the syntax for 
inline lambdas and I've been using D since 2013.

Has there been any objections against adding something similar?
Oct 16 2020