Байтовое сито

Byte Sieve — это компьютерная реализация «Решета Эратосфена», опубликованная компанией Byte в качестве языка программирования теста производительности . Впервые он появился в сентябрьском номере журнала 1981 года и время от времени к нему пересматривался. Несмотря на то, что он предназначен для сравнения производительности разных языков на одних и тех же компьютерах, он быстро стал широко используемым машинным тестом.

Sieve был одним из наиболее популярных тестов в эпоху домашних компьютеров , вторым был тест Creative Computing Benchmark 1983 года и тесты Rugg/Feldman , которые в ту эпоху чаще всего встречались в Великобритании. Позже в 1995 году компания Byte опубликовала более подробный NBench , заменив его.

История

Происхождение

Джим Гилбрит из Центра военно-морских океанских систем в течение некоторого времени рассматривал идею написания небольшой программы сравнительного анализа языков, желая, чтобы она была переносимой на разные языки, достаточно маленькой, чтобы программный код умещался на одной печатной странице, и не полагаться на определенные функции, такие как аппаратное умножение или деление. Решение было вдохновлено встречей с Чаком Форсбергом на собрании USENIX в январе 1980 года в Боулдере, штат Колорадо , где Форсберг упомянул реализацию сита, написанную Дональдом Кнутом .

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

После шести месяцев усилий по портированию его на максимальное количество платформ, к которым у него был доступ, первые результаты были представлены в сентябрьском выпуске журнала Byte за 1981 год в статье, озаглавленной «Эталон языка высокого уровня». Гилбрет поспешил отметить следующее:

Я должен подчеркнуть, что этот тест — не единственный критерий, по которому можно судить о языке или компиляторе.

В статье представлены эталонные реализации на десяти языках, включая более популярные варианты, такие как BASIC , C , Pascal , COBOL и FORTRAN , а также некоторые менее известные примеры, такие как Forth , ZSPL , Ratfor , PL/1 и PLMX .

Примеры запуска были предоставлены для различных машин, в основном на базе Zilog Z80 или MOS 6502 . Первоначально лучшее время составило 16,5 секунды, которое показал Ratfor на машине Z80 с частотой 4 МГц, но Гэри Килдалл лично предоставил версию в Digital Research . прототипе версии PL/1 от который пробежал за 14 секунд и установил отметку для этой первой коллекции. Самым медленным был Microsoft COBOL на той же машине, который занял целых 5115 секунд (почти полтора часа), что даже больше, чем у интерпретируемых языков, таких как BASIC. Примечательной особенностью этого первого запуска было то, что C, Pascal и PL/1 показали примерно одинаковую производительность, что легко обогнало различные интерпретаторы.

Второй набор тестов был проведен на более мощных машинах: Motorola 68000 ассемблер показал самое быстрое время — 1,12 секунды, немного обойдя C на PDP-11/70 и почти вдвое быстрее, чем ассемблер 8086. У большинства PDP-11 и HP-3000 время было намного медленнее, порядка 10–50 секунд. Тесты на этих машинах с использованием только языков высокого уровня проводил NBS Pascal на PDP-11 за 2,6 секунды.

UCSD Pascal предоставил еще один интересный набор результатов, поскольку одну и ту же программу можно запускать на нескольких машинах. Работая на выделенной машине Ithaca InterSystems Pascal-100, компьютере на базе Pascal MicroEngine , он работал за 54 секунды, в то время как на Z80 это было 239, а на Apple II — 516.

Распространение

Гилбрит, на этот раз вместе со своим братом Гэри, вновь обратился к коду в январском выпуске журнала Byte 1983 года . В этой версии удалено большинство менее популярных языков, оставлены Паскаль, C, FORTRAN IV и COBOL, но добавлены Ada и Modula-2 . Благодаря тому, что читатели предоставили дополнительные образцы, количество машин, операционных систем и языков, сравниваемых в итоговых таблицах, было значительно расширено.

