Ухудшение скорости? Увы, если не предпринимать особых мер то это приведет к быстрому заполнению популяции очень длинными особями. Они будут считать то же самое, но медленнее, при этом за счет своей длины будут очень сильно тормозить сам генетический процесс. Средняя длина особи без ограничений начинает расти очень быстро, для исходной особи в 10 инструкций через сотню поколений средняя длина особи в популяции может превысить 50 инструкций. И все становится до невозможности медленным.
Например чтобы запустить оптимизацию джавовского примера из статьи надо написать что-то типа:
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 версии).
Правда, как я уже писал, глазами результатов ее работы увы не видно. Слишком маленькие оптимизации. Поэтому я и забросил это дело, слегка в нем разочаровавшись.
Это если мы ищем самую-самую оптимальную (тавтология, но как мне кажется более понятное определение) последовательность инструкций. Этим занимаются так называемые Супероптимизаторы, о которых выше в комментах уже писали.
Но для прикладных задач нам достаточно найти просто какой-нибудь вариант который будет быстрее исходного. Будет ли он наилучшим вообще или просто «более хорошим» — нас любой вариант устроит. И вот тут генетика дает как раз невероятное преимущество перед перебором.
Процесс у меня обычно сходился за ~200 поколений по 100 особей, то есть всего за 20к исполнений кода. А всего же возможных его вариантов (если рассматривать пример из начала статьи — последовательность из 11 инструкций, пара десятков возможных разных инструкций) — миллиарды раз надо запустить будет сгенерированные фрагменты.
Поэтому например во всех статьях о супероптимизации рассматриваются обычно последовательности не более 3-4 инструкций длиной. Генетика же, как показано тут, отлично справляется с 10+ инструкциями. Можно бы даже еще длиннее, но тут уже сложно искать подходящие кандидаты для проверки. Синтетические тесты не очень интересны, а в реальных приложениях я своим кравлером не смог найти последовательностей длиннее, они всегда прерывались ветвлениями всякими.
x86 архитектуру я толком не смог осилить. Реализовал только несколько простейших инструкций и застрял — слишком сложные как инструкции, так и общее состояние процессора (куча регистров, стек, память — все это надо отслеживать для поддержания корректности особей).
Ну в каком-то смысле это похоже на мою идею. Но с функциями общего вида есть свои проблемы, например проблема останова — невозможно определить, она вообще завершится когда-нибудь или просто зависла, непонятно как это верифицировать, в случае с ветвлениями — нет гарантий что мимо всех тестов не просочилась какая-нибудь хитрая ветка условий, нарушающих спецификацию.
У меня в этом смысле более простой вариант, так как локальная оптимизация не имеет дела с ветвлениями и условиями, только линейный код.
Не совсем. Они там ищут совсем-совсем оптимальные последовательности, как я понял. Генетика же, как и любой вероятностный метод, строго говоря не гарантирует оптимальность решения. Можно найти что-то что будет лучше оригинала, но будет ли оно наилучшим вообще — совершенно не факт.
Спасибо за идею. Про LLVM я уже думал, но изначально решил взяться за то что мне более знакомо (диплом же, сроки горят как всегда, хотя начал я его писать практически с начала магистратуры), в итоге слегка обломался.
Хотя конечно любой лишний уровень абстракции и промежуточных представлений кода вносит свои проблемы и непредсказуемость поведения.
Может они пошли вслед за Торвальдсом, а охрана, видевшая что они только что разговаривали, решила что они вместе и не стали останавливать? Но вообще тоже интересно.
Да? Ну я не видел. Весь второй день проторчал рядом с экраном, висевшим возле лектория (если речь о нем), но по нему крутился только ролик самого старкона + реклама спонсоров.
Вот, точно, было же. А то я испытал мощное чувство дежавю когда открыл сегодняшний пост и на всякий случай проверил дату — не занесло ли меня на пару лет назад, так как явно на хабре я про это уже когда-то читал…
Меня давно интересует вопрос: а что мешает сделать надежную сигнализацию автомобильную? Надежную в смысле защищенную от перехвата всякими там код-грабберами? ИТ дало алгоритмы шифрования, обмена ключами, всяких там цифровых подписей. При этом случай с авто еще и достаточно простой — там есть как бы «защищенный» канал связи между машиной и брелком для установки общих ключей, так как владелец имеет физический доступ к обеим компонентам системы у себя в гараже.
В чем проблема-то? Почему сигнализации до сих пор вскрывают и машины угоняют неинвазивными, то есть не требующими физического взлома (например слышал о способе просверлить дверь и подключиться к проходящей где-то там шине данных), методами?
Не знаю как конкретно в Hearthstone, но вообще во всех современных моба-играх балансер старается подбирать равных по скиллу оппонентов, поэтому у всех игроков доля побед колеблется в районе 50 +-5%. Так что в целом да, можно наверное считать что в каждом отдельном матче шансы у противников примерно равны.
Для защиты от некоторых видов атак, указанных в статье (определения позиций нажатых кнопок с помощью камеры или акселерометра) давно уже придумана элементарная защита — рандомизированные пин-пады, у которых цифры каждый раз располагаются по кнопкам в случайном порядке.
Тут есть нюанс. Вот допустим добыл я нефть, продал ее и купил себе мерседес. И вокруг этого мерседеса сразу закипело движение, появилась работа у всяких там автослесарей, автомойщиков, страховщиков, производителей автоаксессуаров, гаишников, дорожных служб (это бюджетники, но я же в бюджет налоги с покупки заплатил тоже получается). И вот вроде уже накрутился большой такой ком произведенных товаров и услуг, в котором цена этого мерседеса уже составляет лишь маленькую часть. Вот только если бы я его не купил, то и всех остальных товаров и услуг бы не было, так как кому нужна автомойка если ни у кого нет машины. И если внезапно мерседес старый совсем уже сломается, а на новый денег у меня не будет, ибо нефть подешевела, то и все остальные звенья увянут так же быстро, как и появились.
Первый пункт — про необходимость финансовой мотивации сотрудников — очень важен. Сам с этим сейчас сталкиваюсь. Делаю игру, начинал в одиночку, сейчас уже собрал команду. Игра опенсорс, все новые версии выкладываем в открытый доступ. Как следствие — народ играет, многим нравится, многие хотят помочь и пишут, предлагая свои услуги (как правило арт и сюжет-сценарий, а вот программистов не было ни разу) забесплатно.
В начале разработки, когда я был один, я соглашался, так как деваться было некуда, сам я не мог сделать все своими руками в нужном объеме. В итоге:
1) Быстро пропадает мотивация. Вау-фактор «я делаю крутую игру» угасает уже через неделю. И доброволец остается один на один с необходимостью тратить часы своей жизни на работу за просто так. Внезапно все оказывается гораздо сложнее, чем казалось изначально. Энтузиазм умирает, человек сливается, сделав в лучшем случае 1-2 задания. При этом результат его труда приходится выкинуть, так как в случае с артом, например, игра, где весь арт нарисован разными людьми и с разным качеством и стилем, выглядит ужасно. В итоге результата нет, потрачено время на общение и организацию.
2) Иногда опухает ЧСВ, любая попытка критики (даже если человек сделал вообще не то, что его просили) ведет к скандалу. В духе «Ну ты там полгода назад просил зеленый треугольник нарисовать, вот, на тебе желтый шарик. Что, не нравится? Да иди нафиг, мог бы спасибо сказать, что я хоть что-то сделал. Тьфу, ему тут рисуют за так, а он еще и выделывается».
3) Банальный срыв сроков — у человека есть куча других дел, и очевидно что неоплачиваемая работа быстро будет задвинута в самый дальний угол списка приоритетов.
4) Низкий профессионализм. В большинстве случаев профессионал знает цену своему времени и не работает за так. Так что бесплатно помочь соглашаются новички в своем деле, со всеми вытекающими.
Короче, оно того не стоит. И теперь я либо отклоняю подобные предложения, либо (если отказать нет возможности, например срочно что-то нужно, денег на настоящего фрилансера нет, а тут кто-то предлагает свои услуги за так) настаиваю на пусть небольшой, но оплате. Даже символическая плата, в разы ниже рыночной цены, уже переводит отношения из разряда «работаю забесплатно — делаю что и как хочу» в «кто платит — тот и заказывает музыку». К тому же совсем неуверенные в себе, которые скорее всего быстро бы слились, начинают исчезать уже на этом этапе, так как все становится слишком серьезно, и позволяют не тратить на себя время.
Такой подход позволяет, с одной стороны, вести разработку используя только мои личные небольшие деньги и пожертования игроков, а с другой — подбирать-таки правильных людей, не тратя время на совсем уж бесперспективных.
По моему опыту как раз собеседование на первую работу больше всего похоже именно на экзамен. Именно там вас обязательно спросят про отличие абстрактного класса от интерфейса, о том какова трудоемкость быстрой сортировки и как примерно эта сортировка работает. Потому что у студента и спрашивать-то больше нечего, раз работа у него первая — то опыта скорее всего нет и его даже не спросишь о том, какую интересную задачу он решал последней. Только и остается что спрашивать стандартную программу по языку и алгоритмам, благо он их еще должен хорошо помнить, даже то, что в жизни редко приходится применять.
А вот по мере набора опыта собеседования от экзамена плавно уходят в беседу (причем двухстороннюю) на тему прошлых проектов, каких-то интересных особенностей и предпочтений.
bitbucket.org/e_smirnov/gp_optimizer
Например чтобы запустить оптимизацию джавовского примера из статьи надо написать что-то типа:
После выполнения данного кода rz будет содержать наилучший из найденных и прошедших верификацию результатов.
Есть бекенды для JVM, x86 (там очень маленький набор поддержанных инструкций) и пиксельных шейдеров. Примеры использования можно увидеть в main.java
Для работы нужен верификатор Z3 майкрософтовский
Для оптимизации шейдеров — консольная тулза NvShaderPerf которая считает их производительность.
Помимо такого вида запуска я там даже запилил целый сервер, который с помощью библиотечки распределенных вычислений JPPF может принимать и раскидывать задачи оптимизации по вычисляющим серверам. И клиент, который парсит заданные jar-файлы, ищет в них подходящие последовательности инструкций и шлет их на сервер, ждет ответа а потом если пришел ответ с найденными оптимизациями — патчит джарники оптимизированными инструкциями. Можно эту инфраструктуру всю попробовать поднять (JPPF там правда старый какой-то типа 2 версии).
Правда, как я уже писал, глазами результатов ее работы увы не видно. Слишком маленькие оптимизации. Поэтому я и забросил это дело, слегка в нем разочаровавшись.
Но для прикладных задач нам достаточно найти просто какой-нибудь вариант который будет быстрее исходного. Будет ли он наилучшим вообще или просто «более хорошим» — нас любой вариант устроит. И вот тут генетика дает как раз невероятное преимущество перед перебором.
Процесс у меня обычно сходился за ~200 поколений по 100 особей, то есть всего за 20к исполнений кода. А всего же возможных его вариантов (если рассматривать пример из начала статьи — последовательность из 11 инструкций, пара десятков возможных разных инструкций) — миллиарды раз надо запустить будет сгенерированные фрагменты.
Поэтому например во всех статьях о супероптимизации рассматриваются обычно последовательности не более 3-4 инструкций длиной. Генетика же, как показано тут, отлично справляется с 10+ инструкциями. Можно бы даже еще длиннее, но тут уже сложно искать подходящие кандидаты для проверки. Синтетические тесты не очень интересны, а в реальных приложениях я своим кравлером не смог найти последовательностей длиннее, они всегда прерывались ветвлениями всякими.
У меня в этом смысле более простой вариант, так как локальная оптимизация не имеет дела с ветвлениями и условиями, только линейный код.
Хотя конечно любой лишний уровень абстракции и промежуточных представлений кода вносит свои проблемы и непредсказуемость поведения.
В чем проблема-то? Почему сигнализации до сих пор вскрывают и машины угоняют неинвазивными, то есть не требующими физического взлома (например слышал о способе просверлить дверь и подключиться к проходящей где-то там шине данных), методами?
В начале разработки, когда я был один, я соглашался, так как деваться было некуда, сам я не мог сделать все своими руками в нужном объеме. В итоге:
1) Быстро пропадает мотивация. Вау-фактор «я делаю крутую игру» угасает уже через неделю. И доброволец остается один на один с необходимостью тратить часы своей жизни на работу за просто так. Внезапно все оказывается гораздо сложнее, чем казалось изначально. Энтузиазм умирает, человек сливается, сделав в лучшем случае 1-2 задания. При этом результат его труда приходится выкинуть, так как в случае с артом, например, игра, где весь арт нарисован разными людьми и с разным качеством и стилем, выглядит ужасно. В итоге результата нет, потрачено время на общение и организацию.
2) Иногда опухает ЧСВ, любая попытка критики (даже если человек сделал вообще не то, что его просили) ведет к скандалу. В духе «Ну ты там полгода назад просил зеленый треугольник нарисовать, вот, на тебе желтый шарик. Что, не нравится? Да иди нафиг, мог бы спасибо сказать, что я хоть что-то сделал. Тьфу, ему тут рисуют за так, а он еще и выделывается».
3) Банальный срыв сроков — у человека есть куча других дел, и очевидно что неоплачиваемая работа быстро будет задвинута в самый дальний угол списка приоритетов.
4) Низкий профессионализм. В большинстве случаев профессионал знает цену своему времени и не работает за так. Так что бесплатно помочь соглашаются новички в своем деле, со всеми вытекающими.
Короче, оно того не стоит. И теперь я либо отклоняю подобные предложения, либо (если отказать нет возможности, например срочно что-то нужно, денег на настоящего фрилансера нет, а тут кто-то предлагает свои услуги за так) настаиваю на пусть небольшой, но оплате. Даже символическая плата, в разы ниже рыночной цены, уже переводит отношения из разряда «работаю забесплатно — делаю что и как хочу» в «кто платит — тот и заказывает музыку». К тому же совсем неуверенные в себе, которые скорее всего быстро бы слились, начинают исчезать уже на этом этапе, так как все становится слишком серьезно, и позволяют не тратить на себя время.
Такой подход позволяет, с одной стороны, вести разработку используя только мои личные небольшие деньги и пожертования игроков, а с другой — подбирать-таки правильных людей, не тратя время на совсем уж бесперспективных.
А вот по мере набора опыта собеседования от экзамена плавно уходят в беседу (причем двухстороннюю) на тему прошлых проектов, каких-то интересных особенностей и предпочтений.