[HEAP.INC TIER 2 EVO] Use rbtrees for variable freelists.
Introduce heap.inc:RbTree
(private for now) translated from Linux’s rbtree.h
, rbtree_augmented.h
, rbtree.c
.
At the cost of a ton of 200 IQ code (actually half a ton as I came up with a 201 IQ trick to fold mirrored cases at seemingly no performance cost), using RbTree
for variable freelists instead of the linear search improves both the performance and the behavior in sufficiently fragmented scenarios, as RbTree
always finds the absolutely best fit and does so in logarithmic time. In Boost
terms, this changes simple_seq_fit
to rbtree_best_fit
.
This example speeds up arbitrarily, on my computer: trunk 20984 ms, 20 ms
→ MR 9 ms, 23 ms
(mormot.core.fpcx64mm
: 15 ms, 23 ms
, @synopse surrender while you can). I’d like to say that this problem wouldn't have arisen, but 200M variable allocations should still take around half a minute. May improve over time; there is at least one optimization related to avoiding reinsertions which I’m too lazy to implement.