Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #118038 > unrolled thread

Interesting proposal...

Back to article view | Back to comp.lang.c++

Contents

  Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-06 17:05 -0800
    Re: Interesting proposal... Lynn McGuire <lynnmcguire5@gmail.com> - 2023-12-07 00:04 -0600
      Re: Interesting proposal... Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-07 07:57 +0100
        Re: Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-08 12:17 -0800
          Re: Interesting proposal... Bonita Montero <Bonita.Montero@gmail.com> - 2023-12-09 19:11 +0100
            Re: Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-09 12:54 -0800
      Re: Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-14 21:59 -0800
    Re: Interesting proposal... jseigh <jseigh_es00@xemaps.com> - 2023-12-07 17:52 -0500
      Re: Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-07 17:28 -0800
        Re: Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-08 20:48 -0800
          Re: Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-08 20:51 -0800
      Re: Interesting proposal... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-12-09 22:54 -0800

#118038 — Interesting proposal...

Context:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf

SMR in std C++? Humm...

[toc] | [next] | [standalone]

#118039

On 12/6/2023 7:05 PM, Chris M. Thomasson wrote:
> Context:
> 
> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf
> 
> SMR in std C++? Humm...

"A hazard pointer is a single-writer multi-reader pointer that can be 
owned by at most one thread at any time. Only the owner of the hazard 
pointer can set its value, while any number of threads may read its 
value. A thread that is about to access dynamic objects optimistically 
acquires ownership of a set of hazard pointer (typically one or two for 
linked data structures) to protect such objects from being reclaimed. 
The owner thread sets the value of a hazard pointer to point to an 
object in order to indicate to concurrent threads — that may remove such 
object — that the object is not yet safe to reclaim."

Looks cool.  Are these currently supported in cpu hardware or would cpus 
have to be extended ?

Lynn

[toc] | [prev] | [next] | [standalone]

#118040

Am 07.12.2023 um 07:04 schrieb Lynn McGuire:
> On 12/6/2023 7:05 PM, Chris M. Thomasson wrote:
>> Context:
>>
>> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf
>>
>> SMR in std C++? Humm...
> 
> "A hazard pointer is a single-writer multi-reader pointer that can be 
> owned by at most one thread at any time. Only the owner of the hazard 
> pointer can set its value, while any number of threads may read its 
> value. A thread that is about to access dynamic objects optimistically 
> acquires ownership of a set of hazard pointer (typically one or two for 
> linked data structures) to protect such objects from being reclaimed. 
> The owner thread sets the value of a hazard pointer to point to an 
> object in order to indicate to concurrent threads — that may remove such 
> object — that the object is not yet safe to reclaim."
> 
> Looks cool. ...

The problem with that is: "The number of removed objects that are not
yet reclaimed is bounded"; userland RCU ain't that flexible like kernel
-RCU since you can't interact with the scheduler-code in userland so
that you have a fixed number of hazard pointers. And hazard pointers
how their superiority mostly in synthetic benchmarks; usually there's
almost no gain over an atomic<shared_ptr<X>.

[toc] | [prev] | [next] | [standalone]

#118047

On 12/6/2023 10:57 PM, Bonita Montero wrote:
> Am 07.12.2023 um 07:04 schrieb Lynn McGuire:
>> On 12/6/2023 7:05 PM, Chris M. Thomasson wrote:
>>> Context:
>>>
>>> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf
>>>
>>> SMR in std C++? Humm...
>>
>> "A hazard pointer is a single-writer multi-reader pointer that can be 
>> owned by at most one thread at any time. Only the owner of the hazard 
>> pointer can set its value, while any number of threads may read its 
>> value. A thread that is about to access dynamic objects optimistically 
>> acquires ownership of a set of hazard pointer (typically one or two 
>> for linked data structures) to protect such objects from being 
>> reclaimed. The owner thread sets the value of a hazard pointer to 
>> point to an object in order to indicate to concurrent threads — that 
>> may remove such object — that the object is not yet safe to reclaim."
>>
>> Looks cool. ...
> 
> The problem with that is: "The number of removed objects that are not
> yet reclaimed is bounded"; userland RCU ain't that flexible like kernel
> -RCU since you can't interact with the scheduler-code in userland so
> that you have a fixed number of hazard pointers. And hazard pointers
> how their superiority mostly in synthetic benchmarks; 

> usually there's
> almost no gain over an atomic<shared_ptr<X>.
^^^^^^^^^^^^^^^^^^

Humm.. Oh really? Fwiw, RCU and SMR (aka, Hazard pointers) are different 
things. Userland RCU is not hazard pointers, and vise versa.

[toc] | [prev] | [next] | [standalone]

#118055

Am 08.12.2023 um 21:17 schrieb Chris M. Thomasson:

> Humm.. Oh really? Fwiw, RCU and SMR (aka, Hazard pointers) are different 
> things. Userland RCU is not hazard pointers, and vise versa.

Ok, but there's usually still no significant gain over
a atomic<<>shared_ptr>> outside synthetic benchmarks.

