On Mon, Apr 16, 2012 at 12:30 AM, Martin Stjernholm, Roxen IS @ Pike developers forum 10353@lyskom.lysator.liu.se wrote:
Just to make it clear, you're talking about the linear lookup to find the right block when structs are freed?
Yes.
No, std::allocator is a block allocator used by std::list, std::map and so on. Compared to glibc free/malloc, the std::allocator is quite fast.
It would be interesting to see a comparison with plain old (glibc) malloc, just to put it into perspective.
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.
Slight ones. For the CritBits, we need the allocator in the object storage (block allocators are used tree-locally).
So the nodes for each critbit tree are allocated within its own blocks? Sifting through the code just briefly I got the impression the nodes were allocated from a single global pool, considering that CB_NODE_ALLOC() doesn't take any context. Did I miss something?
And my bad again. Currently the code does not do this, for comparability between the two block allocators as used by CritBits, I think.
http://fortranland.com/compare_7.9_block_alloc.txt http://fortranland.com/compare_7.9_block_alloc_cleanup_on_exit.txt
Hmm, do you have any theories to explain the variations seen in those two?
Currently, no explanation that would make you go "Ah ok, in that case, sure." is available. Especially not any based on facts :).
Otherwise it seems to me like there's still a lot of noise, and I suspect none of those tests really stress BLOCK_ALLOC in the way where your implementation would show its strength, i.e. freeing structs when there's a large number allocated.
I figured I could add a test for that, but I can't compile CritBit from clean source on the arne/block_alloc branch:
#### Making dynamic: post_modules/CritBit make[5]: *** No rule to make target `/home/mast/Pike/devel/src/post_modules/CritBit/bitvector.h', needed by `inttree.o'. Stop. make[4]: *** [all] Error 2 make[3]: *** [CritBit] Error 1
That seems to be either an issue with dependencies, or you need to touch src/post_modules/CritBit/*.cmod, or both. In arne/block_alloc, bitvector.h was moved from src/post_modules/CritBit/ to src/ - any chance, your src/post_modules/CritBit/dependencies has size > 0?
And of course, a couple of CritBit benchmarks would be welcome - they also ought to show off GJAlloc, right? ;)
That can be arranged.