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

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

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

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

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

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

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

Вы также можете попробовать попросить gcc приложить больше усилий с помощью горячих атрибут.

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

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

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

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

Вы правы, говоря, что ключевое слово «register» предназначено просто как подсказка для компилятора (так же, как встроенный).

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

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

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

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

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

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

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

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

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

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

если компилятор не встраивает их, вставьте их в цикл самостоятельно.

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

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 является степенью двойки, поэтому деление будет реализовано как сдвиг)

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

РЕДАКТИРОВАТЬ: Еще одна вещь, которую следует учитывать, если вы действительно хотите сделать часть кода быстрее, вы можете использовать специальные инструкции ЦП, ваш компилятор, вероятно, не будет знать, когда их использовать. Например, в 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 включены");

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

Если правда, что /* материал */ код во внутреннем 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);

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

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

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

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

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

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 в качестве регистров, что снижает возможность компилятора хранить в них значения. И, как уже говорили другие, вызов в середине цикла тоже не помогает, так как регистры все равно нужно сохранять.

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

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

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