On 25.08.2016 16:33, Jacek Caban wrote:
On 25.08.2016 15:59, Sebastian Lackner wrote:
On 25.08.2016 15:30, Jacek Caban wrote:
Hi Sebastian,
[...]
I assume that there are currently no plans to exchange the RBTree with something else, nevertheless it shouldn't hurt to share some code. I've attached a proof-of-concept patch to replace the RBTree with a Scapegoat tree I wrote a while ago. In contrast to other trees a nice property is that it is not really required to keep the tree balanced all the time, instead we have rebuild operations which will automatically detect it if the performance gets too bad and build a binary search tree. When deleting lots of elements for example we could disable rebuild temporarily to avoid too much overhead.
Sure. Since you posted it, I had a quick look. That implementation requires allocators, which is what we should avoid to simplify usage of the tree. You could get rid of the array by storing another pointer in nodes that would be used to link them into ordered list instead of an array (that would require a bit more tricky wine_rb_build, but it should be doable without much perf cost). However, then you'd give up memory advantage.
Well, I do not think allocators in general are a problem.It is only a problem if important operations can fail because of out of memory errors. The Scapegoat tree uses it only for the rebuild operation which is not critical (performance will get worse, but everything will continue to work as expected).
Sure, failing operations is the most annoying part of allocators, so it's a step forward. Still, avoiding overhead of adding allocators in each tree user would be nice.
Also, I do not think its possible to replace the array with an ordered list - the rebuild operation requires computation of the median which would be way too expensive for regular lists.
I think that should be doable, but with a different algorithm in wine_rb_build. That's what I meant by tricky. Here is first that comes first into my mind:
let's say that nodes are in list1
while(list1 length > 1) { while(list1 length > 0) { take first 3 elements node1, node2, node3 from list1 (*) node2->left = node1 node2->right = node3 append node2 into list2 } list1 = list2 }
root = the only element in list1
(*) if list length 2, use NULL for node3, if length is 1, node1=node3=NULL, node2=the only node in list
Since on every outer loop iteration length of new list is 3 times shorter than previous length, the complexity is O(n), just like with the array.
Jacek
I see what you mean. In fact, since we know how many nodes are in the subtree which has to be rebuild (and thus the height of the balanced subtree), this could probably even be implemented recursively without using any allocators and O(log n) stack usage. Nevertheless, before spending more time on an alternative implementation it might be useful to decide in which direction we want to proceed. ;)
Regards, Sebastian