More update on hash. Added string_bench.c+cpp.

6 files changed, 359 insertions, 9 deletions

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 <time.h>

+

+#define i_val_str

+#include <stc/cvec.h>

+

+#define i_key_str

+#define i_val size_t

+#include <stc/cmap.h>

+

+#define i_key_str

+#define i_val size_t

+#include <stc/csmap.h>

+

+

+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 <iostream>

+#include <iomanip>

+#include <chrono>

+#include <string>

+#include <vector>

+#include <map>

+#include <unordered_map>

+

+#define i_val_str

+#include <stc/cvec.h>

+

+

+std::vector<std::string> read_file(const char* name)

+{

+    std::vector<std::string> 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<std::chrono::milliseconds>(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<std::string>& 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<std::string>& 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<std::string>& vs, 

+                   std::map<std::string, size_t>& mapNormal,

+                   std::unordered_map<std::string, size_t>& 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<std::string_view>;  // 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<std::string>& vec_string,

+    const std::map<std::string, size_t>& mapNormal,

+    const std::unordered_map<std::string, size_t>& unordmapNormal);

+

+const size_t MAX_LOOP = 2000;

+

+int main()

+{

+    std::vector<std::string> vec_string;

+

+    std::map<std::string, size_t> mapNormal;

+    std::unordered_map<std::string, size_t> 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<std::string>& vec_string, 

+    const std::map<std::string, size_t>& mapNormal,

+    const std::unordered_map<std::string, size_t>& 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 ------------------------- */