From 73b1ed7c17b94647438c7e73738bf0820e5d57ad Mon Sep 17 00:00:00 2001
From: Tyge Løvset <tylo@norceresearch.no>
Date: Tue, 2 Nov 2021 20:31:21 +0100
Subject: Added benchmark to compare with Rust HashMap.

---
 benchmarks/.gitignore      |  1 -
 benchmarks/rust_cmap.c     | 52 ++++++++++++++++++++++++++++++++++++++++++++++
 benchmarks/rust_hashmap.rs | 44 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 96 insertions(+), 1 deletion(-)
 delete mode 100644 benchmarks/.gitignore
 create mode 100644 benchmarks/rust_cmap.c
 create mode 100644 benchmarks/rust_hashmap.rs

diff --git a/benchmarks/.gitignore b/benchmarks/.gitignore
deleted file mode 100644
index b883f1fd..00000000
--- a/benchmarks/.gitignore
+++ /dev/null
@@ -1 +0,0 @@
-*.exe
diff --git a/benchmarks/rust_cmap.c b/benchmarks/rust_cmap.c
new file mode 100644
index 00000000..6014b23d
--- /dev/null
+++ b/benchmarks/rust_cmap.c
@@ -0,0 +1,52 @@
+#include <time.h>
+#include <stdio.h>
+#define i_key uint64_t
+#define i_val uint64_t
+#define i_hash c_default_hash64
+#define i_tag u64
+#include <stc/cmap.h>
+
+uint64_t romu_rotl(uint64_t val, uint32_t r)
+    { return (val << r) | (val >> (64 - r)); }
+
+uint64_t romu_trio(uint64_t s[3]) {
+   const uint64_t xp = s[0], yp = s[1], zp = s[2];
+   s[0] = 15241094284759029579u * zp;
+   s[1] = yp - xp; s[1] = romu_rotl(s[1], 12);
+   s[2] = zp - yp; s[2] = romu_rotl(s[2], 44);
+   return xp;
+}
+
+int main() {
+    c_auto (cmap_u64, m) {
+        const size_t n = 50000000, mask = (1 << 25) - 1; 
+        cmap_u64_max_load_factor(&m, 0.8); cmap_u64_reserve(&m, n);
+        uint64_t rng[3] = {1872361123, 123879177, 87739234}, sum, ms = CLOCKS_PER_SEC/1000;
+        printf("STC cmap  n = %zu, mask = 0x%zx\n", n, mask);
+        clock_t now = clock();
+        c_forrange (n) {
+            uint64_t key = romu_trio(rng) & mask;
+            cmap_u64_insert(&m, key, 0).ref->second += 1;
+            
+        }
+        printf("insert  : %zums  \tsize : %zu\n", (clock() - now)/ms, cmap_u64_size(m));
+        now = clock();
+        sum = 0;
+        c_forrange (key, mask + 1) { sum += cmap_u64_contains(&m, key); }
+        printf("lookup  : %zums  \tsum  : %zu\n", (clock() - now)/ms, sum);
+
+        now = clock();
+        sum = 0;
+        c_foreach (i, cmap_u64, m) { sum += i.ref->second; }
+        printf("iterate : %zums  \tsum  : %zu\n", (clock() - now)/ms, sum);
+
+        uint64_t rng2[3] = {1872361123, 123879177, 87739234};
+        now = clock();
+        c_forrange (n) {
+            uint64_t key = romu_trio(rng2) & mask;
+            cmap_u64_erase(&m, key);
+        }
+        printf("remove  : %zums  \tsize : %zu\n", (clock() - now)/ms, cmap_u64_size(m));
+        printf("press a key:\n"); getchar();
+    }
+}
\ No newline at end of file
diff --git a/benchmarks/rust_hashmap.rs b/benchmarks/rust_hashmap.rs
new file mode 100644
index 00000000..d1372e8b
--- /dev/null
+++ b/benchmarks/rust_hashmap.rs
@@ -0,0 +1,44 @@
+use std::time::{Instant};
+use std::io::Read;
+
+fn romu_rotl(val: u64, r: u32) -> u64
+    { return (val << r) | (val >> (64 - r)); }
+
+fn romu_trio(s: &mut[u64]) -> u64 {
+    let xp = s[0]; let yp = s[1]; let zp = s[2];
+    s[0] = 15241094284759029579 * zp;
+    s[1] = yp - xp; s[1] = romu_rotl(s[1], 12);
+    s[2] = zp - yp; s[2] = romu_rotl(s[2], 44);
+    return xp;
+}
+
+fn main() {
+    let n = 50_000_000; let mask = (1 << 25) - 1;
+    let mut m = std::collections::HashMap::<u64, u64>::with_capacity(n);
+    let mut rng: [u64; 3] = [1872361123, 123879177, 87739234];
+    println!("Rust HashMap  n = {}, mask = {:#x}", n, mask);
+    let now = Instant::now();
+    for _i in 0..n {
+        let key: u64 = romu_trio(&mut rng) & mask;
+        *m.entry(key).or_insert(0) += 1;
+    }
+    println!("insert  : {}ms  \tsize : {}", now.elapsed().as_millis(), m.len());
+    let now = Instant::now();
+    let mut sum = 0;
+    for i in 0..mask + 1 { if m.contains_key(&i) { sum += 1; }}
+    println!("lookup  : {}ms  \tsum  : {}", now.elapsed().as_millis(), sum);
+
+    let now = Instant::now();
+    let mut sum = 0;
+    for (_, value) in &m { sum += value; }
+    println!("iterate : {}ms  \tsum  : {}", now.elapsed().as_millis(), sum);
+
+    let mut rng: [u64; 3] = [1872361123, 123879177, 87739234];
+    let now = Instant::now();
+    for _ in 0..n {
+        let key: u64 = romu_trio(&mut rng) & mask;
+        m.remove(&key);
+    }
+    println!("remove  : {}ms  \tsize : {}", now.elapsed().as_millis(), m.len());
+    println!("press a key:"); std::io::stdin().bytes().next();
+}
\ No newline at end of file
-- 
cgit v1.2.3