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

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

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

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

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

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

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

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

You can use the Boost Flyweight library to intern your immutable strings. String equality/inequality tests then become very fast since all it has to do at that point is compare pointers (pun not intended).

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

• Если ваша проблемная область допускает использование выровненного, буфер фиксированного размера для строк, которые помещаются в машинный регистр, вы можете выполнять сравнения за один цикл (не считая инструкций загрузки).
• Если вы всегда отслеживаете длину ваших строк, вы можете сравнивать длины и использовать memcmp , что быстрее, чем strcmp . Если ваше приложение является мультикультурным, имейте в виду, что это работает только для сравнения порядковых строк .
• Похоже, вы используете C ++. Если вам нужны только сравнения на равенство с неизменяемыми строками, вы можете использовать решение для интернирования строк (скопируйте / вставьте ссылку, поскольку я ' ma new user), чтобы гарантировать, что одинаковые строки хранятся в одном и том же месте памяти, после чего вы можете просто сравнить указатели. См. en.wikipedia.org/wiki/String_interning
• Также ознакомьтесь с разделом 10 Справочного руководства по оптимизации Intel, где подробно описаны инструкции SSE 4.2 по обработке текста. www.intel.com/products/processor/manuals/

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

intel.com/products/processor/manuals/[1228 visibleEdit: если ваша проблемная область допускает использование перечисления, то является вашим решением для сравнения за один цикл. Не борись с этим.

intel.com/products/processor/manuals/[1228 visibleEdit: если ваша проблемная область допускает использование перечисления, то является вашим решением для сравнения за один цикл. Не борись с этим.

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

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

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

Упорядочивание немного сложнее.

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

Or is it possible to instruct c++ compiler to remove string duplicates, so that strings can be compared simply по месту в памяти?

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

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

EDIT (в ответ на ваше EDIT):

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

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

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

You can certainly compare more than one byte in a cycle. If we take the example of x86-64, you can compare up to 64-bits (8 bytes) in a single instruction (cmps), this isn't necessarily one cycle but will normally be in the low single digits (the exact speed depends on the specific processor version).

However, this doesn't mean you'll be able to all the work of comparing two arrays in memory much faster than strcmp :-

1. There's more than just the compare - you need to compare the two values, check if they are the same, and if so move to next chunk.
2. Most strcmp implementations will already be highly optimised, including checking if a and b point to the same address, and any suitable instruction-level optimisations.

Unless you're seeing alot of time spent in strcmp, I wouldn't worry about it - have you got a specific problem / use case you are trying to improve?

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

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

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

Править :

Here's one solution that uses enum-like values instead of strings. It supports enum-value-inheritance and thus supports comparison similar to substring comparison. It also uses special character "¤" for naming, to avoid name collisions. You can take any class, function, or variable name and make it into enum-value (SomeClassA will become ¤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. I had definitely too much free time on my hands this morning, but reinventing the wheel is just too much fun sometimes... :)