假設(shè)我在 64 位 POSIX 系統(tǒng)中有一個(gè) 64 位數(shù)組。假設(shè)處理器緩存包含我的數(shù)組，并且寄存器的長度為 64 位以上。我可以期望 System.arraycopy(…) 的 O(1) 時(shí)間嗎？從某種意義上說，復(fù)制的時(shí)間并不取決于我的數(shù)組的長度。問題與System.arraycopy(...) 的時(shí)間復(fù)雜度有關(guān)？。我覺得我可以期待它，但是它在引擎蓋下的工作原理是這樣的嗎？在這種情況下，我是否會變得依賴于系統(tǒng)和 JVM？
2 回答
ABOUTYOU
TA貢獻(xiàn)1812條經(jīng)驗(yàn) 獲得超5個(gè)贊
假設(shè)處理器緩存包含我的數(shù)組
這并不真正相關(guān)。
相關(guān)內(nèi)容：首先，底層數(shù)組數(shù)據(jù)的類型。
就像這樣：只有當(dāng)您說，byte data[] = new byte[8]時(shí)，您才有真正按順序一個(gè)接一個(gè)地位于內(nèi)存中的 64 位。
因?yàn)?，?dāng)你這樣做的時(shí)候Byte data[] = new Byte[8]，你就已經(jīng)被破壞了，因?yàn)閿?shù)組中的槽只是指針，指向堆上的某個(gè)地方！
因此，讓我們重新表述一下：假設(shè)您有 64 位架構(gòu)，那么當(dāng)然：CPU 應(yīng)該能夠使用單個(gè)指令處理 64 位。無論是將整個(gè)數(shù)組讀入 CPU 緩存或 CPU 寄存器，還是將該數(shù)據(jù)復(fù)制到內(nèi)存中的不同位置。
翻翻過去那場雪
TA貢獻(xiàn)2065條經(jīng)驗(yàn) 獲得超14個(gè)贊
64 位 POSIX 系統(tǒng)。
POSIX 與分塊數(shù)據(jù)復(fù)制相關(guān)的 CPU 功能無關(guān)
假設(shè)處理器緩存包含我的數(shù)組
執(zhí)行復(fù)制指令時(shí)，它會從主存中保存行程，但不影響 Big O 表示法的順序。
寄存器的長度為 64+ 位。
即使您的架構(gòu)具有 AVX512 支持，具有 512 位寬zmm寄存器和 JDK 9+（AFAIK 運(yùn)行時(shí)知道 AVX512 啟動 JDK 9+），它也允許您為每條指令復(fù)制 8 個(gè)打包的 64 位整數(shù)，但不會影響復(fù)雜性的順序。
因此，要復(fù)制 1024 個(gè) 64 位整數(shù)，您將需要再次執(zhí)行至少 128 個(gè)向量指令O(n)，從而產(chǎn)生復(fù)雜性，但常數(shù)較低。
HotSpot 實(shí)施說明：
依賴于體系結(jié)構(gòu)的實(shí)現(xiàn)代碼arraycopy是在 JVM 全局引導(dǎo)“階段”生成的StubRoutines::initialize2。
特別是分塊復(fù)制例程代碼生成是在 HotSpot 代碼的平臺相關(guān)部分中使用copy_bytes_forward函數(shù)完成的（它是使用 HotSpot 自己的宏匯編器實(shí)現(xiàn)完成的）。
它的關(guān)鍵部分是 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 {
? ? //...
}
它根據(jù)可用的 CPU 功能生成代碼。特征檢測器是在基于指令的架構(gòu)相關(guān)生成器generate_get_cpu_info中較早生成和調(diào)用的cpuid。
添加回答
舉報(bào)
0/150
提交
取消