java – ** BUSTED **如何使用sun.misc.Unsafe加快字节[]查找速

每次读取4字节int或8字节更有效.我写了两个函数来做同样的事情：比较两个字节[]的内容,看看它们是否相同：

功能1：

public static boolean hadoopEquals(byte[] b1,byte[] b2)
  {
    if(b1 == b2)
    {
      return true;
    }
    if(b1.length != b2.length)
    {
      return false;
    }
    // Bring WritableComparator code local

    for(int i = 0;i < b1.length; ++i)
    {
     int a = (b1[i] & 0xff);
     int b = (b2[i] & 0xff);
     if (a != b) 
     {
       return false;
     }
    }
    return true;
  }

功能2：

public static boolean goodEquals(byte[] b1,byte[] b2)
  {   
    if(b1 == b2)
    {
      return true;
    }
    if(b1.length != b2.length)
    {
      return false;
    }
    int baSEOffset = UnSafe.arrayBaSEOffset(byte[].class);

    int numLongs = (int)Math.ceil(b1.length / 8.0);

    for(int i = 0;i < numLongs; ++i)
    {
      long currentOffset = baSEOffset + (i * 8);
      long l1 = UnSafe.getLong(b1,currentOffset);
      long l2 = UnSafe.getLong(b2,currentOffset);
      if(0L != (l1 ^ l2))
      {
        return false;
      }
    }
    return true;    
  }

我在笔记本电脑上运行了这两个功能(corei7 2630QM,8GB DDR3,64bit win 7,64bit Hotspot JVM),比较两个400MB byte [],结果如下：

功能1：~670ms

功能2：~80ms

2更快.

所以我的建议是每次读取8字节并使用XOR运算符(^)：

long l1 = UnSafe.getLong(byteArray,offset);  //8 byte
if(0L == l1 ^ 0xFF)  //if the lowest byte == 0?
/* do something */
if(0L == l1 ^ 0xFF00)  //if the 2nd lowest byte == 0?
/* do something */
/* go on... */

================================================== ==========================

嗨威尔夫,
我使用你的代码创建一个测试类,如下所示,这个类比较了查找字节数组中第一个0的3个函数之间的速度：

package test;

import java.lang.reflect.Field;

import sun.misc.Unsafe;

/**
 * Test the speed in looking up the 1st 0 in a byte array
 * Set -Xms the same as -Xms to avoid Heap reallocation
 * 
 * @author yellowb
 *
 */
public class StackOverflow
{
    public static Unsafe UnSafe;

    public static Unsafe getUnsafe() throws SecurityException,NoSuchFieldException,IllegalArgumentException,IllegalAccessException
    {
        Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
        theUnsafe.setAccessible(true);
        Unsafe unsafe = (Unsafe) theUnsafe.get(null);
        return unsafe;
    }

    /**
     * use 'byte[index]' form to read 1 byte every time
     * @param buf
     */
    public static void normalLookup(byte[] buf)
    {
        for (int i = 0; i < buf.length; ++i)
        {
            if ((byte) 0 == buf[i])
            {
                System.out.println("The 1st '0' is at position : " + i);
                return;
            }
        }
        System.out.println("Not found '0'");
    }

    /**
     * use Unsafe.getByte to read 1 byte every time directly from the memory
     * @param buf
     */
    public static void unsafeLookup_1B(byte[] buf)
    {
        int baSEOffset = UnSafe.arrayBaSEOffset(byte[].class);
        for (int i = 0; i < buf.length; ++i)
        {
            byte b = UnSafe.getByte(buf,(long) (baSEOffset + i));
            if (0 == ((int) b & 0xFF))
            {
                System.out.println("The 1st '0' is at position : " + i);
                return;
            }

        }
        System.out.println("Not found '0'");
    }

    /**
     * use Unsafe.getLong to read 8 byte every time directly from the memory
     * @param buf
     */
    public static void unsafeLookup_8B(byte[] buf)
    {
        int baSEOffset = UnSafe.arrayBaSEOffset(byte[].class);

        //The first (numLongs * 8) bytes will be read by Unsafe.getLong in below loop
        int numLongs = buf.length / 8;
        long currentOffset = 0L;
        for (int i = 0; i < numLongs; ++i)
        {
            currentOffset = baSEOffset + (i * 8);  //the step is 8 bytes
            long l = UnSafe.getLong(buf,currentOffset);
            //Compare each byte(in the 8-Byte long) to 0
            //PS:x86 cpu is little-endian mode
            if (0L == (l & 0xFF))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8));
                return;
            }
            if (0L == (l & 0xFF00L))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8 + 1));
                return;
            }
            if (0L == (l & 0xFF0000L))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8 + 2));
                return;
            }
            if (0L == (l & 0xFF000000L))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8 + 3));
                return;
            }
            if (0L == (l & 0xFF00000000L))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8 + 4));
                return;
            }
            if (0L == (l & 0xFF0000000000L))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8 + 5));
                return;
            }
            if (0L == (l & 0xFF000000000000L))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8 + 6));
                return;
            }
            if (0L == (l & 0xFF00000000000000L))
            {
                System.out.println("The 1st '0' is at position : " + (i * 8 + 7));
                return;
            }
        }

        //If some rest bytes exists
        int rest = buf.length % 8;
        if(0 != rest)
        {
            currentOffset = currentOffset + 8;
            //Because the length of rest bytes < 8,we have to read them one by one
            for(; currentOffset < (baSEOffset + buf.length); ++currentOffset)
            {
                byte b = UnSafe.getByte(buf,(long)currentOffset);
                if (0 == ((int) b & 0xFF))
                {
                    System.out.println("The 1st '0' is at position : " + (currentOffset - baSEOffset));
                    return;
                }
            }
        }
        System.out.println("Not found '0'");
    }

    public static void main(String[] args) throws SecurityException,IllegalAccessException
    {
        UnSafe = getUnsafe();

        int len = 1024 * 1024 * 1024;  //1G
        long startTime = 0L;
        long endTime = 0L;

        System.out.println("initialize data...");
        byte[] byteArray1 = new byte[len];
        for (int i = 0; i < len; ++i)
        {
            byteArray1[i] = (byte) (i % 128 + 1);  //No byte will equal to 0
        }
        //If you want to set one byte to 0,uncomment the below statement
//      byteArray1[2500] = (byte)0;
        System.out.println("initialize data done!");

        System.out.println("use normalLookup()...");
        startTime = System.nanoTime();
        normalLookup(byteArray1);
        endTime = System.nanoTime();
        System.out.println("time : " + ((endTime - startTime) / 1000) + " us.");

        System.out.println("use unsafeLookup_1B()...");
        startTime = System.nanoTime();
        unsafeLookup_1B(byteArray1);
        endTime = System.nanoTime();
        System.out.println("time : " + ((endTime - startTime) / 1000) + " us.");

        System.out.println("use unsafeLookup_8B()...");
        startTime = System.nanoTime();
        unsafeLookup_8B(byteArray1);
        endTime = System.nanoTime();
        System.out.println("time : " + ((endTime - startTime) / 1000) + " us.");
    }
}

输出是：

initialize data...
initialize data done!
use normalLookup()...
Not found '0'
time : 1271781 us.
use unsafeLookup_1B()...
Not found '0'
time : 716898 us.
use unsafeLookup_8B()...
Not found '0'
time : 591689 us.

结果表明,每次使用Unsafe.getByte()读取1个字节比定期迭代byte []要快得多.读取8个字节的长度是最快的.