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

Question

我有以下功能:

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

此函数扫描一个 char 数组，搜索给定模式的匹配项，该模式存储为有限自动机。自动机的转换函数存储在名为 transFunc 的变量中。

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

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

提前致谢!

Answer 1

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

内存高速缓存在现代计算机中的作用是处理处理器指令时间(小于 1 ns)与主内存(5 到 10 ns 或更多)之间的速度不匹配。当您的代码在从内存中获取的大部分时间都命中缓存时，它们的效果最好。

现代英特尔芯片组以 64 字节为单位缓存内存，并以突发模式从主内存加载。 (对应于 16 个 int 值。)(比如)I7 处理器上的 L1 缓存为 2MB。

如果您的应用程序能够(大致)按顺序访问大型数组中的数据，那么 8 次访问中有 7 次将是缓存命中。如果访问模式是非顺序的，并且“工作集”是缓存大小的很大倍数，那么您最终可能会在每次内存访问时都出现缓存未命中。

如果内存访问局部性是您问题的根源，那么您的选择是有限的:

• 重新设计你的算法，使内存引用的局部性更好
• 购买缓存更大的硬件
• (也许)重新设计您的算法以使用 GPU 或其他一些策略来减少内存流量

用 C 或 C++ 重新编码您现有的代码可能会提高性能，但同样的内存局部性问题也会困扰您。

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