parallel_quick_sort.cc

#include <algorithm>
#include <chrono>
#include <future>
#include <iostream>
#include <iterator>
#include <random>
#include <thread>

#define unlikely(x) __builtin_expect((x), 0)
#define likely(x) __builtin_expect((x), 1)

static const int kThreshold = 100000;
static const int kVectorSize = 64000000;

struct KeyCmp {
  bool operator() (const int i, const int j) const {
    return i < j;
  }
} key_cmp;

void quick_sort_recursive(int arr[], int start, int end);

// return value only used for async
void quick_sort_recursive(int arr[], int start, int end) {
  if (start >= end) {
    return;
  }
  int mid = arr[end]; int left = start, right = end - 1;
  while (left < right) {
    while (key_cmp(arr[left], mid) && left < right)
      left++;
    while (!key_cmp(arr[right], mid) && left < right)
      right--;
    std::swap(arr[left], arr[right]);
  }
  if (!key_cmp(arr[left], arr[end])) {
    std::swap(arr[left], arr[end]);
  }
  else {
    left++;
  }
  std::future<void> res1, res2;
  bool fleft{false}, fright{false};
  if (likely(left-1-start < kThreshold)) {
    quick_sort_recursive(arr, start, left-1);
  } else {
    fleft = true;
    res1 = std::async(std::launch::async, quick_sort_recursive, arr, start, left-1);
  }
  if (likely(end-left-1 < kThreshold)) {
    quick_sort_recursive(arr, left + 1, end);
  } else {
    fright = true;
    res2 = std::async(std::launch::async, quick_sort_recursive, arr, left+1, end);
  }
  if (unlikely(fleft)) {
    res1.get();
  }
  if (unlikely(fright)) {
    res2.get();
  }
}

void quick_sort(int arr[], int len) {
  quick_sort_recursive(arr, 0, len - 1);
}

void random_generate(std::vector<int> &arr) {
  std::random_device rnd_device;
    // Specify the engine and distribution.
  std::mt19937 mersenne_engine {rnd_device()};  // Generates random integers
  std::uniform_int_distribution<int> dist {1, kVectorSize};

  auto gen = [&dist, &mersenne_engine](){
                 return dist(mersenne_engine);
             };

  std::generate(std::begin(arr), std::end(arr), gen);
}

int main() {
  std::vector<int> arr;
  arr.resize(kVectorSize);
  random_generate(arr);
  /*
  for (auto i: arr) {
    std::cout << i << std::endl;
  }
  */
  auto start = std::chrono::system_clock::now();
  quick_sort(arr.data(), kVectorSize);
  auto end   = std::chrono::system_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
  std::cout << double(duration.count()) * std::chrono::microseconds::period::num / std::chrono::microseconds::period::den << std::endl;
  /*
  for (auto i: arr) {
    std::cout << i << std::endl;
  }
  */
  for (int i = 1; i < arr.size(); i++) {
    if (arr[i] < arr[i-1]) {
      std::cout << "fuck!" << std::endl;
      break;
    }
  }
}