Skip to content

Instantly share code, notes, and snippets.

@ssvb
Created February 20, 2022 17:47
Show Gist options
  • Save ssvb/a9f0fc9c8ff9d01a11829dcc7356fb90 to your computer and use it in GitHub Desktop.
Save ssvb/a9f0fc9c8ff9d01a11829dcc7356fb90 to your computer and use it in GitHub Desktop.
Benchmark AHash vs. FxHash vs. FunnyHash in Crystal language (can be run at https://atcoder.jp/contests/practice/custom_test for example)
require "benchmark"
# Access two 64-bit random seed values
struct Crystal::Hasher
def self.get_seed
@@seed
end
end
# Implementation of FunnyHash from
# https://github.com/crystal-lang/crystal/blob/1.3.2/src/crystal/hasher.cr#L82-L110
struct FunnyHash
private C1 = 0xacd5ad43274593b9_u64
private C2 = 0x6956abd6ed268a3d_u64
def initialize(@a : UInt64 = Crystal::Hasher.get_seed[0], @b : UInt64 = Crystal::Hasher.get_seed[1])
end
private def rotl32(v : UInt64)
(v.unsafe_shl(32)) | (v.unsafe_shr(32))
end
def permute(v : UInt64)
@a = rotl32(@a ^ v) &* C1
@b = (rotl32(@b) ^ v) &* C2
self
end
def result
a, b = @a, @b
a ^= (a.unsafe_shr(23)) ^ (a.unsafe_shr(40))
b ^= (b.unsafe_shr(23)) ^ (b.unsafe_shr(40))
a &*= C1
b &*= C2
a ^= a.unsafe_shr(32)
b ^= b.unsafe_shr(32)
a &+ b
end
end
# Implementation of FxHash from
# https://github.com/rust-lang/rustc-hash/blob/master/src/lib.rs#L64-L81
#
# This hash has no DOS resistance at all. It can be easily reversed to
# generate collisions in lower bits via taking a set of multiples of 2^16
# and multiplying each of them by 0x2040003d780970bd, see:
# https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/
#
# But let's pretend to implement some useless randomization and benchmark it.
struct FxHash
def initialize(@a : UInt64 = Crystal::Hasher.get_seed[0])
end
def permute(v : UInt64)
@a = 0x517cc1b727220a95_u64 &* (@a ^ v)
self
end
def result
@a
end
end
# Implementation of AHash Fallback (AES is not available) from
# https://github.com/tkaitchuck/aHash/blob/master/src/fallback_hash.rs
#
# Crystal code for testing:
#
# hasher = AHash.new(0x243f_6a88_85a3_08d3, 0x1319_8a2e_0370_7344)
# hasher.permute(0)
# puts "%x" % hasher.result
#
# Rust code for testing:
#
# let mut hasher = AHasher::new_with_keys(0, 0);
# hasher.write_u64(0);
# println!("{:x}\n", hasher.finish());
#
# Both should print "cdbcdc77cd2af225"
#
# Note: AHash apparently has some shortcuts with fewer calculations for
# basic integer types, accessible via a slightly different API.
# High performance code should probably take advantage of these
# shortcuts, so improvements are possible.
struct AHash
private MULTIPLE = 6364136223846793005_u64
def initialize(@buffer : UInt64 = Crystal::Hasher.get_seed[0], @pad : UInt64 = Crystal::Hasher.get_seed[1])
end
private def rotl(v : UInt64, rot : UInt64) : UInt64
LibIntrinsics.fshl64(v, v, rot)
end
private def folded_multiply(a : UInt64, b : UInt64) : UInt64
tmp = a.to_u128 &* b
tmp.unsafe_as(UInt64) ^ tmp.unsafe_shr(64)
end
def permute(v : UInt64)
@buffer = folded_multiply(@buffer ^ v, MULTIPLE)
self
end
def result
rot = @buffer & 63
rotl(folded_multiply(@buffer, @pad), rot)
end
end
# https://llvm.org/docs/LangRef.html#llvm-fshl-intrinsic
lib LibIntrinsics
fun fshl64 = "llvm.fshl.i64"(a : UInt64, b : UInt64, c : UInt64) : UInt64
fun fshr64 = "llvm.fshr.i64"(a : UInt64, b : UInt64, c : UInt64) : UInt64
end
###############################################################################
def funnyhash_u64(v : UInt64)
h = FunnyHash.new
h.permute(v)
h.result
end
def fxhash_u64(v : UInt64)
h = FxHash.new
h.permute(v)
h.result
end
def ahash_u64(v : UInt64)
h = AHash.new
h.permute(v)
h.result
end
###############################################################################
n = 500000000_u64
v = 0_u64
puts "== Dependency chain (typical usage) =="
Benchmark.bm do |x|
x.report("FunnyHash:") do
n.times { v = funnyhash_u64(v) }
end
x.report("FxHash:") do
n.times { v = fxhash_u64(v) }
end
x.report("AHash:") do
n.times { v = ahash_u64(v) }
end
end
puts "\n== Instruction level parallelism is possible (synthetic benchmark) =="
Benchmark.bm do |x|
x.report("FunnyHash:") do
v = n.times.reduce(v) {|sum, val| sum &+ funnyhash_u64(val) }
end
x.report("FxHash:") do
v = n.times.reduce(v) {|sum, val| sum &+ fxhash_u64(val) }
end
x.report("AHash:") do
v = n.times.reduce(v) {|sum, val| sum &+ ahash_u64(val) }
end
end
abort "oops, 'v' is still somehow zero\n" if v == 0
@ssvb
Copy link
Author

ssvb commented Feb 20, 2022

Revision 1 run at https://atcoder.jp/contests/practice/custom_test

== Dependency chain (typical usage) ==
                 user     system      total        real
FunnyHash:   2.225762   0.000000   2.225762 (  2.232963)
FxHash:      0.556493   0.000000   0.556493 (  0.556504)
AHash:       1.717990   0.000000   1.717990 (  1.718039)

== Instruction level parallelism is possible (synthetic benchmark) ==
                 user     system      total        real
FunnyHash:   1.113163   0.000000   1.113163 (  1.113178)
FxHash:      0.240055   0.000000   0.240055 (  0.240068)
AHash:       0.636653   0.000000   0.636653 (  0.636664)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment