diff options
Diffstat (limited to 'misc/benchmarks/various/sso_bench.cpp')
| -rw-r--r-- | misc/benchmarks/various/sso_bench.cpp | 156 |
1 files changed, 108 insertions, 48 deletions
diff --git a/misc/benchmarks/various/sso_bench.cpp b/misc/benchmarks/various/sso_bench.cpp index 993ff1bb..244c1291 100644 --- a/misc/benchmarks/various/sso_bench.cpp +++ b/misc/benchmarks/various/sso_bench.cpp @@ -3,65 +3,82 @@ #include <chrono> #include <stc/crand.h> +#define i_static #include <stc/cstr.h> #define i_type StcVec #define i_val_str #include <stc/cstack.h> -#define i_type StcSet -#define i_val_str -#include <stc/csset.h> - #include <vector> using StdVec = std::vector<std::string>; -#include <set> -using StdSet = std::set<std::string>; -static const int BENCHMARK_SIZE = 2000000; -static const int MAX_STRING_SIZE = 50; +#include <unordered_set> +#include "../external/ankerl/robin_hood.h" + +struct string_hash { + using is_transparent = void; + [[nodiscard]] size_t operator()(const char *txt) const { + return std::hash<std::string_view>{}(txt); + } + [[nodiscard]] size_t operator()(std::string_view txt) const { + return std::hash<std::string_view>{}(txt); + } + [[nodiscard]] size_t operator()(const std::string &txt) const { + return std::hash<std::string>{}(txt); + } +}; +using StdSet = robin_hood::unordered_flat_set<std::string, string_hash, std::equal_to<>>; +//using StdSet = std::unordered_set<std::string>; + +#define i_type StcSet +#define i_val_str +//#define i_hash(txtp) std::hash<std::string_view>{}(*txtp) +#include <stc/cset.h> + + +static const int BENCHMARK_SIZE = 250000; +static const int MAX_STRING_SIZE = 100; static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-"; using time_point = std::chrono::high_resolution_clock::time_point; -static inline std::string randomString_STD(int strsize) { - std::string s(strsize, 0); - char* p = &s[0]; +static inline const char* randomString(int strsize) { + static char str[256]; union { uint64_t u8; uint8_t b[8]; } r; for (int i = 0; i < strsize; ++i) { if ((i & 7) == 0) r.u8 = crand() & 0x3f3f3f3f3f3f3f3f; - p[i] = CHARS[r.b[i & 7]]; + str[i] = CHARS[r.b[i & 7]]; } - return s; + str[strsize] = 0; + return str; } -static inline cstr randomString_STC(int strsize) { - cstr s = cstr_with_size(strsize, 0); - char* p = cstr_data(&s); - union { uint64_t u8; uint8_t b[8]; } r; - for (int i = 0; i < strsize; ++i) { - if ((i & 7) == 0) r.u8 = crand() & 0x3f3f3f3f3f3f3f3f; - p[i] = CHARS[r.b[i & 7]]; - } - return s; + + +static inline void addRandomString(StdVec& vec, const char* str) { + vec.push_back(str); } +static inline void addRandomString(StcVec& vec, const char* str) { + StcVec_emplace(&vec, str); +} -void addRandomString(StdVec& vec, int strsize) { - vec.push_back(std::move(randomString_STD(strsize))); +static inline void addRandomString(StdSet& set, const char* str) { + set.insert(str); } -void addRandomString(StcVec& vec, int strsize) { - StcVec_push(&vec, randomString_STC(strsize)); +static inline void addRandomString(StcSet& set, const char* str) { + StcSet_emplace(&set, str); } -void addRandomString(StdSet& set, int strsize) { - set.insert(std::move(randomString_STD(strsize))); +static inline bool getRandomString(const StdSet& set, const char* str) { + return set.find(str) != set.end(); } -void addRandomString(StcSet& set, int strsize) { - StcSet_insert(&set, randomString_STC(strsize)); +static inline bool getRandomString(const StcSet& set, const char* str) { + return StcSet_contains(&set, str); } @@ -70,7 +87,7 @@ int benchmark(C& container, const int n, const int strsize) { time_point t1 = std::chrono::high_resolution_clock::now(); for (int i = 0; i < n; i++) - addRandomString(container, strsize); + addRandomString(container, randomString(strsize)); time_point t2 = std::chrono::high_resolution_clock::now(); const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count(); @@ -78,9 +95,25 @@ int benchmark(C& container, const int n, const int strsize) { return (int)duration; } +template <class C> +int benchmark_lookup(C& container, const int n, const int strsize) { + for (int i = 0; i < n; i++) + addRandomString(container, randomString(strsize)); + + time_point t1 = std::chrono::high_resolution_clock::now(); + int found = 0; + for (int i = 0; i < n; i++) + found += (int)getRandomString(container, randomString(strsize)); + + time_point t2 = std::chrono::high_resolution_clock::now(); + const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count(); + std::cerr << (strsize ? strsize : 32) << "\t" << duration << '\t' << found; + return (int)duration; +} -int main() { - uint64_t seed = 4321; +#include <time.h> +int main(void) { + uint64_t seed = time(NULL); // 4321; int sum, n; // VECTOR WITH STRINGS @@ -88,48 +121,75 @@ int main() { csrand(seed); sum = 0, n = 0; std::cerr << "\nstrsize\tmsecs\tstd::vector<std::string>, size=" << BENCHMARK_SIZE << "\n"; - for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 2) { + for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 4) { StdVec vec; vec.reserve(BENCHMARK_SIZE); sum += benchmark(vec, BENCHMARK_SIZE, strsize), ++n; std::cout << '\t' << vec.front() << '\n'; } - std::cout << "Avg:\t" << sum/n << '\n'; + std::cout << "Avg:\t" << sum/n << "ms\n"; csrand(seed); sum = 0, n = 0; std::cerr << "\nstrsize\tmsecs\tcvec<cstr>, size=" << BENCHMARK_SIZE << "\n"; - for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 2) { + for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 4) { StcVec vec = StcVec_with_capacity(BENCHMARK_SIZE); sum += benchmark(vec, BENCHMARK_SIZE, strsize), ++n; std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; StcVec_drop(&vec); } - std::cout << "Avg:\t" << sum/n << '\n'; + std::cout << "Avg:\t" << sum/n << "ms\n"; + + // INSERT: SORTED SET WITH STRINGS + + csrand(seed); + sum = 0, n = 0; + std::cerr << "\nstrsize\tmsecs\tinsert: robin_hood::unordered_flat_set<std::string>, size=" << BENCHMARK_SIZE/2 << "\n"; + for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 4) { + StdSet set; set.reserve(BENCHMARK_SIZE/2); + sum += benchmark(set, BENCHMARK_SIZE/2, strsize), ++n; + std::cout << '\t' << *set.begin() << '\n'; + } + std::cout << "Avg:\t" << sum/n << "ms\n"; - // SORTED SET WITH STRINGS csrand(seed); sum = 0, n = 0; - std::cerr << "\nstrsize\tmsecs\tstd::set<std::string>, size=" << BENCHMARK_SIZE/16 << "\n"; + std::cerr << "\nstrsize\tmsecs\tinsert: cset<cstr>, size=" << BENCHMARK_SIZE/2 << "\n"; + for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 4) { + StcSet set = StcSet_with_capacity(BENCHMARK_SIZE/2); + sum += benchmark(set, BENCHMARK_SIZE/2, strsize), ++n; + std::cout << '\t' << cstr_str(StcSet_begin(&set).ref) << '\n'; + StcSet_drop(&set); + } + std::cout << "Avg:\t" << sum/n << "ms\n"; + + // LOOKUP: SORTED SET WITH STRINGS + + csrand(seed); + sum = 0, n = 0; + std::cerr << "\nstrsize\tmsecs\tfind: robin_hood::unordered_flat_set<std::string>, size=" << BENCHMARK_SIZE/2 << "\n"; for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 2) { - StdSet set; - sum += benchmark(set, BENCHMARK_SIZE/16, strsize), ++n; + StdSet set; set.reserve(BENCHMARK_SIZE/2); + sum += benchmark_lookup(set, BENCHMARK_SIZE/2, strsize), ++n; std::cout << '\t' << *set.begin() << '\n'; } - std::cout << "Avg:\t" << sum/n << '\n'; + std::cout << "Avg:\t" << sum/n << "ms\n"; csrand(seed); sum = 0, n = 0; - std::cerr << "\nstrsize\tmsecs\tcsset<cstr>, size=" << BENCHMARK_SIZE/16 << "\n"; + std::cerr << "\nstrsize\tmsecs\tfind: cset<cstr>, size=" << BENCHMARK_SIZE/2 << "\n"; for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 2) { - StcSet set = StcSet_with_capacity(BENCHMARK_SIZE/16); - sum += benchmark(set, BENCHMARK_SIZE/16, strsize), ++n; - std::cout << '\t' << cstr_str(StcSet_front(&set)) << '\n'; + StcSet set = StcSet_with_capacity(BENCHMARK_SIZE/2); + sum += benchmark_lookup(set, BENCHMARK_SIZE/2, strsize), ++n; + std::cout << '\t' << cstr_str(StcSet_begin(&set).ref) << '\n'; StcSet_drop(&set); } - std::cout << "Avg:\t" << sum/n << '\n'; + std::cout << "Avg:\t" << sum/n << "ms\n"; + std::cerr << "sizeof(std::string) : " << sizeof(std::string) << std::endl - << "sizeof(cstr) : " << sizeof(cstr) << std::endl; + << "sizeof(cstr) : " << sizeof(cstr) << std::endl + << "sizeof(StdSet) : " << sizeof(StdSet) << std::endl + << "sizeof(StcSet) : " << sizeof(StcSet) << std::endl; return 0; } |