可以优化arrays访问吗？
也许我被我的探测器（Netbeans）误导了，但我看到了一些奇怪的行为，希望也许有人可以帮助我理解它。
我正在开发一个应用程序，它大量使用相当大的哈希表（键是long，值是对象）。 内置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))); }
你的实现中没有任何东西让我觉得特别低效。 我承认我并没有真正遵循你的哈希/查找策略 ，但如果你说它在你的环境中表现得很好，我会相信你。
我唯一期望可能会有所不同的是将键移出Entry数组数组。
而不是这个：
class Entry { long[] values; } //... if ( entry.values[key_index] == key ) { //...
尝试这个：
class Entry { long key; long values[]; } //... if ( entry.key == key ) { //...
而不是承担访问成员的成本，加上边界检查，然后获取数组的值，您应该只承担访问成员的成本。
是否存在比数组更快的随机访问数据类型？
我对这个问题的答案很感兴趣，所以我建立了一个测试环境。 这是我的Array接口：
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％的时间。 因此，如果您知道阵列可能的最大大小，我认为有可能超过arrays的速度。 我会想象交换机使用较少的边界检查或比数组更有效的边界检查。
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
现在你是否可以在实践中获得比我不确定的arrays更快的速度; 很明显，这会产生与接口/类/方法相关的任何开销。
很可能你在对剖析器结果的解释中被误导了。 众所周知，分析器过度充斥了经常被称为小型方法的性能影响。 在您的情况下，get（） – 方法的分析开销可能大于方法本身花费的实际处理。 情况进一步恶化，因为仪器也会干扰JIT内联方法的能力。
作为这种情况的经验法则 – 如果在剖析器下运行时，已知长度的工件的总处理时间增加超过两到三倍，则剖析开销将给出偏差结果。
要validation您的更改确实会产生影响，请始终在不使用分析器的情况下衡量性能改进。 探查器可以暗示你有关瓶颈的问题，但它也可能会欺骗你去看看没有错的地方。
数组边界检查可以对性能产生惊人的巨大影响（如果你做的比较少），但也很难明确区分一般的内存访问惩罚。 在一些微不足道的情况下，JIT可能能够消除它们（在Java 6中已经努力进行边界检查消除），但这是AFAIK主要限于简单的循环结构，如（x = 0; x Mark Peters建议的更改很可能不仅仅是更快，因为它消除了边界检查，还因为它以更加缓存友好的方式改变了数据结构的位置属性。
许多分析师告诉你非常令人困惑的事情，部分是因为他们的工作方式，部分是因为人们对性能有一些有趣的想法。 例如，您想知道调用函数的次数，并且您正在查看代码并认为它看起来像很多逻辑，因此很慢。
有一种非常简单的方法来思考这些东西，这使得很容易理解正在发生的事情。
-
首先，根据例程或语句处于活动状态的时间百分比来考虑，而不是调用它的次数或它所花费的平均时间长度。 原因是它相对不受竞争过程或I / O等不相关问题的影响，它可以节省你不得不将调用次数乘以平均执行时间并除以总时间，看看它是否很大甚至足够关心。 此外，百分比告诉您，底线，修复它可能会减少总体执行时间。
-
其次，我所说的“活动”是“在堆栈上”，其中堆栈包括当前正在运行的指令，所有调用“在其上方”返回“call main”。 如果一个例程负责10％的时间，包括它调用的例程，那么在那段时间它就在堆栈上。 个别陈述甚至指示也是如此。 （忽略“自我时间”或“独家时间”。这是一种分心。）
-
将计时器和计数器放在函数上的分析器只能为您提供一些信息。 仅对程序计数器进行采样的分析器会告诉您更少。 您需要的是对调用堆栈进行采样并按 行 （而不仅仅是函数）向您报告包含该行的堆栈样本的百分比。 它们在I / O或其他阻塞期间对堆栈进行采样也很重要，但b）在等待用户输入时没有。
有分析师可以做到这一点。 我不确定Java。
如果你还在我身边，让我扔掉另一个铃声。 你正在寻找可以优化的东西，对吧？ 并且只有那些有足够大百分比的东西值得麻烦，比如10％或更多？ 成本为10％的这样一行代码在10％的时间内处于堆栈中。 这意味着如果采集了20,000个样本，则大约有2,000个样本。 如果采集20个样本 ，平均约为2 个样本 。 现在，你正试图找到这条线，对吧？ 只要你找到它，百分比是否稍微偏离真的很重要吗？ 这是另外一个关于剖析器的快乐神话 – 时间的精确性很重要。 为了找到值得解决的问题，20,000个样本不会告诉你超过20个样本。 那我该怎么办？ 只需手动取样并研究它们 。 值得优化的代码只会跳出来。
最后，有一大堆好消息。 您可以优化多种内容。 假设您修复了20％的问题并使其消失。 整体时间缩短到原来的4/5，但其他问题并没有花费更少的时间，所以现在它们的百分比是它的5/4，因为分母变小了。 百分比方面， 他们变得更大 ，更容易找到。 这个效果滚雪球，让你真正挤压代码。
您可以尝试使用记忆或缓存策略来减少实际呼叫的数量。 如果你非常绝望，你可以尝试的另一件事是本机数组，因为索引它们的速度令人难以置信，如果你使用不需要编组的long等参数，JNI不应该调用过多的开销。