Быстрее приблизьтесь к проверке все-нулевой буфер в C?

int is_empty(char * buf, int size) 
{
    int i, content=0;  
    for(i = 0; !content && i < size; i++)    
    {  
        content=content | buf(i);       // bitwise or  
    }  
    return (content==0);  
}

Изменить: Плохой ответ

Новый подход может быть

int is_empty(char * buf, int size) {
    char start = buf[0];
    char end = buff[size-1];
    buf[0] = 'x';
    buf[size-1] = '\0';
    int result = strlen(buf) == 0;
    buf[0] = start;
    buff[size-1] = end;
    return result;
}

Почему это безумие? потому что strlen - это одна из библиотечных функций, которая с большей вероятностью будет оптимизирована. Сохранение и замена первого символа - это предотвращение ложного срабатывания. Сохранение и замена последнего символа гарантирует его завершение.

int is_empty(char * buf, int size)
{
   return buf[0] == '\0';
}

If your buffer is not a character string, I think that's the fastest way to check...

memcmp() would require you to create a buffer the same size and then use memset to set it all as 0. I doubt that would be faster...

Я вижу, что многие люди говорят что-то о проблемах с выравниванием, которые мешают вам выполнять доступ размером с слово, но это не всегда так. Если вы хотите создать переносимый код, то это, безусловно, проблема, однако x86 действительно допускает несогласованный доступ. Например, это не сработает на x86, если в EFLAGS включена проверка выравнивания (и, конечно, buf на самом деле не выровнен по словам).

int is_empty(char * buf, int size) {
 int i;
 for(i = 0; i < size; i+= 4) {
   if(*(int *)(buf + i) != 0) {
     return 0;
   }   
 }

 for(; i < size; i++) {
   if(buf[i] != 0) 
     return 0;
 }

 return 1;
}

Независимо от того, компилятор МОЖЕТ преобразовать ваш исходный цикл в цикл сравнений на основе слов с дополнительными прыгает, чтобы решить проблемы с выравниванием, однако он не будет делать этого на любом нормальном уровне оптимизации, потому что ему не хватает информации. В случаях, когда размер небольшой, развертывание цикла таким образом замедлит код, и компилятор хочет быть консервативным.

Чтобы обойти эту проблему, используйте оптимизацию, управляемую профилями. Если вы позволите GCC получить информацию профиля для функции is_empty, а затем повторно скомпилировать ее, он будет готов развернуть цикл до сравнений размером с слово с проверкой выравнивания. Вы также можете принудительно настроить это поведение с помощью -funroll-all-loops

Кто-нибудь упоминал разворачивание цикла? В любом из этих циклов накладные расходы и индексация будут значительными.

Кроме того, какова вероятность того, что буфер действительно будет пуст? Это единственный случай, когда вам нужно все это проверить. Если обычно в буфере есть какой-то мусор, цикл должен быть остановлен очень рано, поэтому это не имеет значения.

Если вы планируете очистить его до нуля, если он не равен нулю, вероятно, будет быстрее просто очистить его с помощью memset (buf, 0, sizeof (buf)) , независимо от того, равен ли он нулю.

Книга / сайт Hackers Delight - все про оптимизированный C / сборку. Также с этого сайта есть много хороших ссылок, которые достаточно актуальны (также AMD64, технологии NUMA).

Try checking the buffer using an int-sized variable where possible (it should be aligned).

