forked from Morwenn/cpp-sort
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbench.cpp
More file actions
109 lines (96 loc) · 3.96 KB
/
Copy pathbench.cpp
File metadata and controls
109 lines (96 loc) · 3.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
#include <cpp-sort/sorters.h>
#include "distributions.h"
#ifdef _WIN32
#include <intrin.h>
#define rdtsc __rdtsc
#else
#ifdef __i586__
static __inline__ unsigned long long rdtsc() {
unsigned long long int x;
__asm__ volatile(".byte 0x0f, 0x31" : "=A" (x));
return x;
}
#elif defined(__x86_64__)
static __inline__ unsigned long long rdtsc(){
unsigned hi, lo;
__asm__ __volatile__("rdtsc" : "=a"(lo), "=d"(hi));
return ((unsigned long long) lo) | (((unsigned long long) hi) << 32);
}
#else
#error no rdtsc implementation
#endif
#endif
template<template<typename...> class Collection, typename T>
using distr_f = void (*)(std::back_insert_iterator<Collection<T>>, std::size_t);
template<template<typename...> class Collection, typename T>
using sort_f = void (*)(Collection<T>&);
// Type of data to sort during the benchmark
using value_t = int;
int main()
{
using namespace std::chrono_literals;
// Always use a steady clock
using clock_type = std::conditional_t<
std::chrono::high_resolution_clock::is_steady,
std::chrono::high_resolution_clock,
std::chrono::steady_clock
>;
std::pair<std::string, distr_f<std::vector, value_t>> distributions[] = {
{ "shuffled", shuffled() },
{ "shuffled_16_values", shuffled_16_values() },
{ "all_equal", all_equal() },
{ "ascending", ascending() },
{ "descending", descending() },
{ "pipe_organ", pipe_organ() },
{ "push_front", push_front() },
{ "push_middle", push_middle() },
{ "ascending_sawtooth", ascending_sawtooth() },
{ "descending_sawtooth", descending_sawtooth() },
{ "alternating", alternating() },
{ "alternating_16_values", alternating_16_values() }
};
std::pair<std::string, sort_f<std::vector, value_t>> sorts[] = {
{ "heap_sort", cppsort::heap_sort },
{ "pdq_sort", cppsort::pdq_sort },
{ "quick_sort", cppsort::quick_sort },
{ "spread_sort", cppsort::spread_sort },
{ "std_sort", cppsort::std_sort },
{ "verge_sort", cppsort::verge_sort }
};
std::size_t sizes[] = { 1'000'000 };
for (auto& distribution: distributions) {
for (auto& sort: sorts) {
for (auto size: sizes) {
std::vector<std::uint64_t> cycles;
auto total_start = clock_type::now();
auto total_end = clock_type::now();
while (std::chrono::duration_cast<std::chrono::seconds>(total_end - total_start) < 5s) {
std::vector<value_t> collection;
distribution.second(std::back_inserter(collection), size);
std::uint64_t start = rdtsc();
sort.second(collection);
std::uint64_t end = rdtsc();
assert(std::is_sorted(std::begin(collection), std::end(collection)));
cycles.push_back(double(end - start) / size + 0.5);
total_end = clock_type::now();
}
std::sort(std::begin(cycles), std::end(cycles));
std::cerr << size << ' ' << distribution.first << ' ' << sort.first
<< ' ' << cycles[cycles.size() / 2] << '\n';
std::cout << size << ' ' << distribution.first << ' ' << sort.first
<< ' ' << cycles[cycles.size() / 2] << '\n';
}
}
}
}