java - 可以优化数组访问吗？

Question

也许我被我的分析器 (Netbeans) 误导了，但我看到了一些奇怪的行为，希望这里有人可以帮助我理解它。

我正在开发一个应用程序，它大量使用相当大的哈希表(键是长整型，值是对象)。内置 Java 哈希表(特别是 HashMap)的性能非常差，在尝试了一些替代方案后——Trove、Fastutils、Colt、Carrot——我开始自己工作。

该代码使用双重哈希策略非常基础。这工作得很好，并且显示了迄今为止我尝试过的所有其他选项的最佳性能。

问题是，根据探查器，查找哈希表是整个应用程序中最昂贵的方法——尽管事实上其他方法被调用了很多次，和/或者做很多更多的逻辑。

真正让我困惑的是查找只被一个类调用；调用方法进行查找并处理结果。两者的调用次数几乎相同，调用查找的方法中有很多逻辑来处理查找结果，但速度大约快 100 倍。

下面是哈希查找的代码。它基本上只是对数组的两次访问(根据分析，计算哈希码的函数实际上是免费的)。我不明白这段代码怎么会这么慢，因为它只是数组访问，而且我看不到任何让它更快的方法。

请注意，代码只是返回与键匹配的桶，调用者应该处理桶。 'size' 是 hash.length/2，hash1 在哈希表的前半部分进行查找，hash2 在后半部分进行查找。 key_index 是传递给构造函数的哈希表上的最终 int 字段，而 Entry 对象上的 values 数组是一个通常长度为 10 或更小的 long 数组。

非常感谢人们对此有任何想法。

谢谢。

public final Entry get(final long theKey) {
    Entry aEntry = hash[hash1(theKey, size)];

    if (aEntry != null && aEntry.values[key_index] != theKey) {
        aEntry = hash[hash2(theKey, size)];

        if (aEntry != null && aEntry.values[key_index] != theKey) {
            return null;
        }
    }

    return aEntry;
}

编辑，hash1 和 hash2 的代码

private static int hash1(final long key, final int hashTableSize) { 
    return (int)(key&(hashTableSize-1)); 
}
private static int hash2(final long key, final int hashTableSize) { 
    return (int)(hashTableSize+((key^(key>>3))&(hashTableSize-1))); 
}

Answer 1

在您的实现 中没有任何东西让我觉得特别低效。我承认我并没有真正遵循您的散列/查找策略，但如果您说它在您的情况下表现出色，我会相信您。

我认为唯一可能使 一些 不同的是将键从 Entry 的值数组中移出。

而不是这样:

class Entry {
    long[] values;
}

//...
if ( entry.values[key_index] == key ) { //...

试试这个:

class Entry {
    long key;
    long values[];
}

//...
if ( entry.key == key ) { //...

与其产生访问成员的成本，加上进行边界检查，然后获取数组的值，您应该只产生访问成员的成本。

有没有比数组更快的随机访问数据类型？

我对这个问题的答案很感兴趣，所以搭建了一个测试环境。这是我的 Array 接口(interface):

interface Array {
    long get(int i);
    void set(int i, long v);
}

当索引超出范围时，此“数组”具有未定义的行为。我把明显的实现放在一起:

class NormalArray implements Array {
    private long[] data;

    public NormalArray(int size) {
        data = new long[size];
    }

    @Override
    public long get(int i) {
        return data[i];
    }

    @Override
    public void set(int i, long v) {
        data[i] = v;
    }
}

然后是一个控件:

class NoOpArray implements Array {
    @Override
    public long get(int i) {
        return 0;
    }
    @Override
    public void set(int i, long v) {
    }
}

最后，我设计了一个“数组”，其中前 10 个索引是硬编码成员。通过开关设置/选择成员:

class TenArray implements Array {
    private long v0;
    private long v1;
    private long v2;
    private long v3;
    private long v4;
    private long v5;
    private long v6;
    private long v7;
    private long v8;
    private long v9;
    private long[] extras;

    public TenArray(int size) {
        if (size > 10) {
            extras = new long[size - 10];
        }
    }

    @Override
    public long get(final int i) {
        switch (i) {
        case 0:
            return v0;
        case 1:
            return v1;
        case 2:
            return v2;
        case 3:
            return v3;
        case 4:
            return v4;
        case 5:
            return v5;
        case 6:
            return v6;
        case 7:
            return v7;
        case 8:
            return v8;
        case 9:
            return v9;
        default:
            return extras[i - 10];
        }
    }

    @Override
    public void set(final int i, final long v) {
        switch (i) {
        case 0:
            v0 = v; break;
        case 1:
            v1 = v; break;
        case 2:
            v2 = v; break;
        case 3:
            v3 = v; break;
        case 4:
            v4 = v; break;
        case 5:
            v5 = v; break;
        case 6:
            v6 = v; break;
        case 7:
            v7 = v; break;
        case 8:
            v8 = v; break;
        case 9:
            v9 = v; break;
        default:
            extras[i - 10] = v;
        }
    }
}

我用这个线束测试了它:

import java.util.Random;

public class ArrayOptimization {
    public static void main(String[] args) {
        int size = 10;
        long[] data = new long[size];
        Random r = new Random();
        for ( int i = 0; i < data.length; i++ ) {
            data[i] = r.nextLong();
        }

        Array[] a = new Array[] {
                new NoOpArray(),
                new NormalArray(size),
                new TenArray(size)
        };

        for (;;) {
            for ( int i = 0; i < a.length; i++ ) {
                testSet(a[i], data, 10000000);
                testGet(a[i], data, 10000000);
            }
        }
    }

    private static void testGet(Array a, long[] data, int iterations) {
            long nanos = System.nanoTime();
        for ( int i = 0; i < iterations; i++ ) {
            for ( int j = 0; j < data.length; j++ ) {
                data[j] = a.get(j);
            }
        }
        long stop = System.nanoTime();
        System.out.printf("%s/get took %fms%n", a.getClass().getName(), 
                (stop - nanos) / 1000000.0);
    }

    private static void testSet(Array a, long[] data, int iterations) {
        long nanos = System.nanoTime();
        for ( int i = 0; i < iterations; i++ ) {
            for ( int j = 0; j < data.length; j++ ) {
                a.set(j, data[j]);
            }
        }
        long stop = System.nanoTime();
        System.out.printf("%s/set took %fms%n", a.getClass().getName(), 
                (stop - nanos) / 1000000.0);

    }
}

结果有些出乎意料。 TenArray 的执行速度比 NormalArray 快得多(对于大小 <= 10)。减去开销(使用 NoOpArray 平均值)你得到 TenArray 占用正常数组时间的 ~65%。因此，如果您知道数组可能的最大大小，我想有可能超过数组的速度。我想 switch 使用比数组更少的边界检查或更有效的边界检查。

NoOpArray/set took 953.272654ms
NoOpArray/get took 891.514622ms
NormalArray/set took 1235.694953ms
NormalArray/get took 1148.091061ms
TenArray/set took 1149.833109ms
TenArray/get took 1054.040459ms
NoOpArray/set took 948.458667ms
NoOpArray/get took 888.618223ms
NormalArray/set took 1232.554749ms
NormalArray/get took 1120.333771ms
TenArray/set took 1153.505578ms
TenArray/get took 1056.665337ms
NoOpArray/set took 955.812843ms
NoOpArray/get took 893.398847ms
NormalArray/set took 1237.358472ms
NormalArray/get took 1125.100537ms
TenArray/set took 1150.901231ms
TenArray/get took 1057.867936ms

现在我不确定你是否可以在实践中获得比数组更快的速度；显然，这种方式会招致与接口(interface)/类/方法相关的任何开销。