我有一個計算 checkLeadingZeroBits 的函式，如下所示：
typedef std::array<uint8_t, 32> SHA256Hash;
bool checkLeadingZeroBits(SHA256Hash& hash, unsigned int challengeSize) {
int bytes = challengeSize / 8;
const uint8_t * a = hash.data();
if (bytes == 0) {
return a[0]>>(8-challengeSize) == 0;
} else {
for (int i = 0; i < bytes; i ) {
if (a[i] != 0) return false;
}
int remainingBits = challengeSize - 8*bytes;
if (remainingBits > 0) return a[bytes 1]>>(8-remainingBits) == 0;
else return true;
}
return false;
}
我還嘗試了以下大致相同的運行時間：
bool checkLeadingZeroBits(SHA256Hash& hash, unsigned int challengeSize) {
int bytes = challengeSize / 8;
const uint8_t * a = hash.data();
if (bytes == 0) {
return a[0]>>(8-challengeSize) == 0;
} else {
if (memcmp(NULL_SHA256_HASH.data(), a, bytes) != 0) return false;
int remainingBits = challengeSize - 8*bytes;
if (remainingBits > 0) return a[bytes 1]>>(8-remainingBits) == 0;
else return true;
}
return false;
}
我想優化此功能以盡快運行。有沒有比使用我的實作中顯示的 for 回圈更簡單的方法來檢查前導位？
uj5u.com熱心網友回復：
正如所寫，沒有。在位級別掃描原始位元組陣列不能比逐位元組比較操作更快。
但是，如果您的目標平臺具有計數前導零指令或等效指令，則可以通過檢查本機處理器字的塊大小（x86/ARM 為 32 位，AMD64/AA64 為 64 位）來加快行程。這會給您帶來輕微的改進，但總體而言可能不足以在這種情況下有用。
為此，您需要將資料轉換為 C 指標，然后將其轉換為與機器上的字大小相同的指標 ( uintptr_t*)。從那里，您可以讀出記憶體塊，并將它們傳遞給編譯器內部函式，以計算該單詞的前導零。
對此有一些注意事項。一方面，您需要非常小心，以免對新指標的最后一次讀取不會越權進入您不擁有的記憶體。此外，對于引入lzcnt之前（在 AMD ABM 或 Intel Haswell 之前）的x86 架構，您需要處理bsr（位掃描反向，MSB 到 LSB）指令找不到位的情況，這會設定零標志而不是回傳一個真實結果（這可能對您不可見，或由內在函式自動轉換，但我知道 MSVC 的_BitScanReverse函式根據指令是否找到一點回傳 true 或 false）。
最終，您可能會在性能上獲得微不足道的改進，這可能會被從緩沖區讀取資料所需的記憶體訪問所抵消。總的來說，這并不值得 - 編譯器在優化回圈方面會比使用世界上所有指令做得更好。撰寫清晰且易于維護的代碼比脆弱、遲鈍且依賴于處理器特定指令的代碼更好。
這是一種恥辱，因為我真的很喜歡lzcnt, bsr/ bsf, 和clz說明。它們可以顯著加快掃描位圖的速度，但它們在這里并沒有真正的用處。
uj5u.com熱心網友回復：
有 SSE4.2 指令可用于批量比較位元組并加速此演算法。您可以使用一條指令一次比較 16 個位元組。
https://github.com/WojciechMula/sse4-strstr/blob/master/sse4.2-strstr.cpp
uj5u.com熱心網友回復：
這里的問題之一是字符陣列似乎是大端格式。在某些架構中，這可以通過位元組交換來緩解，而在某些其他架構中，無論如何都可以通過讀取 64 位但專注于 LSB 位來緩解這種情況。
// MSB
// x = 00 00 00 00 08 FE BB AB <-- as stored byte wise in memory
// y = AB BB FE 08 00 00 00 00 <-- as read from memory in x86
bool check(uint8_t const *x, int challenge_count) {
uint64_t y;
std::memcpy(&y, x, 8);
if (y & (~0ull << (challenge_count & ~7))) {
}
... check the remaining byte (or nibble)
}
這里如果需要多次執行相同的比較，快取(~0ull << (challenge_count & ~7)). 這里challenge_count >= 64也省略了 的處理，可以通過memcpy后跟與零的比較來實作。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/382466.html
上一篇：struct中使用alignof運算子時是否會影響sizeof
下一篇：OpenMP并行回圈例外