быстрый способ проверить, равен ли массив символов нулю

Question

У меня есть массив байтов в памяти. Каков самый быстрый способ увидеть, все ли байты в массиве равны нулю?

Answer 1

В настоящее время, короткие использования 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"); 
} 

Однако с конвейерных супер-скалярной современных процессоров конструкций комплектных с branch prediction, все подходы, не SSE являются virtualy неотличимы внутри цикла. Если что-либо, сравнение каждого элемента с нулем и выход из цикла в начале (как только встретится первый ненулевой элемент), может быть в конечном счете более эффективным, чем подход sum |= array[i] (который всегда проходит весь массив) если только вы не ожидаете, что ваш массив будет почти всегда состоять исключительно из нулей (и в этом случае подход, основанный на sum |= array[i], по-настоящему безветренный, с использованием 0CCGCC, может дать вам лучшие номера - см. номера ниже для процессора 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 

Answer 2

Если вы хотите сделать это в 32-битном C, вероятно, просто цикл по массиву, как 32-разрядного целого массив и сравнить его с 0, то убедитесь, что материал в конце также 0.

Answer 3

Если массив любого приличного размера, ваш ограничивающий фактор на современном процессоре будет доступ к Память.

Обязательно используйте предварительную выборку кеша на подходящее расстояние вперед (то есть 1-2K) с чем-то вроде __dcbt или prefetchnta (или prefetch0, если вы снова захотите использовать буфер снова).

Вы также захотите сделать что-то вроде SIMD или SWAR или несколько байтов за раз. Даже с 32-битными словами это будет на 4 раза меньше операций, чем на версию для каждого символа. Я бы порекомендовал разворачивать или перевести их в «дерево» или. Вы можете видеть, что я имею в виду в моем примере кода - это использует суперскалярную возможность делать два целых ops (or или) параллельно, используя ops, у которых не так много промежуточных зависимостей данных. Я использую размер дерева 8 (4x4, затем 2x2, затем 1x1), но вы можете увеличить его до большего числа в зависимости от количества свободных регистров, которые у вас есть в архитектуре вашего процессора.

Следующий пример псевдокода для внутреннего цикла (без пролога/эпилога) использует 32-битные int, но вы можете сделать 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*** 

Я бы на самом деле предлагаю Инкапсуляцию сравнить из «линии» значений в одну функцию, а затем разворачивая, что пару раз с упреждающим кэшем.

Answer 4

Вот короткое, быстрое решение, если вы можете использовать встроенную сборку.

#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, до нуля), уменьшая значение указанного регистра на каждой итерации до тех пор, пока не встретится ненулевой байт. Теперь, если строка была равна нулю, регистр тоже будет равен нулю, так как он уменьшался на length раз. Однако, если встречается ненулевое значение, «цикл», который проверял нули, заканчивается преждевременно, и, следовательно, регистр не будет равен нулю. Затем мы получаем значение этого регистра и возвращаем его булево отрицание.

Профилирование это дало следующие результаты:

$ 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 код приходит от ответа Влада вызовы функций были устранены в обоих случаях..)

Answer 5

Разделите проверенную половину памяти и сравните первую часть со второй.
a. Если какая-либо разница, это не может быть одинаковым.
b. Если в первом тайме разница не повторяется.

Худший случай 2 * N. Эффективная память и основанная на memcmp.
Не уверен, что его следует использовать в реальной жизни, но мне понравилась идея самопомощи.
Работает на нечетной длине. Понимаете, почему? :-)

bool memcheck(char* p, char chr, size_t size) { 
    // Check if first char differs from expected. 
    if (*p != chr) 
     return false; 
    int near_half, far_half; 
    while (size > 1) { 
     near_half = size/2; 
     far_half = size-near_half; 
     if (memcmp(p, p+far_half, near_half)) 
      return false; 
     size = far_half; 
    } 
    return true; 
} 

Answer 6

Измеряется две реализации на ARM64, один с помощью цикла с ранним возвращением на ложь, одна из которых OrS все байты:

int is_empty1(unsigned char * buf, int size) 
{ 
    int i; 
    for(i = 0; i < size; i++) { 
     if(buf[i] != 0) return 0; 
    } 
    return 1; 
} 

int is_empty2(unsigned char * buf, int size) 
{ 
    int sum = 0; 
    for(int i = 0; i < size; i++) { 
     sum |= buf[i]; 
    } 
    return sum == 0; 
} 

Результаты:

Все результаты, в микросекундах:

 is_empty1 is_empty2 
MEDIAN 0.350  3.554 
AVG  1.636  3.768 

только ложные результаты:

 is_empty1 is_empty2 
MEDIAN 0.003  3.560 
AVG  0.382  3.777 

только истинные результаты:

 is_empty1 is_empty2 
MEDIAN 3.649  3,528 
AVG  3.857  3.751 

Резюме: только для наборов данных, где вероятность ложных результатов очень мала, второй алгоритм, использующий ORing работает лучше, из-за пропущенную ветвь. В противном случае возвращение на раннем этапе явно превосходит стратегию.

Answer 7

Rusty Russel's memeqzero является очень быстро.Он повторно использует memcmp, чтобы сделать тяжелый подъем: https://github.com/rustyrussell/ccan/blob/master/ccan/mem/mem.c#L92.