threads_runqueue.cpp File Reference

#include <cstdlib>
#include "main.h"
#include <Eigen/ThreadPool>

Macros
#define	EIGEN_USE_THREADS

Functions
int	rand_reentrant (unsigned int *s)
void	test_basic_runqueue ()
void	test_empty_runqueue ()
void	test_stress_runqueue ()
	EIGEN_DECLARE_TEST (cxx11_runqueue)

Macro Definition Documentation

EIGEN_USE_THREADS

#define EIGEN_USE_THREADS

Function Documentation

EIGEN_DECLARE_TEST()

EIGEN_DECLARE_TEST

(

cxx11_runqueue

)

                                   {
  CALL_SUBTEST_1(test_basic_runqueue());
  CALL_SUBTEST_2(test_empty_runqueue());
  CALL_SUBTEST_3(test_stress_runqueue());
}

References CALL_SUBTEST_1, CALL_SUBTEST_2, CALL_SUBTEST_3, test_basic_runqueue(), test_empty_runqueue(), and test_stress_runqueue().

rand_reentrant()

int rand_reentrant

(

unsigned int *

s

)

                                    {
#if EIGEN_COMP_MSVC_STRICT
  EIGEN_UNUSED_VARIABLE(s);
  return rand();
#else
  return rand_r(s);
#endif
}

References EIGEN_UNUSED_VARIABLE, and s.

Referenced by test_empty_runqueue().

test_basic_runqueue()

void test_basic_runqueue

(

)

                           {
  RunQueue<int, 4> q;
  // Check empty state.
  VERIFY(q.Empty());
  VERIFY_IS_EQUAL(0u, q.Size());
  VERIFY_IS_EQUAL(0, q.PopFront());
  std::vector<int> stolen;
  VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
  VERIFY_IS_EQUAL(0u, stolen.size());
  // Push one front, pop one front.
  VERIFY_IS_EQUAL(0, q.PushFront(1));
  VERIFY_IS_EQUAL(1u, q.Size());
  VERIFY_IS_EQUAL(1, q.PopFront());
  VERIFY_IS_EQUAL(0u, q.Size());
  // Push front to overflow.
  VERIFY_IS_EQUAL(0, q.PushFront(2));
  VERIFY_IS_EQUAL(1u, q.Size());
  VERIFY_IS_EQUAL(0, q.PushFront(3));
  VERIFY_IS_EQUAL(2u, q.Size());
  VERIFY_IS_EQUAL(0, q.PushFront(4));
  VERIFY_IS_EQUAL(3u, q.Size());
  VERIFY_IS_EQUAL(0, q.PushFront(5));
  VERIFY_IS_EQUAL(4u, q.Size());
  VERIFY_IS_EQUAL(6, q.PushFront(6));
  VERIFY_IS_EQUAL(4u, q.Size());
  VERIFY_IS_EQUAL(5, q.PopFront());
  VERIFY_IS_EQUAL(3u, q.Size());
  VERIFY_IS_EQUAL(4, q.PopFront());
  VERIFY_IS_EQUAL(2u, q.Size());
  VERIFY_IS_EQUAL(3, q.PopFront());
  VERIFY_IS_EQUAL(1u, q.Size());
  VERIFY_IS_EQUAL(2, q.PopFront());
  VERIFY_IS_EQUAL(0u, q.Size());
  VERIFY_IS_EQUAL(0, q.PopFront());
  // Push one back, pop one back.
  VERIFY_IS_EQUAL(0, q.PushBack(7));
  VERIFY_IS_EQUAL(1u, q.Size());
  VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
  VERIFY_IS_EQUAL(1u, stolen.size());
  VERIFY_IS_EQUAL(7, stolen[0]);
  VERIFY_IS_EQUAL(0u, q.Size());
  stolen.clear();
  // Push back to overflow.
  VERIFY_IS_EQUAL(0, q.PushBack(8));
  VERIFY_IS_EQUAL(1u, q.Size());
  VERIFY_IS_EQUAL(0, q.PushBack(9));
  VERIFY_IS_EQUAL(2u, q.Size());
  VERIFY_IS_EQUAL(0, q.PushBack(10));
  VERIFY_IS_EQUAL(3u, q.Size());
  VERIFY_IS_EQUAL(0, q.PushBack(11));
  VERIFY_IS_EQUAL(4u, q.Size());
  VERIFY_IS_EQUAL(12, q.PushBack(12));
  VERIFY_IS_EQUAL(4u, q.Size());
  // Pop back in halves.
  VERIFY_IS_EQUAL(2u, q.PopBackHalf(&stolen));
  VERIFY_IS_EQUAL(2u, stolen.size());
  VERIFY_IS_EQUAL(10, stolen[0]);
  VERIFY_IS_EQUAL(11, stolen[1]);
  VERIFY_IS_EQUAL(2u, q.Size());
  stolen.clear();
  VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
  VERIFY_IS_EQUAL(1u, stolen.size());
  VERIFY_IS_EQUAL(9, stolen[0]);
  VERIFY_IS_EQUAL(1u, q.Size());
  stolen.clear();
  VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
  VERIFY_IS_EQUAL(1u, stolen.size());
  VERIFY_IS_EQUAL(8, stolen[0]);
  stolen.clear();
  VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
  VERIFY_IS_EQUAL(0u, stolen.size());
  // Empty again.
  VERIFY(q.Empty());
  VERIFY_IS_EQUAL(0u, q.Size());
  VERIFY_IS_EQUAL(0, q.PushFront(1));
  VERIFY_IS_EQUAL(0, q.PushFront(2));
  VERIFY_IS_EQUAL(0, q.PushFront(3));
  VERIFY_IS_EQUAL(1, q.PopBack());
  VERIFY_IS_EQUAL(2, q.PopBack());
  VERIFY_IS_EQUAL(3, q.PopBack());
  VERIFY(q.Empty());
  VERIFY_IS_EQUAL(0u, q.Size());
}

