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

Question

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

Я говорю о хардкоре . Как Tiny Teensy ELF , История Мел ; практически все в демосцене и т. д.

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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

Самой большой проблемой для моих товарищей были очень загадочные сообщения, отображаемые, потому что мне нужно было все место для кода. Это было похоже на «FFVD RM?», Что означало «FindForm Virus Detected, Remove?»

Я был вполне доволен этим фрагментом кода. Оптимизация была размером программы, а не скоростью. Две совершенно разные оптимизации в сборке.

Answer 4

Мой фаворит - обратный квадратный корень с плавающей запятой через целочисленные операции. Это крутой небольшой взлом того, как значения с плавающей запятой хранятся и могут выполняться быстрее (даже выполнение 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;
}

Answer 5

Несколько лет назад я написал игровой движок на основе плитки для Apple IIgs на языке ассемблера 65816. Это была довольно медленная машина, и программирование «на металле» является виртуальным требованием для получения приемлемой производительности.

Чтобы быстро обновить графический экран, необходимо отобразить стек на экран, чтобы использовать некоторые специальные инструкции, которые позволяют обновлять 4 пикселя экрана всего за 5 машинных циклов. В этом нет ничего особенно фантастического, и он подробно описан в IIgs Tech Note # 70 . Основным моментом было то, как я должен был организовать код, чтобы сделать его достаточно гибким, чтобы стать библиотекой общего назначения при сохранении максимальной скорости.

Я разложил графический экран на строки сканирования и создал 246-байтовый буфер кода для вставки специализированных 65816 кодов операций. Требуются 246 байтов, потому что каждая строка сканирования графического экрана имеет ширину 80 слов, и для дополнительного плавного перемещения требуется 1 дополнительное слово на каждом конце. Команда Push Effective Address (PEA) занимает 3 байта, поэтому 3 * (80 + 1 + 1) = 246 байтов.

Графический экран отображается при переходе по адресу в буфере 246-байтового кода, который соответствует правому краю экрана, и добавлению в инструкцию BRanch Always (BRA) кода в коде слова, следующего сразу за крайним левым. слово. Инструкция BRA принимает 8-битное смещение со знаком в качестве аргумента, поэтому она едва имеет диапазон для выхода из буфера кода.

Даже это не так уж сложно, но здесь идет настоящая оптимизация ядра. Мой графический движок фактически поддерживал два независимых фоновых слоя и анимированные листы, используя разные 3-байтовые последовательности кода в зависимости от режима:

1. Фон 1 использует инструкцию Push Effective Address (PEA)
2. Фон 2 использует инструкцию Индексации с косвенной загрузкой (LDA ($ 00), y), за которой следует push (PHA)
3. Анимированные листы используют индексированную страницу загрузки с прямой индексацией (LDA $ 00, x), за которой следует push (PHA)

Критическим ограничением является то, что оба регистра 65816 (X и Y) используются для ссылки на данные и не могут быть изменены. Кроме того, регистр прямой страницы (D) устанавливается на основе происхождения второго фона и не может быть изменен; регистр банка данных установлен в банк данных, который содержит данные пикселей для второго фона и не может быть изменен; указатель стека (S) отображается на графическом экране, поэтому нет возможности перейти к подпрограмме и вернуться.

Учитывая эти ограничения, мне нужно было быстро обрабатывать случаи, когда слово, которое собирается поместить в стек, смешано, то есть половина приходит из фона 1, а половина из фона 2. Мое решение было обменять память на скорость. Поскольку все обычных регистров использовались, у меня был только регистр счетчика программ (ПК) для работы. Мое решение было следующим:

1. Определить фрагмент кода для смешивания в том же банке программ 64K, что и буфер кода
2. Создать копию этого кода для каждого из 82 слов
3. Существует соответствие 1-1, поэтому возвращаемый фрагмент кода может быть жестко закодированным адресом
4. Готово! У нас есть жестко запрограммированная подпрограмма, которая не влияет на регистры процессора.

Вот фактические фрагменты кода

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 МБ / с.

Answer 6

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

Краткая справка: Тройки нуклеотидов ДНК (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? )

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

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

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

Answer 7

В " Zen of Assembly Language " Майкла Абраша были некоторые изящные вещи, хотя я признаю, что не припоминаю подробности на моей голове.

На самом деле, кажется, что все, что написал Абраш, содержало некоторые изумительные оптимизации.

Answer 8

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

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

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

Answer 9

Компилятор Stalin Scheme в этом аспекте довольно сумасшедший.

Answer 10

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

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