Заполняет ли этот код кэш процессора?

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

Способ 1:

doTheWork(int action)
{
    for(int i = 0 i < 1000000000; ++i)
    {
        doAction(action);
    }
}

Способ 2:

doTheWork(int action)
{
    switch(action)
    {
    case 1:
        for(int i = 0 i < 1000000000; ++i)
        {
            doAction<1>();
        }
        break;
    case 2:
        for(int i = 0 i < 1000000000; ++i)
        {
            doAction<2>();
        }
        break;
    //-----------------------------------------------
    //... (there are 1000000 cases here)
    //-----------------------------------------------
    case 1000000:
        for(int i = 0 i < 1000000000; ++i)
        {
            doAction<1000000>();
        }
        break;
    }
}

Давайте предположим, что функция doAction(int action) и функция template<int Action> doAction() состоят из примерно 10 строк кода, которые будут встроены во время компиляции. призвание doAction(#) эквивалентно doAction<#>() по функциональности, но не по шаблону doAction(int value) несколько медленнее, чем template<int Value> doAction(), поскольку некоторые хорошие оптимизации могут быть сделаны в коде, когда значение аргумента известно во время компиляции.

Итак, мой вопрос: все ли миллионы строк кода заполняют кэш L1 ЦП (и более) в случае шаблонной функции (и, таким образом, значительно ухудшают производительность), или только строки doAction<#>() внутри цикла, который в данный момент выполняется, кэшироваться?

Источник

2 ответа

Решение

Это зависит от фактического размера кода - 10 строк кода могут быть маленькими или большими - и, конечно, на реальном компьютере.

Тем не менее, метод 2 жестоко нарушает это правило десятилетий: инструкции дешевы, а доступ к памяти - нет.

Предел масштабируемости

Ваши оптимизации обычно линейны - вы можете сократить 10, 20 или даже 30% времени выполнения. Достижение лимита кэша очень нелинейно - как в случае "столкновения с кирпичной стеной" нелинейно.

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

  • DDR3-1333 с 10667MB/s пиковая пропускная способность памяти,
  • Intel Core i7 Extreme с ~75000 MIPS

дает 10667 МБ / 75000 М = ​​0,14 байта на инструкцию для безубыточности - ничего большего, а основная память не справляется с процессором.

Типичные размеры команд x86 составляют 2..3 байта, выполняя в циклах 1..2 (теперь, конечно, это не обязательно те же инструкции, поскольку инструкции x86 разбиты. Тем не менее...) Типичные длины команд x64 еще больше,

Насколько помогает ваш кеш?
Я нашел следующее число (другой источник, поэтому его трудно сравнивать): кэш i7 Nehalem L2 (256 КБ, >200 ГБ / с пропускной способности), который почти не отставал от инструкций x86, но, вероятно, не для x64.

Кроме того, ваш кэш L2 будет полностью активирован, только если

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

Учитывая это, вы можете проиграть намного раньше, особенно на процессоре / плате с меньшим объемом кеша.

Источник

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

Другими словами, из-за цикличности обоих ваших методов, кэш L1 будет работать превосходно в обоих случаях и не будет узким местом.

Источник
Другие вопросы по тегам