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

Question

Задача состоит в том, чтобы найти самый быстрый способ определить в C / C ++ длину строки c, используя побитовые операции в C.

char thestring[16];

C-строка имеет максимальный размер 16 символов и находится внутри буфера Если строка равна 16 символам, в конце не будет нулевого байта.

Я уверен, что можно сделать, но пока не понял правильно.

Сейчас я работаю над этим, но при условии, что строка записана в буфер заполненный нулями .

len =   buff[0] != 0x0 +
            buff[1] != 0x0 +
            buff[2] != 0x0 +
            buff[3] != 0x0 +
            buff[4] != 0x0 +
            buff[5] != 0x0 +
            buff[6] != 0x0 +
            buff[7] != 0x0 +
            buff[8] != 0x0 +
            buff[9] != 0x0 +
            buff[10] != 0x0 +
            buff[11] != 0x0 +
            buff[12] != 0x0 +
            buff[13] != 0x0 +
            buff[14] != 0x0 +
            buff[15] != 0x0;

Примечание : буфер заполнен нулями"\ 0123456789abcde" не может быть.

Answer 1

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

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

---

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

Answer 2

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

"\0123456789abcde";

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

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

Answer 3

Вот небольшой трюк, который я прочитал в «Хакерском восторге» под названием 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 поразрядно-НЕ всех столбцов вместе. Любая строка со всеми нулями будет иметь бит этой строки в результате. Затем мы просто находим первый бит, установленный в результате, и это длина строки. Эта конкретная реализация гарантирует, что биты 16-31 установлены в результате, если все символы не равны NULL. Фактическое преобразование битов также может быть намного быстрее (то есть без ветвей).

Answer 4

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

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

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

Answer 5

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

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 ^{22 * ​​1014 * раз, затем взял среднее значение за 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);
}

Answer 6

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

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

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

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

Answer 7

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

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

и что-то построить. Чтобы иметь значение W, вероятно, должен быть 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

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

Answer 8

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

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

Answer 9

Предполагается, что 64-битная система long и little-endian:

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

Answer 10

В гипотетическом 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.)