[phobos] Clear appending cache?

[Steve Schveighoffer]

The major speedup in any append operation is to use the free space of the 
current block without requesting more space from the GC.

To determine if the new data can fit in the current block, one needs to get the 
current block size.  With builtin arrays, this is a lookup of both the block 
info for the current block (which either is in the LRU cache or is obtained by 
searching the heap metadata), and then a look inside the hidden 'allocated' 
length element inside the memory block.  When the cache is used, this is not a 
complexity-wise expensive operation (it should be a constant), but it's a rather 
large constant.  You must call several functions, do a search through the cache, 
figure out where your 'allocated' length is stored in the block, etc.

With Appender, the capacity is stored with the instance, so instead of all these 
lookups in the GC/cache etc, it's just a pointer dereference.  Plus, since we 
assume the appender owns the data, it is assumed we can always append.  So the 
constant factor is drastically smaller (a couple instructions), and guaranteed 
bounded, does not have any interaction with other threads (no GC lock to take).

I think Appender should be as fast as possible when appending data, since that 
is what it's supposed to be good at.  I don't see a point of simply wrapping 
builtin array appending, what's so bad about the builtin syntax that you need to 
define a wrapper around it?

-Steve



----- Original Message ----
> From: Andrei Alexandrescu <andrei at erdani.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Sent: Thu, November 18, 2010 4:42:02 PM
> Subject: Re: [phobos] Clear appending cache?
> 
> What is the efficiency difference? Can it be reduced?
> 
> Andrei
> 
> On  11/18/10 1:36 PM, Steve Schveighoffer wrote:
> > Appender is currently much  faster than array appending because it has a
> > dedicated place to store  the array length/capacity.  Simply wrapping arrays
> > makes it much  slower (which has a necessarily very convoluted way to lookup 
>the
> > block  capacity).  Or am I missing something?
> >
> >  -Steve
> >
> >
> >
> > ----- Original Message ----
> >>  From: Andrei Alexandrescu<andrei at erdani.com>
> >> To:  Discuss the phobos library for D<phobos at puremagic.com>
> >>  Sent: Thu, November 18, 2010 4:28:43 PM
> >> Subject: Re: [phobos] Clear  appending cache?
> >>
> >> Related question: can we make Appender  a thin wrapper over arrays? It
> >> looks  like improving "~="  caching is the right way to place  effort.
> >>
> >>  Andrei
> >>
> >> On 11/18/10 1:15 PM, David Simcha  wrote:
> >>>   Can someone who knows better than me how it works  (probably Steve)
> >>>   please put a function in druntime to  clear the current thread's array
> >>>   appending cache?  I  need this for two reasons:
> >>>
> >>> 1.  To   make sure arrays I'm done with get GC'd.
> >>>
> >>>  2.  To make it  safe(r) to free arrays  manually.
> >>>
> >>>
> >>>
> >>>    _______________________________________________
> >>> phobos  mailing  list
> >>> phobos at puremagic.com
> >>> http://lists.puremagic.com/mailman/listinfo/phobos
> >>  _______________________________________________
> >> phobos  mailing  list
> >> phobos at puremagic.com
> >> http://lists.puremagic.com/mailman/listinfo/phobos
> >>
> >
> >
> >
> >  _______________________________________________
> > phobos mailing  list
> > phobos at puremagic.com
> > http://lists.puremagic.com/mailman/listinfo/phobos
> _______________________________________________
> phobos  mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>