From e78dd0918583a831e90f4c008c369ca143840124 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 16 Oct 2021 14:59:12 +0200 Subject: More update on hash. Added string_bench.c+cpp. --- benchmarks/string_bench.c | 150 +++++++++++++++++++++++++++++++++ benchmarks/string_bench.cpp | 198 ++++++++++++++++++++++++++++++++++++++++++++ include/stc/ccommon.h | 9 +- include/stc/cmap.h | 6 +- include/stc/cstr.h | 3 +- include/stc/csview.h | 2 +- 6 files changed, 359 insertions(+), 9 deletions(-) create mode 100644 benchmarks/string_bench.c create mode 100644 benchmarks/string_bench.cpp diff --git a/benchmarks/string_bench.c b/benchmarks/string_bench.c new file mode 100644 index 00000000..e5059075 --- /dev/null +++ b/benchmarks/string_bench.c @@ -0,0 +1,150 @@ +// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark +// https://github.com/shaovoon/cpp_hetero_lookup_bench + +#include + +#define i_val_str +#include + +#define i_key_str +#define i_val size_t +#include + +#define i_key_str +#define i_val size_t +#include + + +cvec_str read_file(const char* name) +{ + cvec_str data = cvec_str_init(); + c_auto (cstr, line) + c_autovar (FILE* f = fopen(name, "r"), fclose(f)) + while (cstr_getline(&line, f)) + cvec_str_emplace_back(&data, line.str); + return data; +} + +void initShortStringVec(cvec_str* vs) +{ + cvec_str_clear(vs); + + *vs = read_file("names.txt"); + size_t lengths = 0; + c_foreach (i, cvec_str, *vs) + { + lengths += cstr_size(*i.ref); + } + printf("avg len: %f\n", (float)lengths / cvec_str_size(*vs)); +} + +void initLongStringVec(cvec_str* vs) +{ + cvec_str_clear(vs); + *vs = read_file("names.txt"); + cstr* s = vs->data; + size_t lengths = 0; + cstr_append(s, s[1].str); + cstr_append(s, s[2].str); + cstr_append(s, s[3].str); + for (int i=1; i < cvec_str_size(*vs); ++i) + { + cstr* t = vs->data + i; + cstr_append(t, t->str); + cstr_append(t, t->str); + cstr_append(t, s->str); + cstr_append(t, t->str); + lengths += cstr_size(*t); + } + printf("avg len: %f\n", (float)lengths / cvec_str_size(*vs)); +} + +struct Maps { + csmap_str* snormal; + cmap_str* unormal; +}; + +void initMaps(cvec_str vs, struct Maps maps) +{ + csmap_str_clear(maps.snormal); + cmap_str_clear(maps.unormal); + + for (size_t i = 0; i < cvec_str_size(vs); ++i) + { + cstr str = *cvec_str_at(&vs, i); + csmap_str_insert(maps.snormal, cstr_clone(str), i); + cmap_str_insert(maps.unormal, cstr_clone(str), i); + } +} + +void benchmark(cvec_str vec_string, struct Maps maps); + +static const size_t MAX_LOOP = 2000; + +int main() +{ + c_auto (cvec_str, vec_string) + c_auto (csmap_str, snormal) + c_auto (cmap_str, unormal) + { + struct Maps maps = { &snormal, &unormal }; + + initShortStringVec(&vec_string); + initMaps(vec_string, maps); + + puts("Short String Benchmark"); + puts("======================"); + + benchmark(vec_string, maps); + + puts("\nLong String Benchmark"); + puts("======================"); + + initLongStringVec(&vec_string); + initMaps(vec_string, maps); + + benchmark(vec_string, maps); + } +} + +void benchmark(cvec_str vec_string, struct Maps maps) +{ + size_t grandtotal = 0; + size_t total; + clock_t stopwatch; + + total = 0; + printf("%32s", "Trans Map with char*"); + stopwatch = clock(); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + csmap_str_iter_t it, end = csmap_str_end(maps.snormal); + for (size_t j = 0; j < cvec_str_size(vec_string); ++j) + { + csmap_str_find_it(maps.snormal, vec_string.data[j].str, &it); + if (it.ref != end.ref) + total += it.ref->second; + } + } + grandtotal += total; + printf(" timing:%5.0fms\n", (clock() - stopwatch) / (float)CLOCKS_PER_SEC * 1000.0f); + + + total = 0; + printf("%32s", "Trans Unord Map with char*"); + stopwatch = clock(); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + cmap_str_iter_t it, end = cmap_str_end(maps.unormal); + for (size_t j = 0; j < cvec_str_size(vec_string); ++j) + { + it = cmap_str_find(maps.unormal, vec_string.data[j].str); + if (it.ref != end.ref) + total += it.ref->second; + } + } + grandtotal += total; + printf(" timing:%5.0fms\n", (clock() - stopwatch) / (float)CLOCKS_PER_SEC * 1000.0f); + + printf("C grandtotal: %zu <--- Ignore this\n", grandtotal); +} diff --git a/benchmarks/string_bench.cpp b/benchmarks/string_bench.cpp new file mode 100644 index 00000000..0c9ab1ee --- /dev/null +++ b/benchmarks/string_bench.cpp @@ -0,0 +1,198 @@ +// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark +// https://github.com/shaovoon/cpp_hetero_lookup_bench + +#include +#include +#include +#include +#include +#include +#include + +#define i_val_str +#include + + +std::vector read_file(const char* name) +{ + std::vector data; + c_auto (cstr, line) + c_autovar (FILE* f = fopen(name, "r"), fclose(f)) + while (cstr_getline(&line, f)) + data.emplace_back(line.str); + return data; +} + +class timer +{ +public: + timer() = default; + void start(const std::string& text_) + { + text = text_; + begin = std::chrono::high_resolution_clock::now(); + } + void stop() + { + auto end = std::chrono::high_resolution_clock::now(); + auto dur = end - begin; + auto ms = std::chrono::duration_cast(dur).count(); + std::cout << std::setw(32) << text << " timing:" << std::setw(5) << ms << "ms" << std::endl; + } + +private: + std::string text; + std::chrono::high_resolution_clock::time_point begin; +}; + +void initShortStringVec(std::vector& vs) +{ + vs.clear(); + vs = read_file("names.txt"); + size_t num = 0; + + for (size_t i = 0; i < vs.size(); ++i) + { + num += vs[i].size(); + } + printf("avg len: %f\n", (float)num / vs.size()); +} + +void initLongStringVec(std::vector& vs) +{ + vs.clear(); + vs = read_file("names.txt"); + size_t num = 0; + vs[0] += vs[1]; + vs[0] += vs[2]; + vs[0] += vs[3]; + for (size_t i = 1; i < vs.size(); ++i) + { + vs[i] += vs[i]; + vs[i] += vs[i]; + vs[i] += vs[0]; + vs[i] += vs[i]; + num += vs[i].size(); + } + printf("avg len: %f\n", (float)num / vs.size()); +} + +void initMapNormal(const std::vector& vs, + std::map& mapNormal, + std::unordered_map& unordmapNormal) +{ + mapNormal.clear(); + unordmapNormal.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + mapNormal.insert(std::make_pair(vs.at(i), i)); + unordmapNormal.insert(std::make_pair(vs.at(i), i)); + } +} +/* +struct string_hash { + using is_transparent = void; + using hash_type = std::hash; // just a helper local type + size_t operator()(const std::string& txt) const { return hash_type{}(txt); } + size_t operator()(const char* txt) const { return hash_type{}(txt); } +};*/ + +void benchmark( + const std::vector& vec_string, + const std::map& mapNormal, + const std::unordered_map& unordmapNormal); + +const size_t MAX_LOOP = 2000; + +int main() +{ + std::vector vec_string; + + std::map mapNormal; + std::unordered_map unordmapNormal; + + initShortStringVec(vec_string); + initMapNormal(vec_string, mapNormal, unordmapNormal); + + std::cout << "Short String Benchmark" << std::endl; + std::cout << "======================" << std::endl; + + benchmark(vec_string, mapNormal, unordmapNormal); + + std::cout << "Long String Benchmark" << std::endl; + std::cout << "=====================" << std::endl; + + initLongStringVec(vec_string); + initMapNormal(vec_string, mapNormal, unordmapNormal); + + benchmark(vec_string, mapNormal, unordmapNormal); + return 0; +} + +void benchmark( + const std::vector& vec_string, + const std::map& mapNormal, + const std::unordered_map& unordmapNormal) +{ + size_t grandtotal = 0; + size_t total = 0; + timer stopwatch; + + total = 0; + stopwatch.start("Normal Map with string"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_string.size(); ++j) + { + const auto& it = mapNormal.find(vec_string[j]); + if(it!=mapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Normal Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_string.size(); ++j) + { + const auto& it = mapNormal.find(vec_string[j].c_str()); + if (it != mapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Normal Unord Map with string"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_string.size(); ++j) + { + const auto& it = unordmapNormal.find(vec_string[j]); + if (it != unordmapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Normal Unord Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_string.size(); ++j) + { + const auto& it = unordmapNormal.find(vec_string[j].c_str()); + if (it != unordmapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + std::cout << "C++ grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl; +} \ No newline at end of file diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 5480d9f2..b61c7daf 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -102,8 +102,7 @@ #define c_rawstr_compare(x, y) strcmp(*(x), *(y)) #define c_rawstr_equals(x, y) (strcmp(*(x), *(y)) == 0) -#define c_rawstr_hash(p, dummy) c_default_hash(*(p), strlen(*(p))) -#define c_strhash(s) c_default_hash(s, strlen(s)) +#define c_rawstr_hash(p, dummy) c_strhash(*(p)) #define c_no_clone(x) (assert(!"c_no_clone() called"), x) #define c_default_fromraw(x) (x) @@ -111,6 +110,12 @@ #define c_default_del(ptr) ((void) (ptr)) +#define _c_rotl(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) +STC_INLINE uint64_t c_strhash(const char *str) { + int c; uint64_t h = 0xb5ad4eceda1ce2a9; + while ((c = *str++)) h = (_c_rotl(h, 4) ^ (h << 13)) + c; + return h; +} STC_INLINE uint64_t c_default_hash(const void *key, size_t len); #define c_default_hash32(data, len_is_4) \ ((*(const uint32_t*)data * 0xc6a4a7935bd1e99d) >> 15) diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 1dc1fd90..b764a717 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -216,12 +216,10 @@ cx_memb(_erase_at)(Self* self, cx_iter_t it) { #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_imp) #ifndef CMAP_H_INCLUDED -#define _c_rotl(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) STC_INLINE uint64_t c_default_hash(const void *key, size_t len) { - const char* str = (const char*)key; + const char* str = (const char*)key, *e = str + len; uint64_t h = 0xb5ad4eceda1ce2a9; - for (size_t i = 0; i < len; ++i) - h ^= (_c_rotl(h, 4) ^ (h << 13)) + str[i]; + while (str != e) h = (_c_rotl(h, 4) ^ (h << 13)) + *str++; return h; } diff --git a/include/stc/cstr.h b/include/stc/cstr.h index 98b95e3d..41af7925 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -167,10 +167,9 @@ cstr_ends_with(cstr s, const char* sub) { } /* container adaptor functions: */ -#define cstr_toraw(xp) ((xp)->str) // deprecated #define cstr_compare(xp, yp) strcmp((xp)->str, (yp)->str) #define cstr_equals(xp, yp) (strcmp((xp)->str, (yp)->str) == 0) -#define cstr_hash(xp, ...) c_default_hash((xp)->str, cstr_size(*(xp))) +#define cstr_hash(xp, dummy) c_strhash((xp)->str) /* -------------------------- IMPLEMENTATION ------------------------- */ diff --git a/include/stc/csview.h b/include/stc/csview.h index 6733912d..d4ef0bd1 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -115,7 +115,7 @@ STC_INLINE bool cstr_ends_with_v(cstr s, csview sub) /* ---- Container helper functions ---- */ #define csview_compare(xp, yp) strcmp((xp)->str, (yp)->str) -#define csview_hash(xp, ...) c_default_hash((xp)->str, (xp)->size) +#define csview_hash(xp, dummy) c_strhash((xp)->str) #define csview_equals(xp, yp) (strcmp((xp)->str, (yp)->str) == 0) /* -------------------------- IMPLEMENTATION ------------------------- */ -- cgit v1.2.3