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

Question

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

Профилирование проблемы показывает, что программа тратит много времени, просто увеличивая счетчики циклов (++) и тестируя на завершение (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))
            {
                .
                .
                .
            }
        }
    }
}

Спасибо

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

... который компилятор мог бы иметь больше шансов для оптимизации / развертывания должным образом.

Answer 5

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

Answer 6

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

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

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