Как реализовать strlen максимально быстро

Question

Предположим, что вы работаете с 32-разрядной системой x86. Ваша задача - реализовать strlen как можно быстрее.

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

Нетрудно найти первый адрес выравнивания в данной строке.

Затем мы можем прочитать память один раз с 4 байтами и подсчитать ее общую длину. Но мы должны остановиться, как только в 4 байтах будет нулевой байт, и посчитать левые байты до нулевого байта. Чтобы быстро проверить нулевой байт, есть фрагмент кода из glibc:

unsigned long int longword, himagic, lomagic;
himagic = 0x80808080L;  
lomagic = 0x01010101L;

// There's zero byte in 4 bytes.
if (((longword - lomagic) & ~longword & himagic) != 0) {
    // do left thing...
}

Я использовал его в Visual C ++, чтобы сравнить с реализацией CRT. ЭЛТ гораздо быстрее, чем выше.

Я не знаком с реализацией CRT, они использовали более быстрый способ проверки нулевого байта?

Answer 1

Вы можете сохранить длину строки вместе со строкой при ее создании, как это делается в Pascal.

Answer 2

Первый ЭЛТ записан напрямую на ассемблере. Вы можете увидеть его исходный код здесь C:\Program Files\Microsoft Visual Studio 9.0\VC\crt\src\intel\strlen.asm (это для VS 2008)

Answer 3

Это зависит. Библиотека Microsoft действительно имеет две разные версии strlen. Одна из них - это переносимая версия на C, представляющая собой наиболее тривиальную версию strlen, довольно близкую (и, вероятно, эквивалентную) к:

size_t strlen(char const *str) { 
    for (char const *pos=str; *pos; ++pos)
        ;
    return pos-str;
}

Другой язык написан на ассемблере (используется только для Intel x86) и очень похож на то, что вы имеете выше, по крайней мере, до загрузки 4 байтов, проверка одного из них равна нулю и реагирует соответствующим образом. Единственное очевидное отличие состоит в том, что вместо вычитания они в основном добавляют пре-отрицательные байты и добавляют. То есть вместо word-0x0101010101 они используют word + 0x7efefeff.

Answer 4

есть также встроенные версии компилятора, которые используют пару команд REPNE SCAS, хотя они, как правило, на старых компиляторах, они все еще могут быть довольно быстрыми. Существуют также версии strlen для SSE2, такие как Реализация библиотеки производительности доктора Агнера Фога , или что-то типа this

Answer 5

Удалите эти суффиксы 'L' и посмотрите ... Вы переводите все вычисления в "long"! В моих 32-битных тестах это удваивает стоимость.

Я также делаю две микрооптимизации:

• Поскольку большинство строк, которые мы используем для сканирования, состоят из символов ASCII в диапазоне от 0 до 127, старший бит (почти) никогда не устанавливается , поэтому проверять его можно только во втором тесте.

• Увеличьте индекс, а не указатель , который дешевле в некоторых архитектурах (особенно x86) и даст вам длину для 'free' ...

---

uint32_t gatopeich_strlen32(const char* str)
{
    uint32_t *u32 = (uint32_t*)str, u, abcd, i=0;
    while(1)
    {
        u = u32[i++];
        abcd = (u-0x01010101) & 0x80808080;
        if (abcd && // If abcd is not 0, we have NUL or a non-ASCII char > 127...
             (abcd &= ~u)) // ... Discard non-ASCII chars
        {
        #if BYTE_ORDER == BIG_ENDIAN
            return 4*i - (abcd&0xffff0000 ? (abcd&0xff000000?4:3) : abcd&0xff00?2:1);
        #else
            return 4*i - (abcd&0xffff ? (abcd&0xff?4:3) : abcd&0xff0000?2:1);
        #endif
        }
    }
}

Answer 6

Очевидно, что создание такого узкого цикла в ассемблере было бы самым быстрым, однако если вы хотите / хотите сделать его более читабельным и / или переносимым в C (++), вы все равно можете увеличить скорость стандартного использовать ключевое слово register .

Ключевое слово register предлагает компилятору сохранить счетчик в регистре ЦП, а не в памяти, что значительно ускорит цикл.

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

size_t strlen ( const char* s ) {
  for (register const char* i=s; *i; ++i);
  return (i-s);
}

Answer 7

Предполагая, что вы знаете максимально возможную длину и вы инициализировали память до \ 0 перед использованием, вы можете выполнить двоичное разбиение и перейти влево / вправо в зависимости от значения (\ 0, разделение слева, иначе разделение право). Таким образом, вы значительно уменьшите количество чеков, которое вам нужно, чтобы найти длину. Не оптимально (требуется некоторая настройка), но должно быть очень быстрым.

// Эрик