Ничего подобного std::lower_bound не будет хорошо масштабироваться с использованием SSE. Причина, по которой SSE ускоряет процесс, заключается в том, что он позволяет выполнять несколько вычислений одновременно. Например, одна инструкция SSE может привести к одновременному выполнению 4 операций умножения. Однако способ работы std::lower_bound нельзя распараллелить, потому что каждый шаг в алгоритме требует сравнения результатов предыдущих шагов. Кроме того, это уже O (LG N), и в результате вряд ли будет узким местом.
Более того, прежде чем переходить к встроенной сборке, вы должны знать, что всякий раз, когда вы используете встроенную сборку, вы побеждаете большинство оптимизаций компилятора, которые могут произойти в этом разделе вашей программы, и часто в результате ваша программа будет работать медленнее - компиляторы обычно пиши лучше ассемблера, чем мы, люди, пишем.
Если вы хотите использовать SSE, вам лучше использовать intrinsics - специальные «функции» или ключевые слова, предоставляемые компилятором, которые вызывают инструкцию SSE, но в остальном позволяют выполнять оптимизацию. Такие встроенные функции доступны в Microsoft Visual C ++ , а также в GNU Compiler Collection . (И, возможно, большинство других компиляторов. Обратитесь к документации вашего компилятора)
Вместо того, чтобы пытаться ускорить std::lower_bound с помощью SSE, вы должны попытаться не вызывать его в первую очередь. Например, если вы постоянно вставляете элементы в вектор, используя lower_bound, вы должны знать, что вы фактически создали сортировку вставки , и плохую сортировку вставки, что потребует квадратичного времени , Скорее всего, было бы лучше просто поместить новые элементы в конец вектора, а затем отсортировать вектор, когда вам это нужно, после сортировки, что приводит к сортировке O (n lg n). Если ваши шаблоны доступа к данным таковы, что вы будете прибегать к ним слишком часто, вам следует использовать что-то вроде std::set, которое обеспечивает операции O (lg n) для вставок, а не O (n + lg n) вставок, которые вы ' в настоящее время получаю с векторами.
И, конечно же, не забывайте тестировать:)