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

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

Re: Futex Stack Test...

Show all headers | View raw

On 5/2/2025 8:02 PM, Bonita Montero wrote:
> That's the atomic_stack:
> 
> header:
> 
> #pragma once
> #if defined(_MSC_VER)
>      #include <Windows.h>
> #endif
> #include <atomic>
> #include "dcas_atomic.h"
> 
> struct atomic_stack
> {
>      struct link { link *next; };
>      atomic_stack();
>      atomic_stack( link *pFirstItem );
>      void push( link *pItem );
>      void push_chain( link *pFirstItem );
>      void push_chain( link *pFirstItem, link *pLastItem );
>      link *pop();
>      link *pop_all();
>      operator bool();
> private:
>      using dcas_pair = typename dcas_atomic::pair_t;
>      dcas_atomic m_top;
> };
> 
> inline atomic_stack::atomic_stack() :
>      atomic_stack( nullptr )
> {
> }
> 
> inline atomic_stack::atomic_stack( link *pFirstItem ) :
>      m_top( dcas_pair( (size_t)pFirstItem, 0 ) )
> {
> }
> 
> inline void atomic_stack::push_chain( link *pFirstItem )
> {
>      link *pLastItem = pFirstItem;
>      for( ; pLastItem->next; pLastItem = pLastItem->next );
>      push_chain( pFirstItem, pLastItem );
> }
> 
> inline atomic_stack::operator bool()
> {
>      return m_top.first();
> }
> 
> cpp:
> 
> #include "atomic_stack.h"
> 
> void atomic_stack::push( link *pItem )
> {
>      dcas_pair cmp( m_top ), niu;
>      do
>      {
>          pItem->next = (link *)cmp.first;
>          niu.first = (size_t)pItem;
>          niu.second = cmp.second + 1;
>      } while( !m_top.compare_exchange( cmp, niu, dcas_release() ) );
> }
> 
> void atomic_stack::push_chain( link *pFirstItem, link *pLastItem )
> {
>      dcas_pair cmp( m_top ), niu;
>      do
>      {
>          pLastItem->next = (link *)cmp.first;
>          niu.first = (size_t)pFirstItem;
>          niu.second = cmp.second + 1;
>      } while( !m_top.compare_exchange( cmp, niu, dcas_release() ) );
> }
> 
> typename atomic_stack::link *atomic_stack::pop()
> {
>      using namespace std;
>      dcas_pair cmp, niu;
>      link *pItem;
>      cmp.first = m_top.first();
>      if( !(pItem = (link *)cmp.first) ) [[unlikely]]
>          return nullptr;
>      cmp.second = m_top.second();
>      for( ; ; )
>      {
>          niu.first = (size_t)pItem->next;
>          niu.second = cmp.second + 1;
>          if( m_top.compare_exchange( cmp, niu, dcas_acquire() ) ) 
> [[likely]]
>              return pItem;
>          if( !(pItem = (link *)cmp.first) ) [[unlikely]]
>              return nullptr;
>      }
> }
> 
> typename atomic_stack::link *atomic_stack::pop_all()
> {
>      using namespace std;
>      dcas_pair cmp, niu;
>      cmp.first = m_top.first();
>      if( !cmp.first ) [[unlikely]]
>          return nullptr;
>      cmp.second = m_top.second();
>      niu.first = (size_t)nullptr;
>      do
>          niu.second = cmp.second + 1;
>      while( !m_top.compare_exchange( cmp, niu, dcas_acquire() ) );
>      return (link *)cmp.first;
> }

 From a cursory read it seems fine, Bonita. Also, I had a suspicion that 
Wuns Haerst just "might" be you because the code style itself looked 
fairly similar to yours. Am I right? Also, I like the push chain. 
Actually, I was thinking about adding it to my my futex stack test.

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.

Wrt DWCAS, it's a god damn shame that C++ tends to make it not lock 
free: That sucks! Believe it or not, there is a way to make it work with 
single word exchange for the push and pop. I posted about it before on 
this group.

Now, there is another issue with a single pop... If you delete a node, 
it can bite the dust. A proxy collector works well with it, but that is 
a bit overkill! Uggg ;^o However, iirc, SEH can be used to handle it. 
Iirc, that is what the SLIST uses on windows? Been a while...

There is no memory issue if you flush, or pop_all. :^)

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