Crash Bandicoot, или как разработчики упаковывали целые игры в 2MB RAM

Перевод
Вот вам анекдот из конца 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. Удачи.

Это - шедевр. Энди и Дейв, нереально крутые мужики, которые подарили нам ярких и харизматичных персонажей.
Спасибо вам ребята.

помню играли в клубах игровых)

На спеке 48 килобайт было и многое вмещалось,ща сраный браузер гигами память жрет и всех устраивает,программисты кончились похоже,остались говнокодеры

Не понял не фига, но игра была супер, за это спасибо.

Да, упаковщик с методом научного тыка, такие уже, наверное, не делают.

Последние строки воспоминаний натолкнули на "свежую" мысль о написании собственного компилятора, хорошо хоть до этого дело не дошло.
А так - годно. Как современный прогер, начавший свой путь в средине девяностых, прекрасно представляю себе уровень сложности описанных достижений в эпоху отсутствия нормального интернета и всезнающего stackoverflow. Это подвиг.

Сейчас время такое, что если ты не программишь "матрёшку", то твой продукт к моменту выпуска уже безнадёжно устареет.
Матрёшку - имею в виду цепочку из готовых фреймворков, каждый из которых добавляет свою избыточность потребления ресурсов к предыдущим. Так и берут готовые реализации движков и алгоритмов и лепят из них новые поделки в угоду рынка.
Докупить памяти часто дешевле, чем оплатить затраты тысяч и миллионов человекочасов на выпуск оптимизированной версии.
И поддержка готовых продуктов, написанных с нуля на низкоуровневых языках, практически невозможна в современных реалиях. Сложность продуктов растёт и к моменту начала разработки новой версии у тебя в команде уже может не быть того гениального разработчика, который использовал нестандартные подходы и идеи для оптимизации, и в этом коде без него уже не разберётся никто.
Такие дела.

Это сообщение отредактировал ICELedyanoj - 10.12.2017 - 09:25

я и сейчас не гнушаюсь кодить микроконтроллеры, стирая всё "лишнее" из них для добычи лишнего килобайта места ))))
как-нибудь собирусь и запилю постик о своем рукожопстве.... наверное

Я все понимаю конечно,но это снежный ком,который может расти бесконечно

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

Читал и плакал.
Скорость процессоров и объем памяти современных ПК совершенно равратили нас (разработчиков). По опыту своему и моих коллег могу утверждать, что проблемы памяти нас начинают интересовать только тогда, когда мы захерачиваем кривой алгоритм, который выделяет ее в бесконечном цикле. Если же ты переживаешь, когда отладчик начинает хлестать из всех щелей утечками, ты уже перфекционист.

О Crash Bandicoot! Моя любимая бродилка!!!! Ностальгия! Хочу соньку и эту игрушку, мечта прям!

Просто оправдание говнокода через потреблятство.

Я понимаю в играх, а брабузеры? Их что сложно оптимизировать? Или, блять, калькулятор весом от 20 до 40 мегабайт ( windows 3.11 для рабочих групп весил 32 мегабайта после установки)? Сайты написанные через жопу?



Отправлено с мобильного клиента YAPik+

Это сообщение отредактировал ShamanIEA - 10.12.2017 - 09:56

Хе! Ностальжи... Тяжелое детство, килобайтные игрушки и поговорки, которые теперь ставят в ступор новые поколения программистов, типа "Дай бог памяти"...
Буду старым дедом, буду рассказывать внучарам программистские сказки:
"Давным-давно, когда компьютеры были большими, а люди, по сравнению с ними -маленькими....."

Практика показывает, что успешными становятся компании, которые вкладываются в маркетинг, а не в разработку. Куда выгоднее продать дешевый кривой софт миллиону пользователей, чем продвинутый, но дорогой - тысяче.
Не все юзеры способны оценить качество софта, не каждый обманутый попросит moneyback, вот на этой марже и живут.
Вот менеджмент и стоит перед непростым выбором между баблом и совестью. Бабло чаще побеждает.

Это сообщение отредактировал ICELedyanoj - 10.12.2017 - 10:03

но я с автором бухать не сяду

Львиная доля вины в потреблении ресурсов браузерами лежит на сайтах, а их клепают все от мала до велика. Студенты клепают "Сайт за один день" на шаблонах и в путь. Калькулятор содержит в себе десяток готовых фреймворков, из которых использует 1% функционала.
Не всё так плохо. У нас достаточно продвинутый софт с размером инсталлятора 20 мегабайт, и я за последние полгода уменьшил его до 14.
А вот с памятью беда. Борюсь с наследием того периода, когда задачи пользователей были куда скромнее, и софт был написан так, что он уже не справляется с новыми задачами. Достаточно успешно борюсь. Но днями и ночами.

Это сообщение отредактировал ICELedyanoj - 10.12.2017 - 10:04

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

Это сообщение отредактировал Hiten - 10.12.2017 - 10:04

Вот умели же раньше оптимизировать игры , а вот что сейчас мешает я хз

Всё это так же как с веб вёрсткой.
Раньше, при диалапе и раннем адсл-е, мы за каждый килобайт странички, жопу рвали.
А сейчас, при нынешних скоростях порой просто хуярят джипеги без сжатия на весь экран и похуй.

Ни один снежный ком не может расти бесконечно

Сонька наверняка уже вышла замуж и у ней куча детей. А вот игруху можно купить на развалах.

Помню время когда весь Дюк был на 12 дискетах. Помню как вёз их до дому завёрнутыми в фольгу :))