Строка strlen MAX 16 с использованием побитовых операторов

Ответ 1

Это будет работать отлично, поскольку buf инициализируется нулем. В вашем решении есть !=, который будет использовать инструкцию перехода. Если GPU имеет несколько блоков XOR, следующий код можно конвейерно конвейерно настроить. С другой стороны, инструкция JUMP вызовет промывку трубопровода.

len = !!buf[0] +
      !!buf[1] +
      //...
      !!buf[15]

Обновление. Приведенный выше код и код OP создают тот же код сборки при компиляции GCC с флагами -O3. (разные, если флаги оптимизации не предусмотрены)

Ответ 2

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

"\0123456789abcde";

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

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

Ответ 3

Вот небольшой трюк, который я читал в Hacker Delight, называемый SWAR (SIMD-in-a-register), предполагающий 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 побитовое NOT всех столбцов вместе. Любая строка, имеющая все нули, будет иметь бит этой строки, установленный в результате. Затем мы просто находим первый бит, установленный в результате, и длину строки. Эта конкретная реализация гарантирует, что биты 16-31 задаются в результате, если все символы не являются NULL. Фактическая битовая транспозиция может быть намного быстрее (что означает без ветвей).

Ответ 4

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

// 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;

Ответ 5

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

Я уверен, что код, который вы выложили, выглядит только скользким, но на самом деле это не так здорово, если бы он был скомпилирован для многих процессоров, хотя он мог бы и на вас. Большинство процессоров, о которых я знаю, на самом деле не имеют простого способа получить 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];
...

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

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

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

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

Ответ 8

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

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.)

Ответ 9

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

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; 
}

Update:

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

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

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

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

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

Мне не удалось получить какие-либо другие функции, размещенные здесь для работы, поэтому я не смог сравнить. Ближайшей является оригинальная функция плаката, которая компилируется, но не всегда возвращает правильное значение. Когда это происходит, он выполняется примерно через 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);
}

Ответ 10

Предполагая 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-реализация будет использовать это.