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

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

smrproxy v2

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

Contents

  smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-17 08:10 -0400
    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-17 13:10 -0700
      Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-17 17:08 -0400
        Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-17 16:40 -0700
          Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-17 17:16 -0700
            Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-17 17:24 -0700
          Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-18 08:07 -0400
            Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-25 15:00 -0700
              Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-25 18:56 -0400
                Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-27 12:33 -0700
                  Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-27 18:29 -0400
                    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-27 15:32 -0700
                      Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-27 20:35 -0400
                        Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-27 21:02 -0700
                          Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-28 07:45 -0400
                            Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-28 14:57 -0700
                              Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-28 15:09 -0700
                              Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-28 21:17 -0400
                                Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-28 21:35 -0700
                                  Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-29 07:23 -0400
                                    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-29 14:51 -0700
                                Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-28 21:38 -0700
                                  Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-29 07:27 -0400
                                    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-29 14:56 -0700
                                      Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-30 12:36 -0400
                                        Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-01 12:20 -0700
                                Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-28 21:41 -0700
                                  Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-29 15:05 -0700
                                    Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-30 12:39 -0400
                                      Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-03 21:14 -0800
                                        Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-04 07:46 -0500
                                          Re: smrproxy v2 Muttley@DastartdlyHQ.org - 2024-11-04 14:09 +0000
                                            Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-04 12:42 -0800
                                              Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-09 13:51 -0800
                                          Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-12-12 00:43 -0800
                                            Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-12-12 07:29 -0500
                                              Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-12-12 13:55 -0800
                                                Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-12-12 19:48 -0500
                                                  Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-12-25 20:36 -0800
                    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-27 21:08 -0700
                      Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-27 21:09 -0700
                      Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-27 21:13 -0700
    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-28 22:02 -0700
      Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-29 23:40 -0700
      Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-29 23:42 -0700
        Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-29 23:53 -0700
    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-10-29 23:54 -0700
      Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-10-30 12:43 -0400
    Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-02 13:50 -0700
    Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-21 15:17 -0500
      Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-23 11:10 -0500
        Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-23 13:31 -0800
          Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-23 17:12 -0500
            Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-23 17:46 -0800
        Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-24 15:14 -0500
          Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-24 15:19 -0800
            Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-24 19:09 -0500
              Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-24 16:37 -0800
                Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-24 16:48 -0800
              Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-24 16:47 -0800
                Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-25 06:31 -0500
                  Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-11-25 14:12 -0800
          Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-11-27 10:29 -0500
            Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-12-09 13:34 -0500
              Re: smrproxy v2 jseigh <jseigh_es00@xemaps.com> - 2024-12-11 07:13 -0500
                Re: smrproxy v2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-12-11 16:22 -0800

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#120782

On 10/29/2024 4:23 AM, jseigh wrote:
> On 10/29/24 00:35, Chris M. Thomasson wrote:
>> On 10/28/2024 6:17 PM, jseigh wrote:
>>> On 10/28/24 17:57, Chris M. Thomasson wrote:
>>>> On 10/28/2024 4:45 AM, jseigh wrote:
> 
>>>
>>> fwiw, here's the lock and unlock logic from smrproxy rewrite
>>>
>>>      inline void lock()
>>>      {
>>>          epoch_t _epoch = shadow_epoch.load(std::memory_order_relaxed);
>>>          _ref_epoch.store(_epoch, std::memory_order_relaxed);
>>
>>
>>>          std::atomic_signal_fence(std::memory_order_acquire);
>> ^^^^^^^^^^^^^^^^^^^^^^
>>
>>>      }
>>
>> Still don't know how your pure C++ write up can handle this without an 
>> std::atomic_thread_fence(std::memory_order_acquire).
> 
> No thread fence is necessary.  The loads can move before
> the store.  They just can't move before the async
> membar.  After that membar any previously retired
> objects are no longer reachable.

Ahhhh. I thought your C++ version is going to be one that did not use an 
asymmetric membar in order to make it so called "100%" pure... Not sure 
about C++ including one in the actual standard. If they did I think it 
would have some info about it, perhaps akin to:

https://en.cppreference.com/w/cpp/atomic/atomic/is_lock_free

Well, even then if an asymmetric was not available on the arch the code 
is being compiled for, it can say, well, shit happens! Then allow you to 
fall back to another version...?

Also, the C++ wording of this is interesting:

https://en.cppreference.com/w/cpp/atomic/atomic/is_always_lock_free

wrt:
_____________
​0​ for the built-in atomic types that are never lock-free,
1 for the built-in atomic types that are sometimes lock-free,
2 for the built-in atomic types that are always lock-free.
_____________

That's fun... ;^)



> 
>>
>>>
>>>      inline void unlock()
>>>      {
>>>          _ref_epoch.store(0, std::memory_order_release);
>>>      }
>>

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

#120771

