Byte Sieve

Last updated

The Byte Sieve is a computer-based implementation of the Sieve of Eratosthenes published by Byte as a programming language performance benchmark. It first appeared in the September 1981 edition of the magazine and was revisited on occasion. Although intended to compare the performance of different languages on the same computers, it quickly became a widely used machine benchmark.

Contents

The Sieve was one of the more popular benchmarks of the home computer era, another being the Creative Computing Benchmark of 1983, and the Rugg/Feldman benchmarks, mostly seen in the UK in this era. Byte later published the more thorough NBench in 1995 to replace it.

History

Origins

Jim Gilbreath of the Naval Ocean System Center had been considering the concept of writing a small language benchmarking program for some time, desiring one that would be portable across languages, small enough that the program code would fit on a single printed page, and did not rely on specific features like hardware multiplication or division. The solution was inspired by a meeting with Chuck Forsberg at the January 1980 USENIX meeting in Boulder, CO, where Forsberg mentioned an implementation of the sieve written by Donald Knuth. [1] [2]

Gilbreath felt the sieve would be an ideal benchmark as it avoided indirect tests on arithmetic performance, which varied widely between systems. The algorithm mostly stresses array lookup performance and basic logic and branching capabilities. Nor does it require any advanced language features like recursion or advanced collection types. The only modification from Knuth’s original version was to remove a multiplication by two and replace it with an addition instead. With the original version, machines with hardware multipliers would otherwise run so much faster that the rest of the performance would be hidden. [1]

After six months of effort porting it to as many platforms as he had access to, the first results were introduced in the September 1981 edition of Byte in an article entitled "A High-Level Language Benchmark". [1] Gilbreath was quick to point out that:

I should emphasize that this benchmark is not the only criterion by which to judge a language or compiler. [1]

The article provided reference implementations in ten languages, including more popular selections like BASIC, C, Pascal, COBOL, and FORTRAN, and some less well-known examples like Forth, ZSPL, Ratfor, PL/1 and PLMX. [3]

Example runs were provided for a variety of machines, mostly Zilog Z80 or MOS 6502-based. The best time was initially 16.5 seconds, turned in by Ratfor on a 4 MHz Z80 machine, but Gary Kildall personally provided a version in Digital Research's prototype version of PL/1 [4] that ran in 14 seconds and set the mark for this first collection. The slowest was Microsoft COBOL on the same machine, which took a whopping 5115 seconds (almost one and a half hours), longer even than interpreted languages like BASIC. [5] A notable feature of this first run was that C, Pascal and PL/1 all turned in a roughly similar performance that easily beat the various interpreters. [4]

A second set of tests was carried out on more powerful machines, with Motorola 68000 assembly language turning in the fastest times at 1.12 seconds, slightly besting C on a PDP-11/70 and almost twice as fast as 8086 assembler. Most PDP-11 and HP-3000 times were much slower, on the order of 10 to 50 seconds. [6] Tests on these machines using only high-level languages was led by NBS Pascal on the PDP-11, at 2.6 seconds. [7]

UCSD Pascal provided another interesting set of results as the same program can be run on multiple machines. Running on the dedicated Ithaca InterSystems Pascal-100 machine, a Pascal MicroEngine based computer, it ran in 54 seconds, while on the Z80 it was 239, and 516 on the Apple II. [7]

Spread

Gilbreath, this time along with his brother Gary, revisited the code in the January 1983 edition of Byte. This version removed most of the less popular languages, leaving Pascal, C, FORTRAN IV, and COBOL, while adding Ada and Modula-2. Thanks to readers providing additional samples, the number of machines, operating systems and languages compared in the resulting tables was greatly expanded. [8]

Motorola 68000 (68k) assembly remained the fastest, almost three times the speed of the Intel 8086 running at the same 8 MHz clock. Using high-level languages the two were closer in performance, with the 8086 generally better than half the speed of the 68k and often much closer. [9] A wider variety of minicomputers and mainframes was also included, with times that the 68k generally beat except for the very fastest machines like the IBM 3033 and high-end models of the VAX. Older machines like the Data General Nova, PDP-11 and HP-1000 were nowhere near as fast as the 68k. [8]