Off the top of my head (uncompiled, untested code follows - there's almost certainly at least one bug here. This just gives the general idea):

/* check the start of the buf byte by byte while it's unaligned */
while (size && !int_aligned( buf)) {
    if (*buf != 0) {
        return 0;
    }

    ++buf;
    --size;
}


/* check the bulk of the buf int by int while it's aligned */

size_t n_ints = size / sizeof( int);
size_t rem = size / sizeof( int);

int* pInts = (int*) buf;

while (n_ints) {
    if (*pInt != 0) {
        return 0;
    }

    ++pInt;
    --n_ints;
}


/* now wrap up the remaining unaligned part of the buf byte by byte */

buf = (char*) pInts;

while (rem) {
    if (*buf != 0) {
        return 0;
    }

    ++buf;
    --rem;
}

return 1;

Для чего-то такого простого вам нужно будет посмотреть, какой код генерирует компилятор.

$ gcc -S -O3 -o empty.s empty.c

И содержимое сборки:

        .text
        .align 4,0x90
.globl _is_empty
_is_empty:
        pushl       %ebp
        movl        %esp, %ebp
        movl        12(%ebp), %edx  ; edx = pointer to buffer
        movl        8(%ebp), %ecx   ; ecx = size
        testl       %edx, %edx
        jle L3
        xorl        %eax, %eax
        cmpb        $0, (%ecx)
        jne L5
        .align 4,0x90
L6:
        incl        %eax            ; real guts of the loop are in here
        cmpl        %eax, %edx
        je  L3
        cmpb        $0, (%ecx,%eax) ; compare byte-by-byte of buffer
        je  L6
L5:
        leave
        xorl        %eax, %eax
        ret
        .align 4,0x90
L3:
        leave
        movl        $1, %eax
        ret
        .subsections_via_symbols

Это очень оптимизировано. Цикл делает три вещи:

• Увеличивает смещение
• Сравнивает смещение с размером
• Сравнивает байтовые данные в памяти по основанию + смещение с 0

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

Когда ничего не помогает, сначала измерьте, а не гадайте.

Если ваша программа предназначена только для x86 или только для x64, вы можете легко оптимизировать ее с помощью встроенного ассамблера. Инструкция REPE SCASD будет сканировать буфер до тех пор, пока не будет найдено двойное слово, отличное от EAX.

Поскольку эквивалентной стандартной библиотечной функции не существует, ни один компилятор / оптимизатор, вероятно, не сможет использовать эти инструкции (как Подтверждено кодом Суфиана).

Из головы, что-то вроде этого будет сделано, если длина вашего буфера выровнена по 4 байта (синтаксис MASM):

_asm {
   CLD                ; search forward
   XOR EAX, EAX       ; search for non-zero
   LEA EDI, [buf]     ; search in buf
   MOV ECX, [buflen]  ; search buflen bytes
   SHR ECX, 2         ; using dwords so len/=4
   REPE SCASD         ; perform scan
   JCXZ bufferEmpty:  ; completes? then buffer is 0
}

Томас

РЕДАКТИРОВАТЬ: обновлено исправлениями Тони Д.

Четыре функции для проверки нулевого значения буфера с помощью простого тестирования:

#include <stdio.h> 
#include <string.h> 
#include <wchar.h> 
#include <inttypes.h> 

#define SIZE (8*1024) 
char zero[SIZE] __attribute__(( aligned(8) ));

#define RDTSC(var)  __asm__ __volatile__ ( "rdtsc" : "=A" (var)); 

#define MEASURE( func ) { \ 
  uint64_t start, stop; \ 
  RDTSC( start ); \ 
  int ret = func( zero, SIZE ); \ 
  RDTSC( stop ); \ 
  printf( #func ": %s   %12"PRIu64"\n", ret?"non zero": "zero", stop-start ); \ 
} 


int func1( char *buff, size_t size ){
  while(size--) if(*buff++) return 1;
  return 0;
}

int func2( char *buff, size_t size ){
  return *buff || memcmp(buff, buff+1, size-1);
}

int func3( char *buff, size_t size ){
  return *(uint64_t*)buff || memcmp(buff, buff+sizeof(uint64_t), size-sizeof(uint64_t));
}

int func4( char *buff, size_t size ){
  return *(wchar_t*)buff || wmemcmp((wchar_t*)buff, (wchar_t*)buff+1, size/sizeof(wchar_t)-1);
}

int main(){
  MEASURE( func1 );
  MEASURE( func2 );
  MEASURE( func3 );
  MEASURE( func4 );
}

Результат на моем старом ПК:

func1: zero         108668
func2: zero          38680
func3: zero           8504
func4: zero          24768

Посмотрите на fast memcpy - его можно адаптировать для memcmp (или memcmp с постоянным значением).

One potential way, inspired by Kieveli's dismissed idea:

int is_empty(char *buf, size_t size)
{
    static const char zero[999] = { 0 };
    return !memcmp(zero, buf, size > 999 ? 999 : size);
}

Note that you can't make this solution work for arbitrary sizes. You could do this:

int is_empty(char *buf, size_t size)
{
    char *zero = calloc(size);
    int i = memcmp(zero, buf, size);
    free(zero);
    return i;
}

But any dynamic memory allocation is going to be slower than what you have. The only reason the first solution is faster is because it can use memcmp(), which is going to be hand-optimized in assembly language by the library writers and will be much faster than anything you could code in C.

EDIT: An optimization no one else has mentioned, based on earlier observations about the "likelyness" of the buffer to be in state X: If a buffer isn't empty, will it more likely not be empty at the beginning or the end? If it's more likely to have cruft at the end, you could start your check at the end and probably see a nice little performance boost.

EDIT 2: Thanks to Accipitridae in the comments:

int is_empty(char *buf, size_t size)
{
    return buf[0] == 0 && !memcmp(buf, buf + 1, size - 1);
}

This basically compares the buffer to itself, with an initial check to see if the first element is zero. That way, any non-zero elements will cause memcmp() to fail. I don't know how this would compare to using another version, but I do know that it will fail quickly (before we even loop) if the first element is nonzero. If you're more likely to have cruft at the end, change buf[0] to buf[size] to get the same effect.