Как оптимизировать цикл C? - PullRequest
15 голосов
/ 30 июля 2009

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

Профилирование проблемы показывает, что программа тратит много времени, просто увеличивая счетчики циклов (++) и тестируя на завершение (i / j <8). </p>

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

Вот вывод сборки. Источник C - это простой вложенный цикл со счетчиками i / j.

  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>

Как и просили, вот код C Компилятор gcc кстати:

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))
            {
                .
                .
                .
            }
        }
    }
}

Спасибо

Ответы [ 16 ]

13 голосов
/ 30 июля 2009

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

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

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

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

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

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

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

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

8 голосов
/ 30 июля 2009

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

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

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

6 голосов
/ 30 июля 2009

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

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

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

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

5 голосов
/ 30 июля 2009

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

3 голосов
/ 18 октября 2009

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

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

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

3 голосов
/ 30 июля 2009

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

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

1 голос
/ 31 июля 2009

Если верно, что код / ​​* 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);
1 голос
/ 30 июля 2009

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

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 - это степень 2, поэтому деление будет выполнено в виде смены)

1 голос
/ 30 июля 2009

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

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 включены»);

См. Руководства по указателям на функции , Конкретно это .

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...