dynamic array capacity

spir denis.spir at gmail.com
Wed Dec 29 11:49:35 PST 2010


On Wed, 29 Dec 2010 13:48:48 -0500
"Steven Schveighoffer" <schveiguy at yahoo.com> wrote:

> On Wed, 29 Dec 2010 13:14:29 -0500, spir <denis.spir at gmail.com> wrote:
> 
> > I've done some timings using reserve and Appender. Seems not to work on  
> > my use case (decomposition of a string [actually a sequence of code  
> > points] according to NFD). (see sample code below)
> > * use reserve (to source string's length) with builtin append (operator  
> > '~=') --> 20% slower
> > * use Appender w/o reserve --> 3 times slower
> > * user Appender + its own reserve --> 1.5 times slower (i.e. divide  
> > above time per 2)
> 
> What is the baseline for this?  I.e. what is it 20% slower than? FWIW,  
> Appender should be much faster than builtin append, even without reserve.

The baseline is builtin append (~=) without reserving. (Sorry, thought it was clear.)

> However, Appender has a recently fixed bug (not fixed in 2.051) where  
> appending *arrays* of elements goes very slow.  I see you are doing that  
> in a couple spots.

As explained below, I'm doing _only_ that. So (as guessed), seems it may be the reason why Appender performs so badly in my case.

> > I'm surprised that reserve does not speed up builtin appending, since it  
> > can only avoid numerous reallocations. How to interpret that?

* This question remains. ??? *

> > I'm even more surprised of Appender's results on this use case, after  
> > having read about it's performance several times on the list. Strange.  
> > Can it be due to the fact that I only append sub-sequences? (the  
> > decomposition '*p' below is also a mini-array)
> 
> It should speed up appending.  If it doesn't, then it's either a bug or  
> pilot error.  As I said before, Appender in 2.051 and earlier has a bug  
> where appending an array is very slow.
> 
> But builtin appending should be faster if you reserve.

Yop!

> Simple tests I run prove that this is true.  Recent developments in how  
> the appending array grows mitigate this quite a bit, but it certainly will  
> result in less memory being consumed, and it always runs faster.

I can upload the modified version using reserve & Appender (with the timing module) if you like. (The original one is at https://bitbucket.org/denispir/denispir-d/src, files pile.d and chrono.d.)
Anyway, why reserve does not help builtin append is a mystery. In the worst case, it should not trouble.
By the way, how comes I do not need to import anything to be able to use reserve (like if it were a builtin prop)?

About Appender, I have had a look at the code in std.array and could not find any sign of why -- except that appending a slice loops over its elements --calling put() for each one--, but this should not be _that_ slow, I guess. (Or should it?) Maybe a specialisation of put to take an array (or slice) would help? (Instead of using an array interface, as is done now.)
The details of realloc are beyong my competence (e.g. the computation of resizing ratio), so I can hardly search further.

> -Steve

Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com



More information about the Digitalmars-d-learn mailing list