[toc] | [prev] | [next] | [standalone]

#118056

On 12/9/2023 10:11 AM, Bonita Montero wrote:
> Am 08.12.2023 um 21:17 schrieb Chris M. Thomasson:
> 
>> Humm.. Oh really? Fwiw, RCU and SMR (aka, Hazard pointers) are 
>> different things. Userland RCU is not hazard pointers, and vise versa.
> 
> Ok, but there's usually still no significant gain over
> a atomic<<>shared_ptr>> outside synthetic benchmarks.
> 

If you say so. :^)

[toc] | [prev] | [next] | [standalone]

#118067

On 12/6/2023 10:04 PM, Lynn McGuire wrote:
> On 12/6/2023 7:05 PM, Chris M. Thomasson wrote:
>> Context:
>>
>> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf
>>
>> SMR in std C++? Humm...
> 
> "A hazard pointer is a single-writer multi-reader pointer that can be 
> owned by at most one thread at any time. Only the owner of the hazard 
> pointer can set its value, while any number of threads may read its 
> value. A thread that is about to access dynamic objects optimistically 
> acquires ownership of a set of hazard pointer (typically one or two for 
> linked data structures) to protect such objects from being reclaimed. 
> The owner thread sets the value of a hazard pointer to point to an 
> object in order to indicate to concurrent threads — that may remove such 
> object — that the object is not yet safe to reclaim."
> 
> Looks cool.  Are these currently supported in cpu hardware or would cpus 
> have to be extended ?

No CPU extensions necessary. SMR is supported in current arch's. 
However, it can be made much better, aka avoiding that damn #StoreLoad 
style membar. One way is Joe's SMR+RCU hybrid proxy method...

[toc] | [prev] | [next] | [standalone]

#118042

On 12/6/23 20:05, Chris M. Thomasson wrote:
> Context:
> 
> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf
> 
> SMR in std C++? Humm...

It will be based on the one in Meta's folly library.  Based on a quick 
scan of the code I think it will use a global membar if that is 
available.  Looks like it will do some tracing collection for acyclic 
data structures.

I (finally) got around to writing the proxy version of it here 
https://github.com/jseigh

smrproxy - hazard pointer based proxy collector
arcproxy - atomic reference counted proxy collector
proxytest - timing tests
atomic-ptr-plus - obsolete, not updated and missing some files during 
the sourceforge to google to github moves.

Some timing comparisons in my blog here 
https://threadnought.wordpress.com/2023/06/09/smrproxy-timing-comparisons/

arcproxy looks good compared to rwlock but compared to smrproxy it looks 
really bad.  The rcu timings are simulated.

I've been considering creating an interface for all the different 
schemes.  Not sure if it would be a c++ abstact class or a rust trait, 
neither are my main languages. But then I would need a shared data 
structure that would utilize it.  I did figure out how to do a lock-free 
hashmap (w/ per bucket linked lists) that can do lock-free resizing but 
I found Cliff Click has one that's probably faster (because no linked 
lists).  But all that's on back burner for now.

Joe Seigh

[toc] | [prev] | [next] | [standalone]

#118043

On 12/7/2023 2:52 PM, jseigh wrote:
> On 12/6/23 20:05, Chris M. Thomasson wrote:
>> Context:
>>
>> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf
>>
>> SMR in std C++? Humm...
> 
> It will be based on the one in Meta's folly library.  Based on a quick 
> scan of the code I think it will use a global membar if that is 
> available.  Looks like it will do some tracing collection for acyclic 
> data structures.

I think so, ala sys_membarrier()...? Afaict, perhaps akin to a call to 
FlushProcessWriteBuffers:

https://learn.microsoft.com/en-us/windows/win32/api/processthreadsapi/nf-processthreadsapi-flushprocesswritebuffers

Active vs passive quiescent state detection schemes. Active being 
"issuing" an explicit request for quiescence. Passive akin to detecting 
quiescent states...

Also, btw, Joe, it has been a while since we have conversed on Usenet! 
We have had some hyper interesting conversations in the past, indeed. :^)

So nice to hear from you. :^)


> I (finally) got around to writing the proxy version of it here 
> https://github.com/jseigh

I need to check it out, big time! Unfortunately, I am a bit busy right 
now. However, you just made me think of that most interesting SMR+RCU 
hybrid of yours. :^)

I know I am going to have a good time when I read your code, Joe. :^)


> smrproxy - hazard pointer based proxy collector
> arcproxy - atomic reference counted proxy collector
> proxytest - timing tests
> atomic-ptr-plus - obsolete, not updated and missing some files during 
> the sourceforge to google to github moves.
> 
> Some timing comparisons in my blog here 
> https://threadnought.wordpress.com/2023/06/09/smrproxy-timing-comparisons/

Excellent. Fwiw, remember my single word proxy collector over here?

https://groups.google.com/g/lock-free/c/X3fuuXknQF0

It looks like some of your comments got deleted from that post? Ahhh, it 
was a while back. Here is a link to raw text:

