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

Groups > comp.lang.c++ > #122270

Re: Futex Stack Test...

From "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups comp.lang.c++
Subject Re: Futex Stack Test...
Date 2025-05-10 13:48 -0700
Organization A noiseless patient Spider
Message-ID <vvoe2a$3mrhl$3@dont-email.me> (permalink)
References (5 earlier) <vv5ln8$26ei$1@dont-email.me> <vv5mn0$38ie$1@raubtier-asyl.eternal-september.org> <vv5shh$89nm$1@dont-email.me> <vv6hhn$rebo$1@dont-email.me> <vvjc8o$27602$1@dont-email.me>

Show all headers | View raw

On 5/8/2025 3:46 PM, jseigh wrote:
> On 5/3/25 21:57, Chris M. Thomasson wrote:
>> On 5/3/2025 12:58 PM, Chris M. Thomasson wrote:
>>> On 5/3/2025 11:19 AM, Bonita Montero wrote:
>>>> Am 03.05.2025 um 20:02 schrieb Chris M. Thomasson:
>>>>
>>>>> Now, its fun to be able to get a lock-free stack with only single 
>>>>> word exchange and cas, and have the ability to use it with a futex 
>>>>> to allow one to wait on empty conditions.
>>>>
>>>> Is a lock-free stack with a single word CAS really possible without an
>>>> ABA-problem ?
>>>
>>> Will get back to you. Need to run a bunch of errands. If you omit 
>>> single item pop, yup. It's also possible to get rid of the cas in push.
>>
>> The ABA problem _and_ memory issue is only there in on the single node 
>> pop for a lock-free stack. If you just whack it with a nullptr aka 
>> flush _all_ nodes, then you are all right and ready to roll.
>>
>> Actually, IBM had/has a nice write up of it in an appendix for the 
>> principles of operations iirc. I think it might of been in appendix 40 
>> ish or something. God it's been a while since I read that Bonita. Then 
>> they have a rather nifty PLO, or perform locked operation, again iirc...
>>
>> The futex is fun to use because it allows one to wait on an empty 
>> condition...
>>
>> Actually, I remember Joe Seigh taking all the nodes in an exchange, 
>> reversing them, and BAM, its FIFO. ;^)
>>
> 
> Probably for a MPSC queue.  I don't the FIFO semantics would hold up
> very well for MPMC queue.

:^)

Well, even with a MPMP FIFO queue without the pop_all reverse results 
type approach, it can go:

Thread A pushes say, 10 items:

item[0]
item[1]
...

Thread B pops item[0], gets interrupted, thread C pops item[1] and 
processes it before thread B got a chance to process item[0]? That can 
happen even without the pop_all/flush "trick"... Or, am I missing 
something Joe?

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-02-17 15:17 -0800
  Re: Futex Stack Test... Paavo Helde <eesnimi@osa.pri.ee> - 2025-02-18 09:01 +0200
    Re: Futex Stack Test... James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-02-18 14:13 -0500
      Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-02-19 12:06 -0800
    Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-02-19 11:57 -0800
    Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-02-28 00:41 -0800
  Re: Futex Stack Test... Wuns Haerst <Wuns.Haerst@wurstfabrik.at> - 2025-05-02 13:01 +0200
    Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-02 11:30 -0700
      Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-02 14:41 -0700
    Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-02 18:49 -0700
      Re: Futex Stack Test... Wuns Haerst <Wuns.Haerst@wurstfabrik.at> - 2025-05-03 04:21 +0200
        Re: Futex Stack Test... Bonita Montero <Bonita.Montero@gmail.com> - 2025-05-03 05:02 +0200
          Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-03 11:02 -0700
            Re: Futex Stack Test... Bonita Montero <Bonita.Montero@gmail.com> - 2025-05-03 20:19 +0200
              Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-03 12:58 -0700
                Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-03 18:57 -0700
                Re: Futex Stack Test... Bonita Montero <Bonita.Montero@gmail.com> - 2025-05-08 11:11 +0200
                Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-08 12:37 -0700
                Re: Futex Stack Test... jseigh <jseigh_es00@xemaps.com> - 2025-05-08 18:46 -0400
                Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-10 13:48 -0700
                Re: Futex Stack Test... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-05-10 13:48 -0700

csiph-web