intrusive binary tree

Question

intrusive binary tree

hawkw opened this issue 7 years ago · 2 comments

The current buddy allocator in SOS uses linked lists for free lists. Using a binary tree would likely offer much better performance. We should eventually write one.

Answer 1 · 2018-01-30T18:51:42.000Z

Could be trickier than writing lists. Also, low-priority, as the lists should basically work fine.

Answer 2 · 2018-01-31T21:07:20.000Z

i think if we really want to aggressively optimize data structures (and who doesn't? :D) an intrusive AVL tree is probably a good fit for alloc