#include <RunQueue.h>

Classes
struct	Elem

Public Member Functions
	RunQueue ()

	~RunQueue ()

Work	PushFront (Work w)

Work	PopFront ()

Work	PushBack (Work w)

Work	PopBack ()

unsigned	PopBackHalf (std::vector< Work > *result)

unsigned	Size () const

bool	Empty () const

void	Flush ()

Private Types
enum	State { kEmpty , kBusy , kReady }

Private Member Functions
template<bool NeedSizeEstimate>
unsigned	SizeOrNotEmpty () const

EIGEN_ALWAYS_INLINE unsigned	CalculateSize (unsigned front, unsigned back) const

	RunQueue (const RunQueue &)=delete

void	operator= (const RunQueue &)=delete

Private Attributes
EIGEN_ALIGN_TO_AVOID_FALSE_SHARING std::atomic< unsigned >	front_

EIGEN_ALIGN_TO_AVOID_FALSE_SHARING std::atomic< unsigned >	back_

EIGEN_MUTEX	mutex_

EIGEN_ALIGN_TO_AVOID_FALSE_SHARING Elem	array_ [kSize]

Static Private Attributes
static const unsigned	kMask = kSize - 1

static const unsigned	kMask2 = (kSize << 1) - 1

Member Enumeration Documentation

◆ State

template<typename Work , unsigned kSize>

enum Eigen::RunQueue::State

private

Enumerator
kEmpty
kBusy
kReady

              {
     kEmpty,
     kBusy,
     kReady,
   };

Constructor & Destructor Documentation

◆ RunQueue() [1/2]

template<typename Work , unsigned kSize>

Eigen::RunQueue< Work, kSize >::RunQueue ( )

inline

              : front_(0), back_(0) {
     // require power-of-two for fast masking
     eigen_plain_assert((kSize & (kSize - 1)) == 0);
     eigen_plain_assert(kSize > 2);            // why would you do this?
     eigen_plain_assert(kSize <= (64 << 10));  // leave enough space for counter
     for (unsigned i = 0; i < kSize; i++) array_[i].state.store(kEmpty, std::memory_order_relaxed);
   }

References Eigen::RunQueue< Work, kSize >::array_, eigen_plain_assert, i, and Eigen::RunQueue< Work, kSize >::kEmpty.

◆ ~RunQueue()

template<typename Work , unsigned kSize>

Eigen::RunQueue< Work, kSize >::~RunQueue ( )

inline

51 { eigen_plain_assert(Size() == 0); }

Eigen::RunQueue::Size

unsigned Size() const

Definition: RunQueue.h:141

References eigen_plain_assert, and Eigen::RunQueue< Work, kSize >::Size().

◆ RunQueue() [2/2]

template<typename Work , unsigned kSize>

Eigen::RunQueue< Work, kSize >::RunQueue ( const RunQueue< Work, kSize > & )

privatedelete

Member Function Documentation

◆ CalculateSize()

template<typename Work , unsigned kSize>

EIGEN_ALWAYS_INLINE unsigned Eigen::RunQueue< Work, kSize >::CalculateSize	(	unsigned	front,
		unsigned	back
	)		const

inlineprivate

                                                                                   {
     int size = (front & kMask2) - (back & kMask2);
     // Fix overflow.
     if (EIGEN_PREDICT_FALSE(size < 0)) size += 2 * kSize;
     // Order of modification in push/pop is crafted to make the queue look
     // larger than it is during concurrent modifications. E.g. push can
     // increment size before the corresponding pop has decremented it.
     // So the computed size can be up to kSize + 1, fix it.
     if (EIGEN_PREDICT_FALSE(size > static_cast<int>(kSize))) size = kSize;
     return static_cast<unsigned>(size);
   }

References EIGEN_PREDICT_FALSE, Eigen::RunQueue< Work, kSize >::kMask2, and size.

Referenced by Eigen::RunQueue< Work, kSize >::SizeOrNotEmpty().

◆ Empty()

template<typename Work , unsigned kSize>

bool Eigen::RunQueue< Work, kSize >::Empty ( ) const

inline

145 { return SizeOrNotEmpty<false>() == 0; }

Referenced by Eigen::RunQueue< Work, kSize >::Flush(), Eigen::RunQueue< Work, kSize >::PopBack(), and Eigen::RunQueue< Work, kSize >::PopBackHalf().

