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