Commit f67ce1e35f

Sahnvour <sahnvour@pm.me>
2020-07-26 22:08:48
make use of hasUniqueRepresentation to speed up hashing facilities, fastpath in getAutoHashFn is particularly important for hashmap performance
gives a 1.18x speedup on gotta-go-fast hashmap bench
1 parent 345cb32
Changed files (2)
lib/std/hash/auto_hash.zig
@@ -56,9 +56,6 @@ pub fn hashPointer(hasher: anytype, key: anytype, comptime strat: HashStrategy)
 pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
     switch (strat) {
         .Shallow => {
-            // TODO detect via a trait when Key has no padding bits to
-            // hash it as an array of bytes.
-            // Otherwise, hash every element.
             for (key) |element| {
                 hash(hasher, element, .Shallow);
             }
@@ -75,6 +72,12 @@ pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) vo
 /// Strategy is provided to determine if pointers should be followed or not.
 pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
     const Key = @TypeOf(key);
+
+    if (strat == .Shallow and comptime meta.trait.hasUniqueRepresentation(Key)) {
+        @call(.{ .modifier = .always_inline }, hasher.update, .{mem.asBytes(&key)});
+        return;
+    }
+
     switch (@typeInfo(Key)) {
         .NoReturn,
         .Opaque,
@@ -119,9 +122,6 @@ pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
         },
 
         .Struct => |info| {
-            // TODO detect via a trait when Key has no padding bits to
-            // hash it as an array of bytes.
-            // Otherwise, hash every field.
             inline for (info.fields) |field| {
                 // We reuse the hash of the previous field as the seed for the
                 // next one so that they're dependant.
lib/std/hash_map.zig
@@ -5,6 +5,7 @@ const testing = std.testing;
 const math = std.math;
 const mem = std.mem;
 const meta = std.meta;
+const trait = meta.trait;
 const autoHash = std.hash.autoHash;
 const Wyhash = std.hash.Wyhash;
 const Allocator = mem.Allocator;
@@ -1023,9 +1024,13 @@ pub fn getTrivialEqlFn(comptime K: type) (fn (K, K) bool) {
 pub fn getAutoHashFn(comptime K: type) (fn (K) u32) {
     return struct {
         fn hash(key: K) u32 {
-            var hasher = Wyhash.init(0);
-            autoHash(&hasher, key);
-            return @truncate(u32, hasher.final());
+            if (comptime trait.hasUniqueRepresentation(K)) {
+                return @truncate(u32, Wyhash.hash(0, std.mem.asBytes(&key)));
+            } else {
+                var hasher = Wyhash.init(0);
+                autoHash(&hasher, key);
+                return @truncate(u32, hasher.final());
+            }
         }
     }.hash;
 }