Skip to contentSkip to conversation

Query on the rcu red-black tree status

DISCUSSION Mathieu Desnoyers 2 participants 2 messages Jan 21, 2013 2 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 6 lines · * 泰来 ([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

Quoted 3 lines

Thanks,
Yuan

Signature · 8 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

_______________________________________________
lttng-dev mailing list
[email protected]
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

A message that is not in the archive (sent off-list or not yet received): 20130121010550.GA2364@Krystal

#3 lore raw
Quoted 78 lines · Mathieu Desnoyers
Quoted 6 lines · * 泰来 ([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.

Quoted 4 lines

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