[lttng-dev] URCU binary search tree

[Mathieu Desnoyers]

----- On Dec 15, 2017, at 3:30 AM, Navin Agrawal <anavin at gmail.com> wrote: 

> One quick question Mathieu on the below note of yours.


> ​
> Note that I do _not_ consider my propotype branch to be production-ready.

> Can we assume that the code is functionally working in all known scenarios? I am
> trying to warm up work folks about URCU. Hence I am planning a demo using your
> RB tree code.

The code passed all tests when I stopped developing this branch. However, I did not 
feel confident that I understood all corner-cases thoroughly enough to merge the code 
into liburcu master branch. 

So if things don't work as expected, it may take a lot of effort to understand why. 

That's why this development branch is provided "as is", 

Mathieu 

> Thanks
> Navin

> On Fri, Dec 15, 2017 at 9:48 AM, Navin Agrawal < [ mailto:anavin at gmail.com |
> anavin at gmail.com ] > wrote:

>> Thanks Mathieu. Will check out your implementation.

>> Regards
>> Navin

>> On Fri, Dec 15, 2017 at 1:35 AM, Mathieu Desnoyers < [
>> mailto:mathieu.desnoyers at efficios.com | mathieu.desnoyers at efficios.com ] >
>> wrote:

>>> Hi,

>>> I did a URCU rbtree prototype branch around 2011, but it's not pretty, and it's
>>> complex.

>>> I went in a different direction afterward, and did a RCU Judy Array prototype
>>> instead.

>>> ​​
>>> The basic problem with rbtree is that there will always be some form of
>>> higher contention on the nodes near the top.

>>> Anyway, the branch is there:

>>> [ http://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/rbtree2 |
>>> http://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/rbtree2 ]

>>> See this Linux Plumbers Conference presentation introducing it:

>>> [ http://www.efficios.com/pub/lpc2011/Presentation-lpc2011-desnoyers-urcu.pdf |
>>> http://www.efficios.com/pub/lpc2011/Presentation-lpc2011-desnoyers-urcu.pdf ]

>>> ​​
>>> Note that I do _not_ consider my propotype branch to be production-ready.

>>> Enjoy!

>>> Mathieu

>>> ----- On Dec 14, 2017, at 2:38 PM, Navin Agrawal < [ mailto:anavin at gmail.com |
>>> anavin at gmail.com ] > wrote:

>>>> Hi,

>>>> I have searched enough for any existing implementation of URCU based BST. But to
>>>> no avail.

>>>> I was keen to attempt develop it myself. But I wanted to cross if there is any
>>>> particular reason it is not developed by anyone.

>>>> Do let me know.

>>>> Thanks
>>>> Navin

>>>> _______________________________________________
>>>> lttng-dev mailing list
>>>> [ mailto:lttng-dev at lists.lttng.org | lttng-dev at lists.lttng.org ]
>>>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
>>>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]

>>> --
>>> Mathieu Desnoyers
>>> EfficiOS Inc.
>>> [ http://www.efficios.com/ | http://www.efficios.com ]

-- 
Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.lttng.org/pipermail/lttng-dev/attachments/20171215/64d8ced1/attachment.html>