Gilbreath's second article appeared as the benchmark was becoming quite common as a way to compare the performance of various machines, let alone languages. In spite of his original warning not to do so, it soon began appearing in magazine advertisements as a way to compare performance against the competition, [10] [11] and as a general benchmark. [12]

Byte once again revisited the sieve later in August 1983 as part of a whole-magazine series of articles on the C language. In this case the use was more in keeping with the original intent, using a single source code and running it on a single machine to compare the performance of C compilers on the CP/M-86 operating system, [13] on CP/M-80, [14] and for the IBM PC. [15]

In spite of Gilbreath's concern in the original article, by this time the code had become almost universal for testing, and one of the articles remarked that "The Sieve of Eratosthenes is a mandatory benchmark". [13] It was included in the Byte UNIX Benchmark Suite introduced in August 1984. [16]

Today

New versions of the code continue to appear for new languages, [17] eg Rosetta Code and GitHub has many versions available. [18] It is often used as an example of functional programming in spite of the common version not actually using the sieve algorithm. [19]

Implementation

The provided implementation calculated odd primes only, so the 8191 element array actually represented primes less than 16385. As shown in a sidebar table, the 0th element represented 3, 1st element 5, 2nd element 7, and so on.

This is the original BASIC version of the code presented in 1981. [20] [lower-alpha 1] The dialect is not specified, but a number of details mean it does not run under early versions of Microsoft BASIC (4.x and earlier), among these the use of long variable names like SIZE and FLAGS. The lack of line numbers may suggest a minicomputer variety that reads source from a text file, but may have also been a printing error.

REM Eratosthenes Sieve Prime Number Program in BASIC 1SIZE=81902DIMFLAGS(8191)3PRINT"Only 1 iteration"5COUNT=06FORI=0TOSIZE7FLAGS(I)=18NEXTI9FORI=0TOSIZE10IFFLAGS(I)=0THEN1811PRIME=I+I+312K=I+PRIME13IFK>SIZETHEN1714FLAGS(K)=015K=K+PRIME16GOTO1317COUNT=COUNT+118NEXTI19PRINTCOUNT," PRIMES"

And in C, with some whitespace adjustments from the original: [21] 

#define true 1#define false 0#define size 8190#define sizepl 8191charflags[sizepl];main(){inti,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);}

Notes

  1. ↑ Note that the line number for the first line is missing in the original source listing.

Related Research Articles

<span class="mw-page-title-main">Intel 8086</span> 16-bit microprocessor

The 8086 is a 16-bit microprocessor chip designed by Intel between early 1976 and June 8, 1978, when it was released. The Intel 8088, released July 1, 1979, is a slightly modified chip with an external 8-bit data bus, and is notable as the processor used in the original IBM PC design.

<span class="mw-page-title-main">Motorola 68000</span> Microprocessor

The Motorola 68000 is a 16/32-bit complex instruction set computer (CISC) microprocessor, introduced in 1979 by Motorola Semiconductor Products Sector.

<span class="mw-page-title-main">Motorola 6809</span> 8-bit microprocessor

The Motorola 6809 ("sixty-eight-oh-nine") is an 8-bit microprocessor with some 16-bit features. It was designed by Motorola's Terry Ritter and Joel Boney and introduced in 1978. Although source compatible with the earlier Motorola 6800, the 6809 offered significant improvements over it and 8-bit contemporaries like the MOS Technology 6502, including a hardware multiplication instruction, 16-bit arithmetic, system and user stack registers allowing re-entrant code, improved interrupts, position-independent code and an orthogonal instruction set architecture with a comprehensive set of addressing modes.

Turbo Pascal is a software development system that includes a compiler and an integrated development environment (IDE) for the programming language Pascal running on the operating systems CP/M, CP/M-86, and DOS. It was originally developed by Anders Hejlsberg at Borland, and was notable for its very fast compiling. Turbo Pascal, and the later but similar Turbo C, made Borland a leader in PC-based development tools.

<span class="mw-page-title-main">Sieve of Eratosthenes</span> Ancient algorithm for generating prime numbers

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

