1 // Copyright 2020 The SwiftShader Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "System/LRUCache.hpp"
16
17 #include "benchmark/benchmark.h"
18
19 #include <array>
20
21 namespace {
22
23 // https://en.wikipedia.org/wiki/Xorshift
24 class FastRnd
25 {
26 public:
operator ()()27 inline size_t operator()()
28 {
29 x ^= x << 13;
30 x ^= x >> 7;
31 x ^= x << 17;
32 return x;
33 }
34
35 private:
36 size_t x = 3243298;
37 };
38
39 struct ComplexKey
40 {
41 std::array<size_t, 8> words;
42 };
43
operator ==(const ComplexKey & a,const ComplexKey & b)44 bool operator==(const ComplexKey &a, const ComplexKey &b)
45 {
46 for(size_t w = 0; w < a.words.size(); w++)
47 {
48 if(a.words[w] != b.words[w]) { return false; }
49 }
50 return true;
51 }
52
53 struct ComplexKeyHash
54 {
operator ()__anon8290f6550111::ComplexKeyHash55 size_t operator()(const ComplexKey &key) const
56 {
57 size_t hash = 12227;
58 for(size_t w = 0; w < key.words.size(); w++)
59 {
60 hash = hash * 11801 + key.words[w];
61 }
62 return hash;
63 }
64 };
65
66 } // namespace
67
68 class LRUCacheBenchmark : public benchmark::Fixture
69 {
70 public:
SetUp(const::benchmark::State & state)71 void SetUp(const ::benchmark::State &state)
72 {
73 size = state.range(0);
74 }
75
TearDown(const::benchmark::State & state)76 void TearDown(const ::benchmark::State &state) {}
77
78 size_t size;
79 };
80
BENCHMARK_DEFINE_F(LRUCacheBenchmark,AddInt)81 BENCHMARK_DEFINE_F(LRUCacheBenchmark, AddInt)
82 (benchmark::State &state)
83 {
84 sw::LRUCache<size_t, size_t> cache(size);
85 FastRnd rnd;
86
87 int i = 0;
88 for(auto _ : state)
89 {
90 cache.add(rnd() % size, i);
91 i++;
92 }
93 }
94 BENCHMARK_REGISTER_F(LRUCacheBenchmark, AddInt)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
95
BENCHMARK_DEFINE_F(LRUCacheBenchmark,GetIntCacheHit)96 BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetIntCacheHit)
97 (benchmark::State &state)
98 {
99 sw::LRUCache<size_t, size_t> cache(size);
100 FastRnd rnd;
101
102 for(size_t i = 0; i < size; i++)
103 {
104 cache.add(i, i);
105 }
106
107 for(auto _ : state)
108 {
109 cache.lookup(rnd() % size);
110 }
111 }
112 BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetIntCacheHit)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
113
BENCHMARK_DEFINE_F(LRUCacheBenchmark,GetIntCacheMiss)114 BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetIntCacheMiss)
115 (benchmark::State &state)
116 {
117 sw::LRUCache<size_t, size_t> cache(size);
118 FastRnd rnd;
119 for(size_t i = 0; i < size; i++)
120 {
121 cache.add(size + i, i);
122 }
123
124 for(auto _ : state)
125 {
126 cache.lookup(rnd() % size);
127 }
128 }
129 BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetIntCacheMiss)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
130
BENCHMARK_DEFINE_F(LRUCacheBenchmark,AddRandomComplexKey)131 BENCHMARK_DEFINE_F(LRUCacheBenchmark, AddRandomComplexKey)
132 (benchmark::State &state)
133 {
134 sw::LRUCache<ComplexKey, size_t, ComplexKeyHash> cache(size);
135 FastRnd rnd;
136
137 int i = 0;
138 for(auto _ : state)
139 {
140 ComplexKey key;
141 for(size_t w = 0; w < key.words.size(); w++)
142 {
143 key.words[w] = rnd() & 1;
144 }
145
146 cache.add(key, i);
147 i++;
148 }
149 }
150 BENCHMARK_REGISTER_F(LRUCacheBenchmark, AddRandomComplexKey)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
151
BENCHMARK_DEFINE_F(LRUCacheBenchmark,GetComplexKeyCacheHit)152 BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetComplexKeyCacheHit)
153 (benchmark::State &state)
154 {
155 sw::LRUCache<ComplexKey, size_t, ComplexKeyHash> cache(size);
156 FastRnd rnd;
157
158 for(size_t i = 0; i < size; i++)
159 {
160 ComplexKey key;
161 for(size_t w = 0; w < key.words.size(); w++)
162 {
163 key.words[w] = (1ull << w);
164 }
165 cache.add(key, i);
166 }
167
168 for(auto _ : state)
169 {
170 auto i = rnd() & size;
171
172 ComplexKey key;
173 for(size_t w = 0; w < key.words.size(); w++)
174 {
175 key.words[w] = i & (1ull << w);
176 }
177 cache.lookup(key);
178 }
179 }
180 BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetComplexKeyCacheHit)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
181
BENCHMARK_DEFINE_F(LRUCacheBenchmark,GetComplexKeyCacheMiss)182 BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetComplexKeyCacheMiss)
183 (benchmark::State &state)
184 {
185 sw::LRUCache<ComplexKey, size_t, ComplexKeyHash> cache(size);
186 FastRnd rnd;
187
188 for(size_t i = 0; i < size; i++)
189 {
190 ComplexKey key;
191 for(size_t w = 0; w < key.words.size(); w++)
192 {
193 key.words[w] = 8 + (1ull << w);
194 }
195 cache.add(key, i);
196 }
197
198 for(auto _ : state)
199 {
200 auto i = rnd() & size;
201
202 ComplexKey key;
203 for(size_t w = 0; w < key.words.size(); w++)
204 {
205 key.words[w] = i & (1ull << w);
206 }
207 cache.lookup(key);
208 }
209 }
210 BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetComplexKeyCacheMiss)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
211