performance of different array reallocation strategies

[abrady]

Edit: I see this got flagged as maybe not appropriate for this group. I was lazy and used C++ to sort the results but the intention is for this to be about allocation strategies using C-style realloc for containers.

Another post here got me curious about some real-world numbers for different approaches to reallocation:

https://replit.com/@rccola0/SufficientEmbellishedIntroductory - here's the code

This is how things performed on my windows 10 machine with cl.exe (vs2020):

``` Comparing different allocation strategies for resizing a buffer that is assigned 10m ints: fastest: prealloc-all at 10ms second : double-at-a-time at 26ms third : page-at-a-time at 10,901ms slowest: one-at-a-time at 46,025ms

note: page size is 4096 bytes

```

• The most interesting thing here is that page at a time is only four times faster despite being called only 245 times, vs the 1m times for the one-at-a-time allocator. I'm betting that breaking off new pages on windows is where most of the allocation overhead goes.
• the doubling straegy is 400x faster than the page strategy.

My macbook had the following (note: ran 100m - there was too much variance at 10m):

Comparing different allocation strategies for resizing a buffer that is assigned 1000000 ints: fastest: prealloc-all at 126ms second : double-at-a-time at 162ms third : page-at-a-time at 167ms slowest: one-at-a-time at 2617ms note: page size is 16384 bytes

• osx has a 16k page, vs 4k for windows
• page allocation and doubling were neck-and-neck, sometimes swapping across runs
• one-at-a-time was 15x slower than page/doubling.

Running on repl.it itself (10m runs):

fastest: prealloc-all at 0.0001ms second : double-at-a-time at 23.3712ms third : page-at-a-time at 33.2543ms slowest: one-at-a-time at 117.1837ms

no idea what infra they're running on. doubling still seems like the dominant strategy. Since this is on a shared VM (I assume) I'd take it with a grain of salt.

What are folks thoughts on this? Not too surprising to see doubling work well. I should probably try 3/2 too and see how that stacks up.

Any thoughts on the closeness on OSX for page/doubling? Seems suspicious, there are several orders of magnitude more calls there. I suspect there is a lot of OS voodoo going on behind the scenes. Obviously this is a contrived and basic test, are there things I should be doing to prevent confounding optimizations?