Unsafe: efficiently comparing two byte arrays

[Paul Sandoz]

On Feb 26, 2014, at 6:21 PM, Martin Buchholz <martinrb at google.com> wrote:

> Every once in  a while I see an attempt to introduce a "general purpose" unsafe array class, but efforts stall due to:

Yes, in general this is "arrays 2.0" stuff, which is tricky especially since on and off-heap seem to have conflicting requirements (the latter might require some form of explicit layout where as for the former it would be better to let hotspot work out what to do with better GC mechanisms).


Mostly in the context of just comparing byte arrays:

> - it's not obvious whether unaligned access to e.g. 8 bytes via long is even possible or more efficient than just reading 8 bytes
> - endianness is an issue

In Guava's implementation there is an optimization for big endian natural byte order and a clever trick otherwise:

        for (int i = 0; i < minWords * Longs.BYTES; i += Longs.BYTES) {
          long lw = theUnsafe.getLong(left, BYTE_ARRAY_BASE_OFFSET + (long) i);
          long rw = theUnsafe.getLong(right, BYTE_ARRAY_BASE_OFFSET + (long) i);
          if (lw != rw) {
            if (BIG_ENDIAN) {
              return UnsignedLongs.compare(lw, rw);
            }

            /*
             * We want to compare only the first index where left[index] != right[index].
             * This corresponds to the least significant nonzero byte in lw ^ rw, since lw
             * and rw are little-endian.  Long.numberOfTrailingZeros(diff) tells us the least
             * significant nonzero bit, and zeroing out the first three bits of L.nTZ gives us the
             * shift to get that least significant nonzero byte.
             */
            int n = Long.numberOfTrailingZeros(lw ^ rw) & ~0x7;
            return (int) (((lw >>> n) & UNSIGNED_MASK) - ((rw >>> n) & UNSIGNED_MASK));
          }
        }

> - for best performance, you also want to elide those pesky array bound checks (but hotspot can do a better job of that)
> 

No such checks are provided by Unsafe :-)

For loops a check can often be hoisted out (i think hotspot already can do that). Recently there have been some optimisations implemented for "(i & (a.length - 1))" patterns (e.g. see HashMap). But there are always gonna be cases where it cannot fully remove such checks and people reach for Unsafe to save some cycles.


> I think it's worth doing, but it's harder than it looks, and probably needs help from the VM via intrinsics.
> 

> ---
> 
> lexicographicalComparator saves a lot of cycles.
> 

Yes, in this context we can provide such methods and over time they could be modified to benefit from any future improvements.

Just trying to whittle down small use-cases as to why Unsafe is currently used today.

Paul.