Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: jruby/jruby
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 0cb3433d9c8c
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: cb4581c2005f
Choose a head ref
  • 4 commits
  • 1 file changed
  • 2 contributors

Commits on May 5, 2014

  1. Avoid manual unroll of non-hot SipHash loops 

    As these loops will be executed only once for every #hash invokation,
it would make sense to defer the decision to unroll the loops to the
runtime.
    @grddev
    grddev committed May 5, 2014
    Copy the full SHA
    23570f5 View commit details

  2. Hoist SipHashInline range checks 

    In principle, this should allow the JIT compiler to remove all range
checks within the loop. I haven't had time to verify this though.
    @grddev
    grddev committed May 5, 2014
    Copy the full SHA
    43b2ef4 View commit details

  3. Use Unsafe to read a long at a time 

    While one could wish that JIT compilation optimised the eight sequential
byte reads into a single long read, it in fact does not.

This implementation should fallback to the slow implementation in a
context where Unsafe fails to load, but I haven't figured out how to
test that properly.
    @grddev
    grddev committed May 5, 2014
    Copy the full SHA
    c02fcd7 View commit details

Commits on Nov 2, 2014

  1. Merge pull request #1681 from grddev/unsafe-siphash-opt 

    Optimize SipHash using sun.misc.Unsafe
    @headius
    headius committed Nov 2, 2014
    Copy the full SHA
    cb4581c View commit details
Showing with 65 additions and 45 deletions.
  1. +65 −45 core/src/main/java/org/jruby/util/SipHashInline.java
110 changes: 65 additions & 45 deletions core/src/main/java/org/jruby/util/SipHashInline.java
View file
Original file line number Diff line number Diff line change
@@ -1,5 +1,11 @@
package org.jruby.util;

import java.nio.ByteOrder;

import org.jruby.util.unsafe.UnsafeHolder;

import sun.misc.Unsafe;

/**
* SipHash implementation with hand inlining the SIPROUND.
*
@@ -23,17 +29,16 @@ public static long hash24(long k0, long k1, byte[] src, int offset, int length)
int last = offset + length / 8 * 8;
int i = offset;

if (offset < 0) {
throw new ArrayIndexOutOfBoundsException(offset);
} else if (offset + length > src.length) {
throw new ArrayIndexOutOfBoundsException(src.length);
}

// processing 8 bytes blocks in data
while (i < last) {
// pack a block to long, as LE 8 bytes
m = (long) src[i++] |
(long) src[i++] << 8 |
(long) src[i++] << 16 |
(long) src[i++] << 24 |
(long) src[i++] << 32 |
(long) src[i++] << 40 |
(long) src[i++] << 48 |
(long) src[i++] << 56 ;
m = LongReader.INSTANCE.getLong(src, i);
i += 8;
// MSGROUND {
v3 ^= m;

@@ -110,6 +115,7 @@ public static long hash24(long k0, long k1, byte[] src, int offset, int length)
m |= (long) length << 56;
// MSGROUND {
v3 ^= m;
for (int j = 0; j < 2; j++) {
// SIPROUND {
v0 += v1; v2 += v3;
v1 = (v1 << 13) | v1 >>> 51; v3 = (v3 << 16) | v3 >>> 48;
@@ -119,20 +125,13 @@ public static long hash24(long k0, long k1, byte[] src, int offset, int length)
v3 = (v3 << 21) | v3 >>> 43; v1 ^= v2;
v3 ^= v0; v2 = (v2 << 32) | v2 >>> 32;
// }
// SIPROUND {
v0 += v1; v2 += v3;
v1 = (v1 << 13) | v1 >>> 51; v3 = (v3 << 16) | v3 >>> 48;
v1 ^= v0; v3 ^= v2;
v0 = (v0 << 32) | v0 >>> 32; v2 += v1;
v0 += v3; v1 = (v1 << 17) | v1 >>> 47;
v3 = (v3 << 21) | v3 >>> 43; v1 ^= v2;
v3 ^= v0; v2 = (v2 << 32) | v2 >>> 32;
// }
}
v0 ^= m;
// }

// finishing...
v2 ^= 0xff;
for (int j = 0; j < 4; j++) {
// SIPROUND {
v0 += v1; v2 += v3;
v1 = (v1 << 13) | v1 >>> 51; v3 = (v3 << 16) | v3 >>> 48;
@@ -142,33 +141,54 @@ public static long hash24(long k0, long k1, byte[] src, int offset, int length)
v3 = (v3 << 21) | v3 >>> 43; v1 ^= v2;
v3 ^= v0; v2 = (v2 << 32) | v2 >>> 32;
// }
// SIPROUND {
v0 += v1; v2 += v3;
v1 = (v1 << 13) | v1 >>> 51; v3 = (v3 << 16) | v3 >>> 48;
v1 ^= v0; v3 ^= v2;
v0 = (v0 << 32) | v0 >>> 32; v2 += v1;
v0 += v3; v1 = (v1 << 17) | v1 >>> 47;
v3 = (v3 << 21) | v3 >>> 43; v1 ^= v2;
v3 ^= v0; v2 = (v2 << 32) | v2 >>> 32;
// }
// SIPROUND {
v0 += v1; v2 += v3;
v1 = (v1 << 13) | v1 >>> 51; v3 = (v3 << 16) | v3 >>> 48;
v1 ^= v0; v3 ^= v2;
v0 = (v0 << 32) | v0 >>> 32; v2 += v1;
v0 += v3; v1 = (v1 << 17) | v1 >>> 47;
v3 = (v3 << 21) | v3 >>> 43; v1 ^= v2;
v3 ^= v0; v2 = (v2 << 32) | v2 >>> 32;
// }
// SIPROUND {
v0 += v1; v2 += v3;
v1 = (v1 << 13) | v1 >>> 51; v3 = (v3 << 16) | v3 >>> 48;
v1 ^= v0; v3 ^= v2;
v0 = (v0 << 32) | v0 >>> 32; v2 += v1;
v0 += v3; v1 = (v1 << 17) | v1 >>> 47;
v3 = (v3 << 21) | v3 >>> 43; v1 ^= v2;
v3 ^= v0; v2 = (v2 << 32) | v2 >>> 32;
// }
}
return v0 ^ v1 ^ v2 ^ v3;
}

private static abstract class LongReader {
public abstract long getLong(byte[] src, int offset);

public static final LongReader INSTANCE = createBestLongReader();

private static LongReader createBestLongReader() {
try {
if (UnsafeHolder.U != null) {
if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
return new UnsafeLongReader(UnsafeHolder.U);
}
}
} catch (Exception e) {
}
return new FallbackLongReader();
}

private static final class FallbackLongReader extends LongReader {
@Override
public long getLong(byte[] src, int offset) {
return (long) src[offset++] |
(long) src[offset++] << 8 |
(long) src[offset++] << 16 |
(long) src[offset++] << 24 |
(long) src[offset++] << 32 |
(long) src[offset++] << 40 |
(long) src[offset++] << 48 |
(long) src[offset++] << 56 ;
}
}

private static final class UnsafeLongReader extends LongReader {
final Unsafe unsafe;
final int byteArrayBaseOffset;

public UnsafeLongReader(Unsafe unsafe) {
this.unsafe = unsafe;
this.byteArrayBaseOffset = unsafe.arrayBaseOffset(byte[].class);
}

@Override
public final long getLong(byte[] src, int offset) {
return unsafe.getLong(src, byteArrayBaseOffset + (long)offset);
}
}
}
}