最快的方式找到緩衝

我已閱讀What is the fastest substring search algorithm?，這可能是次優的單字符大小寫字節的第一次出現。
strchr需要一個NULL結尾的字符串

我找識別一個字節的緩衝區指定字節中第一次出現的最快方法。

這使人想起的字符串中尋找一個字符的第一個發生不同之處在於：

字節緩衝器不NUL結束，代替我有一個明確的長度（並且可能嵌入的NUL字符）
字節緩衝器中沒有一個string或vector分配，我只傳世切片（又名，指針&長度）

基本的解決方案是：

size_t search(char const* buffer, size_t length, char c) { 
    return std::find(buffer, buffer + length, c) - buffer; 
}

然而，快速往返與Godbolt編譯器（-O2 -msse2 -mavx）不顯示矢量指令，只有一些展開的任何暗示，所以我想知道這是否是最佳。

有沒有更快的方法找到緩衝區中給定字節的第一次出現？

注意：只有第一次出現很重要。

注意：我特別關心Linux上的現代x86_64 CPU，儘管我鼓勵儘可能通用的答案，並提出假設。

來源

2016-11-16 Matthieu M.

也許嘗試['memchr']（https://linux.die.net/man/3/memchr） - 它就像'strchr'，但它不需要NUL終止的字符串？ –

令人沮喪的是'std :: find'沒有被優化以利用GCC上的編譯器內在函數。有人應該寫一個補丁，這是一個明顯的優化。 –

@KonradRudolph：我也很驚訝，尤其是因爲根據David Haim的說法，在VC++上進行了優化。也許關於內聯的問題？（正如在一個純粹的C++實現中可以進行編譯時評估，而一個程序集則不能） –

你可以使用memchr，它通常作爲一個內部函數來實現，並且通常（根據我的經驗）比任何手動滾動循環都快得多。

http://en.cppreference.com/w/c/string/byte/memchr

編輯：至少在VC++（和我賭GCC爲好，我沒有檢查），std::find將使用memchr無論如何，如果你找一個字節，所以我會檢查是否memchr實際使程序運行得更快。

來源

2016-11-16 13:14:06

memchr實現的解釋可以在這裏找到（http://stackoverflow.com/questions/525123/how-does-memchr-work-under-the-hood）。來自[BurntSushi的Rust memchr crate]（https://github.com/BurntSushi/rust-memchr/blob/master/src/lib.rs）的提示表明，儘管libc的memchr在Windows上速度很慢。 –

從Godbolt，不，''char'上的'std :: find'不會被gcc（6.2）簡化爲'memchr'。 –

@MatthieuM。所以這是一個嘗試:) –

最快的方式找到緩衝

回答

相關問題