◆ Flush()

template<typename Work , unsigned kSize>

void Eigen::RunQueue< Work, kSize >::Flush ( )

inline

                {
     while (!Empty()) {
       PopFront();
     }
   }

References Eigen::RunQueue< Work, kSize >::Empty(), and Eigen::RunQueue< Work, kSize >::PopFront().

◆ operator=()

template<typename Work , unsigned kSize>

void Eigen::RunQueue< Work, kSize >::operator= ( const RunQueue< Work, kSize > & )

privatedelete

◆ PopBack()

template<typename Work , unsigned kSize>

Work Eigen::RunQueue< Work, kSize >::PopBack ( )

inline

                  {
     if (Empty()) return Work();
     EIGEN_MUTEX_LOCK lock(mutex_);
     unsigned back = back_.load(std::memory_order_relaxed);
     Elem* e = &array_[back & kMask];
     uint8_t s = e->state.load(std::memory_order_relaxed);
     if (s != kReady || !e->state.compare_exchange_strong(s, kBusy, std::memory_order_acquire)) return Work();
     Work w = std::move(e->w);
     e->state.store(kEmpty, std::memory_order_release);
     back_.store(back + 1 + (kSize << 1), std::memory_order_relaxed);
     return w;
   }

References Eigen::RunQueue< Work, kSize >::array_, Eigen::RunQueue< Work, kSize >::back_, e(), Eigen::RunQueue< Work, kSize >::Empty(), Eigen::RunQueue< Work, kSize >::kBusy, Eigen::RunQueue< Work, kSize >::kEmpty, Eigen::RunQueue< Work, kSize >::kMask, Eigen::RunQueue< Work, kSize >::kReady, Eigen::RunQueue< Work, kSize >::mutex_, s, and w.

◆ PopBackHalf()

template<typename Work , unsigned kSize>

unsigned Eigen::RunQueue< Work, kSize >::PopBackHalf ( std::vector< Work > * result )

inline

                                                 {
     if (Empty()) return 0;
     EIGEN_MUTEX_LOCK lock(mutex_);
     unsigned back = back_.load(std::memory_order_relaxed);
     unsigned size = Size();
     unsigned mid = back;
     if (size > 1) mid = back + (size - 1) / 2;
     unsigned n = 0;
     unsigned start = 0;
     for (; static_cast<int>(mid - back) >= 0; mid--) {
       Elem* e = &array_[mid & kMask];
       uint8_t s = e->state.load(std::memory_order_relaxed);
       if (n == 0) {
         if (s != kReady || !e->state.compare_exchange_strong(s, kBusy, std::memory_order_acquire)) continue;
         start = mid;
       } else {
         // Note: no need to store temporal kBusy, we exclusively own these
         // elements.
         eigen_plain_assert(s == kReady);
       }
       result->push_back(std::move(e->w));
       e->state.store(kEmpty, std::memory_order_release);
       n++;
     }
     if (n != 0) back_.store(start + 1 + (kSize << 1), std::memory_order_relaxed);
     return n;
   }

References Eigen::RunQueue< Work, kSize >::array_, Eigen::RunQueue< Work, kSize >::back_, e(), eigen_plain_assert, Eigen::RunQueue< Work, kSize >::Empty(), Eigen::RunQueue< Work, kSize >::kBusy, Eigen::RunQueue< Work, kSize >::kEmpty, Eigen::RunQueue< Work, kSize >::kMask, Eigen::RunQueue< Work, kSize >::kReady, Eigen::RunQueue< Work, kSize >::mutex_, n, s, size, Eigen::RunQueue< Work, kSize >::Size(), and oomph::CumulativeTimings::start().

◆ PopFront()

template<typename Work , unsigned kSize>

Work Eigen::RunQueue< Work, kSize >::PopFront ( )

inline

                   {
     unsigned front = front_.load(std::memory_order_relaxed);
     Elem* e = &array_[(front - 1) & kMask];
     uint8_t s = e->state.load(std::memory_order_relaxed);
     if (s != kReady || !e->state.compare_exchange_strong(s, kBusy, std::memory_order_acquire)) return Work();
     Work w = std::move(e->w);
     e->state.store(kEmpty, std::memory_order_release);
     front = ((front - 1) & kMask2) | (front & ~kMask2);
     front_.store(front, std::memory_order_relaxed);
     return w;
   }

