Spikes in array capacity

[Ali Çehreli]

BCS wrote:

 >> There is something strange in the array capacity algorithm.
 >> [...]
 >> Is that intended?

 > I'm going to take a guess that the gc is (after some point) allocating
 > into the smallest hole with "enough" capacity.

You may be right. :)

 > If you re run the test
 > but with something else going on to add some noise, do the spikes move?

Yes, the spikes move.

 > void makeNoise()
 > {
 >      static byte[][256] data;
 >      data[rand() % $] = new byte[rand() % 512];
 > }

I am not familiar with the dmd internals; but following the code took me 
to the function newCapacity() in src/druntime/src/rt/lifetime.d. The 
capacity growth is more complicated than what I've been assuming so far.

And yes, GC is in the picture. Quoting the comments from that file:

/*
  * Better version by Dave Fladebo:
  * This uses an inverse logorithmic algorithm to pre-allocate a bit more
  * space for larger arrays.
  * - Arrays smaller than PAGESIZE bytes are left as-is, so for the most
  * common cases, memory allocation is 1 to 1. The small overhead added
  * doesn't affect small array perf. (it's virtually the same as
  * current).
  * - Larger arrays have some space pre-allocated.
  * - As the arrays grow, the relative pre-allocated space shrinks.
  * - The logorithmic algorithm allocates relatively more space for
  * mid-size arrays, making it very fast for medium arrays (for
  * mid-to-large arrays, this turns out to be quite a bit faster than the
  * equivalent realloc() code in C, on Linux at least. Small arrays are
  * just as fast as GCC).
  * - Perhaps most importantly, overall memory usage and stress on the GC
  * is decreased significantly for demanding environments.
  */

So there may not be a bug after all...

Ali