time_operations.h

#include "sequence.h"
#include "get_time.h"
#include "random.h"
#include "counting_sort.h"
#include "collect_reduce.h"
#include "random_shuffle.h"
//#include "histogram.h"
#include "integer_sort.h"
#include "sample_sort.h"
#include "merge.h"
#include "merge_sort.h"
#include "bag.h"
#include "hash_table.h"
#include "sparse_mat_vec_mult.h"
#include "stlalgs.h"
#include "monoid.h"
#include "range_min.h"

#include <iostream>
#include <ctype.h>
#include <math.h>
#include <assert.h>

static timer bt;
using uchar = unsigned char;

#define time(_var,_body)    \
  bt.start();               \
  _body;		    \
  double _var = bt.stop();

template<typename T>
double t_tabulate(size_t n, bool check) {
  auto f = [] (size_t i) {return i;};
  time(t, pbbs::sequence<T>(n, f););
  return t;
}

template<typename T>
double t_map(size_t n, bool check) {
  pbbs::sequence<T> In(n, (T) 1);
  auto f = [&] (size_t i) {return In[i];};
  time(t, pbbs::sequence<T>(n, f));
  return t;
}

template<typename T>
double t_reduce_add(size_t n, bool check) {
  pbbs::sequence<T> S(n, (T) 1);
  //time(t, sum(S.begin(), S.size()););
  //time(t, pbbs::reduce_add(S););
  time(t, pbbs::reduce(S, pbbs::addm<T>()));
  return t;
}

double t_map_reduce_128(size_t n, bool check) {
  int stride = 16;
  pbbs::sequence<size_t> S(n*stride, (size_t) 1);
  auto get = [&] (size_t i) {
    // gives marginal improvement (5% or so on aware)
    __builtin_prefetch (&S[(i+4)*stride], 0, 3);
    return S[i*stride];};
  auto Sa = pbbs::delayed_seq<size_t>(n, get);
  time(t, pbbs::reduce(Sa.slice(0,n-4), pbbs::addm<size_t>()););
  return t;
}

template<typename T>
double t_scan_add(size_t n, bool check) {
  pbbs::sequence<T> In(n, (T) 1);
  pbbs::sequence<T> Out;
  T sum;
  time(t, std::tie(Out,sum) = pbbs::scan(In, pbbs::addm<T>()););
  return t;
}

template<typename T>
double t_scan_add_seq(size_t n, bool check) {
  pbbs::sequence<T> In(n, (T) 1);
  pbbs::sequence<T> Out(n, (T) 0);
  time(t,
       T x = 0;
       for (size_t i=0; i < n; i++) {
	 Out[i] = x;
	 x += In[i];
       });
  return t;
}

template<typename T>
double t_pack(size_t n, bool check) {
  pbbs::sequence<bool> flags(n, [] (size_t i) -> bool {return i%2;});
  pbbs::sequence<T> In(n, [] (size_t i) -> T {return i;});
  time(t, pbbs::pack(In, flags););
  return t;
}

template<typename T>
double t_split3_old(size_t n, bool check) {
  pbbs::sequence<uchar> flags(n, [] (size_t i) -> uchar {return i%3;});
  pbbs::sequence<T> In(n, [] (size_t i) -> T {return i;});
  pbbs::sequence<T> Out(n, (T) 0);
  time(t, pbbs::split_three(In, Out, flags););
  return t;
}

template<typename T>
double t_split3(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> In(n, [&] (size_t i) {return r.ith_rand(i);});
  pbbs::sequence<T> Out(n, (T) 0);
  time(t, pbbs::p_split3(In, Out.slice(), std::less<T>()););
  return t;
}

template<typename T>
double t_partition(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> In(n, [&] (size_t i) -> size_t {return r.ith_rand(i)%n;});
  pbbs::sequence<T> Out;
  auto f = pbbs::delayed_seq<bool>(n, [&] (size_t i) {return In[i] < n/((size_t) 2);});
  size_t m;
  time(t, std::tie(Out,m) = pbbs::split_two(In, f););
  return t;
}

