Computer languege Shootout does'nt like my n-sieve

[Antoni]

I submited there a source that put FB the first, three times faster than GCC for sieving primes.
Now they removed my source from the ranking and put it into interesting alternative programs....
http://shootout.alioth.debian.org/gp4/b ... s&lang=all
C users complained? What will they do when FB uses the gcc optimizer?

[v1ctor]

What a shame, the FAQ shows:

What does Interesting Alternative Program mean?

"Interesting Alternative Program" means that the program doesn't implement the benchmark according to the arbitrary and idiosyncratic rules of the Computer Language Shootout - but we simply couldn't resist showing the program.

"idiosyncratic rules".. meaning: we can refuse anything that we please if we can't figure out how it works.. nah.

[cha0s]

Conspiracy.

[VirusScanner]

It's called "C and C++ are better than anything else out there, and if you happen to make something that beats them then you cheated somehow."

[counting_pine]

In the FAQ it says:

We are not trying to

* compare different algorithms

Since the FB program is implemented differently from the C one, it's not really a fair comparison of the compilers.

[VirusScanner]

It also says "Write the program to be as fast as possible", oh well.

[voodooattack]

hmm so what, they want their algo "as-is" without considering the language differences?

sucks imo.. :(

[counting_pine]

Seems perfectly reasonable to me.

[Antoni]

These are the rules

diff program output N = 2 with this output file to check your program is correct before contributing.

Each program should count the prime numbers from 2 to M, using the same naïve Sieve of Eratosthenes algorithm:

* create an array of M bit flags
* for each index number
o if the flag value at that index is true
+ set all the flag values at multiples of that index false
+ increment the count

Calculate 3 prime counts, for M = 2N × 10000, 2N-1 × 10000, and 2N-2 × 10000.

They can accuse me only of reversing the logic in the sieve and of skipping multiples of 2 and 3...

[MichaelW]

This I believe is a straightforward implementation of the specified algorithm, patterned after the C gcc version.

Code: Select all

#include "windows.bi"
#include "timer.bas"
#include "crt.bi"

option explicit

'*************************************************

function nsieve( m as uinteger )

    dim as uinteger i,j,count,bytecount
    dim as byte ptr pmem

    bytecount = m shr 3
    pmem = allocate( bytecount )
    memset( pmem, &hff, bytecount )

    for i = 2 to m - 1
      if pmem[i shr 3] and (1 shl (i mod 8)) then
        for j = i + i to m - 1 step i
          pmem[j shr 3] and= not(1 shl (j mod 8))
        next
        count += 1
      endif
    next

    deallocate( pmem )

    function = count

end function

'*************************************************

sub test( n as uinteger )

    dim as uinteger m,count
    m = (1 shl n) * 10000

    count = nsieve( m )

    print "Primes up to ";m;"  ";count

end sub

dim as uinteger n

if len(command$) then

  n = val(command)

  timer_begin(10)
  
  test( n )
  test( n-1 )
  test( n-2 )

  timer_end
  print timer_ms;" ms"

else

  print "Usage: nsieve n"

endif
end

Running this against Antoni’s version with N = 9 under Windows 2000 on my P3, I get times of 2333ms and 425ms. So assuming the ratio would be similar on the P4 test system, .23 * 2333 / 425 = 1.26, which would place the FB version slightly above the C gcc version. I left the timing code intact so hopefully someone could do the comparison on a P4. I posted the timing macros I used here:

http://www.freebasic.net/forum/viewtopic.php?t=4252

[yetifoot]

I had this problem when i submitted a super-fast PI routine, they are very strict that the algorithms are exactly the same. I wasn't lucky enough to get mine as an 'Interesting Other' though.

[Antoni]

My results in a P4 2,4 for n=9

My program 0.147 sec
Michael's 1.333 sec
the c sample 0.409 sec

[MichaelW]

This is the fastest version so far on a P3, running in ~67% of the time for my first version, but it might not be the fastest on a P4 because shifts are relatively slow on a P4 and the loops each have a shr reg,5 followed by a shl reg,2 of the same register. A byte array version would have only a single shr reg,3 in each of the loops.

Code: Select all

#include "windows.bi"
#include "timer.bas"
#include "crt.bi"

option explicit

'************************************************

function nsieve( m as uinteger )

    dim as uinteger i,j,mm1,count,dwcount

    dim lut(0 to 31) as uinteger
    dim nlut(0 to 31) as uinteger

    for i = 0 to 31
      lut(i) = 1 shl i
      nlut(i) = not(1 shl i)
    next

    dwcount = m shr 5
    dim a(0 to dwcount shl 2) as uinteger

    memset( @a(0), &hff, dwcount shl 2)

    mm1 = m - 1

    for i = 2 to mm1
      if a(i shr 5) and lut(i mod 32) then
        for j = i + i to mm1 step i
          a(j shr 5) and= nlut(j mod 32)
        next
        count += 1
      endif
    next

    function = count

end function

'************************************************

sub test( n as uinteger )

    dim as uinteger m,count
    m = (1 shl n) * 10000

    count = nsieve( m )

    print "Primes up to ";m;"  ";count

end sub

'************************************************

dim as uinteger n

if len(command$) then

  n = val(command)

  timer_begin(10)
  
  test( n )
  test( n-1 )
  test( n-2 )

  timer_end
  print timer_ms;" ms"

else

  print "Usage: nsieve n"

endif

end

[VirusScanner]

However, you have to un-include windows.bi because these are being tested on linux.

[MichaelW]

Yes, I'm aware of that. Windows.bi is included so I can utilize the high resolution performance counter for timing.