Benchmark AHash vs. FxHash vs. FunnyHash in Crystal language (can be run at https://atcoder.jp/contests/practice/custom_test for example)

bench_ahash.cr

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

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)