Какую самую жесткую оптимизацию вы видели?

Я однажды записал грубой силе поиск ключа RC5, который обработал два ключа за один раз, первый ключ использовал целочисленный конвейер, второй ключ использовал конвейеры SSE, и эти два были чередованы на уровне инструкции. Это было тогда вместе с программой супервизора, которая выполнила экземпляр кода каждого ядра в системе. Всего, код работал приблизительно в 25 раз быстрее, чем наивная версия C.

Компилятор Схемы Stalin является довольно сумасшедшим в том аспекте.

В одном (здесь без имени) механизм видеоигры, с которым я работал, они переписали инструмент образцовый экспорта (вещь, которая поворачивается язык майя сетка во что-то игровые загрузки) так, чтобы вместо того, чтобы просто испустить данные, это на самом деле испустило бы точный поток микрокоманд, которые будут необходимы представить ту конкретную модель. Это использовало генетический алгоритм для нахождения того, который будет работать в минимальном количестве циклов. То есть формат данных для данной модели был на самом деле отлично оптимизированной подпрограммой для рендеринга просто той модели. Так, рисование сетки на экран означало загружать его в память и переходить в него.

(Это не было для ПК, а для консоли, которая имела векторную единицу, отдельную и параллельную ЦП.)

В первые годы DOS, когда мы использовали гибкие диски для всего транспорта данных, также были вирусы. Один распространенный способ для вирусов заразить различные компьютеры состоял в том, чтобы скопировать вирусный загрузчик в загрузочный сектор вставленного floppydisc. Когда пользователь вставил floppydisc в другой компьютер и перезагрузил, не помня удалять дискету, вирус был выполнен и заразил загрузочный сектор жесткого диска, таким образом постоянно заразив ПК хоста. Особенно раздражающий вирус, которым я был заражен, назвали "Формой", для борьбы с этим я записал пользовательский гибкий загрузочный сектор, который имел следующие функции:

• Проверяют загрузочный сектор жесткого диска хоста и удостоверяются, что он не был заражен.
• Проверяют гибкий загрузочный сектор и удостоверяются, что он не был заражен.
• Код для удаления вируса из жесткого диска, если это было заражено.
• Код для дублирования антивирусного загрузочного сектора к другой дискете, если специальная клавиша была нажата.
• Код для начальной загрузки жесткого диска, если все было хорошо, и никакие заражения не были найдены.

Это было сделано в пространстве программы загрузочного сектора, приблизительно 440 байтов:)

самой большой проблемой для моих помощников были очень загадочные сообщения, отображенные, потому что мне было нужно все пространство для кода. Это было похоже "на RM FFVD?", который означал "Обнаруженный Вирус FindForm, Удалите?"

я был довольно доволен той частью кода. Оптимизация была размером программы, не скоростью. Две очень отличающейся оптимизации в блоке.

Моим фаворитом является обратный квадратный корень с плавающей точкой через целочисленные операции. Это - прохладный небольшой взлом о том, как значения с плавающей точкой хранятся и могут выполниться быстрее (даже выполнение 1/результата быстрее, чем стандартная запасом функция квадратного корня), или приведите к более точным результатам, чем стандартные методы.

В c/c ++ код: (полученный из Википедии)

float InvSqrt (float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);   // Now this is what you call a real magic number
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

Я однажды видел switch оператор с большим количеством пустых case с, в комментарии во главе переключателя было сказано что-то вроде:

Добавленные операторы выбора, которые никогда не поражаются, потому что компилятор только превращает переключатель в таблицу переходов, если существуют больше, чем случаи N

, я забываю, каков N был. Это было в исходном коде для Windows, который был , протек в 2004 .

Я перешел к Intel (или AMD) ссылки архитектуры для наблюдения что инструкции, там. movsx - перемещаются с расширением знака, является потрясающим для перемещения небольших значений со знаком в большие пробелы, например, в одной инструкции.

Аналогично, если Вы знаете, Вы только используете 16-разрядные значения, но можно получить доступ ко всему EAX, EBX, ECX, EDX, и т.д. - тогда у Вас есть 8 очень быстрых мест для значений - просто поворачивают регистры на 16 битов для доступа к другим значениям.

Michael Abrash" Дзэн Ассемблера " имела некоторый изящный материал, хотя я признаю, что не вспоминаю специфических особенностей первое, что пришло на ум.

На самом деле это кажется на все, что Abrash записал, имел некоторый изящный материал оптимизации в нем.

взломщик DES EFF , который использовал сделанные на заказ аппаратные средства для генерации ключей-кандидатов (аппаратные средства они сделали, мог доказать, что ключ не является решением, но не мог доказать, что ключ был решением), которые были тогда протестированы с более стандартным кодом.

Упаковщик FSG 2.0 сделан польской командой, конкретно сделанный для упаковки исполняемых файлов сделан с блоком. Если упаковка блока не является достаточно впечатляющей (что, как предполагается, является почти максимально низким), загрузчик, с которым это идет, 158 байтов и полностью функциональный. При попытке упаковать сделанный .exe какого-либо блока чем-то как UPX, то он бросит NotCompressableException в Вас ;)

Очень биологическая оптимизация

Краткая справка: Триплеты нуклеотидов ДНК (A, C, G и T) кодируют аминокислоты, которые соединены в белки, которые и создают

Обычно для каждого отдельного белка требуется отдельная последовательность триплетов ДНК (его «ген») для кодирования своих аминокислот - так, например, 3 белка длиной 30, 40 и 50 потребуют 90 + 120 + 150 = 360 нуклеотидов всего. Однако в вирусах пространство ограничено - поэтому некоторые вирусы перекрывают последовательности ДНК для разных генов , используя тот факт, что существует 6 возможных «рамок считывания», которые можно использовать для трансляции ДНК в белок. (а именно, начиная с позиции, которая делится на 3; с позиции, которая делит 3 на остаток 1; или из позиции, которая делит 3 на остаток 2; и то же самое снова, но читать последовательность в обратном порядке.)

Для сравнения: попробуйте написать программу на языке ассемблера x86, в которой 300-байтовая функция doFoo () начинается со смещения 0x1000 ... и еще 200-байтовая функция doBar () начинается со смещения 0x1001! (Я предлагаю название для этого конкурса: Вы умнее, чем гепатит B? )

Это жесткая оптимизация пространства!

ОБНОВЛЕНИЕ: Ссылки на дополнительную информацию:

• Фреймы чтения в Википедии предполагают, что гепатит В и вирус "желтого карлика ячменя" (вирус растений) перекрывают рамки считывания.
• Информация о геноме гепатита В в Википедии . Похоже, что разные субъединицы рамки считывания производят разные варианты поверхностного белка.
• Или вы можете погуглить для «перекрывающихся рамок считывания»
• Кажется, это может случиться даже с млекопитающими ! Обширно перекрывающиеся рамки считывания во втором гене млекопитающих - это научная статья Мэрилин Козак 2001 года, в которой говорится о «втором» гене у крысы с «обширными перекрывающимися рамками считывания». (Это довольно удивительно, поскольку структура генома млекопитающих дает достаточно места для отдельных генов для отдельных белков.) Я не читал ничего сверх абстрактного.