Могут ли 2 маленьких цикла быть быстрее, чем один большой?

Я смотрел это видео "как мы здесь оказались?" Мартин Томпсон из механической симпатии. (http://m.youtube.com/watch?v=oxjT7veKi9c)

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

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


loops performance cpu-cache
person adsisco    schedule 20.09.2015    source источник
comment
Посмотрите мозаику петли. Простой пример здесь - stackoverflow.com/questions/20367246/   -  person Leeor    schedule 20.09.2015

Ответы (2)


arrow_upward
1
arrow_downward

Простой пример:

double sum1 = 0, sum2 = 0;
for (i = n; --i >= 0;){
  sum1 += a[i];
  sum2 += b[i];
}

по сравнению с:

double sum1 = 0, sum2 = 0;
for (i = n; --i >= 0;){
  sum1 += a[i];
}
for (i = n; --i >= 0;){
  sum2 += b[i];
}

В первом примере компилятор должен сгенерировать код для «переключения контекста» между индексацией a[i] и b[i] и отслеживать, куда идет добавление. Если a и b сложные, компилятор может быть не в состоянии хранить ссылки на них обоих в регистрах. В результате это «переключение контекста», поскольку оно должно выполняться на каждой итерации, требует больше командных циклов, чем затраты на дополнительный цикл. (С развертыванием это еще более верно.)

Это все еще без учета проблем с кешем.

person Mike Dunlavey    schedule 20.09.2015

arrow_upward
0
arrow_downward

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

Тем не менее, я сомневаюсь, что этот трюк может быть действительно полезным в целом.

person Matt    schedule 20.09.2015