talloc: nuke in favor of own/NIH reimplementation
- Jan 19, 2021
-
-
Niklas Haas authored
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
-