blachlylab · charlesgregory · Aug 26, 2020 · Aug 26, 2020 · Aug 27, 2020
diff --git a/README.md b/README.md
@@ -1,19 +1,27 @@
 Library of efficient algorithms and data structures ported to templatized D
 from attractivechaos' generic C approach: https://github.com/attractivechaos/klib
 
-# khash
+# khash & khashl
 
 ## Fast
 
 Comparison with [emsi containers](https://github.com/dlang-community/containers) HashMap:
 
-Time, in msec, for n=500,000 operations benchmarked on linux VM; ldc2 -release
+Time, in msec, for n=500,000 operations with uint keys benchmarked on WSL; ldc2 -release
 
-| Operation         | HashMap | khash |
-|-------------------|---------|-------|
-| Insert            | 3573    | 2347  |
-| Retrieve (Serial) | 145     | 26    |
-| Retrieve (Random) | 282     | 84    |
+| Operation         | HashMap | khash | khashl |
+|-------------------|---------|-------|--------|
+| Insert            | 1168    | 411   | 401    |
+| Retrieve (Serial) | 83      | 20    | 110    |
+| Retrieve (Random) | 198     | 91    | 134    |
+
+Time, in msec, for n=500,000 operations with string keys benchmarked on WSL; ldc2 -release
+
+| Operation         | HashMap | khash | khashl | khashl (cached) |
+|-------------------|---------|-------|--------|-----------------|
+| Insert            | 1727    | 782   | 903    | 494             |
+| Retrieve (Serial) | 232     | 261   | 267    | 240             |
+| Retrieve (Random) | 404     | 420   | 422    | 422             |
 
 
 ## Notes
@@ -26,6 +34,10 @@ pass optional third template parameter `kh_is_map = false`.
 By default, memory allocated by the hashmap will be scanned by the GC.
 (pass optional fourth template parameter `useGC = false` to disable)
 
+For ```khashl```, hash caching can be enabled by passing an optional fourth
+ template parameter `cached = true`. This allows faster insertions for 
+ string keys.
+
 Can undergo static initialization (e.g. define as struct member
 with no extra init code needed in struct ctor), unlike
 [emsi containers](https://github.com/dlang-community/containers) HashMap.
@@ -36,6 +48,8 @@ with no extra init code needed in struct ctor), unlike
 ### Declaration
 ```D
 auto map = khash!(keytype, valuetype);
+auto map2 = khashl!(keytype, valuetype);
+auto map3 = khashl!(string, valuetype,true,true); // for hash-caching with strings
 ```
 
 ### Assignment / Insert

diff --git a/dub.json b/dub.json
@@ -10,6 +10,5 @@
 		"unittest-inline": {
 			"buildOptions": ["unittests", "optimize", "inline"]
 		}
-	},
-	"excludedSourceFiles": ["source/dklib/benchmark_khash.d"]
+	}
 }
diff --git a/examples/bench/benchmark_hashmaps.d b/examples/bench/benchmark_hashmaps.d
@@ -0,0 +1,108 @@
+/+dub.sdl:
+dependency "emsi_containers" version="~>0.7"
+dependency "dklib" path="../.."
++/
+import dklib.khash;
+import dklib.khashl;
+import containers;
+
+import std.datetime.stopwatch : StopWatch, AutoStart;
+import std.stdio;
+import std.uuid : randomUUID;
+
+string global_x; /// for benchmarking to prevent elision(?)
+uint global_y;
+
+int main()
+{
+    writeln("hashmap benchmarks");
+
+    enum NUMBER_OF_ITEMS = 500_000;
+
+    void testContainerInsert(T, alias Container, string ContainerName, bool cached = false)()
+    if(is(T == uint) || is(T == string))
+    {
+        static if(cached){
+            static assert(ContainerName == "khashl (cached)");
+            static if(is(T == uint)) auto c = Container!(uint, string,true,true,true)();
+            else auto c = Container!(string, uint,true,true,true)();
+        }else{
+            static if(is(T == uint)) auto c = Container!(uint, string)();
+            else auto c = Container!(string, uint)();
+        }
+
+        StopWatch sw = StopWatch(AutoStart.yes);
+        foreach (i; 0 .. NUMBER_OF_ITEMS)
+            //c.insert(i);
+            static if(is(T == uint)) c[i] = randomUUID().toString;
+            else c[randomUUID().toString] = i;
+        sw.stop();
+        writeln(T.stringof~" inserts for ", ContainerName, " finished in ",
+            sw.peek.total!"msecs", " milliseconds.");
+    }
+
+    void testContainerLookup(T, alias Container, string ContainerName, bool cached = false)()
+    if(is(T == uint) || is(T == string))
+    {
+        import std.random : uniform;
+
+        static if(cached){
+            static assert(ContainerName == "khashl (cached)");
+            static if(is(T == uint)) auto c = Container!(uint, string,true,true,true)();
+            else auto c = Container!(string, uint,true,true,true)();
+        }else{
+            static if(is(T == uint)) auto c = Container!(uint, string)();
+            else auto c = Container!(string, uint)();
+        }
+        // untimed insert
+        string[] items = new string[NUMBER_OF_ITEMS];
+        foreach (i; 0 .. NUMBER_OF_ITEMS)
+            items[i] = randomUUID().toString;
+        foreach (uint i,item; items)
+            static if(is(T == uint)) c[i] = item;
+            else c[item] = i;
+        StopWatch sw = StopWatch(AutoStart.yes);
+        // serial lookups
+        foreach (i; 0 .. NUMBER_OF_ITEMS)
+            static if(is(T == uint)) global_x = c[i];
+            else global_y = c[items[i]];
+        sw.stop();
+        writeln("Serial "~T.stringof~" lookups for ", ContainerName, " finished in ",
+            sw.peek.total!"msecs", " milliseconds.");
+
+        sw.reset();
+
+        // random lookups
+        sw.start();
+        foreach(i; 0 .. NUMBER_OF_ITEMS)
+            static if(is(T == uint)) global_x = c[ uniform(0, NUMBER_OF_ITEMS) ];
+            else global_y = c[ items[uniform(0, NUMBER_OF_ITEMS)] ];
+        sw.stop();
+        writeln("Random "~ T.stringof ~" lookups for ", ContainerName, " finished in ",
+            sw.peek.total!"msecs", " milliseconds.");
+
+        writeln("Confirming stored value of last lookup: ", global_x);
+    }
+
+    testContainerInsert!(uint, HashMap, "HashMap");
+    testContainerInsert!(uint, khash, "khash");
+    testContainerInsert!(uint, khashl, "khashl");
+    // testContainerInsert!(uint, khashl, "khashl (cached)",true);
+
+    testContainerInsert!(string, HashMap, "HashMap");
+    testContainerInsert!(string, khash, "khash");
+    testContainerInsert!(string, khashl, "khashl");
+    testContainerInsert!(string, khashl, "khashl (cached)",true);
+
+    testContainerLookup!(uint, HashMap, "HashMap");
+    testContainerLookup!(uint, khash, "khash");
+    testContainerLookup!(uint, khashl, "khashl");
+    // testContainerLookup!(uint, khashl, "khashl (cached)",true);
+
+    testContainerLookup!(string, HashMap, "HashMap");
+    testContainerLookup!(string, khash, "khash");
+    testContainerLookup!(string, khashl, "khashl");
+    testContainerLookup!(string, khashl, "khashl (cached)",true);
+
+    return 0;
+}
diff --git a/source/dklib/benchmark_khash.d b/source/dklib/benchmark_khash.d