Java性能 – 用于大量快速读取的ArrayLists与Arrays
我有一个程序，我需要在尽可能短的时间内（以毫秒为单位）对类似List的对象进行100,000到1,000,000次随机读取读取，以用于类似细胞自动机的程序。 我认为我正在使用的更新算法已经过优化（有效跟踪活动单元等）。 列表确实需要改变大小，但性能并不重要。 所以我想知道使用Arrays而不是ArrayLists的性能是否足以在如此短的时间内处理那么多读取时产生差异。 目前，我正在使用ArrayLists。
编辑：我忘了提到：我只是存储整数，所以另一个因素是使用Integer包装类（在ArrayLists的情况下）与int（在数组的情况下）。 有没有人知道使用ArrayList实际上是否需要3个指针查找（一个用于ArrayList，一个用于底层数组，一个用于Integer-> int），因为数组只需要1（数组地址+偏移到特定的INT）？ HotSpot会优化额外的外观吗？ 这些额外的观察有多重要？
Edit2：另外，我忘了提到我还需要进行随机访问写入（写入，而不是插入）。
既然您已经提到过您的数组实际上是基本类型的数组，请考虑在Trove库中使用基本类型集合类。
@viking在他的应用程序中使用Trove报告显着（十倍！）加速 – 请参阅注释。 另一方面，Trove集合类型与Java的标准集合API不兼容。 因此Trove（或类似的库）在所有情况下都不会是答案。
尝试两者，但要衡量。
最有可能你可以一起破解一些东西，使内循环使用数组而不改变所有那么多代码。 我怀疑HotSpot已经内联方法调用，你将看不到性能提升。
另外，尝试Java 6更新14并使用-XX：+ DoEscapeAnalysis
ArrayLists比Arrays慢，但是大多数人认为差异很小。 在你的情况下可能很重要，因为你正在处理成千上万的。
顺便说一句，复制： Java中的数组或列表。 哪个更快？
我会和凯文的建议一起去。
如果您的程序要慢慢将其与具有arrays的版本进行比较，请先保留列表并测量性能。 如果这样可以提高性能，可以使用数组，如果没有留在列表中，因为它们会让您的生活更轻松。
使用ArrayList而不是数组会产生开销，但很可能很小。 实际上， ArrayList有用的数据位可以存储在寄存器中，尽管您可能会使用更多（例如， List size）。
您在编辑中提到您正在使用包装器对象。 这些确实产生了巨大的差异。 如果您通常重复使用相同的值，那么合理的缓存策略可能很有用（ Integer.valueOf为-128到128提供相同的结果）。 对于原语，原始数组通常可以轻松获胜。
作为一种改进，您可能希望确保相邻单元格在数组中相邻（您可以比具有空间填充曲线的列行更好）。
一种可能性是重新实现ArrayList（它并不那么难），但是通过锁定/释放调用循环来暴露支持数组。 这为您的写入提供了便利，但是为了您预先知道的大量读/写操作公开数组不会影响数组大小。 如果列表被锁定，则不允许添加/删除 – 只需获取/设置。
例如：
SomeObj[] directArray = myArrayList.lockArray(); try{ // myArrayList.add(), delete() would throw an illegal state exception for (int i = 0; i < 50000; i++){ directArray[i] += 1; } } finally { myArrayList.unlockArray(); }
这种方法继续封装ArrayList的数组增长/等......行为。
Java对其对象使用双重间接，因此它们可以在内存中移动并使其引用仍然有效，这意味着每个引用查找等同于两个指针查找。 这些额外的查找无法完全优化。
也许更糟糕的是你的缓存性能会很糟糕。 访问缓存中的值比访问主内存中的值要快许多倍。 （可能是10x）如果你有一个int []，你知道这些值在内存中是连续的，因此很容易加载到缓存中。 但是，对于Integer []，整数各个对象可以在您的内存中随机出现，更有可能是缓存未命中。 整数也使用24个字节，这意味着它们比4个字节值更不适合您的缓存。
如果更新整数，则通常会导致创建一个新对象，该对象比更新int值要高出许多个数量级。
如果您正在创建列表一次，并从中进行数千次读取，那么ArrayList的开销可能会略微忽略。 如果您要创建数千个列表，请使用标准数组。 循环中的对象创建很快变成二次方，这仅仅是因为实例化成员变量，调用构造函数到inheritance链等所有开销。
因此 – 并回答你的第二个问题 – 坚持使用标准的int而不是Integer类。 对两者进行描述，您将很快（或者，更确切地说，慢慢地）了解原因。
如果你不会比从这个结构中读取更多的东西，那么继续使用数组，因为当通过索引读取时会更快。
但是，请考虑如何在那里获取数据，以及排序，插入，删除等是否是一个问题。 如果是这样，您可能需要考虑其他基于集合的结构。
基元更快（更多）。 总是。 即使使用JIT转义分析等，也可以在java.lang.Integer中跳过包装。 此外，跳过大多数ArrayList实现对get（int）执行的数组边界检查。 大多数JIT可以识别简单的循环模式并删除循环，但如果你担心性能，没有多少理由可以使用它。
您不必自己编写原始访问代码 – 我敢打赌您可以切换到使用COLT库中的IntArrayList – 请参阅http://acs.lbl.gov/~hoschek/colt/ – “Colt提供了一组用于Java中高性能科学和技术计算的开源库“） – 在几分钟的重构中。
选项是：
1.使用数组
2.使用内部使用数组的ArrayList
很明显，ArrayList引入了一些开销（查看ArrayList源代码）。 对于99％的用例，这种开销很容易被忽略。 但是，如果您实现时间敏感算法并通过索引从列表中执行数千万次读取，那么使用裸arrays而不是列表应该可以显着节省时间。 使用常见感。
请看这里： http ： //robaustin.wikidot.com/how-does-the-performance-of-arraylist-compare-to-array我会亲自调整测试以避免编译器优化，例如我会改变“j =“进入”j + =“循环后随后使用”j“。
数组会更快，因为它至少会跳过一个函数调用（即get（i））。
如果您有静态大小，那么Arrays就是您的朋友。