<span class="mw-page-title-main">Atari BASIC</span> Dialect of the BASIC programming language

Atari BASIC is an interpreter for the BASIC programming language that shipped with Atari 8-bit computers. Unlike most American BASICs of the home computer era, Atari BASIC is not a derivative of Microsoft BASIC and differs in significant ways. It includes keywords for Atari-specific features and lacks support for string arrays.

Interlisp is a programming environment built around a version of the programming language Lisp. Interlisp development began in 1966 at Bolt, Beranek and Newman in Cambridge, Massachusetts with Lisp implemented for the Digital Equipment Corporation (DEC) PDP-1 computer by Danny Bobrow and D. L. Murphy. In 1970, Alice K. Hartley implemented BBN LISP, which ran on PDP-10 machines running the operating system TENEX. In 1973, when Danny Bobrow, Warren Teitelman and Ronald Kaplan moved from BBN to the Xerox Palo Alto Research Center (PARC), it was renamed Interlisp. Interlisp became a popular Lisp development tool for artificial intelligence (AI) researchers at Stanford University and elsewhere in the community of the Defense Advanced Research Projects Agency (DARPA). Interlisp was notable for integrating interactive development tools into an integrated development environment (IDE), such as a debugger, an automatic correction tool for simple errors, and analysis tools.

<span class="mw-page-title-main">Zilog Z8000</span> 16-bit microprocessor

The Zilog Z8000 is a 16-bit microprocessor designed by Zilog in early 1979.

<span class="mw-page-title-main">TI BASIC (TI 99/4A)</span> Programming language for TI-99 home computers

TI BASIC is an ANSI-compliant interpreter for the BASIC programming language built into the 1979 Texas Instruments TI-99/4 home computer and its improved 1981 version, the TI-99/4A.

<span class="mw-page-title-main">PROMAL</span>

PROMAL is a structured programming language from Systems Management Associates for MS-DOS, Commodore 64, and Apple II. PROMAL features simple syntax, no line numbers, long variable names, functions and procedures with argument passing, real number type, arrays, strings, pointer, and a built-in I/O library. Like ABC and Python, indentation is part of the language syntax.

KDF9 was an early British 48-bit computer designed and built by English Electric. The first machine came into service in 1964 and the last of 29 machines was decommissioned in 1980 at the National Physical Laboratory. The KDF9 was designed for, and used almost entirely in, the mathematical and scientific processing fields – in 1967, nine were in use in UK universities and technical colleges. The KDF8, developed in parallel, was aimed at commercial processing workloads.

<span class="mw-page-title-main">Action! (programming language)</span> Atari 8-bit computer programming language

Action! is a procedural programming language and integrated development environment written by Clinton Parker for the Atari 8-bit computers. The language, which is similar to ALGOL, compiles to high-performance code for the MOS Technology 6502 of the Atari computers. Action! was distributed on ROM cartridge by Optimized Systems Software starting in 1983. It was one of the company's first bank-switched 16 kB "Super Cartridges". The runtime library is stored in the cartridge; to make a standalone application requires the Action! Toolkit which was sold separately by OSS.

In computer engineering, an orthogonal instruction set is an instruction set architecture where all instruction types can use all addressing modes. It is "orthogonal" in the sense that the instruction type and the addressing mode vary independently. An orthogonal instruction set does not impose a limitation that requires a certain instruction to use a specific register so there is little overlapping of instruction functionality.

UNOS is the first, now discontinued, 32-bit Unix-like real-time operating system (RTOS) with real-time extensions. It was developed by Jeffery Goldberg, MS. who left Bell Labs after using Unix and became VP of engineering for Charles River Data Systems (CRDS), now defunct. UNOS was written to capitalize on the first 32-bit microprocessor, the Motorola 68k central processing unit (CPU). CRDS sold a UNOS based 68K system, and sold porting services and licenses to other manufacturers who had embedded CPUs.

<span class="mw-page-title-main">Alpha Microsystems</span> American computer company

