Нам представилась замечательная возможность провести небольшой, но чрезвычайно поучительный тактический урок.
Вопросы оптимизации программ, выполняющих значительный объем вычислений, к сожалению, недостаточно освещены в литературе и, как правило, сводятся к каким-то общим принципам, правильность которых совершенно не очевидна и до прочтения аргументов автора.
, или даже после.
Поскольку в упомянутом посте (поиск по цитируемым словам) была предложена небезынтересная вычислительная задача, позволяющая продемонстрировать эти принципы и конкретные приемы оптимизации в действии, и был создан реальный пост, который хоть и несколько отклоняется от излюбленного направления автором (я вполне вижу решение этой проблемы на МК М3-класса и даже на Ардуино, попробуйте, но все же микроконтроллеры предназначены немного для других целей), но тем не менее вписывается в концепцию курса программирования МК.
Итак, поехали.
Напомню задачу: нужно найти пять целых неотрицательных чисел, у которых сумма пятых степеней первых четырех из них равна пятой степени последнего.
Формулировка не совсем корректна и будет уточняться в дальнейшем, но для начала сойдет. Естественным алгоритмом решения этой задачи было бы перебор возможных наборов чисел и проверка, выполняется ли для них заданное условие.
Сразу уточним условие - числа, не превышающие определенного предела, иначе поиск может никогда не закончиться, если такого набора вообще не существует (мы не всерьез надеемся проверить ВСЕ наборы из пяти целых неотрицательных чисел, я не знаю как читатели, уверен, до конца поисков не доживу).
Напишем это естественное решение, чтобы сразу отметить одну важную особенность современного программирования, и вот она.
Сразу договоримся, что все наши программы мы запускаем в компиляторе MinGW версии 6.2 на машине x86 i3-2120 3,3 ГГц, что бы ни означали эти цифры.
Если параметры вашей системы отличаются от моих, то абсолютные значения показателей времени будут несколько отличаться, хотя относительное время работы разных вариантов должно быть близким.
Мы видим, что среди наборов чисел меньше 100 не найден набор, удовлетворяющий заданному условию (на самом деле их найдено много, но они нам не подходят, так как числа должны быть разными, а не равными).
до нуля.
Я раньше этого не говорил? - еще один аргумент в пользу тщательного формулирования ТЗ) и в процессе поиска мы проверили 1е10 комбинаций.
В данном случае время работы программы составило 63 секунды.
Мы уже поняли, что программа некорректна из-за неполного формирования условий, но прежде чем начать ее модифицировать, поговорим о возможном ускорении вычислений тем же алгоритмом.
В мое время были книги, в которых давались рекомендации по машинно-независимой оптимизации выполнения с течением времени, и для этого алгоритма подойдут следующие рекомендации: — убрать часть вычислений из внутреннего цикла и сформировать промежуточную сумму первых трёх чисел; — организовать внутренний цикл для уменьшения индекса, а не для его увеличения; — организуйте внутренний цикл как {} while, а не for; — сделать регистр индексной переменной; — оптимизировать вычисление пятой степени, что позволит сократить количество умножений с 4 до 3, - чередовать расчеты градусов, чтобы не заблокировать трубопровод и так далее.
и изначально я собирался провести все эти изменения и показать их влияние на производительность и продемонстрировать, как десятки процентов превращаются в увеличение производительности в несколько раз, но потом я отказался от этой идеи.
Дело в том, что эти рекомендации несколько устарели и на данный момент единственное, что требуется от программиста, это позволить компилятору выполнить оптимизацию на уровне 3. Да, нужно знать, как это сделать, в моем случае контроль оптимизации есть скрыто в разделе Проект/Настройки.
-Компиляция/Оптимизация, но это все, что вам нужно знать для проведения такой оптимизации.
Постоянные читатели моих постов (льщу себя надеждой, что такие есть) уже привыкли видеть в моих опусах сетования на упадок нравственности и отсутствие зеленой травы в современной электронике по сравнению со временами моего прихода в профессию, но сейчас Я, нисколько не отказываясь от высказанного ранее мнения, должен с уверенностью заявить, что современные компиляторы значительно лучше своих предшественников и практически идеальны с точки зрения генерируемого кода, если им разрешена оптимизация.
Столь сильное утверждение требует доказательства, и вот оно — компилируем нашу программу с включенной оптимизацией и на том же процессоре видим время выполнения 20 секунд, то есть рост производительности в 3 раза (в основном за счёт первого рекомендация, хотя и остальные тоже способствовали до пятой части ускорения) и без малейшего усилия с нашей стороны - потрясающе.
Желающие могут попробовать все перечисленные мной способы повышения производительности и посмотреть на результат, но я настоятельно рекомендую просто посмотреть на полученный ассемблерный код и понять, что улучшить его практически невозможно.
Присоединяясь к автору оригинального поста, очень рекомендую сайт gcc.godbolt.org, который дает возможность просмотреть код, сгенерированный компилятором gcc для разных архитектур и для разных режимов оптимизации.
Прирост производительности существенный, тема алгоритмонезависимой оптимизации исчерпана, но на этом пост не заканчивается — неужели еще чем заняться? Да, есть способы улучшить программу (повысить ее производительность) и здесь компилятор нам уже не поможет, так как он не понимает сути действий, происходящих в коде, и не может подсказать необходимые изменения; это может сделать только программист. На мой взгляд, это удача, поскольку даже современные средства разработки программ оставляют простор для творчества, хотя мой молодой коллега нашел определенные неудобства в продвижении современных компиляторов, сказав: «Вам было проще, вы знали, что компилятор не оптимизирует ничего, нет. Мы надеялись и сделали все вручную, но нам нужно решить, с чего начинается наша часть работы».
Ну что сказать - если делать все необходимые оптимизации вручную, то хуже точно не станет (лучше тоже не станет, так как работа будет дублироваться), так что ничто не мешает идти до конца , я просто предложил более короткий путь.
Возвращаемся к нашей программе и ищем способы ее ускорить.
Вернее, прежде чем искать такие способы, нужно убедиться в необходимости данного действия.
Проверяем время выполнения для разных значений границы и обнаруживаем, что для значений 60 и 70 времена отличаются более чем в 2 раза, что подтверждает нашу гипотезу о времени работы алгоритма как o(N**5 ): 70/60=1,17**5 =2,2 раза.
Воспользуемся полученной формулой, чтобы оценить время выполнения нашей программы на границе 1000 и получим 553 часа, что немного выше наших ожиданий; для больших чисел время точно не будет меньше — есть смысл оптимизировать.
Далее перед абзацами будут указаны принципы решения инженерных задач системы ТРИЗ, насколько я помню.
Принцип исключения, или исключения повторной работы
Пока мы не видим возможности изменить полученную оценку времени выполнения алгоритма, мы можем уменьшить коэффициент при определяющем члене.Видно, что мы перечисляем все перестановки данного набора натуральных чисел; если принять во внимание возможность их ранжирования и независимость результата от порядка операндов, то придем к выводу, что необходимо рассматривать комбинации элементов данного множества.
Перебор комбинаций легко реализуется путем изменения начального значения переменной цикла для следующего элемента, что мы и делаем, при этом скорость работы программы резко возрастает, на два порядка.
Ну так и должно быть, мы рассчитывали на прибавку в 5! раз, а это ровно 120. Небольшое отступление - в исходном посте к подобной мысли автор приходит после того, как выписал на листок бумаги различные комбинации индексов и рассмотрел полученные результаты, так как честно признается, что не силен в комбинаторике.
Отдавая должное его стараниям, надо сказать, что комбинаторика и элементы теории вероятностей (именно элементы, поскольку ТерВер во всей его красоте и мощи нельзя назвать простым) — это та часть математики, без которой анализировать алгоритмы контрпродуктивно.
Я, конечно, рад, что автору удалось воссоздать способ образования комбинаций, но его надо просто знать и всё, как таблицу умножения.
Это я относительно периодически возникающих споров на тему, нужна ли программисту математика, но это мое личное мнение, высказанное в частной беседе, и оно может быть ошибочным.
Возвращаясь к основной теме, это именно та оптимизация, которую компилятор делать не будет, так как здесь нужно понимать суть проблемы и алгоритм, реализующий ее решение, а он на это пока не способен (компилятор с двумя инструкции до сих пор остается нереализованным идеалом, хотя кто знает, что будет дальше).
И еще одна важная особенность — обычно польза от такой оптимизации во много раз превышает любую возможную выгоду от оптимизации, проводимой компилятором, что и подтверждается в данном случае, поскольку 120> > 5. Сведем полученные результаты и попробуем экстраполировать их на несколько большие значения, получим Граница__Без оптимизации____Компилятор______Наши________Оба 10_________0.00 _____________0.00__________0.00________0.00 50_________2.32______________0.66__________0.02________0.01 100________62.91_____________19.93_________0.49________0.16 ( 1.43) 150_______476.20____________150.67_________3.80________1.21 (10.99) 10:00_______18:00*____________553 ч*_________14 ч*_______5 ч*(35 ч*) (время расчета для типа результата long long указано в скобках).
Мы видим, что если исходный вариант был практически неприемлем для граничных значений выше 200, то последний вариант применим вплоть до значения 1000. И мы даже нашли решение, их два, однако одно из них ложное, поскольку до переполнения, но об этом позже, а пока попробуем улучшить производительность дальше.
Принцип предварительного исполнения
Очевидное решение - заранее посчитать значения степеней и выбрать его из таблицы, несомненно, дало результат, но, честно говоря, несколько меньший, чем я надеялся, видимо, с реализацией умножения в х86 все в порядке., но с выборкой из массива хуже.
Но все равно увеличение почти в 8 раз очень приятно.
(Почему-то для варианта с типом результата int прироста производительности вообще нет).
Чисто теоретически я могу представить себе компилятор, который будет проводить такую оптимизацию, но пока такого не видел.
Отметим, что в данном случае за производительность пришлось платить дополнительной памятью, что характерно, поскольку два направления оптимизации - по времени и по памяти, как правило, противоречат друг другу.
Теги: #программирование #программирование#include "time.h" #include "stdio.h" #define LOOP(n,m) for (int n=m+1; n<=MAX; n++) #define REZ(i) (Pow5[i]) typedef long long int rez_t; int main(void) {
-
Дроны Доставляют Чай В Китай
19 Oct, 24 -
Куда Идут Деньги В Наших Школах?
19 Oct, 24 -
Новые Шутники?
19 Oct, 24 -
Обновление Netscape Navigator 9.0.0.1
19 Oct, 24
