> In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself.

Or you could just write the open-addressing HashMap, which is easier than implementing your own custom small allocation malloc()/free()?

That's the thing. To make chaining competitive against open-addressing HashMaps, you've got to bend-over backwards and its suddenly not easy anymore. You're right in that different versions of malloc/free could be more efficient. Ex: tcmalloc() has small allocations built in already like you mention.

But even if you erase those 8-bytes from the glibc chunk implementation of malloc, you're _still_ 8-bytes over the open-addressing implementation. So all that work and you're still worse off than the other methodology.

I can write aggregating allocation for a C with my eyes closed, in a tiny number of lines. These days I mostly wouldn't. If the target system thinks it's a good idea to add a header to every 32 byte allocation, that's their problem. No worthwhile malloc implementation does that, other than in a debugging configuration, where it adds "red zones".

The calculations in my other post show that it's not as simple as that next pointer being pure overhead compared to open addressing.

https://news.ycombinator.com/item?id=35416520