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

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

Способ 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<#>() внутри выполняемого в данный момент цикла попасть в кеш?


person zeroes00    schedule 20.07.2010    source источник
comment
Предположим, что функция doAction(int action) и шаблон функции‹ int Action› doAction() состоят примерно из 10 строк кода, который будет встроен во время компиляции. Компиляторы обычно недостаточно умны, чтобы оптимизировать вашу шаблонную версию, коммутатор снизит вашу производительность намного больше, чем ваш кеш L1.   -  person Tomaka17    schedule 20.07.2010
comment
Насколько я понимаю, вы говорите, что такой большой переключатель является самой большой проблемой для производительности. Но меня больше всего интересует, заполняется ли кеш L1 во втором методе и является ли это проблемой или нет. Я просто не знаю, как это работает. Мне также интересно, почему компилятор не знает, как встроить шаблонную версию функции, предполагая, что она очень похожа, но немного проще, чем обычная функция?   -  person zeroes00    schedule 20.07.2010


Ответы (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 полностью сработает только в том случае, если

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

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

person peterchen    schedule 28.07.2010

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

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

person Amardeep AC9MF    schedule 27.07.2010
comment
предполагая, что экземпляры doAction<int> не свернуты снова, код необходимо извлечь из L2/L3/основной памяти. С типичным соотношением памяти и цикла выполнения, даже если вы точно предсказываете, какие инструкции будут следующими, вы не сможете достаточно быстро перелопатить их в кэш L1. - person peterchen; 29.07.2010