假設我在 64 位 POSIX 系統中有一個 64 位數組。假設處理器緩存包含我的數組，并且寄存器的長度為 64 位以上。我可以期望 System.arraycopy(…) 的 O(1) 時間嗎？從某種意義上說，復制的時間并不取決于我的數組的長度。問題與System.arraycopy(...) 的時間復雜度有關？。我覺得我可以期待它，但是它在引擎蓋下的工作原理是這樣的嗎？在這種情況下，我是否會變得依賴于系統和 JVM？
2 回答
ABOUTYOU
TA貢獻1812條經驗 獲得超5個贊
假設處理器緩存包含我的數組
這并不真正相關。
相關內容：首先，底層數組數據的類型。
就像這樣：只有當您說，byte data[] = new byte[8]時，您才有真正按順序一個接一個地位于內存中的 64 位。
因為，當你這樣做的時候Byte data[] = new Byte[8]，你就已經被破壞了，因為數組中的槽只是指針，指向堆上的某個地方！
因此，讓我們重新表述一下：假設您有 64 位架構，那么當然：CPU 應該能夠使用單個指令處理 64 位。無論是將整個數組讀入 CPU 緩存或 CPU 寄存器，還是將該數據復制到內存中的不同位置。
翻翻過去那場雪
TA貢獻2065條經驗 獲得超14個贊
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。
添加回答
舉報
0/150
提交
取消