On 10/28/2024 6:17 PM, jseigh wrote:
> On 10/28/24 17:57, Chris M. Thomasson wrote:
>> On 10/28/2024 4:45 AM, jseigh wrote:
>>> On 10/28/24 00:02, Chris M. Thomasson wrote:
>>>> On 10/27/2024 5:35 PM, jseigh wrote:
>>>>> On 10/27/24 18:32, Chris M. Thomasson wrote:
>>>
>>>>>
>>>>> The membar version?  That's a store/load membar so it is expensive.
>>>>
>>>> I was wondering in your c++ version if you had to use any seq_cst 
>>>> barriers. I think acquire/release should be good enough. Now, when I 
>>>> say C++, I mean pure C++, no calls to FlushProcessWriteBuffers and 
>>>> things like that.
>>>>
>>>> I take it that your pure C++ version has no atomic RMW, right? Just 
>>>> loads and stores?
>>>
>>> While a lock action has acquire memory order semantics, if the
>>> implementation has internal stores, you have to those stores
>>> are complete before any access from the critical section.
>>> So you may need a store/load memory barrier.
>>
>> Wrt acquiring a lock the only class of mutex logic that comes to mind 
>> that requires an explicit storeload style membar is Petersons, and 
>> some others along those lines, so to speak. This is for the store and 
>> load version. Now, RMW on x86 basically implies a StoreLoad wrt the 
>> LOCK prefix, XCHG aside for it has an implied LOCK prefix. For 
>> instance the original SMR algo requires a storeload as is on x86/x64. 
>> MFENCE or LOCK prefix.
>>
>> Fwiw, my experimental pure C++ proxy works fine with XADD, or atomic 
>> fetch-add. It needs an explicit membars (no #StoreLoad) on SPARC in 
>> RMO mode. On x86, the LOCK prefix handles that wrt the RMW's 
>> themselves. This is a lot different than using stores and loads. The 
>> original SMR and Peterson's algo needs that "store followed by a load 
>> to a different location" action to hold true, aka, storeload...
>>
>> Now, I don't think that a data-dependant load can act like a 
>> storeload. I thought that they act sort of like an acquire, aka 
>> #LoadStore | #LoadLoad wrt SPARC. SPARC in RMO mode honors data- 
>> dependencies. Now, the DEC Alpha is a different story... ;^)
>>
> 
> fwiw, here's the lock and unlock logic from smrproxy rewrite
> 
>      inline void lock()
>      {
>          epoch_t _epoch = shadow_epoch.load(std::memory_order_relaxed);
>          _ref_epoch.store(_epoch, std::memory_order_relaxed);
>          std::atomic_signal_fence(std::memory_order_acquire);
>      }
> 
>      inline void unlock()
>      {
>          _ref_epoch.store(0, std::memory_order_release);
>      }
> 
> epoch_t is interesting.  It's uint64_t but handles wrapped
> compares, ie. for an epoch_t x1 and uint64_t n

Only your single polling thread can mutate the shadow_epoch, right?


> 
>      x1 < (x1 + n)
> 
> for any value of x1 and any value of n from 0 to 2**63;
> eg.
>     0xfffffffffffffff0 < 0x0000000000000001
> 
> 
> The rewrite is almost complete except for some thread_local
> stuff.  I think I might break off there.  Most of the
> additional work is writing the test code.  I'm considering
> rewriting it in Rust.

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

#120777

On 10/29/24 00:38, Chris M. Thomasson wrote:
> On 10/28/2024 6:17 PM, jseigh wrote:
>> On 10/28/24 17:57, Chris M. Thomasson wrote:
>>> On 10/28/2024 4:45 AM, jseigh wrote:

>>
>> fwiw, here's the lock and unlock logic from smrproxy rewrite
>>
>>      inline void lock()
>>      {
>>          epoch_t _epoch = shadow_epoch.load(std::memory_order_relaxed);
>>          _ref_epoch.store(_epoch, std::memory_order_relaxed);
>>          std::atomic_signal_fence(std::memory_order_acquire);
>>      }
>>
>>      inline void unlock()
>>      {
>>          _ref_epoch.store(0, std::memory_order_release);
>>      }
>>
>> epoch_t is interesting.  It's uint64_t but handles wrapped
>> compares, ie. for an epoch_t x1 and uint64_t n
> 
> Only your single polling thread can mutate the shadow_epoch, right?
> 

Yes.  It's just an optimization. The reader threads could read
from the global epoch but it would be in a separate cache line
and be an extra dependent load.  So one dependent load and
same cache line.

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

#120783

On 10/29/2024 4:27 AM, jseigh wrote:
> On 10/29/24 00:38, Chris M. Thomasson wrote:
>> On 10/28/2024 6:17 PM, jseigh wrote:
>>> On 10/28/24 17:57, Chris M. Thomasson wrote:
>>>> On 10/28/2024 4:45 AM, jseigh wrote:
> 
>>>
>>> fwiw, here's the lock and unlock logic from smrproxy rewrite
>>>
>>>      inline void lock()
>>>      {
>>>          epoch_t _epoch = shadow_epoch.load(std::memory_order_relaxed);
>>>          _ref_epoch.store(_epoch, std::memory_order_relaxed);
>>>          std::atomic_signal_fence(std::memory_order_acquire);
>>>      }
>>>
>>>      inline void unlock()
>>>      {
>>>          _ref_epoch.store(0, std::memory_order_release);
>>>      }
>>>
>>> epoch_t is interesting.  It's uint64_t but handles wrapped
>>> compares, ie. for an epoch_t x1 and uint64_t n
>>
>> Only your single polling thread can mutate the shadow_epoch, right?
>>
> 
> Yes.  It's just an optimization. The reader threads could read
> from the global epoch but it would be in a separate cache line
> and be an extra dependent load.  So one dependent load and
> same cache line.

