Сравнение строк C ++ за один такт

Question

Можно ли сравнить целые области памяти в одном цикле процессора? Точнее, можно ли сравнить две строки в одном цикле процессора, используя какую-то инструкцию ассемблера MMX? Или strcmp -воплощение уже основано на этой оптимизации?

EDIT: Или же можно поручить компилятору C ++ удалить дубликаты строк, чтобы строки можно было сравнивать просто по их расположению в памяти? Вместо memcmp(a,b) по сравнению a==b (при условии, что a и b являются нативными const char* строками).

Answer 1

Просто используйте стандарт C strcmp() или C ++ std::string::operator==() для сравнения строк.

Их реализации достаточно хороши и, вероятно, скомпилированы в очень высокооптимизированную сборку, которую даже талантливым программистам на сборке сложно найти.

Так что не парься по мелочам. Я бы посоветовал взглянуть на оптимизацию других частей вашего кода.

Answer 2

Вы можете использовать библиотеку Boost Flyweight для интернирования ваших неизменяемых строк. Затем тесты на равенство / неравенство в строке становятся очень быстрыми, поскольку в этот момент все, что нужно сделать, это сравнить указатели (каламбур не предназначен).

Answer 3

Не действительно . Ваша типичная 1-байтовая инструкция сравнения занимает 1 цикл. Лучше всего было бы использовать инструкции сравнения 64-битных MMX (см. на этой странице для примера) . Однако те работают с регистрами, которые должны быть загружены из памяти. Загрузка памяти значительно повредит вашему времени, потому что вы в лучшем случае будете выходить в кэш L1, что добавляет 10-кратное замедление *. Если вы выполняете какую-то тяжелую обработку строк, вы, вероятно, сможете добиться некоторого изящного ускорения, но опять же, это будет больно.

Другие люди предлагают предварительно вычислять строки. Может быть, это будет работать для вашего конкретного приложения, а может и нет. У вас есть для сравнения строк? Вы можете сравнить цифры?

Ваша редакция предлагает сравнивать указатели. Это опасная ситуация, если вы не гарантируете, что не будете сравнивать подстроки (т. Е. Сравниваете две строки байтов: [0x40, 0x50] с [0x40, 0x42]. Это не «равно», а указатель сравнения скажет что они есть).

Вы смотрели на источник gcc strcmp ()? Я бы предположил, что это было бы идеальной отправной точкой.

* Грубо говоря, если цикл занимает 1 единицу, удар L1 - 10 единиц, удар L2 - 100 единиц, а фактическое попадание в ОЗУ занимает очень долго .

Answer 4

Невозможно выполнять строковые операции общего назначения за один цикл, но есть много способов оптимизации, которые можно применить с дополнительной информацией.

• Если ваш проблемный домен позволяет использовать выровненный буфер фиксированного размера для строк, который вписывается в машинный регистр, вы можете выполнять сравнения за один цикл (не считая инструкции по загрузке).
• Если вы всегда отслеживаете длину строк, вы можете сравнить длины и использовать memcmp, что быстрее, чем strcmp. Если ваше приложение мультикультурное, имейте в виду, что это работает только для сравнения порядковых строк .
• Похоже, вы используете C ++. Если вам нужно только сравнение на равенство с неизменяемыми строками, вы можете использовать решение для интернирования строк (ссылка на копирование / вставку, так как я новый пользователь), чтобы гарантировать, что одинаковые строки хранятся в одной и той же ячейке памяти, после чего вы можете просто сравнить указатели. См. ru.wikipedia.org / wiki / String_interning
• Кроме того, ознакомьтесь с Руководством по оптимизации Intel, глава 10, для получения подробных инструкций по обработке текста в SSE 4.2. www.intel.com / продукты / процессор / Инструкции /

Редактировать: Если ваш проблемный домен позволяет использовать перечисление, то является вашим решением для сравнения за один цикл. Не борись с этим.

Answer 5

