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 > ------------------------------------------------------------------------------ Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_d2d_mar _______________________________________________ Genode-main mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/genode-main
