On 01/21/2013 09:05 AM, Mathieu Desnoyers wrote: > * 泰来 ([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, >
Hi Mathieu Thanks for your detailed explanation and I have taken note of it. Judy Arrays looks more powerful, looks forward to seeing it in a production level. Thanks, Yuan _______________________________________________ lttng-dev mailing list [email protected] http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
