воскресенье, 29 июля 2012 г.

Speccy - Три истории

В то время пока разбирался с сапером на ZX, то произошло/заметил три особенные вещи с точки зрения программирования, которые описываю здесь, сразу в одном посте. Будут интересны прежде всего программистам.

Архивация и её тестирование

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

Архиватор, который архивирует более-менее сносно, было написать несложно. Даже на ассемблере, так как монстры RAR'ы не были распространены, а о Хаффманах никто не знал.

Архиватор для уважающих себя программистов был необходим, так как загрузка программ с ленты в 48K повторяющихся последовательностей занимала много времени, а в общем случае, ограничение памяти в 48К приводило к тому, что архивация позволяла в программу впихнуть намного больше всего вкусного.

Мой архиватор был прост до безобразия. В архивируемом блоке искался байт, который встречался как можно реже. Далее этот байт объявлялся маркером. Архивируемый массив байт преобразовался в другой массив, в котором все повторяющиеся последовательности байт преобразовались тройки байт (маркер, что повторяется и сколько). Например так (пусть маркер равен A0):

10 10 10 10 10 → A0 05 10

Если встречалась повторяющаяся последовательность в 4 или более байт, то она заменялась на тройку байт. А если последовательность была более 256 байт, то каждые 256 байт архивировались в 3.

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

Во время тестирования я брал различные последовательности байтов (блоки кода, данные, заставки, …), и, если преобразование разархивировать(заархивировать(A)) = A выполнялось успешно, то это означало, что архиватор работал.

Все было хорошо и замечательно — архиватор успешно использовался во множестве программ, в том числе и сам Сапер им архивировался. Но то, что с архиватором что-то не так, я обнаружил только где-то в 2009-м году (15 лет спустя!), когда просматривал код заархивированного Сапера. Как оказывается, из-за ошибки, допущенной в архиваторе, вышеописанное и любое преобразование архивировалось немного по-другому:

10 10 10 10 10 → 10 A0 04 10

То есть, из-за ошибки вида ±1 архиватор терял 1 байт архивации на каждое преобразование. В принципе, условия ТЗ он выполнял (архивировал и разархивировал корректно), но при этом под капотом вел себя не совсем так, как задумано.

В более современном программировании подобные ошибки могут возникнуть во время любой сериализации-десериализации. Любое преобразование в поток для передачи данных (с чем мы сталкиваемся регулярно) череповато подобными проблемами, а в тестах сопровождаемых проектов я далеко не всегда вижу проверку того, что происходит под капотом (только проверку pack/unpack например).

Первый опыт YAGNI

Так как каждый уважающий себя спектрумист-программист должен был написать свою собственную библиотеку, то и меня не обошла стороной эта участь. Библиотека получилась приличная, где-то 5k кода, делающая много всего.

На Speccy особенность в том, что большое количество базовых процедур недоступно или неудобно. Банально: вывести символ на экран или нарисовать линию — накладно с помощью ПЗУ, так как оно тянуло за собой кучу побочных эффектов (типа изменения атрибутов), работало медленно и только со стандартными шрифтами. Например очистка экрана своей процедурой с использованием стека работала в 4 раза быстрее аналогичной операции ПЗУ, что-то похожее творилось с рисованием линий и точек. Поэтому самому приходилось решать большинство базовых задач.

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

Где-то через пару лет разработки (уже после релиза финального Сапера) я обнаружил с большим удивлением, что две из процедур никогда не использовались. Это были процедуры умножения и деления чисел. То есть получилось так, что за два года использования библиотеки мне ни разу не понадобилось использовать умножение и деление! Не сказал бы что я вообще никогда не делил и умножал, но на ассемблере Speccy большое количество умножений и делений (когда один из множителей или делитель известны) выполняется набором команд. Скажем, чтобы умножить на 4 достаточно выполнить сдвиг по битам 2 раза.

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

Доверие к авторитетам

Когда-то, когда мы ещё только начинали преодолевать барьер ассемблера на ZX (переход от программирования на Бейсике к программированию на асме) мне попала книга от издательства «Инфорком» с названием «Прикладная графика». Там разбирались способы организации и программирования различных графических примитивов и структур, затрагивая спрайтовую, векторную и блочную графику. Книга казалось толстой и серьезной. Литературы было в то время мало (это сейчас каждый может спросить у гугла), и контакты с другими людьми отсутствовали. Поэтому книга воспринималась как Книга.

Программировал на спектруме тогда я с другом, и часто получалась так, что мы решали одинаковые задачи, а потом их сравнивали. Такое конкурирующее N-версионное программирование. И вот в один день стала перед мной одна из базовых задач — определение знакоместа экрана при известных его координатах (зная строку и столбец символа определить адрес его первого байта на экране). Это — одна из самых базовых процедур. Например чтобы напечатать символ, нужно сначала рассчитать первый его байт и потом от него изменять все байты знакоместа. Чтобы рассчитать то же самое для точки, то нужно сначала найти знакоместо, а потом искать адрес дальше. И т.д. Таким образом, эта процедура являлась одной из ключевых по быстродействию, так как использовать её приходилось постоянно.

И вот, я нахожу эту процедуру в Книге, и особо не думая, копирую её оттуда. 61 такт, 16 байт. Книжку же умные люди писали, вряд ли её можно улучшить. Сообщаю об этом другу и продолжаю чего-то там делать дальше. Друг же воспринял все по-другому: «Какая книжка?? У меня будет своя процедура!» И утопал её писать. На следующий день приходит с победоносным видом: «53 такта и 14 байт!». Чего стоит ускорение на 15% ключевого из элементов софта думаю объяснять не нужно.

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

Если заглянуть в Книгу, то следующими процедурами за вычислением знакоместа были печать символа и рисование точки. Эти процедуры мы писали уже сами. Результат не заставил себя ждать: рисование точки работало в ~ 2 раза быстрее Инфоркома и в ~2.5 быстрее процедуры ПЗУ.