Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #120734 > unrolled thread
| Started by | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| First post | 2024-10-17 08:10 -0400 |
| Last post | 2024-12-11 16:22 -0800 |
| Articles | 20 on this page of 66 — 3 participants |
Back to article view | Back to comp.lang.c++
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 1 of 4 [1] 2 3 4 Next page →
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-17 08:10 -0400 |
| Subject | smrproxy v2 |
| Message-ID | <vequrc$2o7qc$1@dont-email.me> |
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. Joe Seigh
[toc] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-17 13:10 -0700 |
| Message-ID | <verr04$2stfq$1@dont-email.me> |
| In reply to | #120734 |
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.
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-17 17:08 -0400 |
| Message-ID | <verubk$2t9bs$1@dont-email.me> |
| In reply to | #120735 |
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. Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-17 16:40 -0700 |
| Message-ID | <ves78h$2ugvm$2@dont-email.me> |
| In reply to | #120736 |
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 ?
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-17 17:16 -0700 |
| Message-ID | <ves9do$2ugvm$3@dont-email.me> |
| In reply to | #120737 |
On 10/17/2024 4:40 PM, 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 ?
I remember a long time ago I was messing around where each thread had
two version counters:
pseudo code:
per_thread
{
word m_version[2];
word acquire()
{
word ver = load(global_version);
m_version[ver % 2] = ver ;
return ver ;
}
void release(word ver)
{
m_version[ver % 2] = 0;
}
}
The global_version would only be incremented by the polling thread. This
was WAY back. I think I might of posted about it on cpt.
So, when a node was made unreachable, it would be included in the
polling logic. The polling could increment the version counter then wait
for all the threads prior m_versions to be zero. Collect the current
generation of objects in a defer list. Then on the next cycle it would
increment the version counter, wait until all threads prior versions
were zero, then delete the defer count, and transfer the current gen to
the defer.
It went something like that.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-17 17:24 -0700 |
| Message-ID | <ves9r9$2v6q6$1@dont-email.me> |
| In reply to | #120738 |
On 10/17/2024 5:16 PM, Chris M. Thomasson wrote:
> On 10/17/2024 4:40 PM, 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 ?
>
> I remember a long time ago I was messing around where each thread had
> two version counters:
>
> pseudo code:
>
> per_thread
> {
> word m_version[2];
>
>
> word acquire()
> {
> word ver = load(global_version);
> m_version[ver % 2] = ver ;
> return ver ;
> }
>
>
> void release(word ver)
> {
> m_version[ver % 2] = 0;
> }
> }
>
>
> The global_version would only be incremented by the polling thread. This
> was WAY back. I think I might of posted about it on cpt.
>
> So, when a node was made unreachable, it would be included in the
> polling logic. The polling could increment the version counter then wait
> for all the threads prior m_versions to be zero. Collect the current
> generation of objects in a defer list. Then on the next cycle it would
> increment the version counter, wait until all threads prior versions
> were zero, then delete the defer count, and transfer the current gen to
> the defer.
>
> It went something like that.
>
Iirc, I was using FlushProcessWriteBuffers back then for an asymmetric
barrier for my experiment. The polling thread would execute one after it
increased the global version. Actualy, I can't remember where I placed
it exactly, after or before. The defer list made things work.
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-18 08:07 -0400 |
| Message-ID | <vetj1f$39iuv$1@dont-email.me> |
| In reply to | #120737 |
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. Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-25 15:00 -0700 |
| Message-ID | <vfh4dh$3bnuq$1@dont-email.me> |
| In reply to | #120740 |
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/
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-25 18:56 -0400 |
| Message-ID | <vfh7mg$3c2hs$1@dont-email.me> |
| In reply to | #120749 |
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. Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-27 12:33 -0700 |
| Message-ID | <vfm4iq$ill4$1@dont-email.me> |
| In reply to | #120750 |
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?
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-27 18:29 -0400 |
| Message-ID | <vfmesn$k6mn$1@dont-email.me> |
| In reply to | #120751 |
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. Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-27 15:32 -0700 |
| Message-ID | <vfmf21$kavl$1@dont-email.me> |
| In reply to | #120752 |
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. Ahh, nice! acquire/release, no seq_cst, right? ;^)
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-27 20:35 -0400 |
| Message-ID | <vfmm9a$lob3$1@dont-email.me> |
| In reply to | #120753 |
On 10/27/24 18:32, 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. > > Ahh, nice! acquire/release, no seq_cst, right? ;^) > The membar version? That's a store/load membar so it is expensive.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-27 21:02 -0700 |
| Message-ID | <vfn2di$r8ca$1@dont-email.me> |
| In reply to | #120755 |
On 10/27/2024 5:35 PM, jseigh wrote: > On 10/27/24 18:32, 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. >> >> Ahh, nice! acquire/release, no seq_cst, right? ;^) >> > > 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?
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-28 07:45 -0400 |
| Message-ID | <vfntgb$vete$1@dont-email.me> |
| In reply to | #120758 |
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. For cmpxchg, it has full cst_seq. For other rmw atomics I don't know. I have to ask on c.a. I think some data dependency and/or control dependency might factor in. Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-28 14:57 -0700 |
| Message-ID | <vfp1c3$16d9f$1@dont-email.me> |
| In reply to | #120763 |
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... ;^) > > For cmpxchg, it has full cst_seq. For other rmw atomics I don't > know. I have to ask on c.a. I think some data dependency and/or > control dependency might factor in. > > Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-28 15:09 -0700 |
| Message-ID | <vfp234$16jt2$1@dont-email.me> |
| In reply to | #120765 |
On 10/28/2024 2:57 PM, 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. The fun part is that since its pure C++, those membars are going to be emitted for me no matter what arch it's compiling for. > 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... ;^) > > > >> >> For cmpxchg, it has full cst_seq. For other rmw atomics I don't >> know. I have to ask on c.a. I think some data dependency and/or >> control dependency might factor in. >> >> Joe Seigh >
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-28 21:17 -0400 |
| Message-ID | <vfpd43$186t4$1@dont-email.me> |
| In reply to | #120765 |
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
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.
Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-10-28 21:35 -0700 |
| Message-ID | <vfpomm$1dqvu$1@dont-email.me> |
| In reply to | #120767 |
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);
^^^^^^^^^^^^^^^^^^^^^^
> }
Still don't know how your pure C++ write up can handle this without an
std::atomic_thread_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
>
> x1 < (x1 + n)
>
> for any value of x1 and any value of n from 0 to 2**63;
> eg.
> 0xfffffffffffffff0 < 0x0000000000000001
For some reason it reminds me of your atomic 63 bit counter from a while
back. If your smr_poll thread is the only thread that can increment the
epoch, then it will be able to detect rolling to zero, right? For one of
my older proxys the thread would have two version counters:
per_thread
{
word m_ver[2];
lock()
{
word ver = g_version;
m_ver[ver % 2] = ver;
}
unlock(word ver)
{
m_ver[ver % 2] = 0;
}
}
So, it's different logic. The only way I got around using memory
barriers (compiler barriers aside for a moment), here was for the
polling thread to use an asymmetric membar. For a pure C++ version, I
think it would require:
per_thread
{
word m_ver[2];
lock()
{
word ver = g_version;
m_ver[ver % 2] = ver;
#LoadStore | #LoadLoad;
}
unlock(word ver)
{
#LoadStore | #StoreStore;
m_ver[ver % 2] = 0;
}
}
I think.... Humm...
>
>
> 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.
>
> Joe Seigh
[toc] | [prev] | [next] | [standalone]
| From | jseigh <jseigh_es00@xemaps.com> |
|---|---|
| Date | 2024-10-29 07:23 -0400 |
| Message-ID | <vfqgkc$1hfo1$1@dont-email.me> |
| In reply to | #120770 |
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.
>
>>
>> inline void unlock()
>> {
>> _ref_epoch.store(0, std::memory_order_release);
>> }
>
[toc] | [prev] | [next] | [standalone]
Page 1 of 4 [1] 2 3 4 Next page →
Back to top | Article view | comp.lang.c++
csiph-web