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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
// Copyright 2021 Google LLC
// SPDX-License-Identifier: Apache-2.0
//
// 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 "hwy/contrib/sort/algo-inl.h"
// Normal include guard for non-SIMD parts
#ifndef HIGHWAY_HWY_CONTRIB_SORT_RESULT_INL_H_
#define HIGHWAY_HWY_CONTRIB_SORT_RESULT_INL_H_
#include <time.h>
#include <algorithm> // std::sort
#include <string>
#include "hwy/base.h"
#include "hwy/nanobenchmark.h"
namespace hwy {
struct Timestamp {
Timestamp() { t = platform::Now(); }
double t;
};
static inline double SecondsSince(const Timestamp& t0) {
const Timestamp t1;
return t1.t - t0.t;
}
// Returns trimmed mean (we don't want to run an out-of-L3-cache sort often
// enough for the mode to be reliable).
static inline double SummarizeMeasurements(std::vector<double>& seconds) {
std::sort(seconds.begin(), seconds.end());
double sum = 0;
int count = 0;
const size_t num = seconds.size();
for (size_t i = num / 4; i < num / 2; ++i) {
sum += seconds[i];
count += 1;
}
return sum / count;
}
} // namespace hwy
#endif // HIGHWAY_HWY_CONTRIB_SORT_RESULT_INL_H_
// Per-target
#if defined(HIGHWAY_HWY_CONTRIB_SORT_RESULT_TOGGLE) == \
defined(HWY_TARGET_TOGGLE)
#ifdef HIGHWAY_HWY_CONTRIB_SORT_RESULT_TOGGLE
#undef HIGHWAY_HWY_CONTRIB_SORT_RESULT_TOGGLE
#else
#define HIGHWAY_HWY_CONTRIB_SORT_RESULT_TOGGLE
#endif
HWY_BEFORE_NAMESPACE();
namespace hwy {
namespace HWY_NAMESPACE {
struct Result {
Result() {}
Result(const Algo algo, Dist dist, size_t num_keys, size_t num_threads,
double sec, size_t sizeof_key, const std::string& key_name)
: target(HWY_TARGET),
algo(algo),
dist(dist),
num_keys(num_keys),
num_threads(num_threads),
sec(sec),
sizeof_key(sizeof_key),
key_name(key_name) {}
void Print() const {
const double bytes = static_cast<double>(num_keys) *
static_cast<double>(num_threads) *
static_cast<double>(sizeof_key);
printf("%10s: %12s: %7s: %9s: %.2E %4.0f MB/s (%2zu threads)\n",
hwy::TargetName(target), AlgoName(algo), key_name.c_str(),
DistName(dist), static_cast<double>(num_keys), bytes * 1E-6 / sec,
num_threads);
}
int64_t target;
Algo algo;
Dist dist;
size_t num_keys = 0;
size_t num_threads = 0;
double sec = 0.0;
size_t sizeof_key = 0;
std::string key_name;
};
template <class Traits, typename LaneType>
bool VerifySort(Traits st, const InputStats<LaneType>& input_stats,
const LaneType* out, size_t num_lanes, const char* caller) {
constexpr size_t N1 = st.LanesPerKey();
HWY_ASSERT(num_lanes >= N1);
InputStats<LaneType> output_stats;
// Ensure it matches the sort order
for (size_t i = 0; i < num_lanes - N1; i += N1) {
output_stats.Notify(out[i]);
if (N1 == 2) output_stats.Notify(out[i + 1]);
// Reverse order instead of checking !Compare1 so we accept equal keys.
if (st.Compare1(out + i + N1, out + i)) {
printf("%s: i=%d of %d lanes: N1=%d %5.0f %5.0f vs. %5.0f %5.0f\n\n",
caller, static_cast<int>(i), static_cast<int>(num_lanes),
static_cast<int>(N1), static_cast<double>(out[i + 1]),
static_cast<double>(out[i + 0]),
static_cast<double>(out[i + N1 + 1]),
static_cast<double>(out[i + N1]));
HWY_ABORT("%d-bit sort is incorrect\n",
static_cast<int>(sizeof(LaneType) * 8 * N1));
}
}
output_stats.Notify(out[num_lanes - N1]);
if (N1 == 2) output_stats.Notify(out[num_lanes - N1 + 1]);
return input_stats == output_stats;
}
// NOLINTNEXTLINE(google-readability-namespace-comments)
} // namespace HWY_NAMESPACE
} // namespace hwy
HWY_AFTER_NAMESPACE();
#endif // HIGHWAY_HWY_CONTRIB_SORT_RESULT_TOGGLE
|
