From 408c608fc7bf1557ee987dd7fbe662fabed21a53 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Mon, 15 Apr 2024 07:39:03 +0200 Subject: Adding upstream version 1.1.1. Signed-off-by: Daniel Baumann --- benchmarks/CMakeLists.txt | 36 ++++++++++++++ benchmarks/Makefile | 27 +++++++++++ benchmarks/bench_int_set.cpp | 94 ++++++++++++++++++++++++++++++++++++ benchmarks/bench_main.cpp | 2 + benchmarks/bench_str_map.cpp | 84 +++++++++++++++++++++++++++++++++ benchmarks/bench_str_search.cpp | 68 +++++++++++++++++++++++++++ benchmarks/bench_str_set.cpp | 102 ++++++++++++++++++++++++++++++++++++++++ 7 files changed, 413 insertions(+) create mode 100644 benchmarks/CMakeLists.txt create mode 100644 benchmarks/Makefile create mode 100644 benchmarks/bench_int_set.cpp create mode 100644 benchmarks/bench_main.cpp create mode 100644 benchmarks/bench_str_map.cpp create mode 100644 benchmarks/bench_str_search.cpp create mode 100644 benchmarks/bench_str_set.cpp (limited to 'benchmarks') diff --git a/benchmarks/CMakeLists.txt b/benchmarks/CMakeLists.txt new file mode 100644 index 0000000..7a079c9 --- /dev/null +++ b/benchmarks/CMakeLists.txt @@ -0,0 +1,36 @@ +list(APPEND CMAKE_MODULE_PATH "${frozen_SOURCE_DIR}/cmake") +include(sed) + +find_package(benchmark REQUIRED) + +add_executable(frozen.benchmark "") + +target_link_libraries(frozen.benchmark PUBLIC + frozen::frozen + benchmark::benchmark) + +option(frozen.benchmark.str_search + "Build Benchmark Boyer-Moore string search (requires C++17 compiler)" OFF) + +target_compile_options(frozen.benchmark PUBLIC + $<$:cxx_std_17>) + +sed(${CMAKE_CURRENT_LIST_DIR}/bench_int_set.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_int_unordered_set.cpp + "set" "unordered_set" "Set" "UnorderedSet") + +sed(${CMAKE_CURRENT_LIST_DIR}/bench_str_set.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_str_unordered_set.cpp + "set" "unordered_set" "Set" "UnorderedSet") + +target_sources(frozen.benchmark PRIVATE + ${CMAKE_CURRENT_LIST_DIR}/bench_main.cpp + ${CMAKE_CURRENT_LIST_DIR}/bench_int_set.cpp + ${CMAKE_CURRENT_LIST_DIR}/bench_str_set.cpp + ${CMAKE_CURRENT_LIST_DIR}/bench_str_map.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_int_unordered_set.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_str_unordered_set.cpp + $<$: + ${CMAKE_CURRENT_LIST_DIR}/bench_str_search.cpp>) + +add_custom_target(benchmark frozen.benchmark) diff --git a/benchmarks/Makefile b/benchmarks/Makefile new file mode 100644 index 0000000..251f2bc --- /dev/null +++ b/benchmarks/Makefile @@ -0,0 +1,27 @@ +ifndef GOOGLE_BENCHMARK_PREFIX + $(error GOOGLE_BENCHMARK_PREFIX is undefined) +endif + +CXXFLAGS=-O2 +override CXXFLAGS+= -std=c++17 #17 for boyer_moore_searcher + +LIBS=-lbenchmark -lpthread +LDFLAGS=-L$(GOOGLE_BENCHMARK_PREFIX)/lib + +CPPFLAGS=-I../include -I$(GOOGLE_BENCHMARK_PREFIX)/include + + +all:bench + ./$< + +bench: bench_main.o bench_str_set.o bench_str_unordered_set.o bench_int_set.o bench_int_unordered_set.o bench_str_search.o + $(CXX) $^ $(LDFLAGS) $(LIBS) -o $@ + +clean: + $(RM) *.o bench bench_str_unordered_set.cpp bench_int_unordered_set.cpp + +bench_str_unordered_set.cpp:bench_str_set.cpp + sed -e 's/set/unordered_set/g' -e 's/Set/UnorderedSet/g' $< > $@ + +bench_int_unordered_set.cpp:bench_int_set.cpp + sed -e 's/set/unordered_set/g' -e 's/Set/UnorderedSet/g' $< > $@ diff --git a/benchmarks/bench_int_set.cpp b/benchmarks/bench_int_set.cpp new file mode 100644 index 0000000..38fa7d3 --- /dev/null +++ b/benchmarks/bench_int_set.cpp @@ -0,0 +1,94 @@ +#include + +#include + +#include +#include +#include + +static constexpr frozen::set Keywords{ + 0, 2, 4, 6, 8, 10, 12, 14, + 16, 18, 20, 22, 24, 26, 28, 30, + 32, 34, 36, 38, 40, 42, 44, 46, + 48, 50, 52, 54, 56, 58, 60, 62 +}; + +static auto const* volatile Some = &Keywords; + +static void BM_IntInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntInFzSet); + +static const std::set Keywords_(Keywords.begin(), Keywords.end()); + +static void BM_IntInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_IntInStdSet); + +static const std::array Keywords__{{ + 0, 2, 4, 6, 8, 10, 12, 14, + 16, 18, 20, 22, 24, 26, 28, 30, + 32, 34, 36, 38, 40, 42, 44, 46, + 48, 50, 52, 54, 56, 58, 60, 62 +}}; +static void BM_IntInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_IntInStdArray); + +static const int SomeInts[32] = { + 1, 3, 5, 7, 9, 11, 13, 15, + 17, 19, 21, 23, 25, 27, 29, 31, + 33, 35, 37, 39, 41, 43, 45, 47, + 49, 51, 53, 55, 57, 59, 61, 63 +}; +static auto const * volatile SomeIntsPtr = &SomeInts; + +static void BM_IntNotInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeIntsPtr) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntNotInFzSet); + +static void BM_IntNotInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeIntsPtr) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntNotInStdSet); + +static void BM_IntNotInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeIntsPtr) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntNotInStdArray); diff --git a/benchmarks/bench_main.cpp b/benchmarks/bench_main.cpp new file mode 100644 index 0000000..71144c2 --- /dev/null +++ b/benchmarks/bench_main.cpp @@ -0,0 +1,2 @@ +#include +BENCHMARK_MAIN(); diff --git a/benchmarks/bench_str_map.cpp b/benchmarks/bench_str_map.cpp new file mode 100644 index 0000000..efe24b2 --- /dev/null +++ b/benchmarks/bench_str_map.cpp @@ -0,0 +1,84 @@ +#include + +#include +#include + +#include +#include +#include +#include + +static constexpr frozen::unordered_map Keywords{ + {"auto", "keyword"}, {"break", "keyword"}, {"case", "keyword"}, {"char", "keyword"}, {"const", "keyword"}, {"continue", "keyword"}, + {"default", "keyword"}, {"do", "keyword"}, {"double", "keyword"}, {"else", "keyword"}, {"enum", "keyword"}, {"extern", "keyword"}, + {"float", "keyword"}, {"for", "keyword"}, {"goto", "keyword"}, {"if", "keyword"}, {"int", "keyword"}, {"long", "keyword"}, + {"register", "keyword"}, {"return", "keyword"}, {"short", "keyword"}, {"signed", "keyword"}, {"sizeof", "keyword"}, {"static", "keyword"}, + {"struct", "keyword"}, {"switch", "keyword"}, {"typedef", "keyword"}, {"union", "keyword"}, {"unsigned", "keyword"}, + {"void", "keyword"}, {"volatile", "keyword"}, {"while", "keyword"} +}; + +static auto const *volatile Some = &Keywords; + +static void BM_StrInFzUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *Some) + { + volatile bool status = Keywords.count(kw.first); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrInFzUnorderedMap); + +static const std::unordered_map Keywords_(Keywords.begin(), Keywords.end()); + +static void BM_StrInStdUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *Some) + { + volatile bool status = Keywords_.count(kw.first); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrInStdUnorderedMap); + +static const frozen::string SomeStrings[32] = { + "auto0", "break0", "case0", "char0", "const0", "continue0", + "default0", "do0", "double0", "else0", "enum0", "extern0", + "float0", "for0", "goto0", "if0", "int0", "long0", + "register0", "return0", "short0", "signed0", "sizeof0", "static0", + "struct0", "switch0", "typedef0", "union0", "unsigned0", "void0", + "volatile0", "while0"}; +static auto const *volatile SomeStringsPtr = &SomeStrings; + +static void BM_StrNotInFzUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *SomeStringsPtr) + { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInFzUnorderedMap); + +static void BM_StrNotInStdUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *SomeStringsPtr) + { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInStdUnorderedMap); diff --git a/benchmarks/bench_str_search.cpp b/benchmarks/bench_str_search.cpp new file mode 100644 index 0000000..945b8a8 --- /dev/null +++ b/benchmarks/bench_str_search.cpp @@ -0,0 +1,68 @@ +#include +#include "frozen/algorithm.h" +#include +#include +#include + +static char const Words [] = R"( +Let it go, let it go +Can't hold it back anymore +Let it go, let it go +Turn my back and slam the door +The snow blows white on the mountain tonight +Not a footprint to be seen +A kingdom of isolation and it looks like I'm the queen +The wind is howling like the swirling storm inside +Couldn't keep it in +Heaven knows I try +Don't let them in, don't let them see +Be the good girl you always had to be +Conceal, don't feel, don't let them know +Well now they know +Let it go, let it go +Can't hold you back anymore +Let it go, let it go +Turn my back and slam the door +And here I stand +And here I'll stay +Let it go, let it go +The cold never bothered me anyway +It's funny how some distance makes everything seem small +And the fears that once controlled me can't get to me at all +Up here +)"; + +static auto * volatile WordsPtr = &Words; + +static constexpr char Word[] = "controlled"; + +static void BM_StrFzSearchInBM(benchmark::State& state) { + for (auto _ : state) { + volatile bool status = frozen::search(std::begin(*WordsPtr), std::end(*WordsPtr), frozen::make_boyer_moore_searcher(Word)); + } +} +BENCHMARK(BM_StrFzSearchInBM); + +static void BM_StrStdSearchInBM(benchmark::State& state) { + for (auto _ : state) { + volatile bool status = std::search(std::begin(*WordsPtr), std::end(*WordsPtr), + std::boyer_moore_searcher(std::begin(Word), std::end(Word))); + } +} +BENCHMARK(BM_StrStdSearchInBM); + +static void BM_StrFzSearchInKMP(benchmark::State& state) { + for (auto _ : state) { + volatile bool status = frozen::search(std::begin(*WordsPtr), std::end(*WordsPtr), frozen::make_knuth_morris_pratt_searcher(Word)); + } +} +BENCHMARK(BM_StrFzSearchInKMP); + +#if 0 +static void BM_StrStdSearchInStrStr(benchmark::State& state) { + for (auto _ : state) { + char const* volatile status = std::strstr(*WordsPtr, Word); + } +} +BENCHMARK(BM_StrStdSearchInStrStr); +#endif diff --git a/benchmarks/bench_str_set.cpp b/benchmarks/bench_str_set.cpp new file mode 100644 index 0000000..fe83cc3 --- /dev/null +++ b/benchmarks/bench_str_set.cpp @@ -0,0 +1,102 @@ +#include + +#include +#include + +#include +#include +#include +#include + +static constexpr frozen::set Keywords{ + "auto", "break", "case", "char", "const", "continue", + "default", "do", "double", "else", "enum", "extern", + "float", "for", "goto", "if", "int", "long", + "register", "return", "short", "signed", "sizeof", "static", + "struct", "switch", "typedef", "union", "unsigned", "void", + "volatile", "while"}; + +static auto const* volatile Some = &Keywords; + +static void BM_StrInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrInFzSet); + +static const std::set Keywords_(Keywords.begin(), Keywords.end()); + +static void BM_StrInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrInStdSet); + +static const std::array Keywords__{ + "auto", "break", "case", "char", "const", "continue", + "default", "do", "double", "else", "enum", "extern", + "float", "for", "goto", "if", "int", "long", + "register", "return", "short", "signed", "sizeof", "static", + "struct", "switch", "typedef", "union", "unsigned", "void", + "volatile", "while"}; + +static void BM_StrInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrInStdArray); + + +static const frozen::string SomeStrings[32] = { + "auto0", "break0", "case0", "char0", "const0", "continue0", + "default0", "do0", "double0", "else0", "enum0", "extern0", + "float0", "for0", "goto0", "if0", "int0", "long0", + "register0", "return0", "short0", "signed0", "sizeof0", "static0", + "struct0", "switch0", "typedef0", "union0", "unsigned0", "void0", + "volatile0", "while0"}; +static auto const * volatile SomeStringsPtr = &SomeStrings; + +static void BM_StrNotInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeStringsPtr) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInFzSet); + +static void BM_StrNotInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeStringsPtr) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInStdSet); + +static void BM_StrNotInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeStringsPtr) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrNotInStdArray); -- cgit v1.2.3