быстрый способ проверить, является ли массив символов нулем [дубликат]
4 ответа
В настоящее время за исключением использования SIMD расширений (например, SSE на процессорах x86 ), вы также можете перебрать массив и сравнить каждое значение с 0.
В далеком прошлом выполнение сравнения и условного перехода для каждого элемента в массиве (в дополнение к самой ветви цикла) считалось дорогостоящим и, в зависимости от того, как часто (или рано) вы могли ожидать ненулевой элемент, который должен появиться в массиве, вы могли бы полностью обойтись без условных обозначений внутри цикла , используя только побитовое или для обнаружения любых установленных битов и отложив фактическую проверку до завершения цикла :
int sum = 0;
for (i = 0; i < ARRAY_SIZE; ++i) {
sum |= array[i];
}
if (sum != 0) {
printf("At least one array element is non-zero\n");
}
Однако с сегодняшними конвейерными суперскалярными процессорами, укомплектованными предсказанием ветвлений , все подходы, не связанные с SSE, практически неразличимы внутри цикла. Во всяком случае, сравнение каждого элемента с нулем и преждевременный выход из цикла (как только встречается первый ненулевой элемент) в конечном итоге может быть более эффективным, чем sum | = array [i] подход (который всегда проходит по всему массиву), если, то есть, вы не ожидаете, что ваш массив почти всегда будет состоять исключительно из нулей (в этом случае используется подход sum | = array [i] действительно без ветвлений, используя GCC -funroll-loops , может дать вам лучшие цифры - см. цифры ниже для процессора Athlon, результаты могут отличаться в зависимости от модели процессора и производителя .)
#include <stdio.h>
int a[1024*1024];
/* Methods 1 & 2 are equivalent on x86 */
int main() {
int i, j, n;
# if defined METHOD3
int x;
# endif
for (i = 0; i < 100; ++i) {
# if defined METHOD3
x = 0;
# endif
for (j = 0, n = 0; j < sizeof(a)/sizeof(a[0]); ++j) {
# if defined METHOD1
if (a[j] != 0) { n = 1; }
# elif defined METHOD2
n |= (a[j] != 0);
# elif defined METHOD3
x |= a[j];
# endif
}
# if defined METHOD3
n = (x != 0);
# endif
printf("%d\n", n);
}
}
$ uname -mp
i686 athlon
$ gcc -g -O3 -DMETHOD1 test.c
$ time ./a.out
real 0m0.376s
user 0m0.373s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD2 test.c
$ time ./a.out
real 0m0.377s
user 0m0.372s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD3 test.c
$ time ./a.out
real 0m0.376s
user 0m0.373s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD1 -funroll-loops test.c
$ time ./a.out
real 0m0.351s
user 0m0.348s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD2 -funroll-loops test.c
$ time ./a.out
real 0m0.343s
user 0m0.340s
sys 0m0.003s
$ gcc -g -O3 -DMETHOD3 -funroll-loops test.c
$ time ./a.out
real 0m0.209s
user 0m0.206s
sys 0m0.003s
Если вы хотите сделать это в 32-битном C, возможно, просто переберите массив как 32-битный целочисленный массив и сравните его с 0, а затем убедитесь, что значение в конце также равно 0.
{ {1}}Вот короткое и быстрое решение, если вы не против использовать встроенную сборку.
#include <stdio.h>
int main(void) {
int checkzero(char *string, int length);
char str1[] = "wow this is not zero!";
char str2[] = {0, 0, 0, 0, 0, 0, 0, 0};
printf("%d\n", checkzero(str1, sizeof(str1)));
printf("%d\n", checkzero(str2, sizeof(str2)));
}
int checkzero(char *string, int length) {
int is_zero;
__asm__ (
"cld\n"
"xorb %%al, %%al\n"
"repz scasb\n"
: "=c" (is_zero)
: "c" (length), "D" (string)
: "eax", "cc"
);
return !is_zero;
}
Если вы не знакомы со сборкой, я объясню, что мы здесь делаем: мы сохраняем длину строки в регистре и просим процессор сканировать строку на предмет нуля (мы указываем это, устанавливая 8 младших битов аккумулятора, а именно %% al , до нуля), уменьшая значение указанного регистра на каждой итерации, пока не встретится ненулевой байт. Теперь, если в строке были все нули, регистр тоже будет нулевым, поскольку его длина раз уменьшалась. Однако, если было обнаружено ненулевое значение, «цикл», который проверял наличие нулей, завершился преждевременно, и, следовательно, регистр не будет нулевым. Затем мы получаем значение этого регистра и возвращаем его логическое отрицание.
Профилирование дало следующие результаты:
$ time or.exe
real 0m37.274s
user 0m0.015s
sys 0m0.000s
$ time scasb.exe
real 0m15.951s
user 0m0.000s
sys 0m0.046s
(Оба тестовых примера выполнялись 100000 раз на массивах размером 100000. Код or.exe взят из ответа Влада. Вызовы функций были исключены в обоих случаях. )
Если массив любого приличного размера, вашим ограничивающим фактором на современном ЦП будет доступ к памяти.
Обязательно используйте предварительную выборку из кеша на приличном расстоянии вперед (например, 1-2 КБ) с чем-то вроде __dcbt или prefetchnta (или prefetch0, если вы собираетесь снова использовать буфер в ближайшее время).
Вы также захотите сделать что-то вроде SIMD или SWAR с или несколькими байтами за раз. Даже с 32-битными словами это будет в 4 раза меньше операций, чем посимвольная версия.Я бы порекомендовал развернуть или и превратить их в «дерево» из или. Вы можете видеть, что я имею в виду в моем примере кода - здесь используется суперскалярная способность выполнять две целочисленные операции (или) параллельно, используя операции, которые не имеют такого большого количества зависимостей между промежуточными данными. Я использую дерево размером 8 (4x4, затем 2x2, затем 1x1), но вы можете расширить его до большего числа в зависимости от того, сколько свободных регистров у вас есть в архитектуре вашего процессора.
В следующем примере псевдокода для внутреннего цикла (без пролога / эпилога) используются 32-битные целые числа, но вы можете делать 64/128-битные с MMX / SSE или чем-то еще, что вам доступно. Это будет довольно быстро, если вы предварительно загрузили блок в кеш. Также вам, возможно, потребуется выполнить невыровненную проверку перед, если ваш буфер не выровнен по 4 байтам, и после, если ваш буфер (после выравнивания) не кратен 32 байтам по длине.
const UINT32 *pmem = ***aligned-buffer-pointer***;
UINT32 a0,a1,a2,a3;
while(bytesremain >= 32)
{
// Compare an aligned "line" of 32-bytes
a0 = pmem[0] | pmem[1];
a1 = pmem[2] | pmem[3];
a2 = pmem[4] | pmem[5];
a3 = pmem[6] | pmem[7];
a0 |= a1; a2 |= a3;
pmem += 8;
a0 |= a2;
bytesremain -= 32;
if(a0 != 0) break;
}
if(a0!=0) then ***buffer-is-not-all-zeros***
Я бы фактически предложил инкапсулировать сравнение «строки» значений в одну функцию, а затем развернуть ее пару раз с предварительной выборкой из кеша.