Are you taking advantage of the fancy alignment capabilities of C++?

https://en.cppreference.com/w/cpp/language/alignas

and friends? They seem to work fine wrt the last time I checked them.

It's nice to have a standard way to pad and align on cache line 
boundaries. :^)

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

#120794

On 10/29/24 17:56, Chris M. Thomasson wrote:
> On 10/29/2024 4:27 AM, jseigh wrote:

>>
>> Yes.  It's just an optimization. The reader threads could read
>> from the global epoch but it would be in a separate cache line
>> and be an extra dependent load.  So one dependent load and
>> same cache line.
> 
> Are you taking advantage of the fancy alignment capabilities of C++?
> 
> https://en.cppreference.com/w/cpp/language/alignas
> 
> and friends? They seem to work fine wrt the last time I checked them.
> 
> It's nice to have a standard way to pad and align on cache line 
> boundaries. :^)

It's target processor dependent.  You need to query the cache line size
and pass to compile as a define variable.

There's supposed to be built in define that would be target system
dependent but it's not implemented.

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

#120817

On 10/30/2024 9:36 AM, jseigh wrote:
> On 10/29/24 17:56, Chris M. Thomasson wrote:
>> On 10/29/2024 4:27 AM, jseigh wrote:
> 
>>>
>>> Yes.  It's just an optimization. The reader threads could read
>>> from the global epoch but it would be in a separate cache line
>>> and be an extra dependent load.  So one dependent load and
>>> same cache line.
>>
>> Are you taking advantage of the fancy alignment capabilities of C++?
>>
>> https://en.cppreference.com/w/cpp/language/alignas
>>
>> and friends? They seem to work fine wrt the last time I checked them.
>>
>> It's nice to have a standard way to pad and align on cache line 
>> boundaries. :^)
> 
> It's target processor dependent.  You need to query the cache line size
> and pass to compile as a define variable.
> 
> There's supposed to be built in define that would be target system
> dependent but it's not implemented.

What about:

https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size

?

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

#120772

On 10/28/2024 6:17 PM, jseigh wrote:
> On 10/28/24 17:57, Chris M. Thomasson wrote:
>> On 10/28/2024 4:45 AM, jseigh wrote:
>>> On 10/28/24 00:02, Chris M. Thomasson wrote:
>>>> On 10/27/2024 5:35 PM, jseigh wrote:
>>>>> On 10/27/24 18:32, Chris M. Thomasson wrote:
>>>
>>>>>
>>>>> The membar version?  That's a store/load membar so it is expensive.
>>>>
>>>> I was wondering in your c++ version if you had to use any seq_cst 
>>>> barriers. I think acquire/release should be good enough. Now, when I 
>>>> say C++, I mean pure C++, no calls to FlushProcessWriteBuffers and 
>>>> things like that.
>>>>
>>>> I take it that your pure C++ version has no atomic RMW, right? Just 
>>>> loads and stores?
>>>
>>> While a lock action has acquire memory order semantics, if the
>>> implementation has internal stores, you have to those stores
>>> are complete before any access from the critical section.
>>> So you may need a store/load memory barrier.
>>
>> Wrt acquiring a lock the only class of mutex logic that comes to mind 
>> that requires an explicit storeload style membar is Petersons, and 
>> some others along those lines, so to speak. This is for the store and 
>> load version. Now, RMW on x86 basically implies a StoreLoad wrt the 
>> LOCK prefix, XCHG aside for it has an implied LOCK prefix. For 
>> instance the original SMR algo requires a storeload as is on x86/x64. 
>> MFENCE or LOCK prefix.
>>
>> Fwiw, my experimental pure C++ proxy works fine with XADD, or atomic 
>> fetch-add. It needs an explicit membars (no #StoreLoad) on SPARC in 
>> RMO mode. On x86, the LOCK prefix handles that wrt the RMW's 
>> themselves. This is a lot different than using stores and loads. The 
>> original SMR and Peterson's algo needs that "store followed by a load 
>> to a different location" action to hold true, aka, storeload...
>>
>> Now, I don't think that a data-dependant load can act like a 
>> storeload. I thought that they act sort of like an acquire, aka 
>> #LoadStore | #LoadLoad wrt SPARC. SPARC in RMO mode honors data- 
>> dependencies. Now, the DEC Alpha is a different story... ;^)
>>
> 
> fwiw, here's the lock and unlock logic from smrproxy rewrite
> 
>      inline void lock()
>      {
>          epoch_t _epoch = shadow_epoch.load(std::memory_order_relaxed);
>          _ref_epoch.store(_epoch, std::memory_order_relaxed);
>          std::atomic_signal_fence(std::memory_order_acquire);
>      }
> 
>      inline void unlock()
>      {
>          _ref_epoch.store(0, std::memory_order_release);
>      }
> 
> epoch_t is interesting.  It's uint64_t but handles wrapped
> compares, ie. for an epoch_t x1 and uint64_t n

