Я ищу более быстрый способ выполнения этого:
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 слишком (long или long long). 16 или выше, вероятно, требуется встроенная сборка, например, для использования векторного модуля.
Кроме того, неправильные предсказания веток действительно вредят, это может помочь устранить ветки. Например, если буфер почти всегда пуст, вместо того, чтобы проверять каждый блок на 0, бит или их вместе и тестировать конечный результат.
Выразить это трудно в переносимом C: приведение char* к long* нарушает строгий псевдоним. Но, к счастью, вы можете использовать memcpy для переносимого выражения невыровненной многобайтовой загрузки, которая может создать псевдоним. Компиляторы оптимизируют его так, как вам нужно.
Например, эта незавершенная реализация (https://godbolt.org/z/3hXQe7) в проводнике компилятора Godbolt показывает, что вы можете получить хороший внутренний цикл (с некоторыми затратами на запуск) из загрузки двух последовательных uint_fast32_t uint_fast32_t ( часто 64-битный) с memcpy и проверкой tmp1 | tmp2 tmp1 | tmp2, потому что многие процессоры будут устанавливать флаги в соответствии с результатом ИЛИ, поэтому это позволяет вам проверить два слова по цене одного.
Для эффективной компиляции для целей без эффективных невыровненных нагрузок требуется некоторое ручное выравнивание в коде запуска, и даже в этом случае gcc может не memcpy для нагрузок, для которых он не может доказать выравнивание.
Один из возможных способов, вдохновленный Kieveli, отклонил идею:
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 <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Если ваша программа - только 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
}
Томас
EDIT: обновлено с помощью исправлений Tony D
Для чего-то такого простого вам нужно будет узнать, какой код генерирует компилятор.
$ 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
Это очень оптимизировано. Цикл выполняет три функции:
Его можно было бы оптимизировать чуть больше, сравнивая поэтапно, но тогда вам нужно будет беспокоиться о выравнивании и т.д.
Когда все остальное не работает, сначала измерьте, не угадывайте.
Приведенные выше тесты (fooobar.com/questions/170307/...) неточны. Они подразумевают, что 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 (она должна быть выровнена).
Сверху моей головы (нескомпилированный, непроверенный код следует - почти наверняка, по крайней мере, одна ошибка здесь. Это просто дает общую идею):
/* check the start of the buf byte by byte while it unaligned */
while (size && !int_aligned( buf)) {
if (*buf != 0) {
return 0;
}
++buf;
--size;
}
/* check the bulk of the buf int by int while it 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;
С помощью 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 байта.
Посмотрите fast memcpy - он может быть адаптирован для memcmp (или memcmp с постоянным значением).
Я вижу, что многие люди говорят о проблемах выравнивания, мешая вам делать доступ к размеру слов, но это не всегда так. Если вы хотите создать переносимый код, это, безусловно, проблема, однако 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-loops
Книга/сайт Hackers Delight посвящена оптимизации C/сборки. Много хороших ссылок с этого сайта также и довольно современны (AMD64, NUMA методы также).
Кто-нибудь говорил о разворачивании цикла? В любом из этих циклов накладные расходы и индексирование цикла будут значительными.
Кроме того, какова вероятность того, что буфер фактически будет пустым? Это единственный случай, когда вы должны проверить все это. Если в буфере обычно есть мусор, цикл должен останавливаться очень рано, поэтому это не имеет значения.
Если вы планируете очистить его до нуля, если он не равен нулю, скорее всего, это будет скорее просто очистить его с помощью memset(buf, 0, sizeof(buf)), независимо от того, уже ли он равен нулю.
В своем вопросе вы заявили, что ищете наиболее вероятную ненужную микро-оптимизацию. В нормальных случаях подход ASM Томаса и других должен дать вам самые быстрые результаты.
Тем не менее, это забывает общую картину. Если ваш буфер действительно большой, то, начиная с самого начала, и существенно, линейный поиск определенно не самый быстрый способ сделать это. Предположим, что ваша замена cp неплохо находит большие последовательные пустые области, но имеет несколько непустых байтов в конце массива. Для всех линейных поисков потребуется считывание всего массива. С другой стороны, алгоритм, основанный на быстрой сортировке, мог искать любые ненулевые элементы и прервать намного быстрее для достаточно большого набора данных.
Поэтому, прежде чем делать какую-либо микро-оптимизацию, я бы внимательно посмотрел данные в вашем буфере и посмотрел, дает ли это вам какие-либо шаблоны. Для одного "1", случайным образом распределенного в буфере, будет самый быстрый подход к линейному поиску (без учета потоковой обработки/распараллеливания), в других случаях это не обязательно.
Встроенная версия сборки исходного кода 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 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 и повторение его, как если бы это был массив int, а не массив char. Число итераций сводится к:
size / sizeof(int)
Далее вы можете развернуть цикл. На некоторых архитектурах Duff Device может представить выигрыш, но это никоим образом не является данным.
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, кроме того, если вы можете заставить компилятор поставить я в регистр с ключевым словом "register", но мне говорят, что это почти всегда игнорируется современными компиляторами.
Также поиск массива с постоянным размером для проверки, является ли он пустым, очень расточительный, а также 0 не пуст, это значение в массиве.
Лучшим решением для скорости было бы использовать динамический массив (int * piBuffer) и переменную, которая хранит текущий размер (unsigned int uiBufferSize), когда массив пуст, тогда указатель равен NULL, а uiBufferSize равен 0. Make класс с этими двумя в качестве защищенных переменных-членов. Можно также легко написать шаблон для динамических массивов, в котором будут храниться 32-битные значения, как примитивные типы, так и указатели, для примитивных типов на самом деле нет никакого способа проверить "пустой" (я интерпретирую это как "undefined" ), но вы можете, конечно, определить 0 для представления доступной записи. Для указателей массива вы должны инициализировать все записи в NULL и задавать запись в NULL, когда вы просто освободили эту память. И NULL DOES означает "точки в никуда", поэтому это очень удобный способ представления пустых. Нельзя использовать динамически измененные массивы в действительно сложных алгоритмах, по крайней мере, не на стадии разработки, просто слишком много вещей, которые могут пойти не так. По крайней мере, сначала нужно реализовать алгоритм, используя STL Container (или хорошо протестированную альтернативу), а затем, когда работает код, можно поменять наш тестовый контейнер на простой динамический массив (и если вы можете слишком часто изменять размер массива, код будет как быть быстрее и безопаснее.
Лучшим решением для сложного и классного кода является использование либо std::vector, либо std:: map (или любого класса контейнера STL, доморощенного или стороннего) в зависимости от ваших потребностей, но, глядя на ваш код, я бы сказал, что std::vector достаточно. Контейнеры STL - это шаблоны, поэтому они тоже должны быть довольно быстрыми. Используйте STL Container для хранения указателей объектов (всегда храните указатели объектов, а не фактические объекты, копируя целые объекты для каждой записи, действительно испортите скорость выполнения) и динамические массивы для более основных данных (растровое изображение, звук и т.д.), Т.е. примитивных типов. В общем случае.
Я придумал решение REPE SCASW самостоятельно, изучив руководства по ассемблеру x86, и я согласен с тем, что пример, использующий эту командную инструкцию, является самым быстрым. Другой пример сборки, который имеет отдельные команды сравнения, перехода и т.д., Почти наверняка медленнее (но все же намного быстрее, чем исходный код C, поэтому все еще хороший пост), поскольку строковые операции являются одними из самых оптимизированных для всех современных процессоров, они могут даже иметь свою собственную логическую схему (кто-нибудь знает?).
REPE SCASD не нужно извлекать новую инструкцию и не увеличивать указатель на инструкцию, а это только то, что может принести новичок, как я, и, кроме того, это оптимизация аппаратного обеспечения, операции с строкой являются критическими практически для всех видов современного программного обеспечения, в частности мультимедийного приложения (копировать звуковые данные PCM, несжатые данные растрового изображения и т.д.), поэтому оптимизация этих инструкций должна быть очень высокой приоритетной при каждом новом чипе 80x86. Я использую его для нового алгоритма столкновения 2d спрайтов.
В нем говорится, что мне не позволено иметь мнение, поэтому рассмотрим следующую объективную оценку: современные компиляторы (UNMANAGED C/С++, почти все остальное - управляемый код и медленный, как ад) довольно хороши в оптимизации, но этого нельзя избежать, что для ОЧЕНЬ конкретных задач компилятор генерирует избыточный код. Можно было бы взглянуть на сборку, которую компилятор выдает так, что вам не нужно полностью переводить сложный алгоритм с нуля, хотя это очень интересно делать (для некоторых), и это гораздо более полезно делать код сложным способом, но во всяком случае, алгоритмы, использующие петли "для", в частности в отношении строковых операций, часто могут быть оптимизированы очень значительно, поскольку цикл for генерирует много кода, что часто не требуется, например: for (int я = 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 становится много сборочных линий, часто делает некоторые оптимизации очень очевидными, а также некоторые команды быстрее других:
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 градусов: P Любой, кто делает это, является удивительным!
Если у кого-то есть некоторая конструктивная коррекция, которая НЕ ОЧЕНЬ обидна, то я бы с удовольствием ее услышал, я почти полностью кодирую себя, поэтому я не подвергаюсь никаким влияниям. Однажды я заплатил отличному канадскому разработчику игр, чтобы научить Direct3d, и хотя я мог так же легко прочитать книгу, взаимодействие с другим кодером, который был несколько выше моего уровня в определенных областях, был забавным.
Спасибо за хороший контент. Я думаю, что поеду и отвечу на некоторые более простые вопросы, немного вернусь.