Am 09.03.2026 um 23:36 schrieb Chris M. Thomasson:I need some more time to really examine it. Seems to look okay for now. Well, I cannot notice anything obviously wrong so far.
I don't think it mentions it there, but SEH is used. I prefer proxy collectors over hazard pointers, but that's just me. Well, Joe knows. Hazard pointers basically need async membar behavior or else they eat your lunch with that damn #StoreLoad.I've developed a lockfree stack with SEH. With one thread it is
lower than a SLIST, with two threads it is faster and with 32
threads it is magnitudes faster:
Notice where you align?
> alignas(2 * sizeof(size_t)) head m_head = { 0, 0 };
Well, I don't think a SLIST anchor is automatically aligned. You should align it on a l2 cache line boundary and pad it up to a l2 cache line.
https://learn.microsoft.com/en-us/windows/win32/sync/using-singly-linked-lists
notice:
typedef struct _PROGRAM_ITEM {
SLIST_ENTRY ItemEntry;
ULONG Signature;
} PROGRAM_ITEM, *PPROGRAM_ITEM;
? Notice _aligned_malloc?
Also, have you checked that your compare_exchange_strong is using CMPXCHG8B on 32 bit systems and CMPXCHG16B on 64 bit systems? That used to piss me off when it said not always lock-free.
Little shits.
PROGRAM_ITEM needs to be aligned and padded, and PSLIST_HEADER needs to be aligned and padded.
Also, how are you testing it? If you never delete any nodes, your SEH is useless. Also, so, well, what memory allocator are you using?
#pragma once
#if defined(_WIN32)
#include <Windows.h>
#endif
#include <atomic>
template<typename T>
struct lockfree_stack
{
struct node : T
{
using T::T;
private:
template<typename T>
friend struct lockfree_stack;
node *m_next;
};
void push( node *nd ) noexcept;
node *pop() noexcept;
private:
struct head { node *ptr; size_t ctr; };
static_assert(atomic_ref<head>::is_always_lock_free);
alignas(2 * sizeof(size_t)) head m_head = { 0, 0 };
};
template<typename T>
void lockfree_stack<T>::push( node *nd ) noexcept
{
using namespace std;
atomic_ref ptr( m_head.ptr );
atomic_ref ctr( m_head.ctr );
head hdRef( ptr.load( memory_order_relaxed ), ctr.load( memory_order_relaxed ) );
atomic_ref<head> aHead( m_head );
do
nd->m_next = (node *)hdRef.ptr;
while( aHead.compare_exchange_strong( hdRef, head( nd, hdRef.ctr + 1 ), memory_order_release, memory_order_relaxed ) );
}
template<typename T>
auto lockfree_stack<T>::pop() noexcept -> node *
{
using namespace std;
atomic_ref ptr( m_head.ptr );
atomic_ref ctr( m_head.ctr );
head hdRef( ptr.load( memory_order_relaxed ), ctr.load( memory_order_relaxed ) );
atomic_ref<head> aHead( m_head );
for( ; ; )
{
node *next;
if( !hdRef.ptr )
return nullptr;
__try
{
next = hdRef.ptr->m_next;
}
__except( EXCEPTION_EXECUTE_HANDLER )
{
hdRef = head( ptr.load( memory_order_relaxed ), ctr.load( memory_order_relaxed ) );
continue;
}
if( aHead.compare_exchange_strong( hdRef, head( next, hdRef.ctr + 1 ), memory_order_acquire, memory_order_relaxed ) )
return hdRef.ptr;
}
}
In the next step I make this Posix'd with my scoped_signal.
Les messages affichés proviennent d'usenet.