[...]

Humm... I am not sure if it would work with just the release. The 
polling thread would read from these per thread epochs, _ref_epoch, 
using an acquire barrier? Still. Not sure if that would work. Need to 
put my thinking cap on. ;^)

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

#120784

On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:
> On 10/28/2024 6:17 PM, jseigh wrote:
>> On 10/28/24 17:57, Chris M. Thomasson wrote:
>>> On 10/28/2024 4:45 AM, jseigh wrote:
>>>> On 10/28/24 00:02, Chris M. Thomasson wrote:
>>>>> On 10/27/2024 5:35 PM, jseigh wrote:
>>>>>> On 10/27/24 18:32, Chris M. Thomasson wrote:
>>>>
>>>>>>
>>>>>> The membar version?  That's a store/load membar so it is expensive.
>>>>>
>>>>> I was wondering in your c++ version if you had to use any seq_cst 
>>>>> barriers. I think acquire/release should be good enough. Now, when 
>>>>> I say C++, I mean pure C++, no calls to FlushProcessWriteBuffers 
>>>>> and things like that.
>>>>>
>>>>> I take it that your pure C++ version has no atomic RMW, right? Just 
>>>>> loads and stores?
>>>>
>>>> While a lock action has acquire memory order semantics, if the
>>>> implementation has internal stores, you have to those stores
>>>> are complete before any access from the critical section.
>>>> So you may need a store/load memory barrier.
>>>
>>> Wrt acquiring a lock the only class of mutex logic that comes to mind 
>>> that requires an explicit storeload style membar is Petersons, and 
>>> some others along those lines, so to speak. This is for the store and 
>>> load version. Now, RMW on x86 basically implies a StoreLoad wrt the 
>>> LOCK prefix, XCHG aside for it has an implied LOCK prefix. For 
>>> instance the original SMR algo requires a storeload as is on x86/x64. 
>>> MFENCE or LOCK prefix.
>>>
>>> Fwiw, my experimental pure C++ proxy works fine with XADD, or atomic 
>>> fetch-add. It needs an explicit membars (no #StoreLoad) on SPARC in 
>>> RMO mode. On x86, the LOCK prefix handles that wrt the RMW's 
>>> themselves. This is a lot different than using stores and loads. The 
>>> original SMR and Peterson's algo needs that "store followed by a load 
>>> to a different location" action to hold true, aka, storeload...
>>>
>>> Now, I don't think that a data-dependant load can act like a 
>>> storeload. I thought that they act sort of like an acquire, aka 
>>> #LoadStore | #LoadLoad wrt SPARC. SPARC in RMO mode honors data- 
>>> dependencies. Now, the DEC Alpha is a different story... ;^)
>>>
>>
>> fwiw, here's the lock and unlock logic from smrproxy rewrite
>>
>>      inline void lock()
>>      {
>>          epoch_t _epoch = shadow_epoch.load(std::memory_order_relaxed);
>>          _ref_epoch.store(_epoch, std::memory_order_relaxed);
>>          std::atomic_signal_fence(std::memory_order_acquire);
>>      }
>>
>>      inline void unlock()
>>      {
>>          _ref_epoch.store(0, std::memory_order_release);
>>      }
>>
>> epoch_t is interesting.  It's uint64_t but handles wrapped
>> compares, ie. for an epoch_t x1 and uint64_t n
> 
> [...]
> 
> Humm... I am not sure if it would work with just the release. The 
> polling thread would read from these per thread epochs, _ref_epoch, 
> using an acquire barrier? Still. Not sure if that would work. Need to 
> put my thinking cap on. ;^)

Ahhh, if you are using an async membar in your upcoming C++ version, 
then it would be fine. No problem. A compiler fence ala 
atomic_signal_fence, and the the explicit release, well, it will work. I 
don't see why it would not work.

For some reason, I thought you were going to not use an async membar in 
your C++ version. Sorry. However, it still would be fun to test 
against... ;^)

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

#120795

On 10/29/24 18:05, Chris M. Thomasson wrote:
> On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:

> 
> Ahhh, if you are using an async membar in your upcoming C++ version, 
> then it would be fine. No problem. A compiler fence ala 
> atomic_signal_fence, and the the explicit release, well, it will work. I 
> don't see why it would not work.
> 
> For some reason, I thought you were going to not use an async membar in 
> your C++ version. Sorry. However, it still would be fun to test 
> against... ;^)

The C version has both versions.  The C++ version does only the
async member version.  But I'm not publishing that code so it's
a moot point.

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

#120830

