Я не говорю об алгоритмических материалах (например, используйте quicksort вместо bubblesort), и я не говорю о простых вещах, таких как разворачивание цикла.
Я говорю о хардкорных вещах. Как Tiny Teensy ELF, История Мела; практически все в демосцене и т.д.
Я однажды написал ручной поиск RC5 ключа, который обрабатывал по два ключа за раз, первый ключ использовал цельный конвейер, второй ключ использовал SSE-конвейеры, а два были чередованными на уровне команд. Затем это было связано с программой супервизора, которая запускала экземпляр кода на каждом ядре в системе. В целом код выполнялся примерно в 25 раз быстрее, чем наивная версия C.
В одном (здесь неназванном) движке видеоигр, с которым я работал, они перезаписали инструмент модели-экспорта (вещь, которая превращает Maya mesh во что-то, что игра загружает), так что вместо того, чтобы просто испускать данные, он фактически испускает точный поток микрокоманд, который необходим для рендеринга этой конкретной модели. Он использовал генетический алгоритм, чтобы найти тот, который будет работать в минимальном количестве циклов. То есть формат данных для данной модели был фактически оптимизированной подпрограммой для рендеринга только этой модели. Таким образом, рисование сетки на экране означало загрузку ее в память и разветвление на нее.
(Это было не для ПК, а для консоли, у которой векторный блок был отдельным и параллельным процессору.)
В первые дни DOS, когда мы использовали гибкие диски для всего транспорта данных, также были вирусы. Одним из распространенных способов заражения вирусов различными компьютерами было копирование загрузчика вирусов в загрузочный сектор вставленного флоппидиска. Когда пользователь вставил floppydisc на другой компьютер и перезагрузился, не забыв удалить дискету, вирус был запущен и заражен загрузочным загрузочным устройством жесткого диска, тем самым постоянно заражая хост-компьютер. Особый раздражающий вирус, которого я заразил, назывался "Форма", для борьбы с этим я написал пользовательский флоппи-загрузчик, который имел следующие функции:
Это было сделано в программном пространстве bootsector, около 440 байт:)
Самая большая проблема для моих товарищей - это самые загадочные сообщения, которые отображались, потому что мне нужно было все пространство для кода. Это было похоже на "FFVD RM?", Что означало "FindForm Virus Detected, Remove?"
Я был очень доволен этой частью кода. Оптимизация была размером программы, а не скоростью. Две совершенно разные оптимизации в сборке.
Моим любимым является обратный квадратный корень с плавающей запятой посредством целых операций. Это классный маленький взлом на том, как хранятся значения с плавающей запятой и могут выполняться быстрее (даже если результат 1/быстрее, чем функция квадратного корня со стандартным фондом) или дает более точные результаты, чем стандартные методы.
В 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;
}
Краткая информация: Тройки нуклеотидов ДНК (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?)
Эта оптимизация жесткого пространства!
ОБНОВЛЕНИЕ: Ссылки на дополнительную информацию:
Несколько лет назад я написал игровой движок для Apple IIgs на ассемблере 65816. Это была довольно медленная машина, и программирование "на металле" - это виртуальное требование уговорить приемлемую производительность.
Чтобы быстро обновить графический экран, нужно сопоставить стек с экраном, чтобы использовать некоторые специальные инструкции, которые позволяют обновлять 4 пикселя экрана всего за 5 машинных циклов. Это ничего особенно фантастического и подробно описано в Техническая заметка IIgs # 70. Ядро жесткого ядра состояло в том, как мне пришлось организовать код, чтобы он был достаточно гибким, чтобы быть универсальной библиотекой, сохраняя при этом максимальную скорость.
Я разложил графический экран в строки сканирования и создал буфер с 246 байтовым кодом для вставки специализированных кодов операций 65816. 246 байтов необходимы, потому что каждая строка сканирования графического экрана имеет ширину 80 слов, а на каждом конце требуется еще одно слово для плавной прокрутки. Команда Push Effective Address (PEA) занимает 3 байта, поэтому 3 * (80 + 1 + 1) = 246 байт.
Графический экран визуализируется путем перехода к адресу в буфере кода 246 байтов, который соответствует правому краю экрана и исправлению в команде BRanch Always (BRA) в код слова сразу после самого левого слово. Команда BRA принимает в качестве аргумента подписанное 8-битное смещение, поэтому он едва ли может выпрыгнуть из буфера кода.
Даже это не слишком сложно, но настоящая жесткая оптимизация приходит сюда. Мой графический движок фактически поддерживал два независимых фоновых слоя и анимированные плитки с использованием разных 3-байтовых кодовых последовательностей в зависимости от режима:
Критическое ограничение состоит в том, что оба регистра 65816 (X и Y) используются для ссылки на данные и не могут быть изменены. Кроме того, прямой регистр страницы (D) задается на основе происхождения второго фона и не может быть изменен; регистр банка данных установлен в банк данных, который содержит данные пикселя для второго фона и не может быть изменен; указатель стека (S) отображается на графический экран, поэтому нет возможности перейти к подпрограмме и вернуться.
Учитывая эти ограничения, мне нужно было быстро обрабатывать случаи, когда слово, которое вот-вот будет вложено в стек, будет смешанным, то есть половина приходит из фона 1 и половины из фона 2. Моим решением было торговать памятью для скорости, Поскольку все обычные регистры были в использовании, у меня только был счетчик программ (ПК) для работы. Мое решение было следующее:
Вот фрагменты кода
code_buff: PEA $0000 ; rightmost word (16-bits = 4 pixels)
PEA $0000 ; background 1
PEA $0000 ; background 1
PEA $0000 ; background 1
LDA (72),y ; background 2
PHA
LDA (70),y ; background 2
PHA
JMP word_68 ; mix the data
word_68_rtn: PEA $0000 ; more background 1
...
PEA $0000
BRA *+40 ; patched exit code
...
word_68: LDA (68),y ; load data for background 2
AND #$00FF ; mask
ORA #$AB00 ; blend with data from background 1
PHA
JMP word_68_rtn ; jump back
word_66: LDA (66),y
...
Конечным результатом был почти оптимальный блиттер, который имеет минимальные накладные расходы и кричит более 15 кадров в секунду при 320x200 на процессоре 2,5 МГц с шиной памяти 1 МБ/с.
Michael Abrash " Zen of Assembly Language" имел некоторые отличные вещи, хотя я признаю, что не помню специфику с вершины моего голова.
На самом деле кажется, что все, что написал Абраш, было в нем отличным оптимистичным материалом.
Компилятор "Сталинская схема" в этом аспекте довольно сумасшедший.
Я когда-то видел инструкцию switch с большим количеством пустых case s, комментарий во главе коммутатора сказал что-то по строкам:
Добавленные операторы case, которые никогда не попадают, потому что компилятор только переключает коммутатор в таблицу перехода, если есть более N случаев
Я забыл, что такое N. Это было в исходном коде для Windows, который был просочился в 2004 году.
Я пошел на ссылки архитектуры Intel (или AMD), чтобы увидеть, какие инструкции есть. movsx - перемещение с расширением знака является удивительным для перемещения небольших знаковых значений в большие пространства, например, в одной инструкции.
Аналогично, если вы знаете, что используете только 16-битные значения, но вы можете получить доступ ко всем EAX, EBX, ECX, EDX и т.д., тогда у вас есть 8 очень быстрых мест для значений - просто поверните регистры на 16 бит до доступ к другим значениям.
EFF DES cracker, в котором использовалось специальное оборудование для создания ключей-кандидатов (аппаратное обеспечение, которое они сделали, могло бы доказать, что ключ не является решение, но не могло доказать, что ключ был решением), которые затем были протестированы с использованием более обычного кода.
Пакер FSG 2.0, сделанный польской командой, специально предназначенный для упаковки исполняемых файлов, выполненных с сборкой. Если упаковочная сборка недостаточно внушительна (что должно быть почти как можно меньше), то загрузчик, к которому он поставляется, составляет 158 байт и полностью функциональен. Если вы попытаетесь упаковать любую сборку, выполненную с расширением .exe, с чем-то вроде UPX, она выведет на вас исключение NotCompressableException;)