Skip to content

talloc: nuke in favor of own/NIH reimplementation

Niklas Haas requested to merge talloc into master

Loosely inspired by https://github.com/apankrat/halloc, this removes one of the last major LGPLv2 dependencies (talloc) from the source code.

Very unfortunately, rather than being a simple drop-in-replacement, I also decided to simplify/change the API a bit while reimplementing it - in particular, I created PL_ARRAY() to turn all arrays into structs, for the new PL_ARRAY_* replacements for TARRAY_*.

In retrospect, this made the commit explode to be much, much huger than it should have been. But oh well, it's too late for that. The new API seems easier to work with, at least, going forwards.

I also dropped a lot of talloc features that I don't really need. In particular, there's no more memory debugging, no more leak detection, no more destructors, and I nuked the weirdly indirect pl_ref_attach() in favor of just kludging around the single use case that existed for it.

One thing worth pointing out is that the new allocator I wrote uses an approach that might be considered unorthodox by some. Rather than using a doubly linked list of siblings (as is the standard in hierarchical allocators), I use a dynamically allocated array storing the children.

This doesn't really have a strong justification other than "I'm lazy and the code was easier to write/test this way". I may backpedal on this decision in the future if I ever have benchmark results demonstrating its worthwhileness.

The major downside of this approach is that freeing/stealing a child becomes O(n) with the number of siblings. But in practice, I think this is a moot point - not only is this a rare operation to begin with, but the number of siblings is quite low in practice. In fact, this may even be faster, because it avoids pointer chasing in favor of a single memmove.

(Note: allocation is still amortized O(1), since we grow the sibling list exponentially)

cf. #124 (closed)

Merge request reports