* 泰来 ([email protected]) wrote: > Hi List > > I am developer of Sheepdog project, which is a heavy user of urcu > library. I noticed there is a branch which implement rcu red-black tree > and it seems to halt on the late 2011. Is there roadmap to merge this > into master branch?
Hi Yuan, There are a couple of factors that are making me uncomfortable with pulling the RCU red-black tree (single-producer, multiple RCU consumers Red Black tree) into the Userspace RCU master branch at this point. It might be a good think to bring them up for discussion: 1) My own understanding of the code is not sufficient to vouch for it. The code, which has been sitting here since late 2011: git://git.lttng.org/userspace-rcu.git branch: rbtree2 Files: urcu/rcurbtree.h (API) urcu-rbtree.c (implementation) tests/test_urcu_rbtree.c (tests, example usage) I implemented this code to show that it is possible to implement a red-black tree that allows completely wait-free RCU readers, but along the way, the code grew to a certain level of complexity. For instance, I could not say that I would be comfortable to do changes to it without very thorough testing. I don't currently feel confident about my own ability to understand each corner-case of this code. If something breaks, the turn-around time to identify the fault might be unacceptably long. 2) Lack of review. If I look at my recent experience with the wait-free and lock-free queues and stack, as well as with the RCU lock-free hash table, a lot of review, discussion about semantics, added testing from many people, as well as feedback from API users are all necessary to get to a point where we can feel comfortable with the implementation, the level of documentation, as well as the API per se. I don't think the RCU red-black tree is at this level yet. 3) Not tested thoroughly enough for my own standards. Even though I created some stress-tests for the data structure that make me rather confident that it works well, we would need to farther in terms of test-cases: creating customized stress-tests that purposefully stress specific aspects of the data structure (e.g. corner-cases that happen rarely) would increase my own confidence in the quality of the implementation. 4) No user so far. This is always a chicken-and-egg problem: we need users to get feedback on the API, but as soon as we settle on an API and release a version with it, it becomes very painful to change it (in fact, we create new APIs and slowly deprecate an old one rather than break an API). So, ideally, I prefer to wait until some users actually show interest (like you are currently doing) before I merge APIs into the master branch. This lets us do some back-and-forth and allow the API to evolve before we finalize it. 5) I am currently working on other, similar data structures As you are probably aware, I am currently working on a RCU implementation of Judy Arrays, which target Multiple-Producers Multiple-Consumers use-cases. The design is well underway, but the implementation is far from complete (I do this part-time as a research track within my own company). At some point, I want to compare the RBtree and RCU judy array implementations in terms of performance, scalability, real-time behavior, and other aspects. I feel it is important that we compare those, and learn from this comparison, before pushing those data structures into production. Thoughts, comments, and feedback are welcome! Thanks, Mathieu > > Thanks, > Yuan -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com _______________________________________________ lttng-dev mailing list [email protected] http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
