Более быстрый алгоритм «Поиск одного совпадающего символа» (ala strchr).
Важные примечания:
Эти функциииспользуйте «число / количество (ведущих | конечных) нулей» gcc intrinsic- __builtin_ctz компилятора.Эти функции могут быть быстрыми только на машинах, на которых есть инструкция (ы), выполняющая эту операцию (например, x86, ppc, arm).
Эти функции предполагают, что целевая архитектура можетвыполнять 32- и 64-битные не выровненные нагрузки.Если ваша целевая архитектура не поддерживает это, вам необходимо добавить некоторую логику запуска для правильного выравнивания показаний.
Эти функции нейтральны по отношению к процессору.Если у целевого ЦП есть векторные инструкции, вы могли бы сделать (намного) лучше.Например, приведенная ниже функция strlen использует SSE3 и может быть тривиально изменена на XOR отсканированных байтов для поиска байта, отличного от 0.Тесты производительности на ноутбуке Core 2 с частотой 2,66 ГГц и Mac OS X 10,6 (x86_64):
- 843,433 МБ / с для
strchr - 2656,742 МБ / с для
findFirstByte64 - 13094,479 МБ / с для
strlen
... 32-разрядной версии:
#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u) ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (__builtin_ctz(_x) + 1) >> 3; })
#endif
unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
byteMask32 |= byteMask32 << 16;
while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}
... и64-битная версия:
#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (__builtin_ctzll(_x) + 1) >> 3; })
#endif
unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
byteMask64 |= byteMask64 << 16;
byteMask64 |= byteMask64 << 32;
while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}
Редактировать 2011/06/04 В комментариях ОП указывается, что в этом решении есть «непреодолимая ошибка»:
он может читать после запрошенного байта или нулевого терминатора, который может получить доступ к неотображенной странице или странице без разрешения на чтение.Вы просто не можете использовать большие чтения в строковых функциях, если они не выровнены.
Это технически верно, но применимо практически к любому алгоритму, который работает с блоками, размер которых превышает один байт, включая метод , предложенный OP в комментариях:
Типичная реализация strchr не наивна, но несколько более эффективна, чем вы дали.В конце приведен наиболее широко используемый алгоритм: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
Он также действительно не имеет ничего общего с alignment per se.Да, это может потенциально привести к поведению, обсуждаемому на большинстве используемых архитектур, но это больше связано с деталями реализации микроархитектуры - если не выровненное чтение пересекает границу 4 КБ (опять же, типично), тогда это чтение вызовет программузавершающая ошибка, если следующая граница страницы 4K не отображена.
Но это не «ошибка» в алгоритме, приведенном в ответе, - такое поведение вызвано тем, что такие функции, как strchr и strlen не принимаютlength аргумент для ограничения размера поиска.Поиск char bytes[1] = {0x55};, который для целей нашего обсуждения именно так и происходит в самом конце границы страницы 4K VM, и следующая страница не отображается, с strchr(bytes, 0xAA) (где strchr - это байт ввременная реализация) будет зависать точно так же.То же самое для strchr родственника двоюродного брата strlen.
Без аргумента length невозможно определить, когда следует переключиться с высокоскоростного алгоритма и вернуться к побайтовому алгоритму,Гораздо более вероятной «ошибкой» будет чтение «за пределами размера выделения», что технически приводит к undefined behavior в соответствии с различными стандартами языка C и будет помечено как ошибка чем-то вроде valgrind.
Таким образом, все, что работает с блоками большего размера, будет работать быстрее, поскольку этот код отвечает и код, указанный OP, но должен иметь семантику считывания с точностью до байта, вероятно, будет "глючным", еслиlength аргумент для управления угловым регистром "последнего чтения" отсутствует.
Код в этом ответе является ядром для возможности найти первый байт в естественном размере слова ЦП.чанк быстро, если целевой процессор имеет быструю ctz подобную инструкцию.Тривиально добавить такие вещи, как проверка того, что он работает только на правильно выровненных естественных границах, или некоторая форма ограничения length, что позволит вам переключиться с высокоскоростного ядра на более медленную побайтную проверку.
ОП также заявляет в комментариях:
Что касается оптимизации ctz, то она имеет значение только для хвостовой операции O (1).Это может улучшить производительность при использовании крошечных строк (например, strchr("abc", 'a');, но, конечно, не применительно к строкам любого большого размера.
То, верно ли это утверждение, во многом зависит от рассматриваемой микроархитектуры. Использованиеканоническая 4-этапная модель конвейера RISC, то это почти наверняка так, но очень трудно сказать, верно ли это для современного суперскалярного суперкадрового ЦП, в котором скорость ядра может сильно затормозить скорость потоковой памяти.В этом случае это не только правдоподобно, но и довольно часто, поскольку существует большой разрыв в «количестве команд, которые могут быть удалены» относительно «количества байтов, которые могут быть переданы», чтобы у вас было «количество»инструкции, которые могут быть удалены для каждого байта, который может быть передан ". Если он достаточно велик, команду ctz + можно выполнить" бесплатно ".