On Sun, 22 Apr 2012, Arne Goedeke wrote:
On Sat, 21 Apr 2012, Martin Stjernholm, Roxen IS @ Pike developers forum wrote:
I think the ideal memory management would be to use a realloc double-the-size strategy for small trees, and switch to a block allocator when they reach the size of a memory page. That's more complex, of course.
True, it would be much more complex. It would effectlively mean having two different algorithms also of the data type using the blocks, I guess. There is also the additional danger of it leading to much higher memory fragmentation. Using realloc and copying has the advantage of always being able to shrink back.
One other (and quite experimental) solution would be to use realloc on reserved address space. There is interesting work by niall douglas and others on a new malloc api which could do that: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1527.pdf
I have not used it, and who knows if it will ever have the chance of becoming part of the standard... On the other hand, he has an implementation, so it would be possible to experiment with it.
Sorry for mass posting here. As a follow up: I just saw that the reserved space is merely a hint. Its intended as an optimization, not as a feature that guarantees the addresses to stay valid. Also, the sizes we are looking at are probably much smaller than memory page size, so it would also mean to always use minimum size of 4K.