Byte Sieve - Byte Sieve

The Byte Sieve je počítačová implementace Síto Eratosthenes publikováno Byte jako programovací jazyk výkonnostní měřítko. Poprvé se objevil ve vydání časopisu v září 1981 a byl příležitostně znovu navštíven. Ačkoli bylo zamýšleno porovnat výkon různých jazyků na stejných počítačích, rychle se stalo široce používaným měřítkem strojů.

Síto bylo jedním z nejoblíbenějších standardů v domácí počítač éry, další bytostí Benchmark Creative Computing z roku 1983 a Referenční hodnoty Rugg / Feldman, většinou viděný ve Velké Británii v této době. Byte později publikoval důkladnější NBench v roce 1995 jej nahradit.

Dějiny

Počátky

Jim Gilbreath z Naval Ocean System Center už nějakou dobu uvažoval o konceptu psaní malého srovnávacího programu jazyka a toužil po takovém, který by byl přenosný napříč jazyky, dostatečně malý, aby se vešel na stránku kódu, a nespoléhal se na konkrétní funkce, jako je hardwarové násobení nebo dělení. Řešení bylo inspirováno setkáním s Chuck Forsberg v lednu 1980 USENIX setkání v Boulder, CO, kde Forsberg zmínil implementaci síta napsaného Donald Knuth.[1][2]

Gilbreath cítil, že síto bude ideálním měřítkem, protože se vyhne nepřímým testům aritmetického výkonu, které se mezi systémy značně liší. Algoritmus většinou zdůrazňuje výkon vyhledávání pole a základní logické a větvící schopnosti. Nevyžaduje ani žádné pokročilé jazykové funkce jako rekurze nebo pokročilé typy sběru. Jedinou úpravou z Knuthovy původní verze bylo odstranit násobení dvěma a místo toho jej nahradit sčítáním. Stroje s hardwarovými multiplikátory by jinak běžely mnohem rychleji, takže by se skryl zbytek výkonu.[1]

Po šesti měsících úsilí o přenesení na tolik platforem, ke kterým měl přístup, byly první výsledky představeny v září 1981 vydání Byte v článku s názvem „High-Level Language Benchmark“.[1] Gilbreath rychle poukázal na to, že:

Zdůraznil bych, že toto měřítko není jediným kritériem, podle kterého se posuzuje jazyk nebo překladač.[1]

Článek poskytuje referenční implementace v deseti jazycích, včetně populárnějších výběrů jako ZÁKLADNÍ, C, Pascal, COBOL, a FORTRAN a některé méně známé příklady jako Forth, ZSPL, Ratfor, PL / 1 a PLMX.[3]

Ukázkové běhy byly většinou poskytovány pro různé stroje Zilog Z80 nebo MOS 6502 -na základě. Nejlepší čas byl zpočátku 16,5 sekundy, předal jej Ratfor na stroji Z80 4 MHz, ale Gary Kildall osobně poskytl verzi v Digitální výzkum prototypová verze PL / 1[4] který běžel za 14 sekund a nastavil značku pro tuto první sbírku. Nejpomalejší byl Microsoft COBOL na stejném stroji, který trval neuvěřitelných 5115 sekund (téměř jeden a půl hodiny), dokonce déle než interpretované jazyky jako BASIC.[5] Pozoruhodnou vlastností tohoto prvního běhu bylo, že C, Pascal a PL / 1 dosáhli zhruba podobného výkonu, který snadno porazil různé tlumočníky.[4]

Druhá sada testů byla provedena na výkonnějších strojích s Motorola 68000 montážní jazyk zapínání nejrychlejších časů za 1,12 sekundy, mírné překonání C na a PDP-11/70 a téměř dvakrát rychlejší než 8086 assembler. Většina PDP-11 a HP-3000 časy byly mnohem pomalejší, řádově 10 až 50 sekund.[6] Testy na těchto strojích využívajících pouze jazyky vyšší úrovně byly vedeny NBS Pascal na PDP-11 za 2,6 sekundy.[7]

UCSD Pascal poskytl další zajímavou sadu výsledků, protože stejný program lze spustit na více počítačích. Běží na vyhrazeném Mezisystémy Ithaca Stroj Pascal-100, a Pascal MicroEngine založený počítač, běžel za 54 sekund, zatímco u Z80 to bylo 239 a 516 u Apple II.[7]

Šíření

Gilbreath, tentokrát spolu se svým bratrem Garym, se vrátil ke kódu ve vydání z ledna 1983 Byte. Tato verze odstranila většinu méně populárních jazyků a při přidávání ponechala Pascal, C, FORTRAN IV a COBOL Ada a Modula-2. Díky čtenářům poskytujícím další vzorky se výrazně zvýšil počet počítačů, operačních systémů a jazyků ve výsledných tabulkách.[8]

Motorola 68000 (68k) sestava zůstala nejrychlejší, téměř třikrát vyšší než rychlost Intel 8086 běží na stejném 8 MHz taktu. Při použití jazyků na vysoké úrovni měli dva výkony blíže, přičemž 8086 byl obecně lepší než poloviční rychlost oproti 68k a často mnohem blíže.[9] Širší paleta minipočítače a sálové počítače byl také zahrnut, s časy, které 68k obecně porazily, s výjimkou velmi nejrychlejších strojů, jako je IBM 3033 a špičkové modely VAX. Starší stroje jako Data General Nova, PDP-11 a HP-1000 nebyly zdaleka tak rychlé jako 68k.[8]

