Standard placement operator

[Norman Feske]

Hello Sergey,

> Well, there are mainly two problems I know about tree:
> 1) 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.

> 2) 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

-- 
Dr.-Ing. Norman Feske
Genode Labs

http://www.genode-labs.com · http://genode.org

Genode Labs GmbH · Amtsgericht Dresden · HRB 28424 · Sitz Dresden
Geschäftsführer: Dr.-Ing. Norman Feske, Christian Helmuth