Более быстрый подход к проверке для всего нуля буфера в C?

Я ищу более быстрый способ выполнения этого:

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

Я понимаю, что ищу ненужную микро оптимизацию, за исключением крайних случаев, но я знаю, что существует более быстрый метод, и мне любопытно, что это такое.

На многих архитектурах сравнение 1 байта занимает такое же количество времени, как 4 или 8, или иногда даже 16. 4 байта обычно легкие (либо int, либо long), а 8 тоже (длинный или длинный). 16 или выше, вероятно, требуется встроенная assembly, например, с использованием векторного блока.

Кроме того, неверные предсказания ветви действительно больно, это может помочь устранить ветви. Например, если буфер почти всегда пуст, вместо проверки каждого блока на 0, бит или их вместе и проверки конечного результата.

Один из возможных способов, вдохновленный отвергнутой идеей Кивели :

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

Обратите внимание, что вы не можете заставить это решение работать для произвольных размеров. Вы можете сделать это:

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

Но любое динамическое распределение памяти будет медленнее, чем у вас. Единственная причина, по которой первое решение работает быстрее, состоит в том, что он может использовать memcmp() , который должен быть оптимизирован вручную на языке ассемблера библиотечными писателями и будет намного быстрее, чем все, что вы могли бы называть C.

EDIT: оптимизация, о которой никто не упомянул, основан на более ранних наблюдениях о «вероятности» буфера в состоянии X: если буфер не пуст, будет ли он скорее не пуст в начале или в конце? Если в конце концов, скорее всего, будет круто, вы можете начать свой чек в конце и, вероятно, увидеть небольшое небольшое повышение производительности.

EDIT 2: Спасибо Accipitridae в комментариях:

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

Это в основном сравнивает буфер с самим собой, с начальной проверкой, чтобы убедиться, что первый элемент равен нулю. Таким образом, любые ненулевые элементы вызовут memcmp() . Я не знаю, как это могло бы сравниться с использованием другой версии, но я знаю, что он быстро завершится (до того, как мы закончим цикл), если первый элемент отличен от нуля. Если вы с большей вероятностью будете иметь рывок в конце, измените buf[0] на buf[size] чтобы получить тот же эффект.

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

 #include  #include  #include  #include  #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 

Если ваша программа только x86 или x64, вы можете легко оптимизировать использование встроенного assambler. Команда REPE SCASD сканирует буфер до тех пор, пока не будет найден dword не 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 } 

Tomas

EDIT: обновлено с исправлениями Тони Д

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

 $ 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

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

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

Исходные данные, приведенные выше ( https://stackoverflow.com/a/1494499/2154139 ), неточны. Они подразумевают, что func3 намного быстрее, чем другие варианты.

Однако, если вы измените порядок тестов, так что func3 появится перед func2, вы увидите, что func2 работает намного быстрее.

Осторожно, когда вы используете комбинированные тесты в рамках одного исполнения … побочные эффекты велики, особенно при повторном использовании одних и тех же переменных. Лучше проводить тесты изолированными!

Например, изменив его на:

 int main(){ MEASURE( func3 ); MEASURE( func3 ); MEASURE( func3 ); MEASURE( func3 ); MEASURE( func3 ); } 

дает мне:

 func3: zero 14243 func3: zero 1142 func3: zero 885 func3: zero 848 func3: zero 870 

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

(извиниться за ответ, а не как комментарий, не имел репутации)

Попробуйте проверить буфер, используя переменную int-size, где это возможно (она должна быть выровнена).

Сверху моей головы (нескомпилированный, непроверенный код следует – почти наверняка, по крайней мере, одна ошибка здесь. Это просто дает общую идею):

 /* 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; 

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

С помощью x86 вы можете использовать SSE для проверки 16 байтов за раз:

 #include "smmintrin.h" // note: requires SSE 4.1 int is_empty(const char *buf, const size_t size) { size_t i; for (i = 0; i + 16 <= size; i += 16) { __m128i v = _mm_loadu_si128((m128i *)&buf[i]); if (!_mm_testz_si128(v, v)) return 0; } for ( ; i < size; ++i) { if (buf[i] != 0) return 0; } return 1; } 

Вероятно, это может быть улучшено с разворачиванием цикла.

На современных процессорах x86 с AVX вы можете даже использовать 256-битный SIMD и тестировать 32 байта за раз.

Я вижу, что многие люди говорят о проблемах выравнивания, которые мешают вам выполнять доступ к размеру слов, но это не всегда так. Если вы хотите создать переносимый код, это, безусловно, проблема, однако x86 фактически допустит неправильные обращения. Для exmaple это произойдет только на 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-loop

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

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

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

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

Вы заявили в своем вопросе, что ищете наиболее вероятную ненужную микро-оптимизацию. В нормальных случаях подход ASM Томаса и других должен дать вам самые быстрые результаты.

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

Поэтому, прежде чем делать какую-либо микро-оптимизацию, я бы внимательно посмотрел данные в вашем буфере и посмотрел, дает ли это вам какие-либо шаблоны. Для одного «1», случайным образом распределенного в буфере, самый быстрый подход – линейный поиск (без учета streamовой обработки / распараллеливания), в других случаях – не обязательно.

Встроенная версия сборки исходного кода C (без проверки ошибок, если uiSize is == 0 и / или массив не распределены, исключения будут сгенерированы. Возможно, используйте try {} catch() поскольку это может быть быстрее, чем добавление большого количества проверьте код или сделайте так, как я, попробуйте не вызывать функции с недопустимыми значениями (обычно это не работает). По крайней мере, добавьте проверку указателя NULL и size != 0 , это очень просто.

  unsigned int IsEmpty(char* pchBuffer, unsigned int uiSize) { asm { push esi push ecx mov esi, [pchBuffer] mov ecx, [uiSize] // add NULL ptr and size check here mov eax, 0 next_char: repe scasb // repeat string instruction as long as BYTE ptr ds:[ESI] == 0 // scasb does pointer arithmetic for BYTES (chars), ie it copies a byte to al and increments ESI by 1 cmp cx,0 // did the loop complete? je all_chars_zero // yes, array is all 0 jmp char_not_zero // no, loop was interrupted due to BYTE PTR ds:[ESI] != 0 all_chars_zero: mov eax, 1 // Set return value (works in MASM) jmp end char_not_zero: mov eax, 0 // Still not sure if this works in inline asm end: pop ecx pop esi } } 

Это написано «на лету», но оно выглядит правильно, исправления приветствуются. ANd, если кто-то знает о том, как установить возвращаемое значение из встроенного asm, скажите, пожалуйста.

Как насчет цикличности от нуля до нуля (более дешевые проверки):

 int is_empty(char * buf, int size) { while(size --> 0) { if(buf[i] != 0) return 0; } return 1; } 

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

Или обрабатывать все с помощью указателей (не тестировалось, но, скорее всего, выполнялось неплохо):

 int is_empty(char* buf, int size) { char* org = buf; if (buf[size-1] == 1) return 0; buf[size-1] = 1; while(! *buf++); buf--; return buf == org[size-1]; } 
 int is_empty(char * buf, int size) { return buf[0] == '\0'; } 

Если ваш буфер не является символьной строкой, я думаю, что это самый быстрый способ проверить …

memcmp () потребовал бы, чтобы вы создали буфер того же размера, а затем используйте memset, чтобы установить его как 0. Я сомневаюсь, что это будет быстрее …

Передайте буфер int и переместите его так, как если бы это был массив int, а не массив char. Количество итераций уменьшается до:

 size / sizeof(int) 

Далее вы можете развернуть цикл. На некоторых архитектурах устройство Даффа может принести выигрыш, но это отнюдь не данное.

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

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

 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 является одной из функций библиотеки, которая, скорее всего, будет оптимизирована. Хранение и замена первого символа – это предотrotation ложного срабатывания. Хранение и замена последнего символа означает, что он завершается.

 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); } 

Я думаю, у меня есть хорошее решение для этого. Создайте фиктивный нулевой массив и используйте memcmp (). Это то, чем я занимаюсь.

Исходный алгоритм C в значительной степени медленный, так как он может быть в VALID C. Если вы настаиваете на использовании C, попробуйте «while» вместо «for»:

  int i = 0; while (i< MAX) { // operate on the string i++; } 

Это почти самый быстрый 1-мерный цикл операций строки, который вы можете записать на C, кроме того, если вы можете заставить компилятор поставить i в регистр с ключевым словом «register», но мне говорят, что это почти всегда игнорируется современными компиляторами ,

Также поиск массива с постоянным размером, чтобы проверить, является ли он пустым, очень расточительный, а также 0 не пуст, это значение в массиве.

Лучшим решением для скорости было бы использовать динамический массив (int * piBuffer) и переменную, которая хранит текущий размер (unsigned int uiBufferSize), когда массив пуст, тогда указатель равен NULL, а uiBufferSize равен 0. Сделайте class с эти два являются защищенными переменными-членами. Можно также легко написать шаблон для динамических массивов, в котором будут храниться 32-битные значения, либо примитивные типы, либо указатели, для примитивных типов на самом деле нет никакого способа проверить «пустой» (я интерпретирую это как «неопределенный»), но вы можете, конечно, определить 0 для представления доступной записи. Для указателей массива вы должны инициализировать все записи в NULL и задавать запись в NULL, когда вы просто освободили эту память. И NULL DOES означает «точки в никуда», поэтому это очень удобный способ представления пустых. Нельзя использовать динамически измененные массивы в действительно сложных алгоритмах, по крайней мере, не на стадии разработки, просто слишком много вещей, которые могут пойти не так. По крайней мере, сначала нужно реализовать алгоритм, используя STL Container (или хорошо протестированную альтернативу), а затем, когда работает код, можно поменять наш тестовый контейнер на простой динамический массив (и если вы можете слишком часто изменять размер массива, код будет как быть быстрее и безопаснее.

Лучшим решением для сложного и classного кода является использование либо std :: vector, либо std :: map (или любого classа контейнера STL, доморощенного или стороннего) в зависимости от ваших потребностей, но, глядя на ваш код, я бы сказал, что std :: vector достаточно. Контейнеры STL - это шаблоны, поэтому они тоже должны быть довольно быстрыми. Используйте STL Container для хранения указателей объектов (всегда храните указатели объектов, а не фактические объекты, копируя целые объекты для каждой записи, действительно испортите скорость выполнения) и динамические массивы для более основных данных (bitmap, звук и т. Д.), Т.е. примитивных типов. В общем-то.

Я придумал решение REPE SCASW самостоятельно, изучив руководства по языку ассемблера x86, и я согласен, что пример, использующий эту командную инструкцию, является самым быстрым. Другой пример сборки, который имеет отдельные команды сравнения, перехода и т. Д., Почти наверняка медленнее (но все же намного быстрее, чем исходный код C, поэтому все еще хороший пост), поскольку строковые операции являются одними из самых оптимизированных для всех современных процессоров, они могут даже иметь свою собственную логическую схему (кто-нибудь знает?).

REPE SCASD не нужно извлекать новую инструкцию и не увеличивать указатель команд, а это только то, что может возникнуть у новичков-сборщиков, таких как я, и, кроме того, это оптимизация аппаратных средств, операции с строкой критически важны для почти всех (копирование звуковых данных PCM, несжатых растровых данных и т. д.), поэтому оптимизация этих инструкций должна быть очень высокой приоритетной при каждом новом чипе 80x86. Я использую его для нового алгоритма столкновения 2d спрайтов.

В нем говорится, что мне не позволено иметь мнение, поэтому рассмотрим следующую объективную оценку: современные компиляторы (UNMANAGED C / C ++, в значительной степени все остальное управляется кодом и медленно, как черт), довольно хорошо оптимизируют, но не могут следует избегать того, что для ОЧЕНЬ конкретных задач компилятор генерирует избыточный код. Можно было бы взглянуть на сборку, которую компилятор выдает так, что вам не нужно полностью переводить сложный алгоритм с нуля, хотя это очень интересно делать (для некоторых), и это гораздо более полезно делать код сложным способом, но в любом случае алгоритмы, использующие петли «для», в частности, применительно к строковым операциям, часто могут быть очень оптимизированы, поскольку цикл for генерирует много кода, что часто не требуется, например: for (int i = 1000; i> 0; i--) DoSomething (); Эта строка генерируется на 6-10 строках сборки, если компилятор не очень умный (может быть), но оптимизированная версия сборки CAN может быть:

  mov cx, 1000 _DoSomething: // loop code....or call Func, slower but more readable loop _DoSomething 

Это было 2 строки, и он делает то же самое, что и строка C (он использует регистры вместо адресов памяти, что намного быстрее, но, возможно, это не ТОЧНО так же, как линия C, но это семантика), сколько оптимизации этот пример зависит от того, насколько хорошо оптимизируются современные компиляторы, о чем я не помню, но анализ алгоритмов, основанный на цели реализации алгоритма с наименьшими и более быстрыми линиями сборки, часто работает хорошо, у меня были очень хорошие результаты с первым внедрением алгоритма в C / C ++ без заботы об оптимизации, а затем перевести и оптимизировать его в сборке. Тот факт, что каждая линия C становится много сборочных линий, часто делает некоторые оптимизации очень очевидными, а также некоторые инструкции быстрее других:

  INC DX ; is faster than: ADD DX,1 ;if ADD DX,1 is not just replaced with INC DX by the assembler or the CPU LOOP ; is faster than manually decreasing, comparing and jumping REPxx STOSx/MOVSx/LODSx is faster than using cmp, je/jne/jea etc and loop JMP or conditional jumping is faster than using CALL, so in a loop that is executed VERY frequently (like rendering), including functions in the code so it is accessible with "local" jumps can also boost performance. 

Последний бит очень важен для этого вопроса, быстрые операции с строкой. Так что этот пост не все бессвязно.

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

Также не беспокойтесь о том, чтобы оптимизировать код, который не называется так часто, использовать профилировщик и видеть, какой код вызывается чаще всего, и начать с этого, все, что называется менее 20 раз в секунду (и выполняется намного быстрее, чем 1000 мс / 20) на самом деле не стоит оптимизировать. Посмотрите на код, который он не синхронизировал с таймерами и тому подобное, и выполняется снова сразу после завершения. С другой стороны, если ваш цикл рендеринга может делать 100+ FPS на скромной машине, экономически нецелесообразно оптимизировать его, но реальные кодеры любят кодировать и не заботятся об экономике, оптимизируют метод AppStart () на 100 %, хотя он называется только один раз 🙂 Или используйте матрицу поворота az для поворота частей тетриса на 90 gradleусов: P Любой, кто делает это, потрясающий!

Если у кого-то есть некоторая конструктивная коррекция, которая НЕ ОЧЕНЬ обидна, то я бы с удовольствием ее услышал, я почти полностью кодирую себя, поэтому я не подвергаюсь никаким влияниям. Однажды я заплатил отличному канадскому разработчику игр, чтобы научить Direct3d, и хотя я мог бы так же легко прочитать книгу, взаимодействие с другим кодером, который был несколько выше моего уровня в определенных областях, был забавным.

Благодарим за хороший контент. Думаю, я пойду и отвечу на некоторые более простые вопросы, немного вернусь.