Какая конфигурация цикла займет больше времени для запуска?

Question

Код I:

for(i=0; i<100; i++){
  for(j=0; j<1000; j++){
    x = y;
  }
}

Код II:

for(i=0; i<1000; i++){
  for(j=0; j<100; j++){
    x = y;
  }
}

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

Answer 1

Это действительно зависит от множества факторов, находящихся вне вашего прямого контроля.

Как говорит пользователь David V в комментариях, оба будут просто устранены хорошим компилятором. Затем, если это не так, они переведут в некоторый машинный код с инструкциями ветвления. Когда процессор выполняет код с ветвлением, он использует так называемое спекулятивное предсказание ветвления, которое ведет себя по-разному в зависимости от того, в какие точные инструкции код переведен. Другие факторы могут повлиять, например, на ошибки в кеше кода. Вы не можете сказать, пока не проведете тщательный и тщательный анализ результатов.

Answer 2

Пока все ответы в целом верны, на мой взгляд. А именно, он будет оптимизирован и будет зависеть от машинного кода и т. Д. Я думаю, что в самом упрощенном случае, при отсутствии оптимизации и спекулятивного ветвления (что может быть нереально), код 1 окажется быстрее, потому что некоторое количество накладных расходов при настройке циклов. А именно, вы должны объявить переменные i и J. Поскольку накладные расходы внешнего цикла всегда происходят только один раз, реальным фактором здесь является внутренний цикл. Поскольку в коде 1 внутренний цикл устанавливается только 100 раз, а в коде 2 внутренний цикл устанавливается 1000 раз, код 1 должен быть быстрее. Опять же, это в самом простом случае, который, вероятно, был тем, на что был нацелен вопрос об интервью или вопрос викторины.

Answer 3

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

На самом деле, существует тривиальная конструкция уровня ЦП (инструкция цикла), которая выполняет вышеуказанное с минимальной программной эмуляцией.Таким образом, умножение является коммутативным, поэтому 100x1000 или 1000x100 одинаковы.

Answer 4

Как правило, внутренний цикл имеет большие шансы полностью поместиться в кэш, поэтому 100 из 1000 должны быть быстрее. Но компиляторы такие умные ...

Answer 5

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

Это был вопрос для интервью, верно?Ну что ж, ответ на собеседование:)