代码之家 › 专栏 › 技术社区 › Michael

阵列访问是否可以优化?

micro-optimization optimization arrays java

Michael · 技术社区 · 14 年前

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

代码是非常基本的使用双哈希策略。这工作很好,显示了我迄今为止尝试过的所有其他选项中最好的性能。

许多的 更多次,和/或做很多

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

下面是哈希查找的代码。基本上只需两次访问一个数组(根据分析,计算哈希代码的函数实际上是免费的)。我不明白这段代码怎么会这么慢,因为它只是数组访问,我看不出有什么方法可以让它更快。

注意,代码只返回与键匹配的bucket,调用方需要处理bucketsize'是hash.length/2,hash1在哈希表的前半部分进行查找,hash2在下半部分进行查找。key_index是散列表上传递给构造函数的最后一个int字段,Entry对象上的values数组是一个通常长度小于等于10的长数组。

人们对此的任何想法都非常感激。

谢谢。

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;
}

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))); 
}

4 回复 | 直到 14 年前

Mark Peters 14 年前

你身上什么都没有实施我觉得效率特别低。我承认我不是真的听你的 ,但如果你说这是在你的情况下表现出来的,我会相信你的。

我唯一能想到的是一些 Entry .

class Entry {
    long[] values;
}

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

试试这个:

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

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

您不应该承担访问成员的成本,再加上执行边界检查,然后获取数组的值,而应该只承担访问成员的成本。

我对这个问题的答案很感兴趣,所以我建立了一个测试环境。这是我的阵列接口:

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快得多(对于size<=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

现在,我不确定您是否能够在实践中获得比数组更快的速度;很明显,这样会导致与接口/类/方法相关联的任何开销。

Durandal 14 年前

对于这种情况,经验法则是,如果在剖析器下运行时,已知长度的工作的总处理时间增加了2到3倍,那么剖析开销将给您带来扭曲的结果。

要验证您的更改是否确实有影响,请始终衡量性能改进也是。探查器可以提示您瓶颈,但它也可以欺骗您查看没有问题的地方。

数组边界检查会对性能产生出人意料的巨大影响(如果您做的其他比较少的话),但是它也很难与一般的内存访问惩罚明显分开。在一些琐碎的情况下,JIT可能能够消除它们(Java 6中已经努力消除边界检查),但这主要是AFAIK,仅限于简单的循环构造,如for(x=0;x<array.length;x++)。在某些情况下,您可以通过简单的成员访问来替换数组访问,从而完全避免绑定检查,但仅限于通过常量索引独占访问数组的少数情况。我看没有办法把它应用到你的问题上。

Mark Peters建议的更改很可能不仅更快,因为它消除了边界检查,而且还因为它以更友好的缓存方式更改了数据结构的局部性属性。

Mike Dunlavey 14 年前

许多剖析者告诉你一些非常令人困惑的事情,一部分是因为它们是如何工作的,另一部分是因为人们对性能有有趣的想法。

有一个非常简单的方法来思考这些事情,这使得我们很容易理解发生了什么。

首先,考虑一个例程或语句被激活的时间百分比,而不是它被调用的次数或它所花费的平均时间长度。其原因是它相对不受不相关问题的影响,比如竞争的进程或I/O,并且它节省了您必须将调用的数量乘以平均执行时间,再除以总时间,看看它是否足够大,甚至可以考虑。此外,百分比告诉你,底线,修复它可能会减少整个执行时间。
其次,我所说的“active”是指“on the stack”,其中堆栈包括当前正在运行的指令以及所有“above”的调用,返回到“call main”。如果一个例程负责10%的时间,包括它调用的例程,那么在这段时间内它就在堆栈上。个别的陈述甚至指令也是如此。(忽略“自我时间”或“独占时间”。这让人分心。)
将计时器和计数器放在函数上的探查器只能提供一些此信息。仅对程序计数器进行采样的探查器告诉您的信息更少。你需要的是一个调用堆栈示例和 铁路支线

有探查器可以做到这一点。我对Java不太确定。

如果你还和我在一起,让我再扔一个响铃。你在寻找你能优化的东西,对吧?只有那些有足够大的百分比值得你去做的事情,比如10%或者更多?这样一行代码花费10%的时间是在堆栈上的10%。这意味着如果采集了20000个样本,其中大约有2000个样本。如果平均来说,大约有两个。现在,你在找电话线,对吧?只要你找到,百分之几的折扣真的有关系吗?这是剖析者的另一个快乐神话——时间的精确性很重要。为了找到有价值的问题,20000个样品不会告诉你超过20个样品。那我该怎么办?手拿样品 研究他们 . 值得优化的代码将直接跳出我。

最后,有一大堆好消息。可能有很多事情你可以优化。假设你解决了一个百分之二十的问题,使它消失。总的时间缩短到原来的4/5,但是其他的问题并没有减少时间,所以现在他们的百分比是原来的5/4,因为分母变小了。百分比 他们变大了

Puppy 14 年前

您可以尝试使用备忘录或缓存策略来减少实际调用的数量。如果你非常绝望,你可以尝试的另一件事情是本地数组,因为索引这些是难以置信的快,JNI不应该调用太多开销,如果你使用不需要编组的参数如long。