sieve.mlton

[Stephen Weeks]

> Wait: bool arrays are 32 bits per entry, Word8Array's are 8 bits per entry,
> and yet the latter are 6 times slower?  How could that be?

I don't understand it either.

> I just tried the version of MLton I have (2001-08-06) and with that the bool
> version is epsilon faster (just under 1% faster).

Hmmm.  I am confused.  We see different numbers.  Maybe it's some other change
that Dan made between the two versions. Here are the running times for the two
variants on my machine, for three different MLton versions.

		bool	word8
20010706	0.68	1.72
20010806	0.21	1.21
20010823	0.21	1.21

I've appended the SML files I used to this message.

> For the test he is running (8K sieve), using a byte means it fits in the L1
> cache, while a word means it doesn't.

Here is my cpuinfo.

% cat /proc/cpuinfo
processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 5
model name	: Pentium II (Deschutes)
stepping	: 2
cpu MHz		: 397.955
cache size	: 512 KB
fdiv_bug	: no
hlt_bug		: no
f00f_bug	: no
coma_bug	: no
fpu		: yes
fpu_exception	: yes
cpuid level	: 2
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 mmx fxsr
bogomips	: 794.62

processor	: 1
vendor_id	: GenuineIntel
cpu family	: 6
model		: 5
model name	: Pentium II (Deschutes)
stepping	: 2
cpu MHz		: 397.955
cache size	: 512 KB
fdiv_bug	: no
hlt_bug		: no
f00f_bug	: no
coma_bug	: no
fpu		: yes
fpu_exception	: yes
cpuid level	: 2
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 mmx fxsr
bogomips	: 794.62


--------------------------------------------------------------------------------
(* sieve.word8.sml *)
(* -*- mode: sml -*-
 * $Id: sieve.mlton,v 1.5 2001/08/20 01:11:11 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 * with help from Dan Wang
 *)

structure WA = Word8Array
val flags  = WA.array (8193, 0w0)

fun init() = let
  fun loop i =
    if i < 8193 then (WA.update(flags,i,0w1);loop(i+1))
    else ()
in loop 2
end

fun do_elts(i,count) =
  if i < 8193 then
    if WA.sub(flags,i) = 0w1 then let
      fun loop k = 
	if k < 8193 then (WA.update(flags,k,0w0);loop(k+i))
	else ()
    in loop (i + i) ; do_elts(i + 1,count + 1)
    end
    else do_elts(i + 1, count)
  else count

fun repeat 0 = (init (); do_elts(2,0))
  | repeat n = (init (); do_elts(2,0);repeat(n-1))

fun printl [] = print "\n" | printl(h::t) = ( print h ; printl t )
fun atoi s = case Int.fromString s of SOME num => num | NONE => 0

fun main(name, param_list) =  let
	val arg = hd(param_list @ ["1"]);
	val num = atoi arg
	val count = repeat num 
    in  printl ["Count: ", Int.toString count];
	OS.Process.success
    end

val _ = main( CommandLine.name(), CommandLine.arguments() );
--------------------------------------------------------------------------------
(* sieve.bool.sml *)
(* -*- mode: sml -*-
 * $Id: sieve.mlton,v 1.3 2001/06/10 05:59:34 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 *)

val flags: bool array = Array.array (8193, false)

fun middle_loop (i, cnt) =
    if i < 8193 then
	if Array.sub (flags, i)
	   then
	      let
		 fun inner_loop k =
		    if k < 8193
		       then (Array.update (flags, k, false)
			     ; inner_loop (k + i))
		    else ()
	      in
		 inner_loop (i + i)
		 ; middle_loop (i + 1, cnt + 1)
	      end
	else middle_loop (i + 1, cnt)
    else cnt

fun init_flags i =
    if i < 8193 then
	( Array.update (flags, i, true) ; init_flags (i + 1) )
    else ()

fun printl nil = print "\n"
  | printl(h::t) = ( print h ; printl t )
		   
fun mytest 0 =
    let 
	val _ = init_flags 0
	val count = middle_loop (2, 0)
	val result = Int.toString count
    in printl ["Count: ", result] end
  | mytest n = (middle_loop (2, 0) ; mytest (n-1))

fun atoi s = case Int.fromString s of SOME num => num | NONE => 0
								
fun main(name, param_list) = 
    let
	val arg = hd(param_list @ ["1"]);
	    val num = atoi arg
    in
	mytest num; OS.Process.success
    end
	
val _ = main( CommandLine.name(), CommandLine.arguments() );