Path: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups: comp.lang.c++
Subject: Re: smrproxy v2
Date: Sun, 27 Oct 2024 21:09:54 -0700
Organization: A noiseless patient Spider
Lines: 139
Message-ID: <vfn2qi$r8ca$3@dont-email.me>
References: <vequrc$2o7qc$1@dont-email.me> <verr04$2stfq$1@dont-email.me>
 <verubk$2t9bs$1@dont-email.me> <ves78h$2ugvm$2@dont-email.me>
 <vetj1f$39iuv$1@dont-email.me> <vfh4dh$3bnuq$1@dont-email.me>
 <vfh7mg$3c2hs$1@dont-email.me> <vfm4iq$ill4$1@dont-email.me>
 <vfmesn$k6mn$1@dont-email.me> <vfn2nn$r8ca$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 28 Oct 2024 05:09:55 +0100 (CET)
Injection-Info: dont-email.me; posting-host="22ea2bd49efaecaba901b5a855237ac5";
	logging-data="893322"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Cfkf0ZqSyicMwmJq0AFA0husS53RTl10="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:nu13UuzlOThmcFbd0iycNaQ6Bm0=
Content-Language: en-US
In-Reply-To: <vfn2nn$r8ca$2@dont-email.me>
Bytes: 7139

On 10/27/2024 9:08 PM, Chris M. Thomasson wrote:
> 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)
> 
> 
> 

It beats a read write lock, but it has trouble beating one that does not 
use any atomic RMW's in the fast path ala:
___________________
     collector& acquire()
     {
         // increment the master count _and_ obtain current collector.
         std::uint32_t current =
             m_current.fetch_add(ct_ref_inc, std::memory_order_acquire);

         // decode the collector index.
         return m_collectors[current & ct_proxy_mask];
     }

     void release(collector& c)
     {
         // decrement the collector.
         std::uint32_t count =
             c.m_count.fetch_sub(ct_ref_inc, std::memory_order_release);

         // check for the completion of the quiescence process.
         if ((count & ct_ref_mask) == ct_ref_complete)
         {
             // odd reference count and drop-to-zero condition detected!
             prv_quiesce_complete(c);
         }
     }
___________________