Байт Сито - Byte Sieve

В Байт Сито это компьютерная реализация Сито Эратосфена опубликовано Байт как язык программирования тест производительности. Впервые он появился в выпуске журнала за сентябрь 1981 года и иногда пересматривался. Хотя он был предназначен для сравнения производительности разных языков на одних и тех же компьютерах, он быстро стал широко используемым тестом для машин.

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

История

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

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

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

После шести месяцев усилий по переносу его на столько платформ, к которым у него был доступ, первые результаты были представлены в сентябрьском выпуске 1981 года. Байт в статье "A High Level Language Benchmark".[1] Гилбрит сразу заметил, что:

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

В статье представлены справочные реализации на десяти языках, в том числе более популярные варианты, например БАЗОВЫЙ, C, Паскаль, КОБОЛ, и FORTRAN, и некоторые менее известные примеры, такие как Четвертый, ZSPL, Ratfor, PL / 1 и PLMX.[3]

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

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

UCSD Паскаль предоставили еще один интересный набор результатов, поскольку одну и ту же программу можно запускать на нескольких машинах. Запуск на выделенном Итака Интерсистемс Машина Паскаль-100, а Паскаль MicroEngine На базе компьютера он работал за 54 секунды, в то время как на Z80 он был 239, а на Apple II - 516 секунд.[7]

Распространять

Гилбрит, на этот раз вместе со своим братом Гэри, пересмотрел код в январском выпуске 1983 г. Байт. Эта версия удалила большинство менее популярных языков, оставив Pascal, C, FORTRAN IV и COBOL, но добавив Ада и Модула-2. Благодаря тому, что читатели предоставили дополнительные образцы, количество машин, операционных систем и языков, сравниваемых в итоговых таблицах, было значительно расширено.[8]

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

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

Байт еще раз пересмотрел сито позже, в августе 1983 года, как часть серии статей о языке Си для всего журнала. В этом случае использование было больше в соответствии с первоначальным намерением, с использованием одного исходный код и запустить его на одной машине, чтобы сравнить производительность компиляторов C на CP / M-86 Операционная система,[13] на CP / M-80,[14] и для IBM PC.[15]

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

Сегодня

Новые версии кода продолжают появляться для новых языков,[17] и GitHub доступно множество версий.[18] Его часто используют как пример функциональное программирование несмотря на то, что общая версия фактически не использует алгоритм сита.[19]

Выполнение

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

Это оригинальная BASIC-версия кода, представленная в 1981 году.[20][а] Диалект не указан, но ряд деталей означает, что он не работает под Microsoft BASIC, среди них использование длинных имен переменных, таких как РАЗМЕР, а массивы начинаются с индекса 0, а не 1.

REM Программа простых чисел Решета Эратосфена на ОСНОВНОМ 1 РАЗМЕР = 81902 РАЗМЕР ФЛАГОВ (8191) 3 ПЕЧАТЬ «Только 1 итерация» 5 СЧЕТ = 06 ДЛЯ I = 0 ДЛЯ РАЗМЕРА 7 ФЛАГОВ (I) = 18 СЛЕДУЮЩИЙ I9 ДЛЯ I = 0 ДЛЯ РАЗМЕРА10 IF ФЛАГОВ (I) = 0 ТОГДА 1811 PRIME = I + I + 312 K = I + PRIME13 ЕСЛИ K> РАЗМЕР ТОГДА 1714 ФЛАГОВ (K) = 015 K = K + PRIME16 GOTO 1317 COUNT = COUNT + 118 NEXT I19 PRINT COUNT, "PRIMES "

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

#define true 1#define false 0#define size 8190#define sizepl 8191char флаги[sizepl];главный() {    int я, основной, k, считать, iter;     printf(«10 итераций п");    за (iter = 1;iter <= 10;iter ++) {        считать=0 ;         за (я = 0;я <= размер;я++)            флаги [я] = истинный;         за (я = 0;я <= размер;я ++) {             если (флаги[я]) {                основной = я + я + 3;                 k = я + основной;                 пока (k <= размер) {                     флаги[k] = ложный;                     k += основной;                 }                считать = считать + 1;            }        }    }    printf(" п% d простых чисел ", считать);}

Рекомендации

Примечания

  1. ^ Обратите внимание, что номер строки для первой строки отсутствует в исходном исходном списке.

Цитаты

  1. ^ а б c d Гилбрит 1981, п. 180.
  2. ^ Кнут 1969.
  3. ^ Гилбрит 1981 С. 181-190.
  4. ^ а б Гилбрит 1981, с. 194.
  5. ^ Гилбрит 1981, стр.195.
  6. ^ Гилбрит 1981, стр.193.
  7. ^ а б Гилбрит 1981, с. 196.
  8. ^ а б Гилбрет и Гилбрит 1983, п. 294.
  9. ^ Гилбрет и Гилбрит 1983, п. 292.
  10. ^ "HS / FORTH (реклама)" (PDF). PC Tech Journal. Октябрь 1985. с. 132.
  11. ^ «FORTH сейчас очень .быстрый (реклама)» (PDF). FORTH Размеры. Ноябрь – декабрь 1985 г. с. 2.
  12. ^ Ciarcia, Стив (1979). Подвал Ciarcia's Circuit, Том 6. п. 133. ISBN  9780070109681.
  13. ^ а б Хьюстон, Джерри; Бродрик, Джим; Кент, Лес (август 1983 г.). «Сравнение компиляторов C для CP / M-86». Байт. С. 82–106.
  14. ^ Керн, Кристофер (август 1983). "Пять компиляторов Си для CP / M-80". Байт. С. 110–130.
  15. ^ Франер, Ральф (август 1983 г.). «Девять компиляторов C для IBM PC». Байт. С. 134–168.
  16. ^ Хиннант, Дэвид (август 1984). «Тестирование систем UNIX: производительность UNIX на микрокомпьютерах и миникомпьютерах». Байт. С. 132–135, 400–409.
  17. ^ "Быстрое решето Эратосфена". 27 июля 2015 г.
  18. ^ "Сито Эратосфена". Получено 2 мая 2019.
  19. ^ О'Нил, Мелисса (январь 2009 г.). «Подлинное сито Эратосфена». Журнал функционального программирования. 19 (1): 95–106. Дои:10.1017 / S0956796808007004.
  20. ^ Гилбрит 1981, п. 188.
  21. ^ Гилбрит 1981, п. 186.

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