1

I have a key value store that has byte[] keys. Some of these keys will be used for longs (longs themselves, also Localdate and LocalTime instances).

I have a nice clean comparator, using standard Java and Guava:

    @Override
    public int compare(byte[] left, byte[] right) {
        long leftLong = Longs.fromByteArray(left);
        long rightLong = Longs.fromByteArray(right);
        return Long.compare(leftLong, rightLong);
    }

but it's slower than I would expect. Sorting 100,000 longs takes 100ms, whereas sorting 100,000 ints takes 6ms.

Is there a faster way to compare two longs, perhaps by avoiding the int conversion?

(You may be wondering if it really needs to be faster. If possible yes, as it will be called for every search, scan, insert, and delete of longs, dates, etc. into the store.)

L. Blanc
  • 2,150
  • 2
  • 21
  • 31

2 Answers2

3

I am not surprised it takes long: allocating and destroying an order of a trillion small objects seems taxing. Why not just compare arrays themselves?

public int compare(byte[] left, byte[] right) {
    int cmp = 0;
    for(int i = 0; i < 8 && cmp == 0; i++) { 
       cmp = (i == 0 || (left[i] >= 0 == right[i] >= 0)) ? left[i] - right[i] : right[i] - left[i]           
    }
    return cmp;
}
Dima
  • 39,570
  • 6
  • 44
  • 70
  • in original code 2 long values are created, in yours 2 ints, do you really think it will be different? – Iłya Bursov Dec 08 '15 at 22:11
  • 1) ints aren't created, they are stack variables; 2) in original code there is way more stuff created on stack inside the function calls. – Dima Dec 08 '15 at 22:13
  • 1. longs are stack variables too 2) jit can inline this, so nothing more is created. also note that Longs.fromByteArray will not use loop, but binary operations, which sometimes will be faster neither for with double comparison – Iłya Bursov Dec 08 '15 at 22:15
  • In repeated runs, this is 30-40% faster. Sorts correctly, too. – L. Blanc Dec 08 '15 at 22:15
  • @L.Blanc Glad I could help. Beware of sign bit though. I updated the answer to take care of it. – Dima Dec 08 '15 at 22:24
  • Since java7 you can also use Byte.compare(byte x, byte y) to make that long line shorter: https://docs.oracle.com/javase/8/docs/api/java/lang/Byte.html#compare-byte-byte- – Laszlo Hirdi Dec 09 '15 at 00:36
  • @Dima Sorry, I didn't test thoroughly enough earlier. The original code worked better in that it sorted negative numbers before positive numbers, but it didn't always sort numerically. The second code doesn't sort negatives first, and also doesn't always sort numerically. For example, they came out: 6655056367206398535 6899858597695139415 6899670273678872055. Hard to read, but the last one should be second. – L. Blanc Dec 09 '15 at 01:03
  • @LaszloHirdi Using Byte.compare produces similar incorrect results. Unfortunately, with longs there is more to comparing two values than comparing the values of each of their bytes in order. It would work for ints, tho. – L. Blanc Dec 09 '15 at 01:07
  • @L.Blanc Sorry about that. I think, I fixed it now. No, comparing bytes works the same for longs and ints, that's not the problem. It's the absence of an unsigned byte type in java that complicates things here. – Dima Dec 09 '15 at 01:37
  • @Dima Thanks. Tests pass now and it's a bit faster than my variation below, so I'll accept this as the answer. – L. Blanc Dec 09 '15 at 01:47
0

This is another variation. It is similar to the original, but effectively does the two byte to long transformations in a single loop. This improves performance about ~20%-30%. @Dima's version is faster.

    public static int compareLongs(byte[] left, byte[] right) {
        long leftLong = 0;
        long rightLong = 0;
        for (int i = 0; i < 8; i++) {
            leftLong <<= 8;
            rightLong <<= 8;
            leftLong |= (left[i] & 0xFF);
            rightLong|= (right[i] & 0xFF);
        }
        return Long.compare(leftLong, rightLong);
    }
L. Blanc
  • 2,150
  • 2
  • 21
  • 31
  • Now, this is weird. You are doing essentially the same thing Longs.fromByteArray() does, even a little bit more: you have 16 x (shift, or, and), and they would only have 14 ors and shifts (none needed for the lowest byte), plus you have a loop, and they don't. So, it seems like the only reason this version can be faster than the original is that you inline the long conversion rather than calling a function. I wonder if it would become even faster if you replace `Long.compare` with `leftLong - rightLong` – Dima Dec 09 '15 at 01:54
  • You have to use essentially the same approach as Longs.compare, because leftLong - rightLong returns a long, and casting it to an int would cause an error if it's to big. – L. Blanc Dec 09 '15 at 02:10
  • Yes, something like `if(leftLong == rightLong) return 0 else if (leftLong < rightLong) return -1 else return 1; ` I just mean to do that inline rather than calling a function, because the improvement you are getting in this version compared to the original seems to suggest that it is actually the function invocation that takes extra time, not creating the longs from bytes – Dima Dec 09 '15 at 02:26