References Eigen::numext::q, VERIFY, and VERIFY_IS_EQUAL.

Referenced by EIGEN_DECLARE_TEST().

test_empty_runqueue()

void test_empty_runqueue

(

)

                           {
  RunQueue<int, 4> q;
  q.PushFront(1);
  std::atomic<bool> done(false);
  std::thread mutator([&q, &done]() {
    unsigned rnd = 0;
    std::vector<int> stolen;
    for (int i = 0; i < 1 << 18; i++) {
      if (rand_reentrant(&rnd) % 2)
        VERIFY_IS_EQUAL(0, q.PushFront(1));
      else
        VERIFY_IS_EQUAL(0, q.PushBack(1));
      if (rand_reentrant(&rnd) % 2)
        VERIFY_IS_EQUAL(1, q.PopFront());
      else {
        for (;;) {
          if (q.PopBackHalf(&stolen) == 1) {
            stolen.clear();
            break;
          }
          VERIFY_IS_EQUAL(0u, stolen.size());
        }
      }
    }
    done = true;
  });
  while (!done) {
    VERIFY(!q.Empty());
    int size = q.Size();
    VERIFY_GE(size, 1);
    VERIFY_LE(size, 2);
  }
  VERIFY_IS_EQUAL(1, q.PopFront());
  mutator.join();
}

References i, if(), Eigen::numext::q, rand_reentrant(), and VERIFY_IS_EQUAL.

Referenced by EIGEN_DECLARE_TEST().

test_stress_runqueue()

void test_stress_runqueue

(

)

                            {
  static const int kEvents = 1 << 18;
  RunQueue<int, 8> q;
  std::atomic<int> total(0);
  std::vector<std::unique_ptr<std::thread>> threads;
  threads.emplace_back(new std::thread([&q, &total]() {
    int sum = 0;
    int pushed = 1;
    int popped = 1;
    while (pushed < kEvents || popped < kEvents) {
      if (pushed < kEvents) {
        if (q.PushFront(pushed) == 0) {
          sum += pushed;
          pushed++;
        }
      }
      if (popped < kEvents) {
        int v = q.PopFront();
        if (v != 0) {
          sum -= v;
          popped++;
        }
      }
    }
    total += sum;
  }));
  for (int i = 0; i < 2; i++) {
    threads.emplace_back(new std::thread([&q, &total]() {
      int sum = 0;
      for (int j = 1; j < kEvents; j++) {
        if (q.PushBack(j) == 0) {
          sum += j;
          continue;
        }
        EIGEN_THREAD_YIELD();
        j--;
      }
      total += sum;
    }));
    threads.emplace_back(new std::thread([&q, &total]() {
      int sum = 0;
      std::vector<int> stolen;
      for (int j = 1; j < kEvents;) {
        if (q.PopBackHalf(&stolen) == 0) {
          EIGEN_THREAD_YIELD();
          continue;
        }
        while (stolen.size() && j < kEvents) {
          int v = stolen.back();
          stolen.pop_back();
          VERIFY_IS_NOT_EQUAL(v, 0);
          sum += v;
          j++;
        }
      }
      while (stolen.size()) {
        int v = stolen.back();
        stolen.pop_back();
        VERIFY_IS_NOT_EQUAL(v, 0);
        while ((v = q.PushBack(v)) != 0) EIGEN_THREAD_YIELD();
      }
      total -= sum;
    }));
  }
  for (size_t i = 0; i < threads.size(); i++) threads[i]->join();
  VERIFY(q.Empty());
  VERIFY(total.load() == 0);
}

References EIGEN_THREAD_YIELD, i, j, Eigen::numext::q, v, and VERIFY.

Referenced by EIGEN_DECLARE_TEST().