Am 19.03.2026 um 03:58 schrieb Chris M. Thomasson:
If you decide to use threads. Make sure to learn about mutex and condvar first! Then learn about embarrassingly parallel, where no mutex and
condvar are "necessarily" needed. Then ponder on lock-free.
Embarassingly parallel doesn't mean that no mutexes or
condvars are necessary, just that parallelizing was easy.
Make sure to never have to use lock-free unless you absolutely have to!
There are only two definitive lock-free algorithms: lock-free stacks
and lock free queues. Lock-free stacks have a very rare usage. Lock
-free queues have the disadvantage that they have to be polled - which
is an absolute noo-go - and that can't be resized at runtime.
But when you have a queue guarded with a mutex and a condvar that's
mostly sufficient because there's rarely an overlap of the access
between producers and consumers since enqueuing and dequeuing usually
takes a minimum of computation time.
On Windows you could use deques. Although the Window's deques are not
very smart since they work with chunks of one element, they don't with-
draw every node which is being poped; instead they go to a standby list
so that they can be recycled very fast. This is allowed by the deque
-interface since it has a shrink_to_fit() call.
Libstdc++ (clang++ and g++ on all OSs except macOS) allocates the items
at chunks up zo 512 bytes. This makes mostly linear memory accesses and allocations and deallocations to happen not often.
I wasn't satisfied with that solution so that I wrote a simple deque -replacement. Acces is supported not by iterators (to much work) but
with a functional interface.
Here's the code:
#pragma once
#include <array>
#include <vector>
#include <memory>
#include <iterator>
#include <algorithm>
#include <concepts>
#include <cassert>
#include <optional>
#include "defer.hpp"
#include "ndi.hpp"
#include "cacheline.hpp"
#undef min
#if defined(__clang__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunqualified-std-cast-call"
#pragma clang diagnostic ignored "-Wdangling-else"
#pragma clang diagnostic ignored "-Wlogical-op-parentheses"
#endif
template<typename T>
struct xdeque
{
xdeque();
xdeque( xdeque<T> &&other ) noexcept;
//xdeque( const xdeque<T> &other );
~xdeque();
xdeque<T> &operator =( xdeque<T> &&other ) noexcept;
//xdeque<T> &operator =( const xdeque<T> &other ) noexcept;
template<typename ... Params>
T &emplace_back( Params &&... params );
//void emplace_back_row( T &&value, size_t n );
void pop_front() noexcept;
std::optional<T> pop_back() noexcept;
T &front() noexcept;
const T &front() const noexcept;
size_t size() const noexcept;
bool empty() const noexcept;
void clear() noexcept;
void shrink_to_fit() noexcept;
template<typename Consumer>
void consume( Consumer consumer );
template<typename Consumer>
void consume( Consumer consumer ) const;
private:
template<size_t N>
struct n_chunk;
template<size_t N>
using n_chunk_ptr = std::unique_ptr<n_chunk<N>>;
template<size_t N>
struct n_chunk : std::array<tndi<T>, N>
{
n_chunk_ptr<N> next;
};
static constexpr ptrdiff_t
XN_CHUNK = (ptrdiff_t)(512 - sizeof(n_chunk<1>)) / (ptrdiff_t)sizeof(T) + 1,
N_CHUNK = XN_CHUNK >= 1 ? XN_CHUNK : 1;
using chunk = n_chunk<N_CHUNK>;
using chunk_ptr = n_chunk_ptr<N_CHUNK>;
using chunk_ptrs = std::vector<chunk_ptr>;
chunk_ptrs m_chunks;
chunk_ptr m_firstStandby;
using chunks_it = typename chunk_ptrs::iterator;
using chunk_it = typename chunk::iterator;
struct pointer
{
chunks_it itChunks;
chunk_it itChunk;
} m_begin, m_end;
void shrinkChunks() noexcept;
#if !defined(NDEBUG)
bool checkQueue() noexcept;
#endif
};
template<typename T>
void xdeque<T>::shrinkChunks() noexcept
{
using namespace std;
defer exitCheck( [&] { assert(checkQueue()); } );
if( (size_t)(m_begin.itChunks - m_chunks.begin()) * 2 <= m_chunks.size() )
return;
std::move_iterator
itBegin( m_begin.itChunks ),
itEnd( m_chunks.end() );
size_t toEnd = m_end.itChunks == m_chunks.end();
m_chunks.resize( copy( itBegin, itEnd, m_chunks.begin() ) - m_chunks.begin() );
m_begin.itChunks = m_chunks.begin();
m_end.itChunks = m_chunks.end() - (!toEnd && m_chunks.size());
}
#if !defined(NDEBUG)
template<typename T>
bool xdeque<T>::checkQueue() noexcept
{
if( m_begin.itChunks > m_end.itChunks )
return false;
if( m_begin.itChunks == m_chunks.end() )
return m_end.itChunks == m_chunks.end();
if( m_begin.itChunks == m_end.itChunks )
return m_begin.itChunk < m_end.itChunk;
if( m_end.itChunks != m_chunks.end() && (m_end.itChunk == (*m_end.itChunks)->begin() || m_end.itChunk == (*m_end.itChunks)->end()) )
return false;
if( m_begin.itChunk < (*m_begin.itChunks)->begin() || m_begin.itChunk
= (*m_begin.itChunks)->end() )
return false;
return true;
}
#endif
template<typename T>
xdeque<T>::xdeque() :
m_begin( m_chunks.begin(), chunk_it() ),
m_end( m_chunks.end(), chunk_it() )
{
}
template<typename T>
xdeque<T>::xdeque( xdeque<T> &&other ) noexcept :
m_chunks( std::move( other.m_chunks ) ),
m_firstStandby( std::move( other.m_firstStandby ) ),
m_begin( other.m_begin ),
m_end( other.m_end )
{
other.m_chunks.resize( 0 );
other.m_begin.itChunks = other.m_chunks.begin();
other.m_end.itChunks = other.m_chunks.end();
}
template<typename T>
xdeque<T> &xdeque<T>::operator =( xdeque<T> &&other ) noexcept
{
using namespace std;
m_chunks = move( other.m_chunks );
m_firstStandby = move( other.m_firstStandby );
m_begin = other.m_begin;
m_end = other.m_end;
other.m_chunks.resize( 0 );
other.m_begin.itChunks = other.m_chunks.begin();
other.m_end.itChunks = other.m_chunks.end();
return *this;
}
template<typename T>
inline xdeque<T>::~xdeque()
{
clear();
}
template<typename T>
template<typename ... Params>
T &xdeque<T>::emplace_back( Params &&... params )
{
using namespace std;
defer exitCheck( [&] { assert(checkQueue()); } );
defer unchunk( [&]
{
if( m_end.itChunks == m_chunks.end() || m_end.itChunk >
(*m_end.itChunks)->begin() )
return;
chunk_ptr lastEmpty = move( *m_end.itChunks );
lastEmpty->next = move( m_firstStandby );
m_firstStandby = move( lastEmpty );
m_chunks.pop_back();
assert(checkQueue());
} );
if( m_end.itChunks == m_chunks.end() )
{
bool wasEmpty = m_begin.itChunks == m_chunks.end();
chunk_ptr append = move( m_firstStandby );
if( append )
m_firstStandby = move( append->next );
else
append = make_cl_unique<chunk>();
defer unappend( [&]
{
append->next = move( m_firstStandby );
m_firstStandby = move( append );
} );
size_t iBegin = m_begin.itChunks - m_chunks.begin();
m_chunks.emplace_back( move( append ) );
unappend.disable();
m_begin.itChunks = m_chunks.begin() + iBegin;
m_end.itChunks = m_chunks.end() - 1;
m_end.itChunk = (*m_end.itChunks)->begin();
if( wasEmpty )
m_begin.itChunk = (*m_begin.itChunks)->begin();
}
T &value = m_end.itChunk->emplace( forward<Params>( params ) ... );
unchunk.disable();
if( ++m_end.itChunk == (*m_end.itChunks)->end() )
m_end.itChunks = m_chunks.end();
return value;
}
template<typename T>
void xdeque<T>::pop_front() noexcept
{
if( empty() )
return;
defer shrink( [&] { shrinkChunks(); } );
m_begin.itChunk++->destruct();
auto remove = [this]
{
chunk_ptr firstEmpty = move( *m_begin.itChunks );
firstEmpty->next = move( m_firstStandby );
m_firstStandby = move( firstEmpty );
};
if( m_begin.itChunks != m_end.itChunks )
{
if( m_begin.itChunk != (*m_begin.itChunks)->end() )
return;
remove();
if( ++m_begin.itChunks != m_chunks.end() )
m_begin.itChunk = (*m_begin.itChunks)->begin();
return;
}
if( m_begin.itChunk != m_end.itChunk )
return;
remove();
m_begin.itChunks = m_chunks.end();
m_end.itChunks = m_chunks.end();
}
template<typename T>
std::optional<T> xdeque<T>::pop_back() noexcept
{
using namespace std;
if( empty() )
return nullopt;
defer shrink( [&] { shrinkChunks(); } );
pointer end = m_end;
if( end.itChunks == m_chunks.end() )
{
end.itChunks = m_chunks.end() - 1;
end.itChunk = (*end.itChunks)->end();
}
T value( move( *--end.itChunk ) );
end.itChunk->destruct();
m_end = end;
bool singleChunk = m_end.itChunks == m_begin.itChunks;
if( singleChunk && m_end.itChunk != m_begin.itChunk ||
!singleChunk && m_end.itChunk != (*m_end.itChunks)->begin() )
return value;
chunk_ptr lastEmpty = move( *m_end.itChunks );
lastEmpty->next = move( m_firstStandby );
m_firstStandby = move( lastEmpty );
m_chunks.pop_back();
m_end.itChunks = m_chunks.end();
if( singleChunk )
m_begin.itChunks = m_chunks.end();
return value;
}
template<typename T>
inline T &xdeque<T>::front() noexcept
{
assert(m_begin.itChunks != m_chunks.end());
return *m_begin.itChunk;
}
template<typename T>
inline const T &xdeque<T>::front() const noexcept
{
assert(m_begin.itChunks != m_chunks.end());
return *m_begin.itChunk;
}
template<typename T>
size_t xdeque<T>::size() const noexcept
{
if( m_begin.itChunks == m_chunks.end() )
return 0;
size_t n = (m_end.itChunks - m_begin.itChunks) * N_CHUNK;
if( m_end.itChunks != m_chunks.end() )
n += m_end.itChunk - (*m_end.itChunks)->begin();
n -= m_begin.itChunk - (*m_begin.itChunks)->begin();
return n;
}
template<typename T>
inline bool xdeque<T>::empty() const noexcept
{
return m_begin.itChunks == m_chunks.end();
}
template<typename T>
void xdeque<T>::clear() noexcept
{
if( empty() )
return;
defer shrink( [&] { shrinkChunks(); } );
for( ; ; )
{
chunk_it itChunkEnd;
if( m_begin.itChunks != m_chunks.end() - 1 || m_end.itChunks ==
m_chunks.end() )
itChunkEnd = (*m_begin.itChunks)->end();
else
itChunkEnd = m_end.itChunk;
do
m_begin.itChunk->destruct();
while( ++m_begin.itChunk != itChunkEnd );
chunk_ptr firstEmpty = move( *m_begin.itChunks );
firstEmpty->next = move( m_firstStandby );
m_firstStandby = move( firstEmpty );
if( ++m_begin.itChunks == m_chunks.end() )
{
m_end.itChunks = m_chunks.end();
return;
}
m_begin.itChunk = (*m_begin.itChunks)->begin();
}
}
template<typename T>
inline void xdeque<T>::shrink_to_fit() noexcept
{
m_firstStandby.reset();
}
template<typename T>
template<typename Consumer>
void xdeque<T>::consume( Consumer consumer )
{
using namespace std;
if( m_begin.itChunks == m_chunks.end() )
return;
defer shrink( [&] { shrinkChunks(); } );
int ret = 1;
do
{
size_t nChunk;
if( m_begin.itChunks != m_end.itChunks )
nChunk = (*m_begin.itChunks)->end() - m_begin.itChunk;
else
nChunk = m_end.itChunk - m_begin.itChunk;
do
{
if constexpr( requires() { (int)consumer( move( **m_begin.itChunk )
); } )
ret = (int)consumer( move( **m_begin.itChunk ) );
else
consumer( move( **m_begin.itChunk ) );
if( ret < 0 )
return;
m_begin.itChunk++->destruct();
} while( --nChunk && ret );
if( nChunk )
return;
chunk_ptr emptied = move( *m_begin.itChunks );
emptied->next = move( m_firstStandby );
m_firstStandby = move( emptied );
if( m_begin.itChunks != m_chunks.end() - 1 )
m_begin.itChunk = (*++m_begin.itChunks)->begin();
else
{
m_begin.itChunks = m_chunks.end();
m_end.itChunks = m_chunks.end();
return;
}
} while( ret );
}
template<typename T>
template<typename Consumer>
void xdeque<T>::consume( Consumer consumer ) const
{
const_cast<xdeque<T> &>( *this ).consume( [&]( const T &value ) { return observer( value ); } );
}
#if !defined(NDEBUG)
template
struct xdeque<int>;
#endif
#if defined(__clang__)
#pragma clang diagnostic pop
#endif
--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)