Как оптимизировать C для цикла?

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

for (byte_index = 0; byte_index < MASK_SIZE / NBBY; )
{
    if (check_byte(mask,byte_index++))
    {
        condition_index = byte_index*NBBY;
        for (bit_index=0; bit_index < NBBY; )
        {
            if (check_bit(condition_mask,condition_index + bit_index++))
            {
                ...
            }
        }
    }
}

(приведенный выше фрагмент не работают по очевидным причинам, но вы должны уловить идею :)

Кроме того, судя по именам функций / макросов в вашем фрагменте C, я предполагаю, что вы работаете с битовыми масками, чтобы делать что-то. Одна вещь, которая раньше помогла мне улучшить производительность, - это перебор массива масок вместо выполнения динамических вычислений на входе, то есть что-то вроде

for (byte_index = 0; byte_index < MASK_SIZE / NBBY; byte_index++)
{
    if (check_byte(mask,byte_index))
    {
        const char masks[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
        for (mask_index=0; mask_index < sizeof(masks) / sizeof(masks[0]); mask_index++)
        {
            if (check_bit(masks[mask_index], byte_index))
            {
                ...
            }
        }
    }
}

... которое компилятор может иметь больше шансов правильно оптимизировать / развернуть.

Не видя, что находится во внутреннем цикле, нет смысла пытаться оптимизировать циклы. Похоже, что код сгенерирован для x86 32bit. Если для вычисления в цикле требуется несколько регистров, компилятору нет смысла хранить счетчик цикла в регистрах, так как ему все равно придется передавать их в стек. Тогда в зависимости от инструкций, используемых во внутреннем цикле, могут возникнуть некоторые проблемы с распределением регистров. Сдвиги используют регистр ECX только в качестве счетчика, умножение и деление имеют ограничения в отношении используемых регистров, строковые команды используют ESI и EDI в качестве регистров, что снижает возможность компилятора хранить в них значения. Если для вычисления в цикле требуется несколько регистров, компилятору нет смысла хранить счетчик цикла в регистрах, так как ему все равно придется передавать их в стек. Тогда в зависимости от инструкций, используемых во внутреннем цикле, могут возникнуть некоторые проблемы с распределением регистров. Сдвиги используют регистр ECX только в качестве счетчика, умножение и деление имеют ограничения в отношении используемых регистров, строковые команды используют ESI и EDI в качестве регистров, что снижает возможность компилятора хранить в них значения. Если для вычисления в цикле требуется несколько регистров, компилятору нет смысла хранить счетчик цикла в регистрах, так как ему все равно придется передавать их в стек. Тогда в зависимости от инструкций, используемых во внутреннем цикле, могут возникнуть некоторые проблемы с распределением регистров. Сдвиги используют регистр ECX только в качестве счетчика, умножение и деление имеют ограничения в отношении используемых регистров, строковые команды используют ESI и EDI в качестве регистров, что снижает возможность компилятора хранить в них значения. И, как уже говорили другие, вызов в середине цикла также не помогает, так как регистры все равно нужно сохранять.

Если верно, что код / ​​* stuff * / внутри внутреннего if () выполняется редко (и есть априори известное ограничение на количество раз, когда это может произойти, или по крайней мере, разумный предел), переход на двухпроходное решение вполне может улучшить производительность. Это устранит давление регистра во вложенных циклах. Следующее основано на моем предыдущем одноиндексном ответе:

for (n = 0, condition_index = 0; condition_index < MASK_SIZE;)
{
    if (check_byte(mask, condition_index / NBBY))
    {
        for (bound = condition_index + NBBY; condition_index < bound; condition_index++)
        {
            if (check_bit(condition_mask, condition_index))
            {
                condition_true[n++] = condition_index;
            }
        }
    }
    else
    {
        condition_index += NBBY;
    }
}

do {
    condition_index = condition_true[--n];
    /* Stuff */
} while (n > 0);

Вы можете попробовать рефакторинг его до одного индекса и посмотреть, изменит ли это мнение компилятора:

for (condition_index = 0; condition_index < MASK_SIZE;)
{
    if (check_byte(mask, condition_index / NBBY))
    {
        for (bound = condition_index + NBBY; condition_index < bound; condition_index++)
        {
            if (check_bit(condition_mask, condition_index))
            {
                /* stuff */
            }
        }
    }
    else
    {
        condition_index += NBBY;
    }
}

(Надеюсь, NBBY - это степень двойки, поэтому разделение будет реализовано как сдвиг)

Есть две возможные причины, по которым она не помещается в регистр:

Переменная должна храниться в памяти

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

gcc плохо справляется с распределением регистров.

Это вполне вероятно. Похоже, что у gcc плохой распределитель (судя по комментариям его разработчиков). Кроме того, распределение регистров непостоянно, и о нем трудно думать. Вы, вероятно, сможете настроить его, чтобы получить некоторые преимущества, используя оптимизацию распределителя регистров . Если хотите, вы можете установить их только для этой функции .

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

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

Наконец, вы также можете настроить параметры с помощью gcc --param флаги. Они раскрывают внутренние настройки компилятора, так что, вероятно, не стоит к этому относиться легкомысленно.

Вы можете попробовать развернуть цикл. Компилятор может сделать это за вас, но если нет, и вам действительно нужна производительность, сделайте это сами. Я предполагаю, что вы делаете что-то вроде вызова функции (.., i, j, ..) на каждой итерации, поэтому просто замените циклы на:

function(.., 0, 0, ..)
...
function(.., 0, 7, ..)
function(.., 1, 0, ..)
...
function(.., 7, 7, ..)

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

Эта страница предполагает, что «ключевое слово register является несколько устаревшей процедурой, поскольку в течение довольно долгого времени оптимизатор в современных компиляторах достаточно умен, чтобы определить, когда сохранение переменной в регистре будет выгодным и будет делать это во время оптимизации. Поэтому предложение компилятору сохранить переменную в регистре может только замедлить работу при неправильном использовании ".

Я предполагаю, что это во многом зависит от вашего компилятора и уровня оптимизации. Как уже говорили другие, это может быть хорошим кандидатом для -funroll-all-loops (gcc).

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

Я предполагаю, что это во многом зависит от вашего компилятора и уровня оптимизации. Как говорили другие, это может быть хорошим кандидатом для -funroll-all-loops (gcc).

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

Я предполагаю, что это во многом зависит от вашего компилятора и уровня оптимизации. Как говорили другие, это может быть хорошим кандидатом для -funroll-all-loops (gcc).

Я предполагаю, что это во многом зависит от вашего компилятора и уровня оптимизации. Как уже говорили другие, это может быть хорошим кандидатом для -funroll-all-loops (gcc).

Я предполагаю, что это во многом зависит от вашего компилятора и уровня оптимизации. Как уже говорили другие, это может быть хорошим кандидатом для -funroll-all-loops (gcc).

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

РЕДАКТИРОВАТЬ: Как всегда, при оптимизации убедитесь, что вы проверили тест и убедили вы сами получите желаемый результат.

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

Я надеюсь, что эти две функции встроены (check_bit и check_byte), поскольку они намного медленнее, чем любая регистровая переменная может сделать ваш цикл.

если компилятор не встраивает их, встраивайте их себя в петлю.

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

    for (bit_index=0; bit_index < NBBY; bit_index++)
    {
        condition_index = byte_index*NBBY + bit_index;
        if (check_bit(condition_mask,condition_index))
        {
            .
            .
            .
        }
    }

могло бы быть так же легко;

    condition_index = byte_index * NBBY;
    for (bit_index=0; bit_index < NBBY; bit_index++, condition_index++)
    {
        if (check_bit(condition_mask,condition_index))
        {
            .
            .
            .
        }
    }

Я поклонник держать вычисления в правильном объеме. У вас есть вся информация для этого во внешнем цикле, но вы решили сделать это во внутреннем цикле. Новый цикл немного запутан, но этого можно избежать, и теперь более вероятно, что ваш компилятор будет все делать правильно. (Вероятно, так и было раньше, но нельзя быть уверенным, не проверив сборку.)

Говоря о правильной области видимости, нет причин объявлять счетчики цикла вне цикла. Этот стиль C устарел в течение многих лет, и хотя он, вероятно, не является специфическим недостатком производительности, ограничение всего до минимальной логической области приводит к более чистому и более удобному в сопровождении коду.

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

Наилучшие результаты (с точки зрения скорости) я получаю при использовании компилятора Intel.

Вы правы, говоря, что ключевое слово 'register' предназначено только как подсказка для компилятора (как и inline).

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

вы можете даже #ifdef весь бит с исходным C код для обеспечения переносимости

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

EDIT: Еще одна вещь, о которой следует подумать, если вы действительно хотите сделать часть кода быстрее, вы можете использовать специальные инструкции ЦП, ваш компилятор, вероятно, не знает, когда их использовать. Например, на Intel есть много инструкций, которые можно использовать, вплоть до SSE4 и других, именно здесь вы можете работать лучше, чем ваш компилятор, поскольку у него нет возможности узнать, чего вы хотите достичь на уровне алгоритма. См. Подробности в Руководстве разработчика программного обеспечения для архитектур Intel (R) 64 и IA-32. Также на этом уровне вы можете получить лучший контроль над конвейером.

Если вы не хотите писать сборку, иногда существуют функции обертывания для инструкций, которые будут использоваться в 'C'.

Относительно проверки того, действительно ли немного горит или нет: Не уверен, что вы хотите сделать, если бит включен, но (при условии, что ваши биты выровнены по байтам):

Предположим, вы получите байт 0110 0110 на X. Вы захотите кое-что сделать, например, распечатать сообщение типа «Биты 1,2,5,6 включены». Вы можете создать 256 функций, каждая будет делать что-то вроде отображения такого массажа. Как узнать, какой из них активировать? Оболочка номера функции будет в точности значением полученного байта, поэтому вы можете просто использовать оператор [], чтобы перейти туда. Однако это будет таблица указателей на функции. Это должно выглядеть примерно так:

//define the functions
void func0()
{
   printf("No Bits are on.");
}

void func1()
{
   printf("Bit 0 is on.");
}
.
.
.

//create the table
void  (*table[256])();
table[0] = &func0;
table[1] = &func1;
.
.
.

//the for loop
void  (*pointer_to_func)();
for...
{
   X = getByte();
   pointer_to_func = table[X]; //table shell contain 256 function pointers.
   pointer_to_func(); //call the function
}

это должно вызвать функцию в позиции X и выполнить ее, я предполагаю, что функция в позиции X == 102 (десятичное число 0110 0110) будет выглядеть примерно так:

printf («Биты 1, 2, 5, 6 включены»);

См. Учебные пособия по указателям на функции , А именно это .

Я бы попытался взглянуть на проблему по-другому.

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

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

Это может показаться второстепенным, но вместо использования формы: index ++, используйте ++ index;

Обоснование состоит в том, что index ++ требует кэширования текущего rvalue перед увеличением, тогда как ++ index возвращает новое вычисленное rvalue, которое уже должно быть кэшировано, таким образом сохраняя ссылку.

Конечно, хороший компилятор оптимизирует это, так что это, вероятно, не проблема.