在我目前正在进行的项目中，我经常需要在排序数组中找到可以插入元素的最低可能索引(如 C++ 中的 std::lower_bound)。
使用 SSE 来加速我的算法对我来说似乎很有吸引力，因为我正在使用 uint32 数组，其大小通常是处理器缓存行的大小。
我以前从未使用过 SSE 指令，所以我无法弄清楚这个函数的 SSE 实现是什么样子的。请提供提示以帮助我使用 SSE 以最佳方式写出它。
最佳答案
std::lower_bound 之类的东西都无法使用 SSE 很好地扩展。 SSE 使事情变得更快的原因是它允许您一次进行多项计算。例如，单个 SSE 指令可能会导致同时进行 4 个乘法运算。但是，std::lower_bound 的操作方式无法并行化，因为算法中的每一步都需要前面步骤的比较结果。另外，它已经是 O(lg n)，因此不太可能成为瓶颈。
此外，在转向内联汇编之前，您应该知道，无论何时使用内联汇编，您都会破坏程序该部分可能发生的大多数编译器优化，结果通常您的程序会变慢——编译器通常编写比我们人类更好的汇编程序。
如果您想使用 SSE，您最好使用 intrinsics -- 编译器提供的特殊“函数”或关键字，它们调用 SSE 指令但允许进行优化。这些内在函数在 Microsoft's Visual C++ 中可用。 ，以及 GNU Compiler Collection . (可能还有大多数编译器。请查阅编译器的文档)
与其尝试使用 SSE 加速 std::lower_bound，不如首先尝试不需要调用它。例如，如果您不断地使用 lower_bound 将元素插入到 vector 中，您应该知道您有效创建的是 insertion sort。 ，并且插入排序很差，这将需要二次时间。您可能最好只是将新元素放在 vector 的末尾，然后在需要排序时对 vector 进行排序，这样可以将事情减少到 O(n lg n) 排序。如果您的数据访问模式使您过于频繁地求助，那么您应该使用类似 std::set 的东西，它为插入提供 O(lg n) 操作，而不是 O( n + lg n) 您当前使用 vector 获得的插入。
当然，记得进行基准测试 :)
关于c - 使用 SSE 加速 lower_bound 函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4770282/