6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Thu Mar 28, 2024 2:34 pm

All times are UTC




Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Fri Jan 20, 2017 8:44 pm 
Offline

Joined: Wed Jun 26, 2013 9:06 pm
Posts: 56
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

Quote:
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.


Top
 Profile  
Reply with quote  
PostPosted: Mon Jan 23, 2017 2:49 pm 
Offline

Joined: Tue Sep 03, 2002 12:58 pm
Posts: 288
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...


Top
 Profile  
Reply with quote  
PostPosted: Mon Jan 23, 2017 3:14 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10760
Location: England
I'll just paste some material from those discussions, for reference.

From the '816 book as excerpted here:
Quote:
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


Attachments:
1984_08_BYTE_09-08_Modula-2_0140.jpeg
1984_08_BYTE_09-08_Modula-2_0140.jpeg [ 371.45 KiB | Viewed 403 times ]
1983_01_BYTE_08-01_Looking_Ahead_0301.jpeg
1983_01_BYTE_08-01_Looking_Ahead_0301.jpeg [ 360.59 KiB | Viewed 403 times ]
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: