Вот вам анекдот из конца 90-ых. Я (Dave Baggett) был одним из двух программистов (вместе с Andy Gavin), разрабатывающих Crash Bandicoot для PlayStation 1.
Оперативная память была главной проблемой даже в те времена. У PS1 было всего 2MB RAM, и нам приходилось совершать безумные вещи, чтобы уместить в них игру. У нас были уровни, содержащие более 10MB чистых данных, и эти 10 мегабайт должны были постранично загружаться и выгружаться в память динамически, без каких-либо видимых задержек для игрока, при фреймрейте в 30 кадров в секунду.
В основном это работало за счёт того, что Andy написал потрясную систему подкачки, которая должна была подгружать и выгружать страницы в память размером 64K, по мере того как Crash проходил уровень. Эта система была настоящим произведением искусства, задействовавшая весь диапазон доступных инструментов, начиная от высокоуровневного менеджмента памятью, заканчивая прямой работой с памятью и программированием в опкодах. Andy также пришлось контроллировать расположение байтов на CD-ROM, чтобы даже при скорости 300KB/сек PS1 могла успеть загрузить данные для всех деталей уровня к тому времени как Crash добирался до него.
Я же написал упаковщик, который брал ресурсы игры — звуки, арт, код на lisp для управления существами, и т.д. и упаковывал их в страницы по 64К для системы подкачки, написанной Andy. (Между прочим, задача упаковки в страницы фиксированного размера набора произвольных размеров данных — NP-полная, и, почти не поддающаяся решению за полиномиальное, т.е. сколь либо приемлемое время. Задача о ранце.).
Некоторые из уровней едва помещались, и мой упаковщик использовал целый набор алгоритмов (first-fit, best-fit, и т.д.), чтобы пробовать получить наилучшый вариант упаковки, включая стохастический поиск, похожий на процесс градиентного спуска, используемый в алгоритме имитации отжига. По существу, у меня была целая куча разных стратегий упаковки, и я пробовал их все и использовал наилучший получившийся результат.
Проблема использования случайного направленного поиска заключалась в том, что ты никогда не мог быть уверен, что сможешь ещё раз получить точно такой же результат. Некоторые уровни Crash Bandicoot умещались в максимально допустимое количество страниц (21, если не ошибаюсь) только лишь из-за того, что упаковщику повезло и он нашёл этот вариант. Так же, это означало, что как только ты получил упакованный уровень, ты мог поменять код для какой-нибудь черепашки и уже никогда не получить упаковку, помещающуюся в 21 страницу. Были случаи, когда дизайнер хотел что-нибудь поменять и это раздувало количество страниц, и нам приходилось менять что-нибудь в других, почти случайных, местах, до тех пор, пока упаковщик снова не найдёт рабочий вариант. Попробуй объяснить это раздражительным дизайнерам в 3 часа утра :)
Самым лучшим эпизодом этой ретроспективы и самым худшим периодом времени тогда была упаковка кода ядра на С и ассемблере. У нас было буквально пару дней чтобы выпусть «gold master» версию — наш последний шанс успеть к сезону праздников, до того, как мы потеряем ещё один год. И мы сидели, переставляя C код в семантически одинаковые, но синтаксически разные конструкции, чтобы заставить компилятор выдать код, который был на 200, 125, 50, а потом и 8 байт меньше. Переставляли, например: «for (i=0; i < x; i++)» — а давайте попробуем переписать это в while-цикл и используем для итерации переменную, которая уже использовалась где-то ранее? Это всё делалось уже после того как мы перепробовали стандартные трюки, такие как помещение данных в два последних бита указателя (и это работало только благодаря тому, что адреса R3000 были выровнены по 4 байта).
В конечном счёте, Crash уместился в память PS1, и даже осталось свободных 4 байта! Да, 4 байта из 2097152. Удачи.
Автор: evnuh
