JAVA中int数组的非顺序迭代性能低下

Question

JAVA中int数组的非顺序迭代性能低下

3

我有以下函数:

public void scanText(char[] T){
    int q=0;
    for(int i=0;i<T.length;i++){
        q = transFunc[preCompRow[q]+T[i]];
        if(q==pattern.length){
            System.out.println("match found at position: "+(i-pattern.length+2));
        }
    }
}

该函数扫描字符数组以搜索给定模式的匹配项，该模式存储为有限自动机。自动机的转移函数存储在名为transFunc的变量中。

我正在测试此函数在包含800000个模式的800万个字符文本中。问题是访问数组preCompRow[q]（它是一个int[]）非常慢。如果删除代码中的preCompRow[q]，则性能会大大提高。我认为这可能是因为在每次循环中，q变量具有不同的非顺序值（2、56、18、9..）。

有没有更好的方法以非顺序方式访问数组？

先行致谢！

- AAA

2

定义“非常慢”。 - Andreas

1

@Andreas 我在一个包含8324701个字符的字符数组上搜索了4000种不同的模式，并花费了143秒的时间。然后我进行了相同的测试，但将transFunc[preCompRow[q]+T[i]]改为了transFunc[T[i]]，只花费了9秒的时间。 @leoxs 在两个测试执行期间，我没有看到任何交换活动。我正在使用2 GB的堆。 - AAA

如果你真的需要性能，可以用C编写代码，并将其作为模块在Java项目中使用。如果可以并行运行，考虑使用线程，或者更好地，在GPU上完成。 - leoxs

等一下，T[i]返回一个字符，然后你将它与preCompRow[q]相加。也许问题不在于数组访问，而是"+"运算符。不要对整个代码进行基准测试，只需尝试访问和操作，以便找到瓶颈。 - leoxs

1

我也认为瓶颈在于 +，但我测试了几个案例 transFunc[T[i]]、transFunc[1+T[I]]、transFunc[T[I]]，所有的性能都很好，但每次我在索引中添加 preCompRow[q] 时整个程序就出问题了。当我将 q 固定为某个值时，事情变得非常快，例如 transFunc[preCompRow[1]+T[I]]。我的结论是问题在于 q 的值，在循环的每一次迭代中，它可以取 1-#模式字符之间的任何值。 - AAA

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stephen C · Accepted Answer

一种可能的解释是，由于内存访问模式中局部性不佳，您的代码看起来内存性能较差。

现代计算机中内存缓存的作用是处理处理器指令时间（小于1纳秒）和主存储器（5到10纳秒或更长）之间的速度不匹配。当您的代码每次从内存中获取时都获得缓存命中时，它们的效果最好。

现代英特尔芯片组以64字节的块缓存内存，并以突发模式从主存储器中加载。（这对应于16个int值。）例如，I7处理器上的L1缓存为2MB。

如果您的应用程序能够大致按顺序访问大型数组中的数据，则每8次访问中有7次将是缓存命中。如果访问模式是非顺序的且“工作集”是缓存大小的大倍数，则每次内存访问可能会导致缓存未命中。

如果内存访问局部性是问题的根源，则您的选项有限：

- 重新设计算法以改善内存引用的局部性。 - 购买具有更大缓存的硬件。 - （也许）重新设计算法以使用GPU或其他策略来减少内存流量。

重新用C或C++编写您现有的代码可能会提高性能，但相同的内存局部性问题也会在那里出现。

我不知道有任何工具可用于测量Java应用程序中的缓存性能。