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

  2738  0.2479  2459  0.1707   :    1e6c:   jne    1dd1 <process_hooks+0x121>
  1041  0.0942  1120  0.0778   :    1e72:   addl   $0x1,0xffffffd4(%ebp)
  2130  0.1928  2102  0.1459   :    1e76:   cmpl   $0x8,0xffffffd4(%ebp)
  2654  0.2403  2337  0.1622   :    1e7a:   jne    1da0 <process_hooks+0xf0>
  809   0.0732   814  0.0565   :    1e80:   jmp    1ce2 <process_hooks+0x32>

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

Ответ 2 · рейтинг 8 · Laserallan

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

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

Ответ 3 · рейтинг 6 · Toad

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

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

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

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

Ответ 4 · рейтинг 6 · Dan Olson

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

Ответ 5 · рейтинг 5 · jcoder

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

Ответ 6 · рейтинг 3 · anthony

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

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

Ответ 7 · рейтинг 3 · dar7yl

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

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

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

Ответ 8 · рейтинг 1 · Toad

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

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

Ответ 9 · рейтинг 1 · caf

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

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

Ответ 10 · рейтинг 1 · Liran Orevi

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

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

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

Ответ 11 · рейтинг 1 · caf

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

Ответ 12 · Matt J

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

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

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