System.arraycopy(…) 能比 O(n) 更快吗？

Question

假设我在 64 位 POSIX 系统中有一个 64 位数组。假设处理器缓存包含我的数组，并且寄存器的长度为 64 位以上。我可以期望 System.arraycopy(…) 的 O(1) 时间吗？从某种意义上说，复制的时间并不取决于我的数组的长度。问题与System.arraycopy(...) 的时间复杂度有关？。我觉得我可以期待它，但是它在引擎盖下的工作原理是这样的吗？在这种情况下，我是否会变得依赖于系统和 JVM？

Answer 1

假设处理器缓存包含我的数组

这并不真正相关。

相关内容：首先，底层数组数据的类型。

就像这样：只有当您说，byte data[] = new byte[8]时，您才有真正按顺序一个接一个地位于内存中的 64 位。

因为，当你这样做的时候Byte data[] = new Byte[8]，你就已经被破坏了，因为数组中的槽只是指针，指向堆上的某个地方！

因此，让我们重新表述一下：假设您有 64 位架构，那么当然：CPU 应该能够使用单个指令处理 64 位。无论是将整个数组读入 CPU 缓存或 CPU 寄存器，还是将该数据复制到内存中的不同位置。

Answer 2

64 位 POSIX 系统。

POSIX 与分块数据复制相关的 CPU 功能无关

假设处理器缓存包含我的数组

执行复制指令时，它会从主存中保存行程，但不影响 Big O 表示法的顺序。

寄存器的长度为 64+ 位。

即使您的架构具有 AVX512 支持，具有 512 位宽zmm寄存器和 JDK 9+（AFAIK 运行时知道 AVX512 启动 JDK 9+），它也允许您为每条指令复制 8 个打包的 64 位整数，但不会影响复杂性的顺序。

因此，要复制 1024 个 64 位整数，您将需要再次执行至少 128 个向量指令O(n)，从而产生复杂性，但常数较低。

---

HotSpot 实施说明：

依赖于体系结构的实现代码arraycopy是在 JVM 全局引导“阶段”生成的StubRoutines::initialize2。

特别是分块复制例程代码生成是在 HotSpot 代码的平台相关部分中使用copy_bytes_forward函数完成的（它是使用 HotSpot 自己的宏汇编器实现完成的）。

它的关键部分是 CPU 功能检查，例如

if (UseAVX > 2) {

  __ evmovdqul(xmm0, Address(end_from, qword_count, Address::times_8, -56), Assembler::AVX_512bit);

  __ evmovdqul(Address(end_to, qword_count, Address::times_8, -56), xmm0, Assembler::AVX_512bit);

} else if (UseAVX == 2) {

  __ vmovdqu(xmm0, Address(end_from, qword_count, Address::times_8, -56));

  __ vmovdqu(Address(end_to, qword_count, Address::times_8, -56), xmm0);

  __ vmovdqu(xmm1, Address(end_from, qword_count, Address::times_8, -24));

  __ vmovdqu(Address(end_to, qword_count, Address::times_8, -24), xmm1);

} else {

    //...

}

它根据可用的 CPU 功能生成代码。特征检测器是在基于指令的架构相关生成器generate_get_cpu_info中较早生成和调用的cpuid。