Adding upstream version 1.1.1.upstream/1.1.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

7 files changed, 413 insertions, 0 deletions

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
+  $<$<BOOL:${frozen.benchmark.str_search}>: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
+  $<$<BOOL:${frozen.benchmark.str_search}>:
+    ${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 <benchmark/benchmark.h>
+
+#include <frozen/set.h>
+
+#include <set>
+#include <array>
+#include <algorithm>
+
+static constexpr frozen::set<int, 32> 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<int> 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<int, 32> 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/benchmark.h>
+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 <benchmark/benchmark.h>
+
+#include <frozen/unordered_map.h>
+#include <frozen/string.h>
+
+#include <algorithm>
+#include <array>
+#include <string>
+#include <unordered_map>
+
+static constexpr frozen::unordered_map<frozen::string, frozen::string, 32> 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<frozen::string, frozen::string> 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 <benchmark/benchmark.h>
+#include "frozen/algorithm.h"
+#include <algorithm>
+#include <functional>
+#include <cstring>
+
+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<char const*>(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 <benchmark/benchmark.h>
+
+#include <frozen/set.h>
+#include <frozen/string.h>
+
+#include <set>
+#include <array>
+#include <string>
+#include <algorithm>
+
+static constexpr frozen::set<frozen::string, 32> 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<frozen::string> 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<frozen::string, 32> 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);