Page 1 of 1
I believe the Sieve benchmark was rigged
Posted: Fri Jan 20, 2017 8:44 pm
by Aaendi
This discussion started in the middle of thread on nesdev
http://forums.nesdev.com/viewtopic.php? ... 6&start=60
I would like to know if anyone had more information on the Sieve benchmark being used in 1983. As in, what was the code used for the 68000. According to several articles an 8Mhz 68000 took .49 seconds compared to the 8Mhz 65816 taking .73 seconds. The problem is there is no 68000 code to compare it with, and we can't find any possible 68000 equivalent code that would run faster than the posted 65816 code, without cheating.
What I speculate is that they used this "cheat" for the 68000.
http://www.keil.com/benchmarks/sieve.asp
Continue until the next remaining number is greater than the square root of the largest number in the original series. In this case, the next number, 7, is greater than the square root of 25, so the process stops. The remaining numbers are all prime.
This was not done in the 65816 code at all, nor does it look like it was used for the 8086 as well just by how poorly it did in comparison.
Re: I believe the Sieve benchmark was rigged
Posted: Mon Jan 23, 2017 2:49 pm
by John West
That's not necessarily unfair. The article in BYTE mentions a couple of major optimisations: stopping the outer loop at the square root of the target, and starting the inner loop at the square of the prime. They are both straightforward to implement if you have the square of the current prime. That's easy with a multiply instruction, but still possible through addition if you don't.
The first optimisation is very well known, and the 68000 has a multiply instruction so I'd expect that implementation to use it. The 65816 doesn't have multiply, and it's not obvious that using addition to maintain the square of the prime will be an improvement over the range used in the test (there's a trade-off between more work being done in the outer loop against fewer executions of the inner loop). The best way to know is for someone who cares enough to implement it.
The second optimisation is obvious once you know it, but I'll confess that I didn't know it before reading the article. I can understand it not being used very often.
Also, "rigged" is a strong word. It implies a deliberate manipulation of the test to favour some processors over others. I don't think that's likely. They're using programs supplied by a number of different people, and they will have put in different levels of optimisation effort. To be a fair test you'd have to specify exactly what algorithm to implement, and then it is still partly testing the skill of the implementor. I'd go with "sloppy".
And now I'm off to make a small change to my (non-6502) prime number library...
Re: I believe the Sieve benchmark was rigged
Posted: Mon Jan 23, 2017 3:14 pm
by BigEd
I'll just paste some material from those discussions, for reference.
From the '816 book as
excerpted here:
The use of the Sieve program first gained popularity as the result of articles written by Jim Gilbreath and Gary Gilbreath, appearing in BYTE magazine (September 1980!?, page 180), and updated in January 1983 (page 283).
Actually
1981 not 1980!
The BYTE issues are online, as PDF-with-text, as plain text and searchable flip-books in the browser:
A High-Level Language Benchmark by Jim Gilbreath
BYTE Sep 1981, p.180
Eratosthenes Revisited: Once More through the Sieve by Jim Gilbreath and Gary Gilbreath
BYTE Jan 83 p.283
Benchmarking UNIX systems by David Hinnant
BYTE Aug 1984 p.132
Tabulation of results (incomplete, I think):
p301 from 1983-01
p140 from 1984-08