On 10/30/2024 9:39 AM, jseigh wrote:
> On 10/29/24 18:05, Chris M. Thomasson wrote:
>> On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:
> 
>>
>> Ahhh, if you are using an async membar in your upcoming C++ version, 
>> then it would be fine. No problem. A compiler fence ala 
>> atomic_signal_fence, and the the explicit release, well, it will work. 
>> I don't see why it would not work.
>>
>> For some reason, I thought you were going to not use an async membar 
>> in your C++ version. Sorry. However, it still would be fun to test 
>> against... ;^)
> 
> The C version has both versions.  The C++ version does only the
> async member version.  But I'm not publishing that code so it's
> a moot point.

I got side tracked with more heavy math. The problem with C++ code that 
uses an async memory barrier is that its automatically rendered into a 
non-portable state... Yikes! Imvvvvvho, C/C++ should think about 
including them in some future standard. It would be nice. Well, for us 
at least! ;^)

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

#120833

On 11/4/24 00:14, Chris M. Thomasson wrote:
> On 10/30/2024 9:39 AM, jseigh wrote:
>> On 10/29/24 18:05, Chris M. Thomasson wrote:
>>> On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:
>>
>>>
>>> Ahhh, if you are using an async membar in your upcoming C++ version, 
>>> then it would be fine. No problem. A compiler fence ala 
>>> atomic_signal_fence, and the the explicit release, well, it will 
>>> work. I don't see why it would not work.
>>>
>>> For some reason, I thought you were going to not use an async membar 
>>> in your C++ version. Sorry. However, it still would be fun to test 
>>> against... ;^)
>>
>> The C version has both versions.  The C++ version does only the
>> async member version.  But I'm not publishing that code so it's
>> a moot point.
> 
> I got side tracked with more heavy math. The problem with C++ code that 
> uses an async memory barrier is that its automatically rendered into a 
> non-portable state... Yikes! Imvvvvvho, C/C++ should think about 
> including them in some future standard. It would be nice. Well, for us 
> at least! ;^)

That's never going to happen.  DWCAS has been around for more than
50 years and c++ doesn't support that and probably never will.
You can't write lock-free queues that are ABA free and
are performant without that.  So async memory barriers won't
happen any time soon either.

Long term I think c++ will fade into irrelevance along with
all the other programming languages based on an imperfect
knowledge of concurrency, which is basically all of them
right now.

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

#120834

On Mon, 4 Nov 2024 07:46:37 -0500
jseigh <jseigh_es00@xemaps.com> boring babbled:
>On 11/4/24 00:14, Chris M. Thomasson wrote:
>> On 10/30/2024 9:39 AM, jseigh wrote:
>>> On 10/29/24 18:05, Chris M. Thomasson wrote:
>>>> On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:
>>>
>>>>
>>>> Ahhh, if you are using an async membar in your upcoming C++ version, 
>>>> then it would be fine. No problem. A compiler fence ala 
>>>> atomic_signal_fence, and the the explicit release, well, it will 
>>>> work. I don't see why it would not work.
>>>>
>>>> For some reason, I thought you were going to not use an async membar 
>>>> in your C++ version. Sorry. However, it still would be fun to test 
>>>> against... ;^)
>>>
>>> The C version has both versions.  The C++ version does only the
>>> async member version.  But I'm not publishing that code so it's
>>> a moot point.
>> 
>> I got side tracked with more heavy math. The problem with C++ code that 
>> uses an async memory barrier is that its automatically rendered into a 
>> non-portable state... Yikes! Imvvvvvho, C/C++ should think about 
>> including them in some future standard. It would be nice. Well, for us 
>> at least! ;^)
>
>That's never going to happen.  DWCAS has been around for more than
>50 years and c++ doesn't support that and probably never will.
>You can't write lock-free queues that are ABA free and
>are performant without that.  So async memory barriers won't
>happen any time soon either.
>
>Long term I think c++ will fade into irrelevance along with
>all the other programming languages based on an imperfect
>knowledge of concurrency, which is basically all of them
>right now.

Given most concurrent operating systems are written in these "imperfect"
languages how does that square with your definition? And how would your 
perfect language run on them?

Anyway, concurrency is the job of the OS, not the language. C++ threading is
just a wrapper around pthreads on *nix and windows threads on Windows. The 
language just needs an interface to the underlying OS functionality, it should
not try and implement the functionality itself as it'll always be a hack.

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

#120836

