使用SSE加速lower_bound函數

Question

在我目前正在研究的項目中，我經常需要在可以插入元素的已排序數組中找到儘可能最低的索引（如C++中的std :: lower_bound） 。 使用SSE加速我的算法似乎很有吸引力，因爲我使用的uint32數組的大小通常是處理器高速緩存行的大小。 我從來沒有使用SSE指令，所以我無法弄清楚這個函數的SSE實現是什麼樣子。請給出提示，以幫助我用SSE優化寫出來。

Answer 1

沒有什麼像std::lower_bound使用SSE進行擴展。 SSE讓事情變得更快的原因是它允許你一次進行多次計算。例如，單個SSE指令可能會導致4次乘法操作一次執行。但是，std::lower_bound的運行方式無法並行化，因爲算法中的每個步驟都需要前面步驟的比較結果。此外，它已經是O（lg n），因此不太可能成爲瓶頸。此外，在轉向內聯彙編之前，您應該知道，無論何時使用內聯彙編，您都會擊敗可能在程序的該部分發生的大多數編譯器優化，並且通常會導致程序運行速度變慢 - 編譯器通常寫出比人類更好的彙編語言。

如果您想使用SSE，您最好使用內部函數 - 編譯器提供的特殊「函數」或關鍵字，它調用SSE指令，但否則會進行優化。這些內在函數可在Microsoft's Visual C++以及GNU Compiler Collection中找到。 （可能是大多數的編譯器，請查閱你的編譯器的文檔）

而不是試圖加速使用SSE的std::lower_bound，你應該嘗試不需要首先調用它。例如，如果您不斷地使用lower_bound將元素插入到矢量中，則應該知道您已有效創建的是insertion sort，並且該插入排序很差，這將需要四次時間。將新元素放在向量的末尾，然後在需要排序的時候對向量進行排序，可能會更好。這樣可以將事物排序爲O（n lg n）。如果您的數據訪問模式過於頻繁，那麼您應該使用類似於std::set的替代方法，它爲插入提供O（lg n）操作，而不是您當前使用的O（n + lg n）插入與載體相處。

當然，記得基準:)