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
|
#include "sieve.hh"
#include <chrono>
#include <functional>
#include <gtest/gtest.h>
#include <iostream>
using ::testing::Combine;
using ::testing::Values;
TEST(Eratosthenes, isPrime) {
EXPECT_FALSE(isPrime(4));
EXPECT_FALSE(isPrime(9409));
EXPECT_TRUE(isPrime(9973));
EXPECT_FALSE(isPrime(53033));
}
constexpr auto sz = 1024 * 1024;
static const auto n = sieve1(sz);
TEST(Eratosthenes, validate) {
EXPECT_EQ(n[0], 2);
for (size_t i = 0; i < n.size(); ++i)
EXPECT_TRUE(isPrime(n[i])) << n[i];
}
typedef std::function<std::vector<int>(std::size_t)> SieveFunction;
class SieveFunctionFixture
: public ::testing::TestWithParam<std::tuple<SieveFunction, std::string>> {
public:
void SetUp() override {
sieve = std::get<SieveFunction>(GetParam());
sieve_name = std::get<std::string>(GetParam());
}
protected:
SieveFunction sieve;
std::string sieve_name;
};
TEST_P(SieveFunctionFixture, validate) {
const auto begin = std::chrono::system_clock::now();
const auto r = sieve(sz);
const auto end = std::chrono::system_clock::now();
const auto ut =
std::chrono::duration_cast<std::chrono::microseconds>(end - begin);
const auto nt =
std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
std::cout << sieve_name << '\n'
<< "run time: " << ut << '\n'
<< "prime count: " << r.size() << '\n'
<< "time per prime: " << nt / r.size() << std::endl;
EXPECT_EQ(n.size(), r.size());
for (size_t i = 0; i < std::min(n.size(), r.size()); ++i) {
EXPECT_EQ(n[i], r[i]) << "difference at index " << i;
}
}
INSTANTIATE_TEST_SUITE_P(
Eratosthenes, SieveFunctionFixture,
Values(std::make_tuple(&sieve1, "sieve1"),
std::make_tuple(&sieve2, "sieve2"),
std::make_tuple(&sieve3, "sieve3"),
std::make_tuple(&segmentedSieve, "segmented sieve"),
std::make_tuple(&pthreadSieve, "threaded sieve")));
TEST(benchmark, segmentedSieve) {
const auto begin = std::chrono::system_clock::now();
const auto r = segmentedSieve(1024 * sz);
const auto end = std::chrono::system_clock::now();
const auto t =
std::chrono::duration_cast<std::chrono::microseconds>(end - begin);
std::cout << r.size() << " values in " << t << std::endl;
for (size_t i = 0; i < std::min(n.size(), r.size()); ++i) {
EXPECT_EQ(n[i], r[i]) << "difference at index " << i;
}
}
TEST(benchmark, threadedSieve) {
const auto begin = std::chrono::system_clock::now();
const auto r = pthreadSieve(1024 * sz);
const auto end = std::chrono::system_clock::now();
const auto t =
std::chrono::duration_cast<std::chrono::microseconds>(end - begin);
std::cout << r.size() << " values in " << t << std::endl;
for (size_t i = 0; i < std::min(n.size(), r.size()); ++i) {
EXPECT_EQ(n[i], r[i]) << "difference at index " << i;
}
}
|
