Hello Sergey,
Well, there are mainly two problems I know about tree:
- it allows to change the key of the element which was already
inserted and in that case no any re-balancing will be performed; if one add here the fact that each node in the tree has a link to its parent, there appears a theoretical possibility to get a cycle in the tree when searching for something
that is because there is no key stored in the nodes but the user of the 'Avl_tree' template supplies the 'higher' function as part of its policy. This function may evaluate any portion of the node data. If non-constant members of node are incorporated in the evaluation, the tree is prone to become inconsistent.
Do you think that this is a weakness of the class template? To me, it seems that the documentation should do a better job about educating users of the template about the meaning and restrictions of the 'higher' function. Of course, a way to prevent such misuse by design would be preferable, but I don't see any. Do you have an idea of how to achieve that?
The kind of "issue" looks somehow similar to how the 'List' class template is not thread safe. So it can be misused when accessed by multiple threads. Would that also qualify as a limitation? I don't think so.
- current implementation of AVL-tree is quite simple and it takes a
lot of time to rebalance it; there are types of balanced trees (e.g. red-black tree) which has more cheap cost of operation "balance", but these types are more complex in terms of internal structures
I am open to replace the current implementation by a faster one, given that there is evidence of the benefit, and that the new implementation is not unreasonably more complex. With evidence, I am referring to an application benchmark that clearly shows the benefit of using the new implementation in the base framework.
Yes, this is a trade off which is not in spirit of Genode. At least env()->heap() is guarded by the ram_quota of the started app. I will think on the possibility to insert allocator in this scheme - that looks interesting. =)
The hook of providing a custom anonymous new operator also allows you to explore the transparent use of alternative allocator implementations. For example, if 'env()->heap()' is too slow for you, the hook enables you to use a better allocator implementation that uses 'env()->heap()' merely to allocate chunks of backing store. So 'env()->heap()' is called rarely and no longer sits on the critical path.
For an example of such an allocator, you may take a look at our 'malloc' implementation at 'libports/src/lib/libc/malloc.cc'. This slab-based allocator is much more efficient and has less meta-data overhead than the AVL-tree-based best-fit allocator used by 'env()->heap()'. We introduced this allocator because it turned out to speed up the lwIP stack (which calls malloc/free multiple times per packet) by circa 20%.
Best regards Norman