/*
 * Copyright 2017 Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <glog/logging.h>
#include <iostream>
#include <array>
#include <vector>
#include <future>

#include <folly/gen/Base.h>
#include <folly/gen/Parallel.h>
#include <folly/gen/test/Bench.h>


DEFINE_int32(threads,
             std::max(1, (int32_t) sysconf(_SC_NPROCESSORS_CONF) / 2),
             "Num threads.");

using namespace folly::gen;
using std::vector;


constexpr int kFib = 28;  // unit of work
size_t fib(int n) { return n <= 1 ? 1 : fib(n - 1) + fib(n - 2); }

static auto add = [](int a, int b) { return a + b; };
static auto mod7 = [](int i) { return i % 7; };

static auto isPrimeSlow = [](int n) {
  if (n < 2) {
    return false;
  } else if (n > 2) {
    for (int d = 3; d * d <= n; d += 2) {
      if (0 == n % d) {
        return false;
      }
    }
  }
  return true;
};

static auto primes =
    seq(1, 1 << 20) | filter(isPrimeSlow) | as<vector>();

static auto isPrime = [](int n) {
  return from(primes)
         | until([&](int d) { return d * d > n; })
         | filter([&](int d) { return 0 == n % d; })
         | isEmpty;
};

static auto factors = [](int n) {
  return from(primes)
       | until([&](int d) { return d * d > n; })
       | filter([&](int d) { return 0 == n % d; })
       | count;
};

static auto factorsSlow = [](int n) {
  return from(primes)
       | filter([&](int d) { return 0 == n % d; })
       | count;
};

static auto sleepyWork = [](int i) {
  const auto sleepyTime = std::chrono::microseconds(100);
  std::this_thread::sleep_for(sleepyTime);
  return i;
};

static auto sleepAndWork = [](int i) {
  return factorsSlow(i) + sleepyWork(i);
};

std::mutex block;
static auto workAndBlock = [](int i) {
  int r = factorsSlow(i);
  {
    std::lock_guard<std::mutex> lock(block);
    return sleepyWork(i) + r;
  }
};

auto start = 1 << 20;
auto v = seq(start) | take(1 << 20) | as<vector>();
auto small = from(v) | take(1 << 12);
auto medium = from(v) | take(1 << 14);
auto large = from(v) | take(1 << 18);
auto huge = from(v);
auto chunks = chunked(v);

BENCH_GEN(small | map(factorsSlow) | sum);
BENCH_GEN_REL(small | parallel(map(factorsSlow)) | sum);
BENCHMARK_DRAW_LINE();

BENCH_GEN(small | map(factors) | sum);
BENCH_GEN_REL(small | parallel(map(factors)) | sum);
BENCHMARK_DRAW_LINE();

BENCH_GEN(large | map(factors) | sum);
BENCH_GEN_REL(large | parallel(map(factors)) | sum);
BENCHMARK_DRAW_LINE();

auto ch = chunks;
auto cat = concat;
BENCH_GEN(huge | filter(isPrime) | count);
BENCH_GEN_REL(ch | cat | filter(isPrime) | count);
BENCH_GEN_REL(ch | parallel(cat | filter(isPrime)) | count);
BENCH_GEN_REL(ch | parallel(cat | filter(isPrime) | sub(count)) | sum);
BENCHMARK_DRAW_LINE();

BENCH_GEN(small | map(sleepAndWork) | sum);
BENCH_GEN_REL(small | parallel(map(sleepAndWork)) | sum);
BENCHMARK_DRAW_LINE();

const int fibs = 1000;
BENCH_GEN(seq(1, fibs) | map([](int) { return fib(kFib); }) | sum);
BENCH_GEN_REL(seq(1, fibs) |
              parallel(map([](int) { return fib(kFib); }) | sub(sum)) | sum);
BENCH_GEN_REL([] {
  auto threads = seq(1, int(FLAGS_threads))
               | map([](int i) {
                   return std::thread([=] {
                     return range((i + 0) * fibs / FLAGS_threads,
                                  (i + 1) * fibs / FLAGS_threads) |
                            map([](int) { return fib(kFib); }) | sum;
                   });
                 })
               | as<vector>();
  from(threads) | [](std::thread &thread) { thread.join(); };
  return 1;
}());
BENCHMARK_DRAW_LINE();

#if 0
============================================================================
folly/gen/test/ParallelBenchmark.cpp            relative  time/iter  iters/s
============================================================================
small | map(factorsSlow) | sum                                4.59s  217.87m
small | parallel(map(factorsSlow)) | sum        1588.86%   288.88ms     3.46
----------------------------------------------------------------------------
small | map(factors) | sum                                   9.62ms   103.94
small | parallel(map(factors)) | sum              89.15%    10.79ms    92.66
----------------------------------------------------------------------------
large | map(factors) | sum                                 650.52ms     1.54
large | parallel(map(factors)) | sum              53.82%      1.21s  827.41m
----------------------------------------------------------------------------
huge | filter(isPrime) | count                             295.93ms     3.38
ch | cat | filter(isPrime) | count                99.76%   296.64ms     3.37
ch | parallel(cat | filter(isPrime)) | count     142.75%   207.31ms     4.82
ch | parallel(cat | filter(isPrime) | sub(count 1538.50%    19.24ms    51.99
----------------------------------------------------------------------------
small | map(sleepAndWork) | sum                               5.37s  186.18m
small | parallel(map(sleepAndWork)) | sum       1840.38%   291.85ms     3.43
----------------------------------------------------------------------------
seq(1, fibs) | map([](int) { return fib(kFib);                1.49s  669.53m
seq(1, fibs) | parallel(map([](int) { return fi 1698.07%    87.96ms    11.37
[] { auto threads = seq(1, int(FLAGS_threads))  1571.16%    95.06ms    10.52
----------------------------------------------------------------------------
============================================================================
#endif
int main(int argc, char *argv[]) {
  gflags::ParseCommandLineFlags(&argc, &argv, true);
  folly::runBenchmarks();
  return 0;
}