Alpha Microsystems, Inc., often shortened to Alpha Micro, was an American computer company founded in 1977 in Costa Mesa, California, by John French, Dick Wilcox and Bob Hitchcock. During the dot-com boom, the company changed its name to AlphaServ, then NQL Inc., reflecting its pivot toward being a provider of Internet software. However, the company soon reverted to its original Alpha Microsystems name after the dot-com bubble burst.

S-algol is a computer programming language derivative of ALGOL 60 developed at the University of St Andrews in 1979 by Ron Morrison and Tony Davie. The language is a modification of ALGOL to contain orthogonal data types that Morrison created for his PhD thesis. Morrison would go on to become professor at the university and head of the department of computer science. The S-algol language was used for teaching at the university at an undergraduate level until 1999. It was also the language taught for several years in the 1980s at a local school in St. Andrews, Madras College. The computer science text Recursive Descent Compiling describes a recursive descent compiler for S-algol, implemented in S-algol.

In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian student S. P. Sundaram in 1934.

The Creative Computing Benchmark, also called Ahl's Simple Benchmark, is a computer benchmark that was used to compare the performance of the BASIC programming language on various machines. It was first introduced in the November 1983 issue of Creative Computing magazine with the measures from a number of 8-bit computers that were popular at the time. Over a period of a few months, the list was greatly expanded to include practically every contemporary machine, topped by the Cray-1 supercomputer, which ran it in 0.01 seconds.

The Rugg/Feldman benchmarks are a series of seven short BASIC programming language programs that are used to test the performance of BASIC implementations on various microcomputers. They were published by Tom Rugg and Phil Feldman in the June 1977 issue of the US computer magazine, Kilobaud.

<span class="mw-page-title-main">Sieve of Pritchard</span> An algorithm for generating prime numbers

In mathematics, the sieve of Pritchard is an algorithm for finding all prime numbers up to a specified bound. Like the ancient sieve of Eratosthenes, it has a simple conceptual basis in number theory. It is especially suited to quick hand computation for small bounds.

References

Citations

  1. 1 2 3 4 Gilbreath 1981, p. 180.
  2. ↑ Knuth 1969, pp. 416, 658.
  3. ↑ Gilbreath 1981, pp. 181–190.
  4. 1 2 Gilbreath 1981, pp. 194.
  5. ↑ Gilbreath 1981, pp. 195.
  6. ↑ Gilbreath 1981, pp. 193.
  7. 1 2 Gilbreath 1981, pp. 196.
  8. 1 2 Gilbreath & Gilbreath 1983, p. 294.
  9. ↑ Gilbreath & Gilbreath 1983, p. 292.
  10. ↑ "HS/FORTH (advertisement)" (PDF). PC Tech Journal. October 1985. p. 132.
  11. ↑ "FORTH is now very.fast (advertisement)" (PDF). FORTH Dimensions. November–December 1985. p. 2.
  12. ↑ Ciarcia, Steve (1979). Ciarcia's Circuit Cellar, Volume 6. Circuit Cellar. p. 133. ISBN   9780070109681.
  13. 1 2 Houston, Jerry; Brodrick, Jim; Kent, Les (August 1983). "Comparing C Compilers for CP/M-86". Byte. pp. 82–106.
  14. ↑ Kern, Christopher (August 1983). "Five C Compilers for CP/M-80". Byte. pp. 110–130.
  15. ↑ Phraner, Ralph (August 1983). "Nine C Compilers for the IBM PC". Byte. pp. 134–168.
  16. ↑ Hinnant, David (August 1984). "Benchmarking UNIX Systems: UNIX performance on microcomputers and minicomputers". Byte. pp. 132–135, 400–409.
  17. ↑ "Swift Sieve of Eratosthenes". 27 July 2015.
  18. ↑ "Sieve of Eratosthenes". GitHub . Retrieved 2 May 2019.
  19. ↑ O'Neill, Melissa (January 2009). "The Genuine Sieve of Eratosthenes". Journal of Functional Programming. 19 (1): 95–106. doi: 10.1017/S0956796808007004 . S2CID   1309380.
  20. ↑ Gilbreath 1981, p. 188.
  21. ↑ Gilbreath 1981, p. 186.

Bibliography

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.