У меня есть массив байтов в памяти. Какой самый быстрый способ увидеть, все ли байты в массиве равны нулю?
Быстрый способ проверить, равен ли массив символов нулю
Ответ 1
В настоящее время не используется SIMD extensions (например, 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
Ответ 2
Здесь короткое, быстрое решение, если вы можете использовать встроенную сборку.
#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 поступает из ответа Влада. В обоих случаях устранены вызовы функций.)
Ответ 3
Если вы хотите сделать это в 32-битном C, возможно, просто перейдем к массиву в виде 32-разрядного целочисленного массива и сравните его с 0, затем убедитесь, что в конце файла также есть 0.
Ответ 4
Если массив имеет подходящий размер, ваш ограничивающий фактор на современном процессоре будет иметь доступ к памяти.
Обязательно используйте предварительную выборку кеша на приличное расстояние вперед (например, 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***
Я бы предложил инкапсулировать сравнение "линии" значений в одну функцию и затем развернуть пару раз с предварительной выборкой кеша.
Ответ 5
Разделите проверенную половину памяти и сравните первую часть со второй.
а. Если какая-либо разница, она не может быть одинаковой.
б. Если в первом тайме разницы не повторяется.
Худший случай 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;
}
Ответ 6
Измерено две реализации на ARM64, одна из которых использует цикл с ранним возвратом на false, один из которых содержит все байты:
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 работает лучше из-за пропущенной ветки. В противном случае возвращение на раннем этапе явно превосходит стратегию.