Standard placement operator

[Sergey Grekhov]

Hello, Norman!
I understand your position and it looks absolutely reasonable. Both 
issues are actually relate to trade-off between complexity and 
simplicity. I know that simplicity is one of your key points in design.
That's why I thought that if someone needs specific data structures it 
would be nice to give ability to use STL. Besides, porting some generic 
code is fun. =)

Thanks for the hint about malloc - I will take a look!

Kind regards,
Sergey.

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