On 11/4/2024 6:09 AM, Muttley@DastartdlyHQ.org wrote:
> On Mon, 4 Nov 2024 07:46:37 -0500
> jseigh <jseigh_es00@xemaps.com> boring babbled:
>> On 11/4/24 00:14, Chris M. Thomasson wrote:
>>> On 10/30/2024 9:39 AM, jseigh wrote:
>>>> On 10/29/24 18:05, Chris M. Thomasson wrote:
>>>>> On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:
>>>>
>>>>>
>>>>> Ahhh, if you are using an async membar in your upcoming C++ version,
>>>>> then it would be fine. No problem. A compiler fence ala
>>>>> atomic_signal_fence, and the the explicit release, well, it will
>>>>> work. I don't see why it would not work.
>>>>>
>>>>> For some reason, I thought you were going to not use an async membar
>>>>> in your C++ version. Sorry. However, it still would be fun to test
>>>>> against... ;^)
>>>>
>>>> The C version has both versions.  The C++ version does only the
>>>> async member version.  But I'm not publishing that code so it's
>>>> a moot point.
>>>
>>> I got side tracked with more heavy math. The problem with C++ code that
>>> uses an async memory barrier is that its automatically rendered into a
>>> non-portable state... Yikes! Imvvvvvho, C/C++ should think about
>>> including them in some future standard. It would be nice. Well, for us
>>> at least! ;^)
>>
>> That's never going to happen.  DWCAS has been around for more than
>> 50 years and c++ doesn't support that and probably never will.
>> You can't write lock-free queues that are ABA free and
>> are performant without that.  So async memory barriers won't
>> happen any time soon either.
>>
>> Long term I think c++ will fade into irrelevance along with
>> all the other programming languages based on an imperfect
>> knowledge of concurrency, which is basically all of them
>> right now.
> 
> Given most concurrent operating systems are written in these "imperfect"
> languages how does that square with your definition? And how would your
> perfect language run on them?
> 
> Anyway, concurrency is the job of the OS, not the language. C++ threading is
> just a wrapper around pthreads on *nix and windows threads on Windows. The
> language just needs an interface to the underlying OS functionality, it should
> not try and implement the functionality itself as it'll always be a hack.
> 

A start would be C++ having an "always lock free" CAS for two contiguous 
words on systems that support it, yes, even 64 bit. ala:

struct anchor {
     word a;
     word b;
};

cmpxchg8b for x86, cmpxchg16b for x64, ect...

https://www.felixcloutier.com/x86/cmpxchg8b:cmpxchg16b

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

#120878

On 11/4/2024 12:42 PM, Chris M. Thomasson wrote:
> On 11/4/2024 6:09 AM, Muttley@DastartdlyHQ.org wrote:
>> On Mon, 4 Nov 2024 07:46:37 -0500
>> jseigh <jseigh_es00@xemaps.com> boring babbled:
>>> On 11/4/24 00:14, Chris M. Thomasson wrote:
>>>> On 10/30/2024 9:39 AM, jseigh wrote:
>>>>> On 10/29/24 18:05, Chris M. Thomasson wrote:
>>>>>> On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:
>>>>>
>>>>>>
>>>>>> Ahhh, if you are using an async membar in your upcoming C++ version,
>>>>>> then it would be fine. No problem. A compiler fence ala
>>>>>> atomic_signal_fence, and the the explicit release, well, it will
>>>>>> work. I don't see why it would not work.
>>>>>>
>>>>>> For some reason, I thought you were going to not use an async membar
>>>>>> in your C++ version. Sorry. However, it still would be fun to test
>>>>>> against... ;^)
>>>>>
>>>>> The C version has both versions.  The C++ version does only the
>>>>> async member version.  But I'm not publishing that code so it's
>>>>> a moot point.
>>>>
>>>> I got side tracked with more heavy math. The problem with C++ code that
>>>> uses an async memory barrier is that its automatically rendered into a
>>>> non-portable state... Yikes! Imvvvvvho, C/C++ should think about
>>>> including them in some future standard. It would be nice. Well, for us
>>>> at least! ;^)
>>>
>>> That's never going to happen.  DWCAS has been around for more than
>>> 50 years and c++ doesn't support that and probably never will.
>>> You can't write lock-free queues that are ABA free and
>>> are performant without that.  So async memory barriers won't
>>> happen any time soon either.
>>>
>>> Long term I think c++ will fade into irrelevance along with
>>> all the other programming languages based on an imperfect
>>> knowledge of concurrency, which is basically all of them
>>> right now.
>>
>> Given most concurrent operating systems are written in these "imperfect"
>> languages how does that square with your definition? And how would your
>> perfect language run on them?
>>
>> Anyway, concurrency is the job of the OS, not the language. C++ 
>> threading is
>> just a wrapper around pthreads on *nix and windows threads on Windows. 
>> The
>> language just needs an interface to the underlying OS functionality, 
>> it should
>> not try and implement the functionality itself as it'll always be a hack.
>>
> 
> A start would be C++ having an "always lock free" CAS for two contiguous 
> words on systems that support it, yes, even 64 bit. ala:
> 
> struct anchor {
>      word a;
>      word b;
> };

Even better:

struct anchor {
     void* a;
     word b;
};

where sizeof(void*) = sizeof(word)... ;^)

> 
> cmpxchg8b for x86, cmpxchg16b for x64, ect...
> 
> https://www.felixcloutier.com/x86/cmpxchg8b:cmpxchg16b
> 
> 

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

#121197

