使用simd查找一個角色的第一個實例

我想查找一個角色的第一個實例，在這種情況下使用simd（AVX2或更早版本）'''。我想使用_mm256_cmpeq_epi8，但是我需要一個快速的方法來查找__m256i中的任何結果字節是否已被設置爲0xFF，然後計劃使用_mm256_movemask_epi8將結果從字節轉換爲位，並使用ffs來獲得匹配的索引。使用_mm_movemask_epi8一次搬出的一部分的任何其他建議使用simd查找一個角色的第一個實例

來源

2016-12-01 Jimbo

我應該補充說，simd是沒有必要的，一般我只是尋找最快的方法。也許有點魔力？ – Jimbo

你的基本想法是合理的 - 我有一種感覺，可能已經有一個SIMD實現，就像你在StackOverflow上的一個問題中描述的一樣，但是一個快速搜索並沒有解決它。注意你正在實現的是'strchr'（或者'memchr'，如果你知道這個長度的話），而且可能已經有了SIMD優化的可用實現。還要注意的是，對於尚未處於緩存中的字符串，您的函數可能會受到內存帶寬的限制。 –

[這是一個SSE實現，它掃描一個''\ 0'']（http://stackoverflow.com/a/14524319/253056）（有效地'strlen'）字符串，你可能會適應它。 –

你有正確的想法與_mm256_cmpeq_epi8 - ？。。>_mm256_movemask_epi8據我所知，這是實現此爲英特爾CPU的最佳方式至少PMOVMSKB r32, ymm是相同的速度作爲XMM的16字節版本，所以解開這兩個l將會是一個巨大的損失一個256b矢量的anes和movemask他們分開，然後重新組合整數結果。（來源：Agner Fog's instruction table看到x86標籤維基其他PERF鏈接。）

由離開ffs，直到你從_mm256_movemask_epi8確定了非零的結果後，充分利用循環內的代碼儘可能高效。

TEST/JCC可以將宏融入單個uop，但BSF/JCC不會，因此需要額外的指令。（你很難得到一個C編譯器發出BSF/JCC無論如何，更可能的分支結果ffs會給你一些測試輸入非零，然後BSF，然後加1 ，然後進行比較和分支。與僅測試movemask結果相比，這顯然非常糟糕。）

還要注意，對於類似的問題，比較movemask（例如檢查是否爲0xFFFFFFFF）與分支效果一樣高效不爲零。

正如Paul R所建議的，看一些strlen，strchr和memchr的實現可能會提供信息。在開源libc實現和其他地方有多個手寫的asm實現。（例如glibc和Agner Fog's asmlib）。

許多glibc的版本掃描到一個對齊邊界，然後使用一次展開64B的展開循環（在4個SSE向量中，因爲我不認爲glibc有一個AVX2版）。

爲了優化長字符串，通過將比較結果「OR」在一起來減少測試比較結果的開銷，並檢查它。如果您發現一個命中，請返回並重新測試您的向量以查看哪個向量具有命中。

將ffs作爲您在多個移動遮罩結果之外建立的一個64位整數（使用shift和|）可能會更有效一些。在測試零之前，我不確定在循環內部執行此操作;我不記得glibc的strlen策略是否做到了。

一切我在這裏提出的東西可以在ASM可以看到在不同的glibc策略的strlen，了memchr，以及相關的功能。這裏是sysdeps/x86_64/strlen.S，但是我可能會在其他地方使用比基準SSE2更多的源文件。（還是不行，我可能會考慮不同的功能，也許沒有什麼可以得到的超越SSE2，直到AVX（3操作數的insn）和AVX2（256B整數向量）

參見：

glibc's strchr-avx2.S（Woboq.org有一個很好的源代碼瀏覽器，可以搜索文件名/符號）。
的glibc的memchr-avx2.S

glibc's memchr使用PMAXUB代替POR。我不確定這對於一些神祕的微架構理由是否有用，但是它在大多數CPU上運行的端口更少。也許這是需要的，以避免資源衝突與其他事情？ IDK似乎很奇怪，因爲它與PCMPEQB競爭。

來源

2016-12-01 16:43:14

_mm_movemask_epi8背後的想法是，它看起來像更快更新處理器比_mm256_movemask_epi8，即使它需要被調用兩次。如果沒有，那麼你可以避免額外的電話費用。這當然似乎是依賴於處理器的，所以在Haswell他們有相同的延遲時間，更大的調用（即_mm256_movemask_epi8）似乎是更好的方法。 – Jimbo

@Jimbo：哦，嗯，我沒有注意到，Agner Fog的Skylake表中的PMOVMSKB r，v被列爲2-3c延遲。在Haswell，'VMOVMSKPS/D r32，ymm'是2c延遲，但xmm版本是3c延遲！這是令人驚訝的。你在哪裏看到256b版本較慢？您確定Skylake的ymm版本不會更快嗎？ –

@Jimbo：無論如何，差異最多隻有一個週期的等待時間，沒有額外的uops或吞吐量。 **'_mm256_movemask_epi8'仍然是你可以做的最好的**。單獨使用兩個半部分無法做到的事情可能與僅使用一個VPMOVMSKB r32，ymm一樣好。在上通道上使用128b movmsk需要先將其提取到寄存器的低128b，然後像VEXTRACTF128一樣進行3週期延遲的通道交叉混洗。 –

使用simd查找一個角色的第一個實例

回答

相關問題