Thrill  0.1
just_sort.cpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * examples/suffix_sorting/just_sort.cpp
3  *
4  * Part of Project Thrill - http://project-thrill.org
5  *
6  * Copyright (C) 2015-2016 Timo Bingmann <[email protected]>
7  *
8  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
9  ******************************************************************************/
10 
11 #include <thrill/api/context.hpp>
13 #include <thrill/common/logger.hpp>
14 #include <thrill/common/qsort.hpp>
15 #include <tlx/cmdline_parser.hpp>
17 
18 #include <algorithm>
19 #include <limits>
20 #include <random>
21 #include <string>
22 #include <tuple>
23 #include <utility>
24 #include <vector>
25 
26 //! A tuple with index (i,t_i,t_{i+1},t_{i+2},...,t_{i+6}).
27 template <typename AlphabetType>
28 struct Chars {
29  AlphabetType ch[7];
30 
31  bool operator == (const Chars& b) const {
32  return std::tie(ch[0], ch[1], ch[2], ch[3], ch[4], ch[5], ch[6])
33  == std::tie(b.ch[0], b.ch[1], b.ch[2], b.ch[3],
34  b.ch[4], b.ch[5], b.ch[6]);
35  }
36 
37  bool operator < (const Chars& b) const {
38  return std::tie(ch[0], ch[1], ch[2], ch[3], ch[4], ch[5], ch[6])
39  < std::tie(b.ch[0], b.ch[1], b.ch[2], b.ch[3],
40  b.ch[4], b.ch[5], b.ch[6]);
41  }
42 
43  friend std::ostream& operator << (std::ostream& os, const Chars& chars) {
44  return os << '[' << chars.ch[0] << ',' << chars.ch[1]
45  << ',' << chars.ch[2] << ',' << chars.ch[3]
46  << ',' << chars.ch[4] << ',' << chars.ch[5]
47  << ',' << chars.ch[6] << ']';
48  }
49 
50  static Chars EndSentinel() {
51  return Chars {
52  {
53  std::numeric_limits<AlphabetType>::lowest(),
54  std::numeric_limits<AlphabetType>::lowest(),
55  std::numeric_limits<AlphabetType>::lowest(),
56  std::numeric_limits<AlphabetType>::lowest(),
57  std::numeric_limits<AlphabetType>::lowest(),
58  std::numeric_limits<AlphabetType>::lowest(),
59  std::numeric_limits<AlphabetType>::lowest()
60  }
61  };
62  }
64 
65 //! A tuple with index (i,t_i,t_{i+1},t_{i+2}).
66 template <typename Index, typename AlphabetType>
67 struct IndexChars {
68  Index index;
69  Chars<AlphabetType> chars;
70 
71  friend std::ostream& operator << (std::ostream& os, const IndexChars& tc) {
72  return os << '[' << tc.index << '|' << tc.chars << ']';
73  }
75 
76 int main(int argc, char* argv[]) {
77 
78  using namespace thrill; // NOLINT
79 
81 
82  cp.set_author("Timo Bingmann <[email protected]>");
83 
84  uint64_t input_size = 50000000;
85  cp.add_bytes('s', "input_size", input_size,
86  "Number of DC7 tuples to sort.");
87 
88  std::string algo = "1";
89  cp.add_string('a', "algo", algo,
90  "select sort algo: '1' pivot, '2' pivots, '3' pivots");
91 
92  if (!cp.process(argc, argv))
93  return -1;
94 
95  using IndexChars = ::IndexChars<uint32_t, uint8_t>;
96  std::vector<IndexChars> input;
97 
98  std::default_random_engine rng_(123456);
99 
100  for (size_t i = 0; i < input_size; ++i) {
101  input.emplace_back(
102  IndexChars {
103  uint8_t(rng_()), {
104  { uint8_t(rng_()), uint8_t(rng_()), uint8_t(rng_()),
105  uint8_t(rng_()), uint8_t(rng_()), uint8_t(rng_()),
106  uint8_t(rng_()) }
107  }
108  });
109  }
110 
111  LOG1 << "Sorting " << input_size << " DC7 tuples, total size = "
112  << tlx::format_iec_units(input_size * sizeof(IndexChars)) << 'B';
113 
114  return Run(
115  [&](Context& ctx) {
116 
117  std::vector<IndexChars> vec = input;
118  auto compare_function_ =
119  [](const IndexChars& a, const IndexChars& b) {
120  return a.chars < b.chars;
121  };
122 
123  ctx.net.Barrier();
124 
125  common::StatsTimerStart sort_time;
126  if (algo == "1")
127  std::sort(vec.begin(), vec.end(), compare_function_);
128  if (algo == "2")
130  vec.begin(), vec.end(), compare_function_);
131  if (algo == "3")
133  vec.begin(), vec.end(), compare_function_);
134  sort_time.Stop();
135 
136  ctx.PrintCollectiveMeanStdev(
137  "sort_time", sort_time.SecondsDouble());
138  });
139 }
140 
141 /******************************************************************************/
void qsort_three_pivots(Iterator left, Iterator right, Compare cmp)
Definition: qsort.hpp:244
#define LOG1
Definition: logger.hpp:28
int Run(const std::function< void(Context &)> &job_startpoint)
Runs the given job startpoint with a Context instance.
Definition: context.cpp:947
void qsort_two_pivots_yaroslavskiy(Iterator lo, Iterator hi, Compare cmp)
Definition: qsort.hpp:186
void add_bytes(char key, const std::string &longkey, uint32_t &dest, const std::string &desc)
struct Chars TLX_ATTRIBUTE_PACKED
std::basic_string< char, std::char_traits< char >, Allocator< char > > string
string with Manager tracking
Definition: allocator.hpp:220
Command line parser which automatically fills variables and prints nice usage messages.
void add_string(char key, const std::string &longkey, std::string &dest, const std::string &desc)
add string option -key, –longkey and store to dest
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.hpp:175
int main(int argc, char *argv[])
Definition: just_sort.cpp:76
bool operator<(const uint_pair &b) const
less-than comparison operator
Definition: uint_types.hpp:187
void set_author(const std::string &author)
Set author of program, will be wrapped.
std::string format_iec_units(uint64_t number, int precision=3)
Format number as something like 1 TiB.
bool process(int argc, const char *const *argv, std::ostream &os)
std::ostream & operator<<(std::ostream &os, const DIABase &d)
make ostream-able.
Definition: dia_base.cpp:449