Gilbreathův druhý článek se objevil, protože měřítko se stalo docela běžným způsobem srovnávání výkonu různých strojů, natož jazyků. I přes jeho původní varování, aby tak neučinil, se brzy začalo objevovat v reklamách časopisů jako způsob porovnání výkonu s konkurencí,[10][11] a jako obecné měřítko.[12]

Byte později v srpnu 1983 znovu navštívil síto jako součást celé časopisové řady článků o jazyce C. V tomto případě bylo použití více v souladu s původním záměrem, s použitím jediného zdrojový kód a jeho běh na jediném stroji k porovnání výkonu kompilátorů C na Windows CP / M-86 operační systém,[13] na CP / M-80,[14] a pro IBM PC.[15]

Navzdory Gilbreathovu znepokojení v původním článku se do této doby kód stal téměř univerzálním pro testování a jeden z článků poznamenal, že „Síto Eratosthenes je povinným měřítkem“.[13] Bylo zahrnuto do Byte UNIX Benchmark Suite představený v srpnu 1984.[16]

Dnes

Nové verze kódu se nadále objevují pro nové jazyky,[17] a GitHub má k dispozici mnoho verzí.[18] Často se používá jako příklad Funkcionální programování navzdory běžné verzi, která ve skutečnosti nepoužívá sítový algoritmus.[19]

Implementace

Poskytnutá implementace počítala pouze lichá prvočísla, takže pole prvků 8191 ve skutečnosti představovalo prvočísla menší než 16385. Jak je znázorněno v tabulce postranního panelu, 0. prvek představoval 3, 1. prvek 5, 2. prvek 7 atd.

Toto je původní ZÁKLADNÍ verze kódu představená v roce 1981.[20][A] Dialekt není zadán, ale řada podrobností znamená, že pod ním nelze běžet Microsoft BASIC, mezi nimi použití dlouhých názvů proměnných jako VELIKOSTa pole začínající na indexu 0 namísto 1.

REM Eratosthenes Sieve Prime Number Program v ZÁKLADNÍ 1 VELIKOST = 81902 DIM FLAGS (8191) 3 TISK "Pouze 1 iterace" 5 POČET = 06 PRO I = 0 VELIKOSTI 7 VLAJKŮ (I) = 18 DALŠÍ I9 PRO I = 0 VELIKOSTI 10 VLAKŮ (I) = 0 POTOM 1811 PRIME = I + I + 312 K = I + PRIME13 IF K> VELIKOST PAK 1714 VLAJKŮ (K) = 015 K = K + PRIME16 GOTO 1317 POČET = POČET + 118 DALŠÍ I19 POČET TISKU, "

A v C, s některými úpravami mezer oproti originálu:[21]

#define true 1#define false 0# definovat velikost 8190#define sizepl 8191char vlajky[sizepl];hlavní() {    int i, primární, k, počet, iter;     printf("10 iterací n");    pro (iter = 1;iter <= 10;iter ++) {        počet=0 ;         pro (i = 0;i <= velikost;i++)            vlajky [i] = skutečný;         pro (i = 0;i <= velikost;i ++) {             -li (vlajky[i]) {                primární = i + i + 3;                 k = i + primární;                 zatímco (k <= velikost) {                     vlajky[k] = Nepravdivé;                     k += primární;                 }                počet = počet + 1;            }        }    }    printf(" n% d prvočísel “, počet);}

Reference

Poznámky

  1. ^ Číslo původního řádku v původním zdrojovém seznamu chybí.

Citace

  1. ^ A b C d Gilbreath 1981, str. 180.
  2. ^ Knuth 1969.
  3. ^ Gilbreath 1981, str. 181-190.
  4. ^ A b Gilbreath 1981 194, str.
  5. ^ Gilbreath 1981, str. 195.
  6. ^ Gilbreath 1981, str. 193.
  7. ^ A b Gilbreath 1981, s. 196.
  8. ^ A b Gilbreath a Gilbreath 1983, str. 294.
  9. ^ Gilbreath a Gilbreath 1983, str. 292.
  10. ^ „HS / FORTH (reklama)“ (PDF). PC Tech Journal. Října 1985. str. 132.
  11. ^ „FORTH je nyní velmi rychlý (reklama)“ (PDF). FORTH Rozměry. Listopad – prosinec 1985. s. 2.
  12. ^ Ciarcia, Steve (1979). Ciarcia's Circuit Cellar, svazek 6. str. 133. ISBN  9780070109681.
  13. ^ A b Houston, Jerry; Brodrick, Jim; Kent, Les (srpen 1983). „Porovnání překladačů C pro CP / M-86“. Byte. str. 82–106.
  14. ^ Kern, Christopher (srpen 1983). "Pět C kompilátorů pro CP / M-80". Byte. 110–130.
  15. ^ Phraner, Ralph (srpen 1983). „Devět C kompilátorů pro IBM PC“. Byte. str. 134–168.
  16. ^ Hinnant, David (srpen 1984). „Benchmarking UNIX Systems: UNIX performance on microcomputers and minicomputers“. Byte. str. 132–135, 400–409.
  17. ^ „Swift Sieve of Eratosthenes“. 27. července 2015.
  18. ^ "Síto Eratosthenes". Citováno 2. května 2019.
  19. ^ O'Neill, Melissa (leden 2009). „Originální síto Eratosthenes“. Journal of Functional Programming. 19 (1): 95–106. doi:10.1017 / S0956796808007004.
  20. ^ Gilbreath 1981, str. 188.
  21. ^ Gilbreath 1981, str. 186.

Bibliografie