pastebin.com/raw/f71480694
(fwiw, my proxy code using Relacy Race Detector)


> arcproxy looks good compared to rwlock but compared to smrproxy it looks 
> really bad.  The rcu timings are simulated.

Yup! IIRC, it's damn hard to compete with your SMR-RCU hybrid, or RCU 
for that matter... I remember first learning about your DWCAS based 
atomic pointer way back on comp.programming.threads. It is nice to hear 
from you again. :^)

Fwiw, check out this rwlock of mine:

https://vorbrodt.blog/2019/02/14/read-write-mutex

Also, I remember you did a really __neat__ rw-spinlock way back on 
comp.programming.threads. IIRC, The algorithm was rather elegant, 
indeed. Could handle overflow into fields...


> I've been considering creating an interface for all the different 
> schemes.  Not sure if it would be a c++ abstact class or a rust trait, 
> neither are my main languages. But then I would need a shared data 
> structure that would utilize it.  I did figure out how to do a lock-free 
> hashmap (w/ per bucket linked lists) that can do lock-free resizing but 
> I found Cliff Click has one that's probably faster (because no linked 
> lists).  But all that's on back burner for now.

Indeed. I will find some more time, maybe late tonight buddy. Fwiw, a 
while back, I had an API that was fairly “generic” in a sense... I used 
it for testing purposes so I could switch up implementations rather 
easily. It was an attempt at a std proxy collector interface for my 
testing purposes. Wow, how times flies! I will get back to you here. 
Need to get some work done wrt plotting some of my fractals...

https://paulbourke.net/fractals/multijulia
(Paul was kind enough to write about some of my work.)

[...]

[toc] | [prev] | [next] | [standalone]

#118050

On 12/7/2023 5:28 PM, Chris M. Thomasson wrote:
> On 12/7/2023 2:52 PM, jseigh wrote:
>> On 12/6/23 20:05, Chris M. Thomasson wrote:
>>> Context:
>>>
>>> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf
>>>
>>> SMR in std C++? Humm...
>>
>> It will be based on the one in Meta's folly library.  Based on a quick 
>> scan of the code I think it will use a global membar if that is 
>> available.  Looks like it will do some tracing collection for acyclic 
>> data structures.
> 
> I think so, ala sys_membarrier()...? Afaict, perhaps akin to a call to 
> FlushProcessWriteBuffers:
> 
> https://learn.microsoft.com/en-us/windows/win32/api/processthreadsapi/nf-processthreadsapi-flushprocesswritebuffers
> 
> Active vs passive quiescent state detection schemes. Active being 
> "issuing" an explicit request for quiescence. Passive akin to detecting 
> quiescent states...
> 
> Also, btw, Joe, it has been a while since we have conversed on Usenet! 
> We have had some hyper interesting conversations in the past, indeed. :^)
> 
> So nice to hear from you. :^)
> 
> 
>> I (finally) got around to writing the proxy version of it here 
>> https://github.com/jseigh
> 
> I need to check it out, big time! Unfortunately, I am a bit busy right 
> now. However, you just made me think of that most interesting SMR+RCU 
> hybrid of yours. :^)
> 
> I know I am going to have a good time when I read your code, Joe. :^)
> 
> 
>> smrproxy - hazard pointer based proxy collector
>> arcproxy - atomic reference counted proxy collector
>> proxytest - timing tests
>> atomic-ptr-plus - obsolete, not updated and missing some files during 
>> the sourceforge to google to github moves.
>>
>> Some timing comparisons in my blog here 
>> https://threadnought.wordpress.com/2023/06/09/smrproxy-timing-comparisons/
> [...]

Ahhh, I just found some time to look at your work. Fun times ahead!

[toc] | [prev] | [next] | [standalone]

#118051

On 12/8/2023 8:48 PM, Chris M. Thomasson wrote:
> On 12/7/2023 5:28 PM, Chris M. Thomasson wrote:
>> On 12/7/2023 2:52 PM, jseigh wrote:
[...]
>>> smrproxy - hazard pointer based proxy collector
>>> arcproxy - atomic reference counted proxy collector
>>> proxytest - timing tests
>>> atomic-ptr-plus - obsolete, not updated and missing some files during 
>>> the sourceforge to google to github moves.
>>>
>>> Some timing comparisons in my blog here 
>>> https://threadnought.wordpress.com/2023/06/09/smrproxy-timing-comparisons/
>> [...]
> 
> Ahhh, I just found some time to look at your work. Fun times ahead!

Ahhh, I am being reminded of differential reference counting. :^)

[toc] | [prev] | [next] | [standalone]

#118057

On 12/7/2023 2:52 PM, jseigh wrote:
> On 12/6/23 20:05, Chris M. Thomasson wrote:
>> Context:
[...]

Just a shot in the dark, do you happen to remember a locking scheme wrt 
IBM called PLO? I cannot remember it exactly right now. It seems to deal 
with locking issues... I think it was in the same appendix as the free 
pool manipulation wrt IBM principles of operation?

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web