Что-то на канале давно ничего не было про кодинг. Попытаюсь исправить ситуацию. Сегодня поговорим с вами об оптимизациях цикла. Хорошо известно, что для оптимизации программы, для её ускорения, наши усилия должны быть сосредоточены на локальных областях, чтобы отдача была максимальной. Конструкции цикла в программе как раз представляют собой такие области. Определенная степень ускорение достигается за счет размыкания, объединения и развертывания циклов.
Размыкание цикла
Если внутри цикла есть условный оператор if-else, и принятие решение внутри цикла происходит на каждой итерации, то это называется замыканием (switching) цикла. Но если при выполнении цикла условие не изменяется, то вы можете разомкнуть (unswitch) цикл, приняв решение вне цикла. Таким образом мы как будто выворачиваем цикл наизнанку. Смысл этого действия в том, чтобы исключить инструкцию проверки условия при каждой итерации, в том случае, когда это условие не изменяется во время итераций цикла.
Не смотря на то, что такие действия нарушают удобочитаемость кода, такое размыкание приводит к увеличению производительности примерно на 20% в C++, Java и Python, а также около 1% в Visual Basic.
Нужно еще понимать, что результат отдельного вида оптимизации непредсказуем в контексте разных языков программирования. Поэтому стоит проверять отдельно на каждом ЯП.
Объединение циклов
А вот и альтернативный, даже противоположный, вариант. Допустим, есть два цикла, которые работаю с одним набором элементов. Тогда можно объединить (jamming) их для получение выгоды при устранение затрат на выполнение дополнительного цикла. Самое важное здесь - это чтобы совпадали диапазоны изменение данных. Приведем пример:
В результате объединения производительность улучшается: в С++ на 28%, в PHP на 32%, в VB на 4%.
Развертывание цикла
В информатике под этой фразой подразумеваются различные способы оптимизации программ, такой своеобразный рефакторинг, при котором количество инструкций в цикле увеличивается. То есть за одну итерацию выполняется либо несколько инструкций, либо более сложная инструкция, которая может быть разбита компилятором на несколько.
Зачем это нужно? В результате таких манипуляций увеличивается количество инструкций, которые (в теории) могут быть исполнены параллельно, а также происходит более интенсивное задействование регистров процессора (быстрая память), кэша данных и исполнительных устройств ( АЛУ, Арифметико-логическое устройство ).
Целью развертывания является сокращение затрат, которые связаны с выполнением цикла. Интересен факт, что полное развертывание цикла, состоящего из инициализации 10 элементов массива циклом увеличивает производительность на 60% в C++ и Java. То есть 10 отдельных обращений к элементам массива выполняется быстрее, чем три строчки цикла. В народе такой код считают индусским, но он объективно работает быстрее.
Приведем еще пару интересных примеров с однократным и двухкратным развертыванием цикла:
Как видно отсюда, мы сталкиваемся с возможность ускорения на 15-43%, не считая Python. Тут уже нужно разбираться в байт-коде, не всё является однозначным.
Для дальнейшей оптимизации циклов стоит подумать надо ценой различных операций. Иногда умножение можно заменить на сложение. Иногда вложение более ресурсоемкого цикла в менее ресурсоемкий дает прирост производительности более 15% и экономии времени до 33% на C++ и 34% на Java. Обязательно нужно пробовать снижение стоимости операций. Об этом можно прочитать в главе 26 Методики оптимизации кода в книге Совершенный код Стива Макконнелла ( скачать тут ).
Расщепление цикла
Существует и другая оптимизация, которая называется расщеплением цикла ( loop fission ). Суть заключается в том, чтобы разбить цикл на несколько циклов, при этом все эти циклы имеют одинаковые диапазоны изменения индекса, только содержат разные части тела исходного цикла.
Чем помогают эти методы?
Такие оптимизации помогают выполнить цикл на нескольких потоках или на различных ядрах CPU, при отсутствии зависимостей данных между инструкциями в новом цикле.
Чем плохи эти методы ?
В случае распараллеливания, происходит сбой порядка обращения к данным, то есть обращение к данным происходит не по порядку их расположения в памяти. Это плохо сказывает на эффективности работы кэширования.
История создания данного вида оптимизации
Были приложены значительные усилия для разработки методов S2S (source-to-source) преобразования кода, в которых применялась реструктуризация конструкций циклов. Делалось это для того, чтобы открыть возможности для параллелизма вычислений.
Рассмотрим следующий цикл:
Этот цикл FOR может быть преобразован в следующий эквивалентный цикл, состоящий из нескольких копий исходного тела цикла:
В этом случае говорят, что это двукратное развертывание цикла. И этот развернутый цикл должен работать быстрее из-за уменьшения расходов на создание цикла.
Изначально развертывание цикла было разработано для снижения накладных расходов на циклы и для обеспечения параллелизма на уровне инструкций для машин с несколькими функциональными блоками. Относительно недавно этот механизм был применен в сочетании с планированием инструкций для конвейерных и RISC архитектур. Увеличивая размер тела цикла, планировщик команд в большинстве случаев может создавать более короткое расписание инструкций для развернутого цикла.
Циклы for, работающие с массивами, можно развернуть, просто изменив счетчик и условие завершения цикла, как было показано выше. В то время как циклы while, как правило, сложнее развернуть. Это происходит главным образом из-за трудностей определения условия завершения развернутого цикла while.
Обобщенная теория развертывания цикла while
Предположим, что циклы записываются в виде while B do S, семантика которого определяется привычным для нас образом ( пока выполняется условие B делать инструкцию S). Это предположение не должно приводить к потере общности, потому что любой другой цикл может быть переписан в этой форме, которую мы предположили в начале абзаца.
Будем называть B — предикатом цикла, а S — телом цикла. Если подробнее, то так:
тело — это набор инструкций, от одной и более.
предикат — выражение, использующее одну или несколько величин с вычисляемым результатом логического типа.
Используя данный метод анализа, можно показать, что выполняются следующее соотношение эквивалентности.
Здесь ⇔ обозначает отношение эквивалентности, а wp(S, B) — самое слабое предварительное условие S ( weakest precondition ) по отношению к постусловию B.
Будем говорить, что эквивалентная программа (с правой стороны) получается при однократном развертывании цикла. Обратите внимание, что если какие-либо данные приведут к тому, что цикл слева повторится n раз, то это приведет к тому, что первый цикл справа повторится ⌊ n / 2 ⌋ раза, а второй цикл справа 0 или 1 раз. Теперь, если мы можем упростить B ∧ wp(S, B) или S; S, как объясняется ниже, то мы можем развернуть цикл для достижения определенной степени ускорения вычислений.
⌊ x ⌋ — функция "пол", определяется как наибольшее целое, меньшее или равное x. Обозначения из дискретной математики. (почитать здесь)
Цикл while можно разворачивать и дальше. Можно показать, что :
Выражение в правой части показывает, как дважды развернуть цикл. Естественно, цикл можно развернуть трижды, четыре раза и так далее и тому подобное.
Таким образом, учитывая конструкцию цикла вида while B do S мы можем ускорить его выполнение, выполнив перечисленные ниже шаги, чтобы развернуть его один раз:
1. Сформировать wp(S, B) как самое слабое предварительное условие S по отношению к B.
2. Развернуть (размотать) цикл один раз, заменив его последовательностью из двух циклов:
while B ∧ wp(S, B) do begin S; S; end;
while B do S
3. Упростите предикат B ∧ wp(S, B) и тело цикла S; S для ускорения.
Обратите внимание, что второй цикл в развернутой конструкции — это исходный цикл. Поскольку он будет повторяться не более одного раза, теоретически его можно заменить конструкцией if B then S. Да, так тоже будет работать. Однако с точки зрения разработки ПО желательно оставлять его неизменным, потому что исходный (оригинальный) цикл легче понять.
Кроме того, если по какой-то причине разворачивание цикла становится нежелательным, всё, что нам требуется сделать, так это просто удалить первый цикл. С этой целью желательно разграничивать первый и второй циклы комментариями. Также с помощью многострочного комментария будет легко отыскать и удалить первый цикл при отладке кода.
Пример 1. Цикл для вычисления целой части q от деления a на b
Развертываем наш цикл и получаем:
Эксперименты показывают, что эти варианты однократного развернутого цикла способны достичь коэффициента ускорения очень близкого к 2. Если развернуть цикл k раз, то можно достичь коэффициента ускорения k.
Коэффициент скорости определяется как соотношение между временем процессора, необходимым для выполнения измененной программы (развернутого цикла), и временем, необходимым для выполнения исходной программы.
Замечания и обсуждения
Хотя три приведенных выше варианта развертывания логически эквивалентны в теории, на практике это может быть не совсем так. Обратите внимание, что в приведенном выше отношении эквивалентности ( смотри выше Обобщенная схема однократного развертывания цикла while ) предикатом цикла первого цикла с правой стороны является B ∧ wp(S, B). Поскольку логическая операция "∧" (И, and, &, конъюнкция ) является коммутативной, теоретически не должно иметь значения, записан ли предикат цикла как B ∧ wp(S, B) или wp(S, B) ∧ B, или если B или wp(S, B) оценивается первым. Однако, на практике сначала следует оценить значение выражения B, и если оно false, то wp(S, B) вообще не следует оценивать, поскольку оно определяет, следует ли выполнять вторую часть развернутого цикла.
Это не будет представлять проблемы, если:
1. компоненты предиката цикла всегда записываются в правильном порядке;
2. программа компилируется и выполняется в среде, где компоненты предиката цикла оцениваются в указанном порядке, и оценка завершается сразу же, как только обнаруживается, что один из компонентов предиката является ложным.
В противном случае, если эти два условия не выполняются, развернутый цикл может содержать ошибки во время выполнения, которые не возникали бы в исходном коде цикла.
Рассмотрим следующий пример...
Пример 2. Цикл для нахождения GCD( Greatest Common Divisor) или НОД (Наибольшего Общего Делителя) двух положительных целых чисел a и b с использованием алгоритма Евклида, конечный результат цикла, который является GCD a и b, хранится в a.
Развернув цикл один раз и упростив результат, мы получим:
Обратите внимание, что значение a % b может быть правильно вычислено только в том случае, если b > 0. И при вычислении a % b возникнет арифметическая ошибка, если b = 0. Чтобы избежать такой ошибки (сбитый приоритет выполнения операций в предикате), мы можем изменить цикл следующим образом.
Ускорение, достигнутое в этом случае, довольно ограничено, поскольку выигрыш в основном достигается за счет сокращения инструкций в телах циклов. В эксперименте, использующем 10 000 пар случайных целых чисел, средний коэффициент ускорения составляет приблизительно 1.05.
Возможной альтернативой является использование обработки исключений. Некоторые языки программирования, такие как C++, Smalltalk и Ada, предоставляют программисту механизм обработки исключений. Хотя временной штраф за обработку исключений высок, это считается жизнеспособным решением, поскольку исключения такого рода встречаются нечасто.
А что по указателям?
Проблемы аналогичного характера могут возникнуть, если задействованы указатели.
Пример 3. Цикл для обхода связанного списка и подсчета пройденных узлов
После двойного развертывание цикла мы получим:
Поскольку мы априори не знаем, сколько еще элементов будет в связанном списке, вычисление lp1 и lp2 может привести к ошибкам во времени выполнения, которые не возникнут в исходном цикле. Чтобы избежать этой проблемы, нам нужно изменить развернутый цикл, чтобы предотвратить выход указателя за пределы диапазона:
Другое возможное решение — прикрепить в конец списка специальный сторожевой узел с именем NULL_NODE. Поле ссылки этого узла указывает на него самого. Проиллюстрируем эту ситуацию:
Обратите внимание, что ссылающийся сам на себя сторожевой узел может быть использован в других приложениях для развертывания цикла, длина которого неизвестна в начале его выполнения.
Его использование позволяет нам размыкать цикл k раз и проверять в конце каждых k итераций, находится ли указатель в сторожевом узле NULL_NODE.
Мы ожидаем повышения производительности от преобразования. Поскольку выигрыш достигается не только за счет снижения накладных расходов цикла, но и за счет уплотнения вычислений, выполняемых в телах цикла. В эксперименте, где цикл развертывается трижды, а используемые связанные списки имеют размеры 100 и 500, средний коэффициент ускорения составляет приблизительно 1.19.
Пример 4. Алгоритм возведения в степень по модулю r = aⁿ (mod m), где a, n, m и r являются целыми числами.
После трехкратного развертывания цикла предикат цикла становится (n>0) && (n>2) && (n>4). Это условие можно упростить до (n>4). Если исходный цикл повторится N раз, развернутый цикл повторится максимум (N/3) + 2 раза (N/3 развернутых итерации и до 2 итераций исходного цикла). В этом случае из-за зависимости данных между итерациями не может быть достигнуто значительного сокращения инструкций. Таким образом, прирост производительности может быть получен только за счет сокращения числа тестов состояния.
Пример готовой программы с самым простым развертыванием цикла for. Подсчет суммы всех 1000000 элементов массива. Смотрим временное ускорение.
Даже такое простейшее преобразование цикла дает ускорение в 18.9 %, что уже является неплохой оптимизацией, на мой взгляд.
А вы используете в своих программах оптимизацию цикла? Если да, то расскажите в комментариях какие оптимизации вы делаете.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram