Eigen::RunQueue< Work, kSize > Class Template Reference

Classes
struct	Elem

Public Member Functions
bool	Empty () const
void	Flush ()
Work	PopBack ()
unsigned	PopBackHalf (std::vector< Work > *result)
Work	PopFront ()
Work	PushBack (Work w)
Work	PushFront (Work w)
	RunQueue ()
unsigned	Size () const
	~RunQueue ()

Private Types
enum	{   kEmpty ,   kBusy ,   kReady }

Private Member Functions
EIGEN_ALWAYS_INLINE unsigned	CalculateSize (unsigned front, unsigned back) const
void	operator= (const RunQueue &)=delete
	RunQueue (const RunQueue &)=delete
template<bool NeedSizeEstimate>
unsigned	SizeOrNotEmpty () const

Private Attributes
Elem	array_ [kSize]
std::atomic< unsigned >	back_
std::atomic< unsigned >	front_
EIGEN_MUTEX	mutex_

Static Private Attributes
static const unsigned	kMask
static const unsigned	kMask2

Detailed Description

template<typename Work, unsigned kSize>
class Eigen::RunQueue< Work, kSize >

Definition at line 40 of file RunQueue.h.

Member Enumeration Documentation

anonymous enum

template<typename Work , unsigned kSize>

anonymous enum

private

Enumerator
kEmpty
kBusy
kReady

Definition at line 172 of file RunQueue.h.

       {
    kEmpty,
    kBusy,
    kReady,
  };

Constructor & Destructor Documentation

RunQueue() [1/2]

template<typename Work , unsigned kSize>

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

inline

Definition at line 42 of file RunQueue.h.

             : 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);
  }

~RunQueue()

template<typename Work , unsigned kSize>

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

inline

Definition at line 51 of file RunQueue.h.

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

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

Definition at line 220 of file RunQueue.h.

                                                              {
    int size = (front & kMask2) - (back & kMask2);
    // Fix overflow.
    if (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 (size > static_cast<int>(kSize)) size = kSize;
    return static_cast<unsigned>(size);
  }

Empty()

template<typename Work , unsigned kSize>

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

inline

Definition at line 156 of file RunQueue.h.

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

Flush()

template<typename Work , unsigned kSize>

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

inline

Definition at line 159 of file RunQueue.h.

               {
    while (!Empty()) {
      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

Definition at line 102 of file RunQueue.h.

                 {
    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;
  }

PopBackHalf()

template<typename Work , unsigned kSize>

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

inline

Definition at line 119 of file RunQueue.h.

                                                {
    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;
  }

PopFront()

template<typename Work , unsigned kSize>

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

inline

Definition at line 70 of file RunQueue.h.

                  {
    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;
  }

PushBack()

template<typename Work , unsigned kSize>

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

inline

Definition at line 86 of file RunQueue.h.

                        {
    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();
  }

PushFront()

template<typename Work , unsigned kSize>

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

inline

Definition at line 55 of file RunQueue.h.

                         {
    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();
  }

Size()

template<typename Work , unsigned kSize>

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

inline

Definition at line 152 of file RunQueue.h.

{ return SizeOrNotEmpty<true>(); }

SizeOrNotEmpty()

template<typename Work , unsigned kSize>

template<bool NeedSizeEstimate>

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

inlineprivate

Definition at line 193 of file RunQueue.h.

                                  {
    // 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;
      }
    }
  }

Member Data Documentation

array_

template<typename Work , unsigned kSize>

Elem Eigen::RunQueue< Work, kSize >::array_[kSize]

private

Definition at line 187 of file RunQueue.h.

back_

template<typename Work , unsigned kSize>

std::atomic<unsigned> Eigen::RunQueue< Work, kSize >::back_

private

Definition at line 186 of file RunQueue.h.

front_

template<typename Work , unsigned kSize>

std::atomic<unsigned> Eigen::RunQueue< Work, kSize >::front_

private

Definition at line 185 of file RunQueue.h.

kMask

template<typename Work , unsigned kSize>

const unsigned Eigen::RunQueue< Work, kSize >::kMask

staticprivate

Definition at line 166 of file RunQueue.h.

kMask2

template<typename Work , unsigned kSize>

const unsigned Eigen::RunQueue< Work, kSize >::kMask2

staticprivate

Definition at line 167 of file RunQueue.h.

mutex_

template<typename Work , unsigned kSize>

EIGEN_MUTEX Eigen::RunQueue< Work, kSize >::mutex_

private

Definition at line 177 of file RunQueue.h.

---

The documentation for this class was generated from the following file:

• RunQueue.h