blob: ebf7f63e4bdb86e9044edc7df337faded827eb4f [file] [log] [blame]
// Copyright 2020 The SwiftShader Authors. All Rights Reserved.
//
// 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 "System/LRUCache.hpp"
#include "benchmark/benchmark.h"
#include <array>
namespace {
// https://en.wikipedia.org/wiki/Xorshift
class FastRnd
{
public:
inline size_t operator()()
{
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
private:
size_t x = 3243298;
};
struct ComplexKey
{
std::array<size_t, 8> words;
};
bool operator==(const ComplexKey &a, const ComplexKey &b)
{
for(size_t w = 0; w < a.words.size(); w++)
{
if(a.words[w] != b.words[w]) { return false; }
}
return true;
}
struct ComplexKeyHash
{
size_t operator()(const ComplexKey &key) const
{
size_t hash = 12227;
for(size_t w = 0; w < key.words.size(); w++)
{
hash = hash * 11801 + key.words[w];
}
return hash;
}
};
} // namespace
class LRUCacheBenchmark : public benchmark::Fixture
{
public:
void SetUp(const ::benchmark::State &state)
{
size = state.range(0);
}
void TearDown(const ::benchmark::State &state) {}
size_t size;
};
BENCHMARK_DEFINE_F(LRUCacheBenchmark, AddInt)
(benchmark::State &state)
{
sw::LRUCache<size_t, size_t> cache(size);
FastRnd rnd;
int i = 0;
for(auto _ : state)
{
cache.add(rnd() % size, i);
i++;
}
}
BENCHMARK_REGISTER_F(LRUCacheBenchmark, AddInt)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetIntCacheHit)
(benchmark::State &state)
{
sw::LRUCache<size_t, size_t> cache(size);
FastRnd rnd;
for(size_t i = 0; i < size; i++)
{
cache.add(i, i);
}
for(auto _ : state)
{
cache.lookup(rnd() % size);
}
}
BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetIntCacheHit)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetIntCacheMiss)
(benchmark::State &state)
{
sw::LRUCache<size_t, size_t> cache(size);
FastRnd rnd;
for(size_t i = 0; i < size; i++)
{
cache.add(size + i, i);
}
for(auto _ : state)
{
cache.lookup(rnd() % size);
}
}
BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetIntCacheMiss)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
BENCHMARK_DEFINE_F(LRUCacheBenchmark, AddRandomComplexKey)
(benchmark::State &state)
{
sw::LRUCache<ComplexKey, size_t, ComplexKeyHash> cache(size);
FastRnd rnd;
int i = 0;
for(auto _ : state)
{
ComplexKey key;
for(size_t w = 0; w < key.words.size(); w++)
{
key.words[w] = rnd() & 1;
}
cache.add(key, i);
i++;
}
}
BENCHMARK_REGISTER_F(LRUCacheBenchmark, AddRandomComplexKey)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetComplexKeyCacheHit)
(benchmark::State &state)
{
sw::LRUCache<ComplexKey, size_t, ComplexKeyHash> cache(size);
FastRnd rnd;
for(size_t i = 0; i < size; i++)
{
ComplexKey key;
for(size_t w = 0; w < key.words.size(); w++)
{
key.words[w] = (1U << w);
}
cache.add(key, i);
}
for(auto _ : state)
{
auto i = rnd() & size;
ComplexKey key;
for(size_t w = 0; w < key.words.size(); w++)
{
key.words[w] = i & (1U << w);
}
cache.lookup(key);
}
}
BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetComplexKeyCacheHit)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");
BENCHMARK_DEFINE_F(LRUCacheBenchmark, GetComplexKeyCacheMiss)
(benchmark::State &state)
{
sw::LRUCache<ComplexKey, size_t, ComplexKeyHash> cache(size);
FastRnd rnd;
for(size_t i = 0; i < size; i++)
{
ComplexKey key;
for(size_t w = 0; w < key.words.size(); w++)
{
key.words[w] = 8 + (1U << w);
}
cache.add(key, i);
}
for(auto _ : state)
{
auto i = rnd() & size;
ComplexKey key;
for(size_t w = 0; w < key.words.size(); w++)
{
key.words[w] = i & (1U << w);
}
cache.lookup(key);
}
}
BENCHMARK_REGISTER_F(LRUCacheBenchmark, GetComplexKeyCacheMiss)->RangeMultiplier(8)->Range(1, 0x100000)->ArgName("cache-size");