Можно ли сравнивать целые области памяти в одном процессорном цикле? Точнее, можно сравнить две строки в одном цикле процессора с помощью какой-то инструкции ассемблера MMX? Или это strcmp -выполнение уже на основе этой оптимизации?
EDIT:
Или можно инструктировать компилятор С++ для удаления дубликатов строк, чтобы строки можно сравнивать просто по месту их памяти? Вместо memcmp(a,b) сравнивается a==b (предполагая, что a и b являются нативными const char* строками).
Не совсем. Ваша типичная 1-байтная команда сравнения занимает 1 цикл. Лучше всего использовать команды сравнения 64-бит MMX (см. эту страницу для примера). Однако они работают с регистрами, которые должны быть загружены из памяти. Загрузка памяти значительно повредит ваше время, потому что в лучшем случае вы будете в кэше L1, что добавит примерно 10-кратное замедление времени *. Если вы делаете тяжелую обработку строк, вы, вероятно, можете получить отличное ускорение там, но опять же, это будет больно.
Другие люди предлагают строки предварительного вычисления. Возможно, это сработает для вашего конкретного приложения, может быть, и нет. Вам нужно сравнивать строки? Вы можете сравнивать числа?
В вашем правлении предлагается сравнение указателей. Это опасная ситуация, если вы не можете специально гарантировать, что вы не будете сравнивать подстроку (т.е. Вы сравниваете строки из двух байтов: [0x40, 0x50] с [0x40, 0x42]. Это не "равные", но сравнение указателей говорит, что они есть).
Вы посмотрели на источник gcc strcmp()? Я бы предположил, что это будет идеальное место для начала.
* Говоря кратко, если цикл занимает 1 единицу, то попадание L1 занимает 10 единиц, удар L2 занимает 100 единиц, а фактический выстрел в RAM занимает очень много времени.
Просто используйте стандартные C strcmp() или С++ std::string::operator==() для сравнения строк.
Реализации их достаточно хороши и, вероятно, скомпилированы на очень высоко оптимизированную сборку, которую даже талантливые программисты по сборке сочтут сложными.
Так что не потейте мелочи. Я бы предложил посмотреть на оптимизацию других частей вашего кода.
Вы можете использовать библиотеку Boost Flyweight, чтобы ставить ваши неизменные строки. Тесты равенства/неравенства в строках затем становятся очень быстрыми, поскольку все, что ему нужно сделать в этой точке, - это сравнивать указатели (каламбур не предназначен).
Невозможно выполнить операции с целыми строками общего назначения за один цикл, но есть много оптимизаций, которые вы можете применить с дополнительной информацией.
memcmp, который быстрее, чем strcmp. Если ваше приложение является многокультурным, имейте в виду, что это работает только для порядкового сравнения строк.Изменить: если ваш проблемный домен позволяет использовать перечисление, это ваше одноцилиндровое решение для сравнения. Не бойся.
Это зависит от того, насколько вы выполняете предварительную обработку. В С# и Java есть процесс с именем interning strings, который делает каждую строчную карту одинаковым адресом, если у них одинаковое содержимое. Предполагая такой процесс, вы можете выполнить сравнение равенства строк с одной командой сравнения.
Заказ немного сложнее.
EDIT: Очевидно, что этот ответ оборачивается фактической проблемой попытки сравнения строк в течение одного цикла. Но это единственный способ сделать это, если у вас не будет последовательности инструкций, которые могут смотреть на неограниченный объем памяти в постоянное время, чтобы определить эквивалент strcmp. Это невероятно, потому что, если бы у вас была такая архитектура, человек, который продал ее вам, сказал бы: "Эй, вот эта удивительная инструкция, которая может выполнять сравнение строк за один цикл! Как это удивительно?" и вам не нужно будет публиковать вопрос о stackoverflow.
Но это только мое мотивированное мнение.
Если вы оптимизируете сравнение строк, вы можете использовать таблицу строк (тогда вам нужно только сравнить индексы двух строк, которые могут быть выполнены в одной машинной инструкции).
Если это невозможно, вы также можете создать хешированный строковый объект, содержащий строку и хэш. Тогда большую часть времени вам нужно сравнить хэши, если строки не равны. Если хеши будут соответствовать, вам нужно будет провести полное сравнение, но убедитесь, что оно не является ложным.
Или можно инструктировать С++ компилятор для удаления дубликатов строк, так что строки можно сравнить просто по месту их памяти?
Нет. Компилятор может удалять дубликаты внутри, но я не знаю компилятора, который гарантирует или предоставляет средства для доступа к такой оптимизации (за исключением, возможно, отключения). Конечно, стандарт С++ нечего сказать в этой области.
Предполагая, что вы имеете в виду x86... Здесь - документация Intel.
Но с головы, нет, я не думаю, что вы можете сравнивать больше, чем размер регистра за раз.
Из любопытства, почему вы спрашиваете? Я последний раз вызываю Кнута преждевременно, но... strcmp обычно выполняет довольно хорошую работу.
Изменить. Ссылка теперь указывает на современную документацию.
В цикле вы можете сравнивать более одного байта. Если мы возьмем пример x86-64, вы можете сравнить до 64 бит (8 байтов) в одной команде (cmps), это не обязательно один цикл, но обычно он будет в младших разрядах ( точная скорость зависит от конкретной версии процессора).
Однако это не означает, что вы сможете выполнить всю работу по сравнению двух массивов в памяти намного быстрее, чем strcmp: -
strcmp уже будут сильно оптимизированы, включая проверку того, соответствуют ли а и b одному и тому же адресу и любые подходящие оптимизации на уровне инструкций.Если вы не видите много времени, проведенного в strcmp, я бы не стал беспокоиться об этом - есть ли у вас конкретная проблема/вариант использования, который вы пытаетесь улучшить?
Даже если обе строки были кэшированы, было бы невозможно сравнивать (произвольно длинные) строки в одном процессорном цикле. Реализация strcmp в современной среде компилятора должна быть в значительной степени оптимизирована, поэтому вам не стоит слишком много оптимизировать.
EDIT (в ответ на ваш EDIT):
Вы не можете проинструктировать компилятор объединить ВСЕ повторяющиеся строки - большинство компиляторов могут сделать что-то подобное, но это только лучшее усилие (и я не знаю компилятора, где он работает в единицах компиляции).
Вы можете получить лучшую производительность, добавив строки к карте и сравнив итераторы после этого... само сравнение может быть одним циклом (или не намного больше), а затем
Если набор используемых строк исправлен, используйте перечисления - то, для чего они предназначены.
Здесь одно решение, которое использует значения типа enum вместо строк. Он поддерживает enum-value-inheritance и, таким образом, поддерживает сравнение, аналогичное сравнению с подстрокой. Он также использует специальный символ "¤" для именования, чтобы избежать конфликтов имен. Вы можете взять любое имя класса, функции или переменной и превратить его в значение enum (SomeClassA станет ¤SomeClassA).
struct MultiEnum
{
vector<MultiEnum*> enumList;
MultiEnum()
{
enumList.push_back(this);
}
MultiEnum(MultiEnum& base)
{
enumList.assign(base.enumList.begin(),base.enumList.end());
enumList.push_back(this);
}
MultiEnum(const MultiEnum* base1,const MultiEnum* base2)
{
enumList.assign(base1->enumList.begin(),base1->enumList.end());
enumList.assign(base2->enumList.begin(),base2->enumList.end());
}
bool operator !=(const MultiEnum& other)
{
return find(enumList.begin(),enumList.end(),&other)==enumList.end();
}
bool operator ==(const MultiEnum& other)
{
return find(enumList.begin(),enumList.end(),&other)!=enumList.end();
}
bool operator &(const MultiEnum& other)
{
return find(enumList.begin(),enumList.end(),&other)!=enumList.end();
}
MultiEnum operator|(const MultiEnum& other)
{
return MultiEnum(this,&other);
}
MultiEnum operator+(const MultiEnum& other)
{
return MultiEnum(this,&other);
}
};
MultiEnum
¤someString,
¤someString1(¤someString), // link to "someString" because it is a substring of "someString1"
¤someString2(¤someString);
void Test()
{
MultiEnum a = ¤someString1|¤someString2;
MultiEnum b = ¤someString1;
if(a!=¤someString2){}
if(b==¤someString2){}
if(b&¤someString2){}
if(b&¤someString){} // will result in true, because someString is substring of someString1
}
PS. У меня было слишком много свободного времени на моих руках сегодня утром, но изобретать колесо просто слишком весело иногда...:)