On 11/4/2024 4:46 AM, jseigh wrote:
> On 11/4/24 00:14, Chris M. Thomasson wrote:
>> On 10/30/2024 9:39 AM, jseigh wrote:
>>> On 10/29/24 18:05, Chris M. Thomasson wrote:
>>>> On 10/28/2024 9:41 PM, Chris M. Thomasson wrote:
>>>
>>>>
>>>> Ahhh, if you are using an async membar in your upcoming C++ version, 
>>>> then it would be fine. No problem. A compiler fence ala 
>>>> atomic_signal_fence, and the the explicit release, well, it will 
>>>> work. I don't see why it would not work.
>>>>
>>>> For some reason, I thought you were going to not use an async membar 
>>>> in your C++ version. Sorry. However, it still would be fun to test 
>>>> against... ;^)
>>>
>>> The C version has both versions.  The C++ version does only the
>>> async member version.  But I'm not publishing that code so it's
>>> a moot point.
>>
>> I got side tracked with more heavy math. The problem with C++ code 
>> that uses an async memory barrier is that its automatically rendered 
>> into a non-portable state... Yikes! Imvvvvvho, C/C++ should think 
>> about including them in some future standard. It would be nice. Well, 
>> for us at least! ;^)
> 
> That's never going to happen.  DWCAS has been around for more than
> 50 years and c++ doesn't support that and probably never will.
> You can't write lock-free queues that are ABA free and
> are performant without that.  

Hummm... If I remember correctly, you said something about using a 
simple atomic exchange to pop a whole list (lock-free stack), then 
simple reversing the list to get a fifo order? Do you remember any of 
that way back on c.p.t?



> So async memory barriers won't
> happen any time soon either.
> 
> Long term I think c++ will fade into irrelevance along with
> all the other programming languages based on an imperfect
> knowledge of concurrency, which is basically all of them
> right now.
> 
> 
> 

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

#121198

On 12/12/24 03:43, Chris M. Thomasson wrote:
> On 11/4/2024 4:46 AM, jseigh wrote:

> 
> Hummm... If I remember correctly, you said something about using a 
> simple atomic exchange to pop a whole list (lock-free stack), then 
> simple reversing the list to get a fifo order? Do you remember any of 
> that way back on c.p.t?
> 
That kind of stuff pre-dates c.p.t. even.

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

#121201

On 12/12/2024 4:29 AM, jseigh wrote:
> On 12/12/24 03:43, Chris M. Thomasson wrote:
>> On 11/4/2024 4:46 AM, jseigh wrote:
> 
>>
>> Hummm... If I remember correctly, you said something about using a 
>> simple atomic exchange to pop a whole list (lock-free stack), then 
>> simple reversing the list to get a fifo order? Do you remember any of 
>> that way back on c.p.t?
>>
> That kind of stuff pre-dates c.p.t. even.

Has to. Although, it was not in the IBM principles of operation where 
the describe their lock-free stack in an appendix, iirc... I cannot 
remember the exact one right now. Iirc, it was under free pool 
manipulation?

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

#121202

On 12/12/24 16:55, Chris M. Thomasson wrote:
> On 12/12/2024 4:29 AM, jseigh wrote:
>> On 12/12/24 03:43, Chris M. Thomasson wrote:
>>> On 11/4/2024 4:46 AM, jseigh wrote:
>>
>>>
>>> Hummm... If I remember correctly, you said something about using a 
>>> simple atomic exchange to pop a whole list (lock-free stack), then 
>>> simple reversing the list to get a fifo order? Do you remember any of 
>>> that way back on c.p.t?
>>>
>> That kind of stuff pre-dates c.p.t. even.
> 
> Has to. Although, it was not in the IBM principles of operation where 
> the describe their lock-free stack in an appendix, iirc... I cannot 
> remember the exact one right now. Iirc, it was under free pool 
> manipulation?

If you pop off a LIFO stack onto another LIFO, everything becomes FIFO.

Also, there's a doubly linked stack where the back links are lazily
initialized.  That seems to get reinvented every so often.

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

#121301

On 12/12/2024 4:48 PM, jseigh wrote:
> On 12/12/24 16:55, Chris M. Thomasson wrote:
>> On 12/12/2024 4:29 AM, jseigh wrote:
>>> On 12/12/24 03:43, Chris M. Thomasson wrote:
>>>> On 11/4/2024 4:46 AM, jseigh wrote:
>>>
>>>>
>>>> Hummm... If I remember correctly, you said something about using a 
>>>> simple atomic exchange to pop a whole list (lock-free stack), then 
>>>> simple reversing the list to get a fifo order? Do you remember any 
>>>> of that way back on c.p.t?
>>>>
>>> That kind of stuff pre-dates c.p.t. even.
>>
>> Has to. Although, it was not in the IBM principles of operation where 
>> the describe their lock-free stack in an appendix, iirc... I cannot 
>> remember the exact one right now. Iirc, it was under free pool 
>> manipulation?
> 
> If you pop off a LIFO stack onto another LIFO, everything becomes FIFO.

Humm.... Merry Christmas!

> 
> Also, there's a doubly linked stack where the back links are lazily
> initialized.  That seems to get reinvented every so often.

ahhhhh!

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

#120759

