[МУЗЫКА] [МУЗЫКА] Работа с массивами в УВК «Самсон». Здесь я начну с некоторой грустной истории. Когда «Самсон» заработал, как вы помните, я помню это до часа, в два часа дня пятого ноября 1987 года, когда приехали всякие члены политбюро, как советские, так и болгарские. Вот в этот момент «Самсон» заработал, потом мы еще несколько лет его «доводили», как это обычно бывает, и гоняли всякие тесты. И в это время для сравнения мы использовали американскую машину IBM PC/AT на 286-м процессоре, частота 16 мегагерц, которая была в это время лучшей из машин такого класса на Западе. А у нас «Самсон» получился с частотой 3,25 мегагерц. Вообще-то инженеры обещали 4 мегагерца, но инженеры такие люди, как всегда, не «дожали». То есть «Самсон» работал на частоте 3,25 мегагерца. В пять раз медленней, чем IBM PC/AT, частота. Но на всех тестах, как ни удивительно, мы выигрывали как минимум в три раза по времени. То есть, если одну и ту же программу «прогнать» на IBM PC/AT и у нас, то наше календарное время будет в три раза меньше, а при том, что частота в пять раз хуже, то есть наш архитектурный выигрыш был 15, что не трудно посчитать. И это не фокус: именно за счет того, что «Самсон» — HLL-машина, ориентирован на языки высокого уровня, то, что аппаратно поддержаны основные действия, это давало нам — я вот только в предыдущем модуле рассказывал, как мы там оптимизировали команды, — все это давало свои результаты: наш архитектурный выигрыш 15, мы этим очень гордились. И вот как-то раз мой любимый ученик Петр Лавров написал тест — маленькую телефонную станцию. И на этом тесте мы вдруг проиграли IBM PC/AT. Я рвал и метал. Как это так может быть? Мы всегда выигрывали, а тут проиграли. Начали изучать это дело. И оказалось это довольно трудно. Тест был не очень большой: три страницы на Алголе 68. И долго не могли понять, в чем дело, но потом, естественно, разобрались. Там была таблица абонентов, это же тест «маленькая телефонная станция», и причем эта таблица занимала max int, то есть 32 на 767 элементов. Когда абонент А хочет позвонить абоненту Б, мы должны найти этого абонента Б в этой таблице, и там еще два параметра, то есть каждый элемент таблицы занимал шесть байтов — три целых числа: номер абонента и его характеристики, которые нужны были для соединения. Так вот, оказалось, что все время тратится на «if «номер» равен tab(i)», на вырезки i-го элемента из таблицы. Как вы помните, мы уже разбирали работу с массивами, как уже говорилось, вырезка a[i] эквивалентна о исполнению формулы C0 + i*d. Так вот, в этой таблице было d равно шести. И поэтому C0 + i*6 и умножение занимало львиную долю времени, в то время умножители были очень медленные. Я решил, что я разделю таблицу на две части: сделаю один массив только из номеров, а второй массив — из характеристик. И тогда окажется, что умножать надо на два или четыре. Я сообразил, что на два и на четыре умножать вовсе не надо, это можно сложить само собой, или сдвину влево на один или на четыре, на два разряда. И, кроме того, я вспомнил, что есть строки, и у них вообще шаг равен один, на единичку вообще глупо умножать. Поэтому я подумал, что надо бы сделать дополнение к команде ИНД, команде ИНД1, ИНДБ, ИНДЦ и ИНДП, то есть в команды, в которых просто во время трансляции известно, как обычно транслятор подсказывает машине, что шаг равен один, два или четыре: для байтовых — один, для целых — два, для плавающих — четыре. И тогда уже машина, получив такую команду, может понимать, что умножать-то вовсе не надо, а можно сделать как-то намного быстрее. Сказано — сделано. Добавили к команде ИНД команды ИНДБ, ИНДЦ, ИНДП и ускорили. Но тогда уж — аппетит приходит во время еды — решили: почему не сэкономить еще и на C0? C0+? Это, конечно, не такое медленное действие, как умножение, но все-таки действие, и его тоже хотелось бы как-нибудь «съесть» во время трансляции. Но не тут-то было! Дело в том, что шаг известен во время трансляции, то есть это статическая величина, и транслятор может породить подходящие команды и для ИНДБ, и для ИНДЦ, и для ИНДП. А нижняя граница — это динамический объект, который вычисляется во время счета. И мы не можем всегда гарантировать, что он будет всегда ноль или еще что-нибудь такое. Так вот, договорились, что нижняя граница определяется во время генератора массива, то есть подпрограммы, которая во время счета отводит память под массив. Если массив имеет границу ноль или единичка, а в случае единички мы легко сводим к нижней границе ноль, введя просто один маленький фиктивный элемент, один элемент, который просто фиктивный. Тогда мы массив объявляем «хорошим» и будем с ним работать одним способом. А если нижняя граница — любая другая, не ноль или один, то мы его обзываем «плохим» и будем работать другим способом. Так вот, для «хороших» массивов генератор выдает адрес начала сегмента массива: не реальный адрес начала, а смещенный на 17. То есть 16 + 1. 16, чтобы избавиться от прибавления 16, а 1, чтобы указать, что это «хороший» массив. Микрокоманда в первом же такте вырезки проверяет, массив «хороший» или «плохой» по четности, адреса, который идет машине, и передает управление либо на «хорошую» ветку, либо на «плохую». Если массив «хороший», то вырезка a[i] занимает всего три такта. А общая вырезка общего вида занимает 33 такта. И поэтому это действительно реально сильная оптимизация, и сейчас я думаю, что команда с «хорошим» массивом используется во много раз чаще, чем обычная индексация. Просто так жизнь устроена, что в основном люди работают с байтами, с целыми или с плавающими числами и очень редко работают с какими-то странными массивами, например, как таблица-массив из структур по шесть байтов. Это дало нам существенный выигрыш. Петя Лавров говорил, что я жулик, подгоняю тест. А я ему объясняю, что я не жулик, я занимаюсь оптимизацией. Есть тест, любую программу можно написать так или эдак, можно написать программу оптимально, можно написать неоптимально. Если мы сообщаем авторам программ, что массивы из целых, и плавающих, и литерных исполняются лучше и быстрее, чем массивы из других, то авторы могут этим приемом воспользоваться. Не только я это делаю, любой автор может это сделать. В результате, когда мы внесли все эти оптимизации, тест, который написал Петя Лавров, «маленькая телефонная станция», стал давать такой же выигрыш в три раза, как и все остальные тесты, которые мы писали до того. Я считаю, что это показательный пример. Возникла ситуация, мы ее исследовали, посмотрели, как ее можно улучшить, придумали. Я много раз студентам говорил, что когда я проектирую машины, я чувствую себя Господом Богом: что хочу, то и делаю. И в данном случае это просто еще один из многочисленных примеров, как мы столкнулись с неоптимальной ситуацией, подумали, прооптимизировали и добились того, что и на этом примере «Самсон» стал выигрывать у американской IBM PC/AT в свои законные три раза, чем мы очень гордимся.
