Strlen МАКСА 16 строк символов с помощью побитовых операторов

Ваш код работает некорректно. Например, рассмотрим буфер, содержащий что-то вроде:

"\0123456789abcde";

Согласно вашему коду, он имеет длину 15, но на самом деле его длина равна 0 из-за начального "\ 0".

Как бы хорошо ни было параллельное вычисление, простой факт состоит в том, что определение строки более или менее требует, чтобы она начиналась с начала и считала символы только до того момента, когда вы встретите "\ 0" (или, в вашем случае, до 16).

Побитовые операции ... может быть что-то вроде:

// TODO: optimize for 64-bit architectures
uint32_t *a = (uint32_t*)thestring;

for (int i = 0; i < 4; i++) // will be unwound
    for (int j = 0; j < 4; j++)
        if (a[i] & 0xff << j == 0)
           return 4*i+j;
return 16;

Вы можете начать с

template <typename T>
bool containsANull(T n) {
   return (n  - ((T) -1)/255) & ((T) -1)/255*128) & ~n;
}

и что-нибудь построить. Чтобы быть достойным, T, вероятно, должен быть 64-битным беззнаковым типом, но даже в этом случае есть некоторая корректировка, которая заставляет меня задуматься, достаточно ли длинен ваш буфер для того, чтобы этот трюк был полезен.

Как это работает?

(T) -1/255 - это битовая комбинация 0x01010101, повторяющаяся столько, сколько необходимо

(T) -1 / 255 * 128, таким образом, битовая комбинация 0x80808080 повторяется

if n is                        0x0123456789ABCDEF
n - 0x1111..1 is               0xF0123456789ABCDE
(n-0x1111...1) & 0x8888...8 is 0x8000000008888888
~n is                          0xFEDCBA9876543210 
so the result is               0x8000000000000000

Единственный способ получить здесь ненулевой байт - начать с нулевого байта.

Предполагая длину 64 бита и система с прямым порядком байтов:

long a = ((long *)string)[0];
long b = ((long *)string)[1];

a = (a - 0x0101010101010101UL) & ~a & 0x8080808080808080UL;
b = (b - 0x0101010101010101UL) & ~b & 0x8080808080808080UL;

return a ? count_trailing_zeros( a ) / 8 : b ? 8 + count_trailing_zeros( b ) / 8 : 16;

Для прямого порядка следования начальных нулей. Любая системная реализация strlen будет использовать это.

Вы можете вертеть все, что хотите, но вы, вероятно, не победите этого:

int fast1(const char *s)
{ 
    if (!*s++) return 0; 
    if (!*s++) return 1; 
    if (!*s++) return 2; 
    if (!*s++) return 3; 
    if (!*s++) return 4; 
    if (!*s++) return 5; 
    if (!*s++) return 6; 
    if (!*s++) return 7; 
    if (!*s++) return 8; 
    if (!*s++) return 9; 
    if (!*s++) return 10; 
    if (!*s++) return 11; 
    if (!*s++) return 12; 
    if (!*s++) return 13; 
    if (!*s++) return 14; 
    if (!*s++) return 15; 
}

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

int fast2(const char *s)
{ 
    if (!s[0]) return 0; 
    if (!s[1]) return 1; 
    if (!s[2]) return 2; 
    if (!s[3]) return 3; 
    if (!s[4]) return 4; 
    if (!s[5]) return 5; 
    if (!s[6]) return 6; 
    if (!s[7]) return 7; 
    if (!s[8]) return 8; 
    if (!s[9]) return 9; 
    if (!s[10]) return 10; 
    if (!s[11]) return 11; 
    if (!s[12]) return 12; 
    if (!s[13]) return 13; 
    if (!s[14]) return 14; 
    if (!s[15]) return 15; 
}

Обновление:

Я профилировал обе эти функции на моем Core2Duo T7200 @ 2,0 ГГц, Windows XP pro, Visual Studio 2008 с отключенной оптимизацией. (Включение оптимизатора заставляет VS заметить, что в моем цикле синхронизации нет вывода, поэтому он полностью удаляет его).

Я вызвал каждую функцию в цикле 2 ²² раз, затем взял среднее значение за 8 прогонов.

fast1 занимает около 87,20 нс на вызов функции.

fast2 занимает около 45,46 нс на вызов функции.

Итак, на моем CPU версия с индексированием массива почти в два раза быстрее, чем версия с указателем.

