Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
можно сунуться в LLVM Passes
http://llvm.org/docs/WritingAnLLVMPass.html
нет хардварного ассемблера, а есть достаточно простой LLVM IR (а уж JIT сама его преобразует в машинный код для конкретных архитектур)
в любом случае проект достаточно большой и известный, и он в сфере ваших наработок
http://llvm.org/docs/WritingAnLLVMPass.html
нет хардварного ассемблера, а есть достаточно простой LLVM IR (а уж JIT сама его преобразует в машинный код для конкретных архитектур)
в любом случае проект достаточно большой и известный, и он в сфере ваших наработок
Спасибо за идею. Про LLVM я уже думал, но изначально решил взяться за то что мне более знакомо (диплом же, сроки горят как всегда, хотя начал я его писать практически с начала магистратуры), в итоге слегка обломался.
Хотя конечно любой лишний уровень абстракции и промежуточных представлений кода вносит свои проблемы и непредсказуемость поведения.
Хотя конечно любой лишний уровень абстракции и промежуточных представлений кода вносит свои проблемы и непредсказуемость поведения.
Можно сунуться и в LLVM MachinePasses. Если по ссылке указан способ написания прохода уровня «платформо-независимого» оптимизатора (LLVM opt), то MachinePasses — это уже уровень кодогенерации и соответственно целевой платформы (LLVM llc). Может быть, в итоге можно будет улучшить что-то в Instruction Selection.
> оператор << использует только 5 младших бит своего первого операнда
Эээ… Второго?
Эээ… Второго?
В принципе это всё более-менее основы Генетического программирования, странно что Вы в статье не упоминали этого.
И да, в этой тематике как раз есть где развернуться при написании диплома
И да, в этой тематике как раз есть где развернуться при написании диплома
Возможно будет полезно для какого-нибудь из существующих супероптимизаторов.
en.wikipedia.org/wiki/Superoptimization
en.wikipedia.org/wiki/Superoptimization
Мне для программирования под NES и ромхакинга наверное очень пригодилось бы. Ассемблер у 6502 процессора очень простой, а скорость работы очень важна. Иногда игры начинают глючить из-за добавления всего нескольких инструкций — не успевают выполняться. Например, из-за этого у меня не получается портировать принца Персии на MMC3 маппер.
Мне как-то пришла в голову похожая, но немного другая мысль. Написание кода автоматически с помощью перебора вариантов. Например, задаем для функции вход и выход, как в юнит-тестах. Объявленные классы, методы, переменные, и операторы языка — единицы перебора. После завершения перебора выбираем наиболее подходящий вариант. В принципе, это возможно, только наверно много времени будет занимать.
Ну в каком-то смысле это похоже на мою идею. Но с функциями общего вида есть свои проблемы, например проблема останова — невозможно определить, она вообще завершится когда-нибудь или просто зависла, непонятно как это верифицировать, в случае с ветвлениями — нет гарантий что мимо всех тестов не просочилась какая-нибудь хитрая ветка условий, нарушающих спецификацию.
У меня в этом смысле более простой вариант, так как локальная оптимизация не имеет дела с ветвлениями и условиями, только линейный код.
У меня в этом смысле более простой вариант, так как локальная оптимизация не имеет дела с ветвлениями и условиями, только линейный код.
Прекратите копать в эту сторону! Сами себя без работы оставите!
Вы молодые, шутливые вам все легко. Это не то. Не чикатило и не архивы спецслужб :D
А вообще я думаю, вряд ли такая опимизация способна оставить без работы программиста. Вряд ли она способна соптимизировать сортировку пузырьком до сортировки Шелла, либо сделать более читаемый и менее связный код.
Тем более уже вариантов для нескольких сотен инструкций будет столько, что не одна машина до конца жизни Вселенной с перебором не справится.
А вообще я думаю, вряд ли такая опимизация способна оставить без работы программиста. Вряд ли она способна соптимизировать сортировку пузырьком до сортировки Шелла, либо сделать более читаемый и менее связный код.
Тем более уже вариантов для нескольких сотен инструкций будет столько, что не одна машина до конца жизни Вселенной с перебором не справится.
напишите плагин для OllyDbg чтоб в памяти инструкции парсил и патчил скажем до ret или jmp/jxx например. или даже не патчил, а показывал до чего можно упростить…
будет большой плюсег в карму и стопицот к ЧСВ ;-)
будет большой плюсег в карму и стопицот к ЧСВ ;-)
А Вы как нибудь данные идеи в какой-нибудь более-менее стабильный продукт оформляли?
Посмотреть бы коды.
Может синтаксис какой изобрели удобный для описания задач?
С удовольствием парочку интересных идей украл бы.
Посмотреть бы коды.
Может синтаксис какой изобрели удобный для описания задач?
С удовольствием парочку интересных идей украл бы.
Есть репозиторий на битбакете.
bitbucket.org/e_smirnov/gp_optimizer
Например чтобы запустить оптимизацию джавовского примера из статьи надо написать что-то типа:
После выполнения данного кода rz будет содержать наилучший из найденных и прошедших верификацию результатов.
Есть бекенды для JVM, x86 (там очень маленький набор поддержанных инструкций) и пиксельных шейдеров. Примеры использования можно увидеть в main.java
Для работы нужен верификатор Z3 майкрософтовский
Для оптимизации шейдеров — консольная тулза NvShaderPerf которая считает их производительность.
Помимо такого вида запуска я там даже запилил целый сервер, который с помощью библиотечки распределенных вычислений JPPF может принимать и раскидывать задачи оптимизации по вычисляющим серверам. И клиент, который парсит заданные jar-файлы, ищет в них подходящие последовательности инструкций и шлет их на сервер, ждет ответа а потом если пришел ответ с найденными оптимизациями — патчит джарники оптимизированными инструкциями. Можно эту инфраструктуру всю попробовать поднять (JPPF там правда старый какой-то типа 2 версии).
Правда, как я уже писал, глазами результатов ее работы увы не видно. Слишком маленькие оптимизации. Поэтому я и забросил это дело, слегка в нем разочаровавшись.
bitbucket.org/e_smirnov/gp_optimizer
Например чтобы запустить оптимизацию джавовского примера из статьи надо написать что-то типа:
GPOptimizer jvmOptimizer = new GPOptimizer(new JavaTargetArchitecture());
InstructionSequence sequence = new InstructionSequence();
sequence.add(new JVMInstruction(JavaOpcodes.ICONST_M1));
sequence.add(new JVMInstruction(JavaOpcodes.IXOR));
sequence.add(new JVMInstruction(JavaOpcodes.ILOAD, new LocalVariableSlot(10)));
sequence.add(new JVMInstruction(JavaOpcodes.IAND));
InstructionSequence rz = jvmOptimizer.optimize(sequence, 550);
После выполнения данного кода rz будет содержать наилучший из найденных и прошедших верификацию результатов.
Есть бекенды для JVM, x86 (там очень маленький набор поддержанных инструкций) и пиксельных шейдеров. Примеры использования можно увидеть в main.java
Для работы нужен верификатор Z3 майкрософтовский
Для оптимизации шейдеров — консольная тулза NvShaderPerf которая считает их производительность.
Помимо такого вида запуска я там даже запилил целый сервер, который с помощью библиотечки распределенных вычислений JPPF может принимать и раскидывать задачи оптимизации по вычисляющим серверам. И клиент, который парсит заданные jar-файлы, ищет в них подходящие последовательности инструкций и шлет их на сервер, ждет ответа а потом если пришел ответ с найденными оптимизациями — патчит джарники оптимизированными инструкциями. Можно эту инфраструктуру всю попробовать поднять (JPPF там правда старый какой-то типа 2 версии).
Правда, как я уже писал, глазами результатов ее работы увы не видно. Слишком маленькие оптимизации. Поэтому я и забросил это дело, слегка в нем разочаровавшись.
Спасибо
Обязательно повнимательней посмотрю — эта тема мне тоже интересна
Обязательно повнимательней посмотрю — эта тема мне тоже интересна
Да и в случае любой оптимизации кода — как пел Дуремар в фильме Буратино — я готов унизится, чтоб потом возвысится.
А вы не пробовали делать алгоритм, но который не только старается всё улучшить, но и ухудшить. только вероятность улучшения больше вероятности ухудшения. и погонять.
средний шаг всё равно остаётся положительным, а вот итоговые результаты лучше должны быть.
и проанализировать зависимость от разности.
А вы не пробовали делать алгоритм, но который не только старается всё улучшить, но и ухудшить. только вероятность улучшения больше вероятности ухудшения. и погонять.
средний шаг всё равно остаётся положительным, а вот итоговые результаты лучше должны быть.
и проанализировать зависимость от разности.
Ухудшение скорости? Увы, если не предпринимать особых мер то это приведет к быстрому заполнению популяции очень длинными особями. Они будут считать то же самое, но медленнее, при этом за счет своей длины будут очень сильно тормозить сам генетический процесс. Средняя длина особи без ограничений начинает расти очень быстро, для исходной особи в 10 инструкций через сотню поколений средняя длина особи в популяции может превысить 50 инструкций. И все становится до невозможности медленным.
habrahabr.ru/post/270443 — я ссылаюсь на Вас в своей статье. Было бы интересно если Вы предложите дополнительные идеи.
Кстати — там может даже будет нужно ухудшать код программы.
Обработка приватных данных на публичных вычислительных сетях
Кстати — там может даже будет нужно ухудшать код программы.
Обработка приватных данных на публичных вычислительных сетях
С удовольствием парочку интересных идей украл бы
GPOptimizer jvmOptimizer = new GPOptimizer(new JavaTargetArchitecture());
InstructionSequence sequence = new InstructionSequence();
sequence.add(new JVMInstruction(JavaOpcodes.ICONST_M1));
sequence.add(new JVMInstruction(JavaOpcodes.IXOR));
sequence.add(new JVMInstruction(JavaOpcodes.ILOAD, new LocalVariableSlot(10)));
sequence.add(new JVMInstruction(JavaOpcodes.IAND));
InstructionSequence rz = jvmOptimizer.optimize(sequence, 550);
Ваш код сильно напоминает абстрактный вычислитель Маркова — замена в сроке символов шаблона на последовательность.
абстрактный вычислитель Маркова, абстрактный вычислитель Тьюринга, машина Поста — всё они эквивалентны.
Соответственно, это модель когда на ленте абстрактного вычислителя записан текст программы.
Шаги замен переводят в эквивалентны тексты программ.
Соответственно можно искать оптимизированную программ в каком либо смысле — например — меньше команд или быстрее исполнение.
Глянте в сторону и языка РЕФАЛ с его супер компилятором.
Только надо делать оптимизированную программ в каком либо смысле — а можно чередовать шаги — сперва делаем меньше команд — потом — быстрее. Чередуем несколько раз — и вот алгоритм для обфукации кода.
в идеале сделать такую штуку, которой на вход подается программа, а дальше она ее крутит так и сяк и пытается всячески ускорить отдельные ее фрагменты без участия человека,
это машина Маркова
попутно собирая себе базу для последующих оптимизаций.
это суперкомпиляция
Сразу скажу что хотя в целом задача была решена, практической пользы я из нее извлечь не смог.
habrahabr.ru/post/270443 Коммерческая тулза для обработки приватных данных на публичных сетях — например в облаке MS Azure
Может старап забацать чтобы пару баксов срубить?
Проблема в том что мой алгоритм работает только с довольно частным подвидом оптимизаций. Он не осилит принципиальную перестановку блоков в программе и все то что обычно делают обфускаторы. Он может обрабатывать только не содержащий ветвлений код (иначе невозможно будет однозначно определить состояния процессора, которые будут получаться после запуска кода и которые должны быть до его запуска), а это очень сильно органичивает область применения.
В свое время тоже занимался оптимизациями на уровне VM только под .NET. Только у меня было без генетических алгоритмов, а просто был перебор. Хотя вся обработка в основном проводилась на более высоком уровне: Математические выражения в .NET.
Я могу Вас успокоить — задача оптимизации произвольного взятого выражения является задачей равной сложности полного перебора.
Доказательство этого факта просто и очевидно.
Рассмотрим произвольную булеву функцию нескольких переменных.
Оценка сложности приведения этой булевой функции к дистрибутивной минимальной форме равна сложности полного перебора — это доказываться ещё на первом курсе института. Таким образом…
Доказательство этого факта просто и очевидно.
Рассмотрим произвольную булеву функцию нескольких переменных.
Оценка сложности приведения этой булевой функции к дистрибутивной минимальной форме равна сложности полного перебора — это доказываться ещё на первом курсе института. Таким образом…
Это если мы ищем самую-самую оптимальную (тавтология, но как мне кажется более понятное определение) последовательность инструкций. Этим занимаются так называемые Супероптимизаторы, о которых выше в комментах уже писали.
Но для прикладных задач нам достаточно найти просто какой-нибудь вариант который будет быстрее исходного. Будет ли он наилучшим вообще или просто «более хорошим» — нас любой вариант устроит. И вот тут генетика дает как раз невероятное преимущество перед перебором.
Процесс у меня обычно сходился за ~200 поколений по 100 особей, то есть всего за 20к исполнений кода. А всего же возможных его вариантов (если рассматривать пример из начала статьи — последовательность из 11 инструкций, пара десятков возможных разных инструкций) — миллиарды раз надо запустить будет сгенерированные фрагменты.
Поэтому например во всех статьях о супероптимизации рассматриваются обычно последовательности не более 3-4 инструкций длиной. Генетика же, как показано тут, отлично справляется с 10+ инструкциями. Можно бы даже еще длиннее, но тут уже сложно искать подходящие кандидаты для проверки. Синтетические тесты не очень интересны, а в реальных приложениях я своим кравлером не смог найти последовательностей длиннее, они всегда прерывались ветвлениями всякими.
Но для прикладных задач нам достаточно найти просто какой-нибудь вариант который будет быстрее исходного. Будет ли он наилучшим вообще или просто «более хорошим» — нас любой вариант устроит. И вот тут генетика дает как раз невероятное преимущество перед перебором.
Процесс у меня обычно сходился за ~200 поколений по 100 особей, то есть всего за 20к исполнений кода. А всего же возможных его вариантов (если рассматривать пример из начала статьи — последовательность из 11 инструкций, пара десятков возможных разных инструкций) — миллиарды раз надо запустить будет сгенерированные фрагменты.
Поэтому например во всех статьях о супероптимизации рассматриваются обычно последовательности не более 3-4 инструкций длиной. Генетика же, как показано тут, отлично справляется с 10+ инструкциями. Можно бы даже еще длиннее, но тут уже сложно искать подходящие кандидаты для проверки. Синтетические тесты не очень интересны, а в реальных приложениях я своим кравлером не смог найти последовательностей длиннее, они всегда прерывались ветвлениями всякими.
Ну никто не спорит, что это задача полного перебора. У меня конечно же тоже был не полный перебор, а алгоритм был простой (насколько я помню): если после раскрытия скобок слагаемых/множителей стало меньше, то раскрываем скобки. В противном случае оставляем все как есть. Генетические алгоритмы и другие методы, основанные на случайном переборе, конечно же, тоже можно использовать. Но добиться оптимальных по скорости и качеству результатов, скорее всего, можно с помощью комбинирования «умных» методов и случайности.
Вы абсолютно правы
собственно что такое эволюция по дарвину?
с помощью комбинирования «умных» методов и случайности
собственно что такое эволюция по дарвину?
В эволюции на мой взгляд как раз таки умных методов (влияния извне) не было в самом начале (если учитывать, что бога нет), просто эволюция проходила очень продолжительное время, за которое была создана жизнь в текущем ее состоянии (и не без большого количества косяков, кстати).
Однако в течении эволюции «умные» методы (естественный отбор) сформировались самостоятельно.
Однако в течении эволюции «умные» методы (естественный отбор) сформировались самостоятельно.
Оценка сложности приведения этой булевой функции к дистрибутивной минимальной форме равна сложности полного перебора — это доказываться ещё на первом курсе института.
С удовольствием парочку интересных идей украл бы.
Вы абсолютно правы
Не смог прочитать формулы в статье. Везде вместо них картинки Codecogs Equation Quota Exceeded. В принципе, и без них статья весьма интересная, но лучше исправьте, пожалуйста
Исправил. Печально что на хабре нет встроенной возможности вставлять формулы, конвертировать их в картинки вручную как-то очень мучительно, а посторонние сервисы вот не выдерживают хабраэффекта.
Вы не представляете, как долго о введении этой фичи просят разработчиков habrahabr
(x + 1)x всегда четное и неотрицательное
Только если х целое. При |х|<1 это не выполняется. Пример: -0.5
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как компьютер сам свой код улучшал, или программируем процесс программирования