Reserving capacity in associative arrays

[Jon D via Digitalmars-d-learn]

On Tuesday, 16 February 2016 at 16:37:07 UTC, Steven 
Schveighoffer wrote:
> On 2/14/16 10:22 PM, Jon D wrote:
>> Is there a way to reserve capacity in associative arrays?
>> [snip]
>> The underlying implementation of associative arrays
>> appears to take an initial number of buckets, and there's
>> a private resize() method, but it's not clear if there's a
>> public way to use these.
>
> There is not a public way to access these methods unfortunately.
>
> It would be a good addition to druntime I believe.
>
> Recently, I added a clear method to the AA, which does not 
> reduce capacity. So if you frequently build large AAs, and then 
> throw them away, you could instead reuse the memory.
>
My programs build AAs lasting the lifetime of the program.
>
> I would caution to be sure of this cause, however, before 
> thinking it would solve the problem. The AA not only uses an 
> array for buckets, but allocates a memory location for each 
> element as well. I'm often wrong when I assume what the problem 
> is when it comes to GC issues...
>
Completely agree. After posting I decided to take a more 
methodical look. Not finished yet, but I can share part of it. 
Key thing so far is noticeable step function related to GC costs 
related to AA size (likely not a surprise).

My programs work with large data sets. Size is open-ended, what 
I'm trying to do is get an idea of the data set sizes they will 
handle reasonably. For purposes of illustration, word-count is a 
reasonable proxy for what I'm doing. It was in this context that 
I saw significant performance drop-off after 'size_t[string]' AAs 
reached about 10 million entries.

I've started measuring with a simple program. Basically:

     StopWatch sw;
     sw.start;
     size_t[size_t] counts;
     foreach (i; 0..iterations)
         counts[uniform(0, uniqMax)]++;
     sw.stop;

Same thing with string as key ('size_t[string]') AAs. 
'iterations' and 'uniqMax' are varied between runs. GC stats are 
printed (via "--DRT-gcopt=profile:1"), plus timing and AA size. 
(Runs use LDC 17, release mode compiles, a fast 16GB MacBook).

For the integer as key case ('size_t[size_t]', there are notable 
jumps in GC total time and GC max pause time as AA size crosses 
specific size thresholds. This makes sense, as the AA needs to 
grow. Approximate steps:

     | entries | gc_total (ms) | gc_max_pause (ms) |
     |---------+---------------+-------------------|
     | 2M      |            30 |                60 |
     | 4M      |           200 |               100 |
     | 12M     |           650 |               330 |
     | 22M     |          1650 |               750 |
     | 44M     |          5300 |              3200 |

Iterations didn't matter, and gc total time and gc max time were 
largely flat between these jumps.

This suggests AA resize is the likely driver, and that 
preallocating a large size might address it.

To the point about being sure about cause - my programs use 
strings as keys, not integers. The performance drop-off with 
strings was quite a bit more significant than with integers. That 
analysis seems a bit trickier, I'm not done with that yet. 
Different memory allocation, perhaps effects from creating 
short-lived, temporary strings to test AA membership. Could 
easily be that string use or the combo of AAs with strings as key 
is a larger effect.

The other thing that jumps out from the table is the GC max pause 
time gets to be multiple seconds. Not an issue for my tools, 
which aren't interactive at those points, but would be 
significant issue for many interactive apps.

--Jon