There is updated graphs on https://github.com/arneg/GJAlloc/wiki/Performance-comparison. Turns out, in fact, I misattributed benefits to the std::allocator it does not have.
Nice, thank you. Afaik there are no near-term 7.9 release plans, so I'm for letting this allocator go in, provided there's a configure option to switch to the old one.
I'd rather have it directly in the source than as a bundle, but I guess it's up to you really. (I tried to symlink the bundle dir to your upstream git, but I couldn't get that to work very well - clearly the bundle system isn't made with that in mind. But that's fixable, of course.)
And my bad again. Currently the code does not do this, for comparability between the two block allocators as used by CritBits, I think.
Do you have any plans for switching to object-local storage? I'm not sure a single shared pool would do that well if there are many objects - I suspect it'd be bad for locality, and if we ever go properly multi-cpu it'd produce a lot of false sharing in cpu caches.
When I implemented the new multisets based on red-black trees, the node memory management was actually the most time consuming part. My implementation separates the nodes for each multiset, and moves them to be able to resize the memory blocks, and to compact them to limit internal fragmentation. It always allocates a single block for the whole multiset, regardless how large. It'd probably be better to use multiple blocks when it fills more than one page, but it could still be important to support moving nodes to be able to compact smaller trees.
Note that handling moving nodes has big effect on the iterators. They need to address nodes by index rather than by direct pointer, if they should be able to handle simultaneous change in the tree. For multisets there's a "semi-frozen" state when there are active iterators: Since iterators address by index, the memory block as a whole may move (and thus be enlarged), but the nodes inside it may not, so compaction is postponed until all iterators are gone. (There's a comment near the top of multiset.h that goes into detail on this.)
So my point is just that handling object-local storage of the nodes could have a quite big effect on the code.
/.../ any chance, your src/post_modules/CritBit/dependencies has size > 0?
Hmm, I'm pretty sure I tried "make depend" a few times before giving up yesterday, but now it works. Sorry for the noise.
And of course, a couple of CritBit benchmarks would be welcome - they also ought to show off GJAlloc, right? ;)
That can be arranged.
Cool. I've added a test that shows the difference better: It allocates and frees random objects while keeping 1000000 objects allocated. That shows a clear difference:
total user mem (runs) Old BLOCK_ALLOC 2.036s 1.689s 89112kb (3) (0/s) GJAlloc 1.110s 0.805s 89084kb (5) (0/s)
Interesting for Roxen as well, since Roxen servers tend to have quite a lot of objects allocated. Sweet. :)