Мне не удалось заставить работать какие-либо другие функции, размещенные здесь, поэтому я не мог сравнивать. Ближайшей является исходная функция постера, которая компилируется, но не всегда возвращает правильное значение. Когда это происходит, он выполняется примерно за 59 нс на вызов функции.

Обновление 2

Эта функция тоже довольно быстрая, около 60 нс на вызов. Я предполагаю, что разыменование указателя выполняется адресной единицей и умножением на целочисленную единицу, поэтому операции конвейерные. В других моих примерах вся работа выполняется адресным блоком.

int fast5(const char *s)
{
    return  /* 0 * (s[0] == 0) + don't need to test 1st byte */
            1 * (s[1] == 0)  +
            2 * (s[2] == 0)  +
            3 * (s[3] == 0)  +
            4 * (s[4] == 0)  +
            5 * (s[5] == 0)  +
            6 * (s[6] == 0)  +
            7 * (s[7] == 0)  +
            8 * (s[8] == 0)  +
            9 * (s[9] == 0)  +
            10 * (s[10] == 0) +
            11 * (s[11] == 0) +
            12 * (s[12] == 0) +
            13 * (s[13] == 0) +
            14 * (s[14] == 0) +
            15 * (s[15] == 0);
}

Обратитесь к fstrlen (), реализованному Полом Хси на ...

http://www.azillionmonkeys.com/ qed / asmexample.html

Хотя это не совсем то, что вы ищете, после небольшой настройки он должен сделать это за вас.

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

Вот небольшой трюк, о котором я читал в Hacker's Delight, под названием SWAR (SIMD-внутри-регистр), предполагающий 8 бит на символ:

#define CHAR_BITS 8
uint_fast_16_t all_character_bits[CHAR_BITS]= { 0 };

for (int bit_index= 0; bit_index<CHAR_BITS; ++bit_index)
{
    for (int character_index= 0; character_index<16; ++character_index)
    {
        all_character_bits[bit_index]|= ((buff[character_index] >> bit_index) & 1) << character_index;
    }
}

uint_fast_32_t zero_byte_character_mask= ~0;

for (int bit_index= 0; bit_index<CHAR_BITS; ++bit_index)
{
    zero_byte_character_mask&= (0xffff0000 | ~all_character_bits[bit_index]);
}

uint_fast_8_t first_null_byte= first_bit_set(zero_byte_character_mask);

где first_bit_set - любое количество популярных и быстрых реализаций поиска первого бит, установленного в целое число.

Основная идея здесь состоит в том, чтобы взять 16 символов как матрицу 8x16 бит и AND побитовое НЕ всех столбцов вместе. Для любой строки, состоящей только из нулей, в результате будет установлен бит этой строки. Затем мы просто находим первый установленный бит в результате и длину строки. Эта конкретная реализация гарантирует, что биты 16–31 будут установлены в результате, если все символы не равны NULL. Фактическая перестановка битов также может быть намного быстрее (то есть без ветвей).

В гипотетическом C ++ - подобном языке, предполагающем дополнение 2 и обратный порядок байтов,

int128_t v = *reinterpret_cast<int128_t*>(thestring);
const int bit_count = 128;
int eight = ((1 << 64) - 1 - v) >> (bit_count - 4) & 8;
v >>>= 8 * eight;
int four  = ((1 << 32) - 1 - v) >> (bit_count - 3) & 4;
v >>>= 8 * four;
int two   = ((1 << 16) - 1 - v) >> (bit_count - 2) & 2;
v >>>= 8 * two;
int one   = ((1 <<  8) - 1 - v) >> (bit_count - 1) & 1;
return (one | two | four | eight) + !!v;

(Изменено из http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog . )

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

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

set R1, 0
test R2+0, 0
cinc R1                   ; conditional increment
test R2+1, 0
cinc R1
...

Это может хорошо работать для графического процессора если он может выполнять условные приращения и хорошо работать с элементами размером с октет.

Если бы компилятор проделал отличную работу, на многих процессорах это было бы примерно так:

set R1, 0
test R2+0, 0
jz end  ; jump if zero
inc R1
test R2+1, 0
jz end
inc R1
...

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

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

int acc = 0;
acc += str[0]/str[0];
acc += str[1]/str[1];
...

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

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

Вам следует ознакомиться с Bit Twiddling Hacks , чтобы получить отличный способ ускорить strlen, который хорошо работает для регистров большого размера.

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