dynamic array capacity

[spir]

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

> On Wed, 29 Dec 2010 07:29:29 -0500, spir <denis.spir at gmail.com> wrote:
> 
> > Hello,
> >
> > Is there a common idiom to pre-allocate a dynamic array. I mean  
> > allocating to avoid numerous re-allocations in loop, not setting length  
> > & filling content.
> 
> int[] x;
> x.reserve(10000); // pre-allocate at least 10000 elements for appending
> 
> Another way to do it:
> 
> Appender!(int[]) app;
> app.reserve(10000);
> 
> this will perform much better than builtin array appending.
> 
> -Steve

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)

I'm surprised that reserve does not speed up builtin appending, since it can only avoid numerous reallocations. How to interpret that?
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)

Denis

// NFD decomposition
Code[] decomposition (Code[] codes) {
    /** Decompose code sequence according to form "NFD". */
//~     Code[] decompCodes;     // new, decomposed; pile
    Appender!(Code[]) decompCodes;
    Decomp* p;              // pointer to single-code decomposition
    Ordinal i0 = 0;         // reference index past last decomposed code
    
    // Decompose each code.
//~     decompCodes.reserve(codes.length);  // worse time! ???
//~     foreach (i,code ; codes) {
//~         // case composed code
//~         p = (code in DECOMPOSITIONS);
//~         // Do not even check whether code is composite
//~         // for simple ASCII & latin characters.
//~         if (code > 0xBF)
//~             if (p) {
//~                 // Append past simple codes, if any.
//~                 if (i > i0) decompCodes ~= codes[i0..i];
//~                 // Append current code's decomposition.
//~                 decompCodes ~= *p;
//~                 // Update reference index.
//~                 i0 = i + 1;
//~             }
//~     }
//~     // Append last simple codes (if any).
//~     decompCodes ~= codes[i0..$];

    decompCodes.reserve(codes.length);  // worse time! ???
    foreach (i,code ; codes) {
        // case composed code
        p = (code in DECOMPOSITIONS);
        // Do not even check whether code is composite
        // for simple ASCII & latin characters.
        if (code > 0xBF)
            if (p) {
                // Append past simple codes, if any.
                if (i > i0) decompCodes.put(codes[i0..i]);
                // Append current code's decomposition.
                decompCodes.put(*p);
                // Update reference index.
                i0 = i + 1;
            }
    }
    // Append last simple codes (if any).
    decompCodes.put(codes[i0..$]);
    
//~     return decompCodes;
    return decompCodes.data;
}
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com