On 10/27/2024 3:29 PM, jseigh wrote:
> On 10/27/24 15:33, Chris M. Thomasson wrote:
>> On 10/25/2024 3:56 PM, jseigh wrote:
>>> On 10/25/24 18:00, Chris M. Thomasson wrote:
>>>> On 10/18/2024 5:07 AM, jseigh wrote:
>>>>> On 10/17/24 19:40, Chris M. Thomasson wrote:
>>>>>> On 10/17/2024 2:08 PM, jseigh wrote:
>>>>>>> On 10/17/24 16:10, Chris M. Thomasson wrote:
>>>>>>>> On 10/17/2024 5:10 AM, jseigh wrote:
>>>>>>>>> I replaced the hazard pointer logic in smrproxy.  It's now 
>>>>>>>>> wait- free
>>>>>>>>> instead of mostly wait-free.  The reader lock logic after loading
>>>>>>>>> the address of the reader lock object into a register is now 2
>>>>>>>>> instructions a load followed by a store.  The unlock is same
>>>>>>>>> as before, just a store.
>>>>>>>>>
>>>>>>>>> It's way faster now.
>>>>>>>>>
>>>>>>>>> It's on the feature/003 branch as a POC.   I'm working on porting
>>>>>>>>> it to c++ and don't want to waste any more time on c version.
>>>>>>>>>
>>>>>>>>> No idea of it's a new algorithm.  I suspect that since I use
>>>>>>>>> the term epoch that it will be claimed that it's ebr, epoch
>>>>>>>>> based reclamation, and that all ebr algorithms are equivalent.
>>>>>>>>> Though I suppose you could argue it's qsbr if I point out what
>>>>>>>>> the quiescent states are.
>>>>>>>>
>>>>>>>> I have to take a look at it! Been really busy lately. Shit happens.
>>>>>>>>
>>>>>>>
>>>>>>> There's a quick and dirty explanation at
>>>>>>> http://threadnought.wordpress.com/
>>>>>>>
>>>>>>> repo at https://github.com/jseigh/smrproxy
>>>>>>>
>>>>>>> I'll need to create some memory access diagrams that
>>>>>>> visualize how it works at some point.
>>>>>>>
>>>>>>> Anyway if it's new, another algorithm to use without
>>>>>>> attribution.
>>>>>>
>>>>>> Interesting. From a quick view, it kind of reminds me of a 
>>>>>> distributed seqlock for some reason. Are you using an asymmetric 
>>>>>> membar in here? in smr_poll ?
>>>>>
>>>>> Yes, linux membarrier() in smr_poll.
>>>>>
>>>>> Not seqlock, not least for the reason that exiting the critical region
>>>>> is 3 instructions unless you use atomics which are expensive and have
>>>>> memory barriers usually.
>>>>>
>>>>> A lot of the qsbr and ebr reader lock/unlock code is going to look
>>>>> somewhat similar so you have to know how the reclaim logic uses it.
>>>>> In this case I am slingshotting off of the asymmetric memory barrier.
>>>>>
>>>>> Earlier at one point I was going to have smrproxy use hazard pointer
>>>>> logic or qsbr logic as a config option, but the extra code complexity
>>>>> and the fact that qsbr required 2 grace periods kind of made that
>>>>> unfeasible.  The qsbr logic was mostly ripped out but there were still
>>>>> some pieces there.
>>>>>
>>>>> Anyway I'm working a c++ version which involves a lot of extra work
>>>>> besides just rewriting smrproxy.  There coming up with an api for
>>>>> proxies and testcases which tend to be more work than the code that
>>>>> they are testing.
>>>>
>>>> Damn! I almost missed this post! Fucking Thunderbird... Will get 
>>>> back to you. Working on something else right now Joe, thanks.
>>>>
>>>> https://www.facebook.com/share/p/ydGSuPLDxjkY9TAQ/
>>>
>>>
>>> No problem.  The c++ work is progressing pretty slowly, not least in
>>> part because the documentation is not always clear as to what
>>> something does or even what problem it is supposed to solve.
>>> To think I took a pass on on rust because I though it was
>>> more complicated than it needed to be.
>>
>> Never even tried Rust, shit, I am behind the times. ;^)
>>
>> Humm... I don't think we can get 100% C++ because of the damn 
>> asymmetric membar for these rather "specialized" algorithms?
>>
>> Is C++ thinking about creating a standard way to gain an asymmetric 
>> membar?
> 
> I don't think so.  It's platform dependent.  Apart from linux, mostly
> it's done with a call to some virtual memory function that flushes
> the TLBs (translation lookaside buffers) which involves IPI calls
> to all the processors and those have memory barriers.  This is
> old, 1973, patent 3,947,823 cited by the patent I did.
> 
> Anyway, I version the code so there's a asymmetric memory barrier
> version and an explicit memory barrier version, the latter
> being much slower.

I should get back into one of my older proxy algorithms. Things are 
mostly wait free, if XADD can be wait free itself. No CAS in sight. I 
just found an older version I posted.. Almost forgot I make this post:

https://groups.google.com/g/comp.lang.c++/c/FBqOMvqWpR4/m/bDZZLUmAAgAJ

https://pastebin.com/raw/nPVYXbWM
(raw text, no ad bullshit)

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

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

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

csiph-web