References Eigen::RunQueue< Work, kSize >::array_, e(), Eigen::RunQueue< Work, kSize >::front_, Eigen::RunQueue< Work, kSize >::kBusy, Eigen::RunQueue< Work, kSize >::kEmpty, Eigen::RunQueue< Work, kSize >::kMask, Eigen::RunQueue< Work, kSize >::kMask2, Eigen::RunQueue< Work, kSize >::kReady, s, and w.

Referenced by Eigen::RunQueue< Work, kSize >::Flush().

◆ PushBack()

template<typename Work , unsigned kSize>

Work Eigen::RunQueue< Work, kSize >::PushBack ( Work w )

inline

                         {
     EIGEN_MUTEX_LOCK lock(mutex_);
     unsigned back = back_.load(std::memory_order_relaxed);
     Elem* e = &array_[(back - 1) & kMask];
     uint8_t s = e->state.load(std::memory_order_relaxed);
     if (s != kEmpty || !e->state.compare_exchange_strong(s, kBusy, std::memory_order_acquire)) return w;
     back = ((back - 1) & kMask2) | (back & ~kMask2);
     back_.store(back, std::memory_order_relaxed);
     e->w = std::move(w);
     e->state.store(kReady, std::memory_order_release);
     return Work();
   }

References Eigen::RunQueue< Work, kSize >::array_, Eigen::RunQueue< Work, kSize >::back_, e(), Eigen::RunQueue< Work, kSize >::kBusy, Eigen::RunQueue< Work, kSize >::kEmpty, Eigen::RunQueue< Work, kSize >::kMask, Eigen::RunQueue< Work, kSize >::kMask2, Eigen::RunQueue< Work, kSize >::kReady, Eigen::RunQueue< Work, kSize >::mutex_, s, and w.

◆ PushFront()

template<typename Work , unsigned kSize>

Work Eigen::RunQueue< Work, kSize >::PushFront ( Work w )

inline

                          {
     unsigned front = front_.load(std::memory_order_relaxed);
     Elem* e = &array_[front & kMask];
     uint8_t s = e->state.load(std::memory_order_relaxed);
     if (s != kEmpty || !e->state.compare_exchange_strong(s, kBusy, std::memory_order_acquire)) return w;
     front_.store(front + 1 + (kSize << 1), std::memory_order_relaxed);
     e->w = std::move(w);
     e->state.store(kReady, std::memory_order_release);
     return Work();
   }

References Eigen::RunQueue< Work, kSize >::array_, e(), Eigen::RunQueue< Work, kSize >::front_, Eigen::RunQueue< Work, kSize >::kBusy, Eigen::RunQueue< Work, kSize >::kEmpty, Eigen::RunQueue< Work, kSize >::kMask, Eigen::RunQueue< Work, kSize >::kReady, s, and w.

◆ Size()

template<typename Work , unsigned kSize>

unsigned Eigen::RunQueue< Work, kSize >::Size ( ) const

inline

141 { return SizeOrNotEmpty<true>(); }

Referenced by Eigen::RunQueue< Work, kSize >::PopBackHalf(), and Eigen::RunQueue< Work, kSize >::~RunQueue().

◆ SizeOrNotEmpty()

template<typename Work , unsigned kSize>

template<bool NeedSizeEstimate>

unsigned Eigen::RunQueue< Work, kSize >::SizeOrNotEmpty ( ) const

inlineprivate

                                   {
     // Emptiness plays critical role in thread pool blocking. So we go to great
     // effort to not produce false positives (claim non-empty queue as empty).
     unsigned front = front_.load(std::memory_order_acquire);
     for (;;) {
       // Capture a consistent snapshot of front/tail.
       unsigned back = back_.load(std::memory_order_acquire);
       unsigned front1 = front_.load(std::memory_order_relaxed);
       if (front != front1) {
         front = front1;
         std::atomic_thread_fence(std::memory_order_acquire);
         continue;
       }
       if (NeedSizeEstimate) {
         return CalculateSize(front, back);
       } else {
         // This value will be 0 if the queue is empty, and undefined otherwise.
         unsigned maybe_zero = ((front ^ back) & kMask2);
         // Queue size estimate must agree with maybe zero check on the queue
         // empty/non-empty state.
         eigen_assert((CalculateSize(front, back) == 0) == (maybe_zero == 0));
         return maybe_zero;
       }
     }
   }