Исходный вопрос
Почему один цикл намного медленнее двух циклов?
Вывод:
Случай 1 - это классическая проблема интерполяции, которая оказывается неэффективной.Я также думаю, что это было одной из главных причин того, почему многие машинные архитектуры и разработчики закончили создание и проектирование многоядерных систем с возможностью выполнения многопоточных приложений, а также параллельного программирования.
Взгляд наэто из такого подхода без учета того, как аппаратное обеспечение, ОС и компилятор (-ы) работают вместе для выделения кучи, что включает в себя работу с ОЗУ, кэш-памятью, файлами подкачки и т. д .;математика, лежащая в основе этих алгоритмов, показывает нам, какой из этих двух вариантов является лучшим решением.Мы можем использовать аналогию, где Boss или Summation, который будет представлять For Loop, который должен путешествовать между рабочими A & B, мы можем легко увидеть, что Case 2 по крайней мере 1 / 2 так быстро, если не чуть больше, чем Случай 1 из-за разницы в расстоянии, необходимом для перемещения ивремя между рабочими.Эта математика почти виртуально и идеально соответствует как Bench Mark Times, так и разнице в инструкциях по сборке.
Теперь я начну объяснять, как все это работает ниже.
Оценка проблемы
Код ОП:
const int n=100000;
for(int j=0;j<n;j++){
a1[j] += b1[j];
c1[j] += d1[j];
}
И
for(int j=0;j<n;j++){
a1[j] += b1[j];
}
for(int j=0;j<n;j++){
c1[j] += d1[j];
}
Соображение
С учетом первоначального вопроса ФП о 2 вариантах циклов for и его исправленного вопросак поведению кешей наряду со многими другими отличными ответами и полезными комментариями;Я хотел бы попытаться сделать что-то другое здесь, по-другому подходя к этой ситуации и проблеме.
Подход
Учитывая два цикла иВо всех дискуссиях о кешировании и хранении страниц я бы хотел использовать другой подход, чтобы взглянуть на это с другой точки зрения.Тот, который не использует кеш и файлы подкачки, ни выполнения для выделения памяти, фактически этот подход даже не касается реального оборудования или программного обеспечения.
Перспектива
После некоторого изучения кода стало ясно, в чем проблема и что ее генерирует.Давайте разберем это в алгоритмической задаче и рассмотрим ее с точки зрения использования математических обозначений, а затем применим аналогию к математическим задачам и алгоритмам.
Что мы знаем
Мы знаем, что его цикл будет выполняться 100 000 раз.Мы также знаем, что a1, b1, c1 & d1 являются указателями на 64-битную архитектуру.В C ++ на 32-разрядной машине все указатели имеют размер 4 байта, а на 64-разрядной машине они имеют размер 8 байтов, поскольку указатели имеют фиксированную длину.Мы знаем, что у нас есть 32 байта для выделения в обоих случаях.Единственное отличие состоит в том, что мы выделяем 32 байта или 2 набора по 2-8 байт на каждую итерацию, тогда как во 2-м случае мы выделяем 16 байтов для каждой итерации для обоих независимых циклов.Таким образом, оба цикла по-прежнему равны 32 байта в общем распределенииС этой информацией давайте продолжим и покажем общую математику, алгоритм и аналогию.Мы знаем, сколько раз один и тот же набор или группа операций должны быть выполнены в обоих случаях.Мы знаем количество памяти, которое нужно выделить в обоих случаях.Мы можем оценить, что общая рабочая нагрузка распределений между обоими случаями будет примерно одинаковой.
Что мы не знаем
Мы не знаем, сколько времени это займет для каждого случая, если только мы не установим счетчик и не проведем тест производительности.Однако контрольные показатели были уже включены в исходный вопрос, а также в некоторые ответы и комментарии, и мы можем видеть существенную разницу между этими двумя вопросами, и в этом заключается полное обоснование этого вопроса для этой проблемы и для ответа на нееНачнем с.
Давайте исследуем
Уже очевидно, что многие уже сделали это, взглянув на распределение кучи, тесты тестов производительности, взглянув на оперативную память., Кэш и файлы подкачки.Рассмотрение конкретных точек данных и конкретных итерационных индексов также было включено, и различные разговоры об этой конкретной проблеме заставили многих людей начать сомневаться в других связанных с этим вещах.Итак, как нам начать смотреть на эту проблему, используя математические алгоритмы и применяя к ней аналогию?Начнем с того, что сделаем пару утверждений!Затем мы строим наш алгоритм оттуда.
Наши утверждения:
- Мы позволим нашему циклу и его итерациям быть суммированием, которое начинается в1 и заканчивается на 100000 вместо того, чтобы начинаться с 0, как в циклах, поскольку нам не нужно беспокоиться о схеме индексации адресации памяти 0, поскольку нас просто интересует сам алгоритм.
- В обоих случаях мыиметь 4 функции для работы и 2 вызова функций с 2 операциями, выполняемыми для каждого вызова функции.Таким образом, мы установим их как функции и вызовы функций:
F1(), F2(), f(a), f(b), f(c) и f(d).
Алгоритмы:
1-й случай: - только одно суммирование, но два независимых вызова функций.
Sum n=1 : [1,100000] = F1(), F2();
F1() = { f(a) = f(a) + f(b); }
F2() = { f(c) = f(c) + f(d); }
2-й случай: - Два суммирования, но каждое имеет свой собственный вызов функции.
Sum1 n=1 : [1,100000] = F1();
F1() = { f(a) = f(a) + f(b); }
Sum2 n=1 : [1,100000] = F1();
F1() = { f(c) = f(c) + f(d); }
Если вы заметили, F2() существует только в Sum, где оба Sum1 и Sum2 содержат только F1().Это также станет очевидным позже, когда мы начнем делать вывод, что со вторым алгоритмом происходит своего рода оптимизация.
Итерации по первому случаю Sum вызывают f(a), которые добавят кего самость f(b) затем вызывает f(c), который будет делать то же самое, но добавляет f(d) к себе для каждого 100000 iterations.Во втором случае у нас есть Sum1 и Sum2, и оба действуют одинаково, как если бы они были одной и той же функцией, вызываемой дважды подряд.В этом случае мы можем трактовать Sum1 и Sum2 как просто старый Sum, где Sum в этом случае выглядит следующим образом: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }, и теперь это выглядит как оптимизация, где мы можем просто считать егота же функция.
Сводка по аналогии
С тем, что мы видели во втором случае, почти кажется, что существует оптимизация, поскольку оба цикла имеют одинаковуюточная подпись, но это не настоящая проблема.Проблема заключается не в работе, выполняемой f(a), f(b), f(c) & f(d) в обоих случаях, а в сравнении между ними, а в разнице расстояния, на которое должно пройти суммирование.в обоих случаях это дает вам разницу во времени выполнения.
Думайте о For Loops как о Summations, который выполняет итерации, как о Boss, который отдает приказы двум людям A &B и что их работа заключается в том, чтобы добывать C и D соответственно, а также забрать у них какую-то посылку и вернуть ее.В аналогии здесь сами итерации цикла или суммирования и проверки условий на самом деле не представляют Boss.То, что на самом деле представляет собой Boss, здесь не непосредственно из фактических математических алгоритмов, а из фактической концепции Scope и Code Block в рамках подпрограммы или подпрограммы, метода, функции, единицы перевода и т. Д. Первый алгоритмимеет 1 область действия, где 2-й алгоритм имеет 2 последовательных области действия.
В первом случае на каждом вызове Boss идет к A и дает заказ, а A уходит, чтобы получить пакет B's, затем Boss идет к C и дает заказы сделать то же самое и получать пакет от D на каждой итерации.
Во втором случае Boss работает напрямую с A, чтобы пойти и получить пакет B's, пока не будут получены все пакеты. Затем Boss работает с C, чтобы сделать то же самое для получения всех пакетов D's.
Поскольку мы работаем с 8-байтовым указателем и занимаемся распределением кучи, давайте рассмотрим эту проблему здесь. Допустим, что Boss составляет 100 футов от A, а A составляет 500 футов от C. Нам не нужно беспокоиться о том, как далеко Boss изначально от C из-за порядка выполнения. В обоих случаях Boss сначала перемещается от A сначала до B. Эта аналогия не говорит о том, что это расстояние является точным; это всего лишь сценарий тестового примера для демонстрации работы алгоритмов. Во многих случаях при распределении кучи и работе с кешем и файлами подкачки эти расстояния между адресами могут не сильно различаться или могут очень сильно зависеть от характера типов данных и размеров массива.
Тестовые случаи:
Первый случай: На первой итерации Boss должен сначала пройти 100 футов, чтобы сдать ордер на A, и A уходит и делает свое дело , но затем Boss должен пройти 500 футов до C, чтобы дать ему ордер. Затем на следующей итерации и на каждой другой итерации после Boss нужно идти вперед и назад на 500 футов между ними.
Второй случай: The Boss должен пройти 100 футов на первой итерации до A, но после этого он уже там и просто ждет A до вернитесь, пока все листки не будут заполнены Затем Boss должен пройти 500 футов на первой итерации до C, потому что C составляет 500 футов от A, так как этот Boss( Summation, For Loop ) вызывается сразу после работы с A, а затем просто ждет, как он делал с A, пока все C's ордера не будут выполнены.
Разница в пройденных расстояниях
const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500);
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst = 10000500;
// Distance Traveled On First Algorithm = 10,000,500ft
distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;
Сравнение произвольных значений
Мы можем легко увидеть, что 600 - намного меньше, чем 10 миллионов. Теперь это не точно, потому что мы не знаем фактической разницы в расстоянии между тем, какой адрес ОЗУ или из какого Cache или файла подкачки каждый вызов в каждой итерации будет вызван многими другими невидимыми переменными, но это просто оценка ситуации, которую нужно знать, и попытка взглянуть на нее с наихудшего сценария.
Таким образом, по этим числам это будет выглядеть так, как будто Алгоритм Один должен быть на 99% медленнее, чем Алгоритм Два; однако, это только The Boss's часть или ответственность алгоритмов, и она не учитывает фактических работников A, B, C, & D и то, что они должны делать с каждым и каждая итерация цикла. Таким образом, работа боссов составляет только около 15-40% всей выполняемой работы. Таким образом, основная часть работы, выполняемой рабочими, оказывает чуть большее влияние на поддержание соотношения разностей скоростей примерно до 50-70%
Наблюдение: - Различия между двумя алгоритмами
В этой ситуации это структура процесса выполняемой работы, и он показывает, что Случай 2 более эффективен как при частичной оптимизации, так и при наличии аналогичного объявления функции и определения, гдеэто только переменные, которые отличаются по имени.И мы также видим, что общее расстояние, пройденное в Случай 1 , намного дальше, чем в Случай 2 , и мы можем считать это расстояние пройденным нашим Фактором времени междудва алгоритма. Дело 1 имеет гораздо больше работы, чем Дело 2 .Это также было замечено в свидетельстве ASM, которое было показано между обоими случаями.Даже с учетом того, что уже было сказано об этих случаях, это также не учитывает тот факт, что в случае 1 боссу придется ждать, пока оба A и C вернутся, прежде чем он сможетвернитесь к A снова на следующей итерации, и это также не учитывает тот факт, что если A или B занимает очень много времени, то и Boss, и другие работникитоже жду на холостых.В случае 2 только один бездействующий является Boss, пока рабочий не вернется.Так что даже это влияет на алгоритм.
Измененный вопрос (-ы) для ОП
РЕДАКТИРОВАТЬ: Вопрос оказался неактуальным, так как поведение серьезнозависит от размеров массивов (n) и кеша процессора.Так что, если есть дальнейший интерес, я перефразирую вопрос:
Не могли бы вы дать некоторое представление о деталях, которые приводят к различным поведениям кэша, какпроиллюстрированы пятью областями на следующем графике?
Также было бы интересно указать на различия между архитектурами ЦП и кэш, предоставляяаналогичный график для этих процессоров.
Относительно этих вопросов
Как я без сомнения продемонстрировал, существует еще одна проблема, лежащая в основе еще до оборудованияи программное обеспечение становится вовлеченным.Теперь что касается управления памятью и кэшированием вместе с файлами подкачки и т. Д., Которые все работают вместе в интегрированном наборе систем между: The Architecture {Аппаратное обеспечение, встроенное ПО, некоторые встроенные драйверы, ядра и наборы инструкций ASM}, The OS{Системы управления файлами и памятью, драйверы и реестр}, The Compiler {Единицы перевода и оптимизация исходного кода}, и даже сам Source Code с его набором (-ами) отличительных алгоритмов;мы уже можем видеть, что в первом алгоритме есть узкое место, прежде чем мы даже применим его к любой машине с произвольными Architecture, OS и Programmable Language по сравнению со вторым алгоритмом.Таким образом, уже существовала проблема, прежде чем задействовать внутренние особенности современного компьютера.
Конечные результаты
Однако;Нельзя сказать, что эти новые вопросы не важны, потому что они сами по себе и играют роль в конце концов.Они действительно влияют на процедуры и общую производительность, и это видно из различных графиков и оценок от многих, которые дали свои ответы и / или комментарии.Если вы обратите внимание на аналогию Boss и двух рабочих A & B, которые должны были пойти и получить пакеты из C & D соответственно, и с учетом математических обозначений двух рассматриваемых алгоритмоввы можете видеть, что даже без участия компьютера Case 2 примерно на 60% быстрее, чем Case 1, и когда вы смотрите на графики и диаграммы после того, как эти алгоритмы были применены к исходному коду, скомпилированы и оптимизированы и выполнены через ОСдля выполнения операций на данном оборудовании вы даже увидите немного большее ухудшение различий в этих алгоритмах.
Теперь, если набор «Данные» довольно мал, на первый взгляд может показаться, что разница не такая уж и плохая, но, поскольку Case 1 примерно на 1340 * медленнее, чем Case 2, мы можем рассматривать рост этой функции как С точки зрения разницы во времени исполнения:
DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)
И это приближение является средней разницей между этими двумя циклами как алгоритмически, так и машинными операциями, включающими оптимизацию программного обеспечения и машинные инструкции. Поэтому, когда набор данных растет линейно, увеличивается и разница во времени между ними. Алгоритм 1 имеет больше выборок, чем алгоритм 2, что очевидно, когда Boss должен был преодолевать максимальное расстояние между A и C для каждой итерации после первой итерации, тогда как алгоритм 2 Boss должен был перемещаться до A один раз, а затем после выполнения A он должен был пройти максимальное расстояние только один раз при переходе от A до C.
То, что попытка Boss сосредоточиться на двух одинаковых вещах одновременно и подтасовывать их взад и вперед вместо того, чтобы концентрироваться на похожих последовательных задачах, к концу дня заставит его разозлиться, потому что он должен был путешествовать и работать вдвое больше. Поэтому не теряйте масштаб ситуации, позволяя вашему боссу попасть в узкое место, поскольку супруга и дети босса этого не оценят.