Если вы оптимизируете для сравнения строк, вы можете использовать таблицу строк (тогда вам нужно только сравнить индексы двух строк, что можно сделать в одной машинной инструкции).

Если это невозможно, вы также можете создать объект хешированной строки, который содержит строку и хеш. Тогда в большинстве случаев вам нужно сравнивать хэши, только если строки не равны. Если хэши совпадают, вам придется провести полное сравнение, чтобы убедиться, что это не ложный положительный результат.

Answer 6

Это зависит от того, сколько предварительной обработки вы делаете. В C # и Java есть процесс, называемый интернирующими строками, который делает каждую строку отображаемой на один и тот же адрес, если они имеют одинаковое содержимое. Предполагая, что такой процесс, вы могли бы сделать сравнение равенства строк с одной инструкцией сравнения.

Заказ немного сложнее.

РЕДАКТИРОВАТЬ: Очевидно, что этот ответ обходит реальную проблему попытки сравнения строк в течение одного цикла. Но это единственный способ сделать это, если у вас нет последовательности инструкций, которая может смотреть на неограниченный объем памяти в постоянное время, чтобы определить эквивалент strcmp. Это невероятно, потому что, если бы у вас была такая архитектура, человек, который продал ее вам, сказал бы: «Эй, вот эта классная инструкция, которая может сравнить строки за один цикл! и вам не нужно будет публиковать вопрос на stackoverflow.

Но это только мое аргументированное мнение.

Answer 7

Или есть возможность поучить с ++ компилятор для удаления дубликатов строк, так что строки можно сравнивать просто по месту их памяти?

Нет. Компилятор может удалять дубликаты изнутри, но я не знаю ни одного компилятора, который бы гарантировал или предоставлял средства для доступа к такой оптимизации (за исключением, возможно, ее отключения). Конечно, стандарту C ++ нечего сказать в этой области.

Answer 8

Вы, конечно, можете сравнить более одного байта в цикле. Если мы возьмем пример x86-64, вы можете сравнить до 64 бит (8 байт) в одной инструкции (cmps), это не обязательно один цикл, но обычно он будет в младших разрядах ( точная скорость зависит от конкретной версии процессора).

Однако это не означает, что вы сможете сравнивать два массива в памяти гораздо быстрее, чем strcmp: -

1. Это больше, чем просто сравнение - вам нужно сравнить два значения, проверить, совпадают ли они, и, если это так, перейти к следующему фрагменту.
2. Большинство strcmp реализаций уже будут сильно оптимизированы, включая проверку, указывают ли a и b на один и тот же адрес, и любые подходящие оптимизации на уровне команд.

Если бы вы не видели много времени, проведенного в strcmp, я бы не волновался об этом - есть ли у вас конкретная проблема / сценарий использования, который вы пытаетесь улучшить?

Answer 9

Предполагается, что вы имеете в виду x86 ... Здесь - документация Intel.

Но я не думаю, что вы можете сравнивать больше, чем размер регистра за раз.

Из любопытства, почему вы спрашиваете? Я последний, кто преждевременно вызывает Кнута, но ... strcmp обычно делает довольно хорошую работу.

Редактировать : теперь ссылка указывает на современную документацию.

Answer 10

Даже если бы обе строки были кэшированы, было бы невозможно сравнивать (произвольно длинные) строки в одном цикле процессора. Реализация strcmp в современной среде компилятора должна быть в значительной степени оптимизирована, поэтому вам не стоит слишком много оптимизировать.

РЕДАКТИРОВАТЬ (в ответ на ваше РЕДАКТИРОВАНИЕ):

1. Вы не можете дать указание компилятору унифицировать ВСЕ повторяющиеся строки - большинство компиляторов могут делать что-то подобное, но это только лучшее из возможного (и я не знаю ни одного компилятора, где он работает через модули компиляции).

2. Вы можете повысить производительность, добавив строки на карту и сравнив итераторы после этого ... само сравнение может быть на один цикл (или не намного больше), чем

3. Если набор используемых строк фиксирован, используйте перечисления - вот для чего они нужны.