No offense intended, but I have to say I was a little bit disappointed by halloc. I expected it to use a custom allocation scheme, like malloc()ing large chunks of memory in one go in order to reduce malloc() time and space overhead and to increase locality of reference. Instead it looks like it just malloc()s every object separately. I'm sure some people will find halloc useful, but in my C++ project where I already use smart pointers I didn't see any advantage in using halloc.
You appear to be mixing two things here. What you described is a form of a "slab allocator" whereby all blocks in a certain size range are allocated from one big piece of memory that is sliced into equally sized chunks. This is really fast, it works great for smaller blocks and it is the way to speed up the STL-heavy code. I did some profiling a while back and a lock-free slab allocator delivered 10x speed up in the code that operated with std::map and strings.
The second thing is locality. An allocator like halloc could theoretically utilize the fact that two blocks are explictly marked as related and allocate them close to each other. However, for this to work the allocation function needs to be passed a pointer to the parent block, which is not the case with halloc. So the API needs to change, the implementation needs to change too, and then it will no longer be a light implementation of a simple idea, but something else.
I suspect the idea behind the library is not performance optimization, but convenience. It's sometimes much more convenient to let someone track allocation dependencies than doing it yourself.
Do you have evidence that rolling your own suballocator under malloc is better than just using malloc. By "evidence" I mean you actually measured it, not arm-waving.
Yes. For example my app has a hash table which it fills upon every request. After this initial filling, not more hash table entries are set. At the end of the request the hash table is deleted, and a new one is created at the next request. I improved performance a bit by clearing the hash table instead of deleting and recreating it. What gave me an even bigger boost in performance was by using a custom allocator that allocates big chunks of memory in a single operation.
The thing is my app is already not doing a lot of work per request so almost any speedup is noticeable.
You saw benefit because you implemented a custom allocator whose behavior was optimized to the memory access pattern that you planned to use with it. Any decent implementation of malloc already allocates large chunks of contiguous memory from the operating system and tries to maintain locality among allocations. It's also possible that you saw performance improvement from the removal of a function call - it's possible that the call to your custom allocator could be inlined, whereas malloc has to be a function call.
My understanding of halloc and talloc is that they are general purpose allocators. A pure library approach - that is, without source code analysis and code generation - won't be able to tailor the allocation scheme based on the data structures themselves.
When two blocks are explictly tied into a parent-child relationship, it gives the allocator valuable locality information. It is another matter that halloc separates allocation and block binding steps, so the relationship information is not available at the allocation time, and so it cannot utilize these locality hints.
It doesn't look like talloc is any better.