jruby/jruby — pull request #1681 by grddev (2014-05-05 09:56:40+00:00)
Title: Optimize SipHash using sun.misc.Unsafe

As SipHash is designed to consume the inputs 8 bytes at a time, a key part of the algorithm is reading the eight bytes as once. Unfortunately, there is no way to directly read eight bytes at once from a byte array without resorting to `Unsafe`. This implements the unsafe operation with a fallback on the original slow implementation for cases where `Unsafe` cannot be loaded (or where the native byte ordering is not little endian, as needed by SipHash).

The following performance comparison that tries strings of increasing lengths shows that the unsafe implementation is roughly 25% faster for really long strings, and about the same speed for short strings.

require 'benchmark'

N = 30_000_000

puts RUBY_DESCRIPTION
Benchmark.bmbm do |x|
[0,1,8,16,32,64,1024,65536].each do |len|
string = 'x'*len
n = N/(0.25*len+10) + N/20_000
x.report(len.to_s) { n.to_i.times { string.hash } }
end
end

jruby 1.7.12 (1.9.3p392) 2014-04-15 643e292 on Java HotSpot(TM) 64-Bit Server VM 1.8.0_05-b13 [darwin-x86_64]

user system total real
0 0.650000 0.000000 0.650000 ( 0.653000)
1 0.630000 0.000000 0.630000 ( 0.626000)
8 0.600000 0.010000 0.610000 ( 0.599000)
16 0.590000 0.000000 0.590000 ( 0.584000)
32 0.570000 0.000000 0.570000 ( 0.573000)
64 0.550000 0.000000 0.550000 ( 0.541000)
1024 0.470000 0.000000 0.470000 ( 0.471000)
65536 0.780000 0.000000 0.780000 ( 0.783000)

jruby 1.7.13-SNAPSHOT (1.9.3p392) 2014-05-01 c02fcd7 on Java HotSpot(TM) 64-Bit Server VM 1.8.0_05-b13 [darwin-x86_64]

user system total real
0 0.650000 0.000000 0.650000 ( 0.643000)
1 0.660000 0.000000 0.660000 ( 0.654000)
8 0.610000 0.010000 0.620000 ( 0.608000)
16 0.570000 0.000000 0.570000 ( 0.559000)
32 0.530000 0.000000 0.530000 ( 0.527000)
64 0.440000 0.000000 0.440000 ( 0.442000)
1024 0.350000 0.000000 0.350000 ( 0.342000)
65536 0.580000 0.000000 0.580000 ( 0.583000)

Running the same benchmark against PerlHash, we can see that the unsafe implementation of SipHash is about the same speed for strings around length 64, and for longer strings the unsafe implementation of SipHash is significantly faster than PerlHash:

user system total real
0 0.460000 0.000000 0.460000 ( 0.452000)
1 0.420000 0.000000 0.420000 ( 0.416000)
8 0.440000 0.000000 0.440000 ( 0.444000)
16 0.430000 0.010000 0.440000 ( 0.422000)
32 0.410000 0.000000 0.410000 ( 0.414000)
64 0.470000 0.000000 0.470000 ( 0.462000)
1024 0.420000 0.000000 0.420000 ( 0.425000)
65536 0.750000 0.000000 0.750000 ( 0.750000)

Even though this implementation of SipHash is faster than the previous, I don't think it is fast enough to replace PerlHash entirely, as the majority of `Hash` keys are most probably predominantly short strings. Keep in mind though, that the 20% difference in PerlHash's advantage represents less than 100ns per invokation, whereas the 20% difference in SipHash's advantage represents a much longer time.