Context:

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

SMR in std C++? Humm...

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

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>.

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

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.)

[...]

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.

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!

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. :^)

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.

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. :^)

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?

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...