#if defined(CILK)
#include "reducer.h"
double t_histogram_reducer(size_t n, bool check) {
  pbbs::random r(0);
  constexpr int count = 1024;
  histogram_reducer<int,count> red;
  using aa = std::array<size_t,8>;
  pbbs::sequence<aa> In(n, [&] (size_t i) {aa x; x[0] = r.ith_rand(i) % count; return x;});
  auto f = [&] (size_t i) { red->add_value(In[i][0]);};
  time(t, parallel_for(0, n, f););
  //cout << red.get_value()[0] << endl;
  return t;
}
#else
double t_histogram_reducer(size_t n, bool check) {
  return 1.0;
}
#endif

template<typename T>
double t_gather(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> in(n, [&] (size_t i) {return i;});
  pbbs::sequence<T> idx(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  auto f = [&] (size_t i) {
    // prefetching helps significantly
    __builtin_prefetch (&in[idx[i+4]], 0, 1);
    return in[idx[i]];};
  // note problem with prefetching since will go over end for last 4 iterations
  if (n < 4) return 0.0;
  time(t, pbbs::sequence<T>(n-4, f););  
  return t;
}

template<typename T>
double t_scatter(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> out(n, (T) 0);
  pbbs::sequence<T> idx(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  auto f = [&] (size_t i) {
    // prefetching makes little if any difference
    //__builtin_prefetch (&out[idx[i+4]], 1, 1);
      out[idx[i]] = i;};
  if (n < 4) return 0.0;
  time(t, parallel_for(0, n-4, f););
  return t;
}

template<typename T>
double t_write_add(size_t n, bool check) {
  pbbs::random r(0);
  //pbbs::sequence<T> out(n, (T) 0);
  pbbs::sequence<std::atomic<T>> out(n);
  parallel_for(0,n,[&] (size_t i) {std::atomic_init(&out[i], (T) 0);});
  pbbs::sequence<T> idx(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  auto f = [&] (size_t i) {
    // putting write prefetch in slows it down
    //__builtin_prefetch (&out[idx[i+4]], 0, 1);
    //__sync_fetch_and_add(&out[idx[i]],1);};
    pbbs::write_add(&out[idx[i]],1);};
  if (n < 4) return 0.0;
  time(t, parallel_for(0, n-4, f););
  return t;
}

template<typename T>
double t_write_min(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<std::atomic<T>> out(n);
  parallel_for(0,n,[&] (size_t i) {std::atomic_init(&out[i], (T) n);});
  //pbbs::sequence<T> out(n, (T) n);
  pbbs::sequence<T> idx(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  auto f = [&] (size_t i) {
    // putting write prefetch in slows it down
    //__builtin_prefetch (&out[idx[i+4]], 1, 1);
    pbbs::write_min(&out[idx[i]], (T) i, std::less<T>());};
  if (n < 4) return 0.0;
  time(t, parallel_for(0, n-4, f););
  return t;
}

template<typename T>
double t_shuffle(size_t n, bool check) {
  pbbs::sequence<T> in(n, [&] (size_t i) {return i;});
  time(t, pbbs::random_shuffle(in, n););
  return t;
}

template<typename T>
bool check_histogram(pbbs::sequence<T> const &in, pbbs::sequence<T> const &out) {
  size_t m = out.size();
  auto a = sort(in, std::less<T>());
  auto b = get_counts(a, [&] (T a) {return a;}, m);
  size_t err_loc = pbbs::find_if_index(m, [&] (size_t i) {return out[i] != b[i];});
  if (err_loc != m) {
    cout << "ERROR in histogram at location "
	 << err_loc << ", got " << out[err_loc] << ", expected " << b[err_loc] << endl;
    return false;
  }
  return true;
}

template<typename T>
double t_histogram(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> in(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  pbbs::sequence<T> out;
  //auto get_key = [&] (T a) {return a;};
  //auto get_val = [&] (T a) {return (T) 1;};
  //time(t, out = pbbs::collect_reduce(in, get_key, get_val, pbbs::addm<T>(), n););
  time(t, out = pbbs::histogram(in, (T) n););
  if (check) check_histogram(in, out);
  return t;
}

template<typename T>
double t_histogram_few(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> in(n, [&] (size_t i) {return r.ith_rand(i)%256;});
  pbbs::sequence<T> out;
  //auto get_key = [&] (T a) {return a;};
  //auto get_val = [&] (T a) {return (T) 1;};
  //time(t, out = pbbs::collect_reduce(in, get_key, get_val, pbbs::addm<T>(), 256););
  time(t, out = pbbs::histogram(in, (T) 256););
  if (check) check_histogram(in, out);
  return t;
}

template<typename T>
double t_histogram_same(size_t n, bool check) {
  pbbs::sequence<T> in(n, (T) 10311);
  pbbs::sequence<T> out;
  //auto get_key = [&] (T a) {return a;};
  //auto get_val = [&] (T a) {return (T) 1;};
  //time(t, out = pbbs::collect_reduce(in, get_key, get_val, pbbs::addm<T>(), n););
  time(t, out = pbbs::histogram(in, (T) n););
  if (check) check_histogram(in, out);
  return t;
}

// this checks against a given sort
template<typename T, typename Cmp>
bool check_sort(pbbs::sequence<T> const &in, pbbs::sequence<T> const &out,
		Cmp less, std::string sort_name) {
  size_t n = in.size();
  auto a = pbbs::merge_sort(in, std::less<T>());
  size_t err_loc = pbbs::find_if_index(n, [&] (size_t i) {
      return less(a[i],out[i]) || less(out[i],a[i]);});
  if (err_loc != n) {
    cout << "ERROR in " << sort_name << " at location " << err_loc << endl;
    return false;
  }
  return true;
}

template<typename T>
double t_sort(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> in(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  pbbs::sequence<T> out;
  time(t, out = pbbs::sample_sort(in, std::less<T>()););
  if (check) check_sort(in, out, std::less<T>(), "sample sort");
  return t;
}

// no check since it is used for the sort for checking, and hence
// checked against the other sorts
template<typename T>
double t_merge_sort(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> in(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  pbbs::sequence<T> out;
  time(t, pbbs::merge_sort_inplace(in.slice(), std::less<T>()););
  return t;
}

template<typename T>
double t_quicksort(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> in(n, [&] (size_t i) {return r.ith_rand(i)%n;});
  pbbs::sequence<T> copy;
  if (check) copy = in;
  time(t, pbbs::p_quicksort_inplace(in.slice(), std::less<T>()););
  if (check) check_sort(copy, in, std::less<T>(), "quicksort");
  return t;
}

template<typename T>
double t_count_sort_bits(size_t n, size_t bits) {
  pbbs::random r(0);
  size_t num_buckets = (1<<bits);
  size_t mask = num_buckets - 1;
  pbbs::sequence<T> in(n, [&] (size_t i) {return r.ith_rand(i);});
  pbbs::sequence<T> out(n);
  auto f = [&] (size_t i) {return in[i] & mask;};
  auto keys = pbbs::delayed_seq<unsigned char>(n, f);
  time(t, pbbs::count_sort(in, out.slice(), keys, num_buckets););
  for (size_t i=1; i < n; i++) {
    if ((out[i-1] & mask) > (out[i] & mask)) {
      cout << "ERROR in count sort at: " << i << endl;
      abort();
    }
  }
  return t;
}

template<typename T>
double t_count_sort_8(size_t n, bool check) {return t_count_sort_bits<T>(n, 8);}

template<typename T>
double t_count_sort_2(size_t n, bool check) {return t_count_sort_bits<T>(n, 2);}

template<typename T>
double t_collect_reduce_pair_dense(size_t n, bool check) {
  using par = std::pair<T,T>;
  pbbs::random r(0);
  pbbs::sequence<par> S(n, [&] (size_t i) -> par {
      return par(r.ith_rand(i) % n, 1);});
  pbbs::sequence<T> out;
  auto get_key = [&] (par a) {return a.first;};
  auto get_val = [&] (par a) {return a.second;};
  time(t, out = pbbs::collect_reduce(S, get_key, get_val, pbbs::addm<T>(), n););
  if (check)
    check_histogram(pbbs::sequence<T>(n, [&] (size_t i) {return S[i].first;}),
		    out);
  return t;
}

template<typename T>
double t_collect_reduce_pair_sparse(size_t n, bool check) {
  using par = std::pair<T,T>;
  pbbs::random r(0);
  struct hasheq {
    static inline size_t hash(par a) {return pbbs::hash64_2(a.first);}
    static inline bool eql(par a, par b) {return a.first == b.first;}
  };
  pbbs::sequence<par> S(n, [&] (size_t i) -> par {
      return par(r.ith_rand(i) % n, 1);});
  time(t, pbbs::collect_reduce_sparse(S, hasheq(), pbbs::addm<T>()););
  return t;
}

template<typename T>
double t_collect_reduce_8(size_t n, bool check) {
  using par = std::pair<T,T>;
  pbbs::random r(0);
  size_t num_buckets = (1<<8);
  pbbs::sequence<par> S(n, [&] (size_t i) {
      return par(r.ith_rand(i) % num_buckets, 1);});
  auto get_key = [&] (par a) {return a.first;};
  auto get_val = [&] (par a) {return a.first;};
  time(t, pbbs::collect_reduce(S, get_key, get_val, pbbs::addm<T>(), num_buckets););
  return t;
}

// template<typename T>
// double t_collect_reduce_8_tuple(size_t n, bool check) {
//   pbbs::random r(0);
//   size_t num_buckets = (1<<8);
//   size_t mask = num_buckets - 1;
//   using sums = std::tuple<float,float,float,float>;

//   auto bucket = [&] (size_t i) -> uchar { return r.ith_rand(i) & mask; };
//   auto keys = pbbs::delayed_seq<unsigned char>(n, bucket);

//   auto sum = [] (sums a, sums b) -> sums {
//     return sums(std::get<0>(a)+std::get<0>(b), std::get<1>(a)+std::get<1>(b),
// 		std::get<2>(a)+std::get<2>(b), std::get<3>(a)+std::get<3>(b));
//   };

//   pbbs::sequence<sums> in(n, [&] (size_t i) -> sums {
//       return sums(1.0,1.0,1.0,1.0);});

//   auto monoid = make_monoid(sum, sums(0.0,0.0,0.0,0.0));

//   time(t,
//        pbbs::collect_reduce<sums>(in, keys, num_buckets, monoid););
//   return t;
// }


template<typename T>
double t_integer_sort_pair(size_t n, bool check) {
  using par = std::pair<T,T>;
  pbbs::random r(0);
  size_t bits = sizeof(T)*8;
  pbbs::sequence<par> S(n, [&] (size_t i) -> par {
      return par(r.ith_rand(i),i);});
  pbbs::sequence<par> R;
  auto first = [] (par a) {return a.first;};
  time(t, R = pbbs::integer_sort(S.slice(),first,bits););

  auto less = [] (par a, par b) {return a.first < b.first;};
  if (check) check_sort(S, R, less, "integer sort pair");
  return t;
}

template<typename T>
double t_integer_sort(size_t n, bool check) {
  pbbs::random r(0);
  size_t bits = sizeof(T)*8;
  pbbs::sequence<T> S(n, [&] (size_t i) -> T {
      return r.ith_rand(i);});
  auto identity = [] (T a) {return a;};
  pbbs::sequence<T> R;
  //time(t, pbbs::integer_sort_inplace(S.slice(),identity,bits););
  time(t, R = pbbs::integer_sort(S, identity, bits););
  if (check) check_sort(S, R, std::less<T>(), "integer sort");
  return t;
}

typedef unsigned __int128 long_int;
double t_integer_sort_128(size_t n, bool check) {
  pbbs::random r(0);
  size_t bits = pbbs::log2_up(n);
  pbbs::sequence<long_int> S(n, [&] (size_t i) -> long_int {
      return r.ith_rand(2*i) + (((long_int) r.ith_rand(2*i+1)) << 64) ;});
  auto identity = [] (long_int a) {return a;};
  pbbs::sequence<long_int> out;
  time(t, out = pbbs::integer_sort(S.slice(),identity,bits););
  return t;
}

template<typename T>
double t_merge(size_t n, bool check) {
  pbbs::sequence<T> in1(n/2, [&] (size_t i) {return 2*i;});
  pbbs::sequence<T> in2(n-n/2, [&] (size_t i) {return 2*i+1;});
  pbbs::sequence<T> out;
  time(t, out = pbbs::merge(in1, in2, std::less<T>()););
  return t;
}

template<typename T>
double t_remove_duplicates(size_t n, bool check) {
  pbbs::random r(0);
  pbbs::sequence<T> In(n, [&] (size_t i) -> T {return r.ith_rand(i) % n;});
  time(t, pbbs::remove_duplicates(In););
  return t;
}

template <typename T, typename F>
static T my_reduce(pbbs::sequence<T> const &s, size_t start, size_t end, F f) {
  if (end - start == 1) return s[start];
  size_t h = (end + start)/2;
  T r, l;
  auto left = [&] () {r = my_reduce(s, h, end, f);};
  auto right = [&] () {l = my_reduce(s, start, h, f);};
  par_do_if(h > 100, left, right);
  return f(l,r);
}

template<typename T>
double t_bag(size_t n, bool check) {
  using TB = pbbs::bag<T>;
  TB::init();
  pbbs::sequence<TB> In(n, [&] (size_t i) -> TB {return TB((T) i);});
  time(t, TB x = my_reduce(In, 0, n, TB::append); x.flatten(););
  return t;
}

template<typename s_size_t, typename T>
double t_mat_vec_mult(size_t n, bool check) {
  pbbs::random r(0);
  size_t degree = 5;
  size_t m = degree*n;
  pbbs::sequence<s_size_t> starts(n+1, [&] (size_t i) {
      return degree*i;});
  pbbs::sequence<s_size_t> columns(m, [&] (size_t i) {
      return r.ith_rand(i)%n;});
  pbbs::sequence<T> values(m, (T) 1);
  pbbs::sequence<T> in(n, (T) 1);
  pbbs::sequence<T> out(n, (T) 0);
  auto add = [] (T a, T b) { return a + b;};
  auto mult = [] (T a, T b) { return a * b;};

  time(t, mat_vec_mult(starts, columns, values, in, out.slice(), mult, add););
  return t;
}

template<typename T>
double t_range_min(size_t n, bool check) {
  pbbs::sequence<T> In(n, [&] (size_t i) {return 5;});
  In[n/2] = 0;
  time(t,
       auto foo = pbbs::make_range_min(In, std::less<T>());
       parallel_for(0, n-1, [&] (size_t i) {foo.query(0,i);}););
  if (foo.query(0,n-1) != n/2 || foo.query(0,n/2-1) != 0 ||
      foo.query(0,n/2) != n/2 || foo.query(n/2+1, n-1) != n/2+1) {
    cout << "error in range min query " << endl;
    abort();
  }
  return t;
}

template<typename T>
double t_find_mid(size_t n, bool check) {
  pbbs::sequence<T> In(n, [&] (size_t i) {return 0;});
  In[n/2] = 1;
  size_t idx;
  time(t, idx = pbbs::find(In, 1););
  if (check)
    if (idx != n/2)
      cout << "error in find " << endl;
  return t;
}

template<typename T>
double t_lexicograhic_compare(size_t n, bool check) {
  pbbs::sequence<T> In1(n, [&] (size_t i) {return 0;});
  pbbs::sequence<T> In2(n, [&] (size_t i) {return 0;});
  In1[n/2] = 1;
  bool ls;
  time(t, ls = pbbs::lexicographical_compare(In1, In2, std::less<T>()););
  if (check)
    if (ls)
      cout << "error in lexicographical_compare " << endl;
  return t;
}