Сборка Motorola 68000 (68k) осталась самой быстрой, почти в три раза превосходя по скорости Intel 8086 , работающую на той же тактовой частоте 8 МГц. При использовании языков высокого уровня эти два процессора были ближе по производительности: 8086 в целом был вдвое медленнее, чем 68k, а часто и намного ближе. Также было включено более широкое разнообразие мини-компьютеров и мэйнфреймов , время которых обычно превосходило 68k, за исключением самых быстрых машин, таких как IBM 3033 , и высокопроизводительных моделей VAX . Старые машины, такие как Data General Nova , PDP-11 и HP-1000, были далеко не такими быстрыми, как 68k.

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

Позже, в августе 1983 года, Байт еще раз вернулся к решету в рамках целой журнальной серии статей о языке C. В этом случае использование больше соответствовало первоначальному замыслу: использование одного исходного кода и запуск его на одной машине для сравнения производительности компиляторов C в операционной системе CP/M-86 . на КП/М-80 , и для IBM PC .

Несмотря на беспокойство Гилбрита в исходной статье, к этому времени код стал почти универсальным для тестирования, и в одной из статей отмечалось, что «Решето Эратосфена является обязательным тестом». Он был включен в пакет Byte UNIX Benchmark Suite, представленный в августе 1984 года.

Сегодня

Продолжают появляться новые версии кода для новых языков. например, Rosetta Code и GitHub имеют множество доступных версий. Его часто используют как пример функционального программирования, несмотря на то, что в распространенной версии алгоритм сита фактически не используется.

Выполнение

Предоставленная реализация рассчитывала только нечетные простые числа, поэтому массив элементов 8191 фактически представлял простые числа меньше 16385. Как показано в таблице на боковой панели, 0-й элемент представлял собой 3, 1-й элемент — 5, 2-й элемент — 7 и так далее.

Это оригинальная версия кода на языке BASIC, представленная в 1981 году. Диалект не указан, но ряд деталей означает, что он не работает в ранних версиях Microsoft BASIC (4.x и более ранних версиях), в том числе использование длинных имен переменных, таких как SIZE и FLAGS. Отсутствие номеров строк может указывать на разновидность миникомпьютера, считывающего исходный код из текстового файла, но также это могло быть и ошибкой печати.

REM Eratosthenes Sieve Prime Number Program in BASIC 
1 SIZE = 8190
2 DIM FLAGS(8191)
3 PRINT "Only 1 iteration"
5 COUNT = 0
6 FOR I = 0 TO SIZE
7 FLAGS (I) = 1
8 NEXT I
9 FOR I = 0 TO SIZE
10 IF FLAGS (I) = 0 THEN 18
11 PRIME = I+I + 3
12 K = I + PRIME
13 IF K > SIZE THEN 17
14 FLAGS (K) = 0
15 K = K + PRIME
16 GOTO 13
17 COUNT = COUNT + 1
18 NEXT I
19 PRINT COUNT," PRIMES"

И в C, с некоторыми корректировками пробелов по сравнению с оригиналом:

#define true 1
#define false 0
#define size 8190
#define sizepl 8191
char flags[sizepl];
main() {
    int i, prime, k, count, iter; 
    printf("10 iterations\n");
    for (iter = 1; iter <= 10; iter ++) {
        count=0 ; 
        for (i = 0; i <= size; i++)
            flags[i] = true; 
        for (i = 0; i <= size; i++) { 
            if (flags[i]) {
                prime = i + i + 3; 
                k = i + prime; 
                while (k <= size) { 
                    flags[k] = false; 
                    k += prime; 
                }
                count = count + 1;
            }
        }
    }
    printf("\n%d primes", count);
}

Ссылки

Библиография

• Гилбрит, Джим (сентябрь 1981 г.). «Эталон языка высокого уровня» . Байт . стр. 180–198.
• Гилбрит, Джим; Гилбрит, Гэри (январь 1983 г.). «Возвращение к Эратосфену: еще раз через решето» . Байт . стр. 283–325.
• Кнут, Дональд (1969). Искусство компьютерного программирования. Том 2: Получисловые алгоритмы . Аддисон-Уэсли. ISBN  978-0-201-89684-8 .