Re: URCU binary search tree

Re: URCU binary search tree

[Mathieu Desnoyers]

[-- Attachment #1.1: Type: text/plain, Size: 1230 bytes --]

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 

See this Linux Plumbers Conference presentation introducing it: 

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 <anavin@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
> lttng-dev@lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

-- 
Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 

[-- Attachment #1.2: Type: text/html, Size: 3412 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: URCU binary search tree

[Navin Agrawal]

[-- Attachment #1.1: Type: text/plain, Size: 1440 bytes --]

Thanks Mathieu. Will check out your implementation.

Regards
Navin

On Fri, Dec 15, 2017 at 1:35 AM, Mathieu Desnoyers <
mathieu.desnoyers@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
>
> See this Linux Plumbers Conference presentation introducing it:
>
> 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 <anavin@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
> lttng-dev@lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
>

[-- Attachment #1.2: Type: text/html, Size: 4771 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: URCU binary search tree

[Navin Agrawal]

[-- Attachment #1.1: Type: text/plain, Size: 2023 bytes --]

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.

Thanks
Navin




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

> Thanks Mathieu. Will check out your implementation.
>
> Regards
> Navin
>
> On Fri, Dec 15, 2017 at 1:35 AM, Mathieu Desnoyers <
> mathieu.desnoyers@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
>>
>> See this Linux Plumbers Conference presentation introducing it:
>>
>> http://www.efficios.com/pub/lpc2011/Presentation-lpc2011-des
>> noyers-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 <anavin@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
>> lttng-dev@lists.lttng.org
>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>>
>>
>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> http://www.efficios.com
>>
>
>

[-- Attachment #1.2: Type: text/html, Size: 6817 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: URCU binary search tree

[Mathieu Desnoyers]

[-- Attachment #1.1: Type: text/plain, Size: 2962 bytes --]

----- On Dec 15, 2017, at 3:30 AM, Navin Agrawal <anavin@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@gmail.com |
> anavin@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@efficios.com | mathieu.desnoyers@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@gmail.com |
>>> anavin@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@lists.lttng.org | lttng-dev@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 

[-- Attachment #1.2: Type: text/html, Size: 9508 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: URCU binary search tree

[Navin Agrawal]

[-- Attachment #1.1: Type: text/plain, Size: 2848 bytes --]

Got it Mathieu.

Thanks a lot for your prompt response.

Regards
Navin

On Fri, Dec 15, 2017 at 10:57 PM, Mathieu Desnoyers <
mathieu.desnoyers@efficios.com> wrote:

> ----- On Dec 15, 2017, at 3:30 AM, Navin Agrawal <anavin@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 <anavin@gmail.com> wrote:
>
>> Thanks Mathieu. Will check out your implementation.
>>
>> Regards
>> Navin
>>
>> On Fri, Dec 15, 2017 at 1:35 AM, Mathieu Desnoyers <
>> mathieu.desnoyers@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
>>>
>>> See this Linux Plumbers Conference presentation introducing it:
>>>
>>> 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 <anavin@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
>>> lttng-dev@lists.lttng.org
>>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
>>>
>>>
>>> --
>>> Mathieu Desnoyers
>>> EfficiOS Inc.
>>> http://www.efficios.com
>>>
>>
>>
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
>

[-- Attachment #1.2: Type: text/html, Size: 9910 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

URCU binary search tree

[Navin Agrawal]

[-- Attachment #1.1: Type: text/plain, Size: 257 bytes --]

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

[-- Attachment #1.2: Type: text/html, Size: 1259 bytes --]

[-- Attachment #2: Type: text/plain, Size: 156 bytes --]

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev