Skip to content
Snippets Groups Projects

talloc: nuke in favor of own/NIH reimplementation

Merged Niklas Haas requested to merge talloc into master
  1. Jan 19, 2021
    • Niklas Haas's avatar
      talloc: nuke in favor of own/NIH reimplementation · e2e08de3
      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
      e2e08de3
Loading