Sieve of Eratosthenes

Andres Valloud andresv at
Mon Oct 9 23:13:56 UTC 2006

Hello Davide,

Monday, October 9, 2006, 3:52:45 PM, you wrote:

DV> The Squeak code is better (of course) but on a number of 1000000
DV> Java spends 94 msec instead Squeak 2650!

Your post made me very curious, so I ran some experiments in
VisualWorks (no recent Squeak available here, sorry!).

Your original code took about 1300ms to run.

Not filling the array with true and using nil instead makes it run in
about 1200ms (make sure that new:withAll: is using from:to:put:).

Interestingly, using "== nil ifTrue:" instead of "isNil ifTrue:"
offered no advantages.  Using ifNil: was much slower.

Not creating intervals makes it run in 1000ms.

If you want it to run even faster, skip even numbers after 2.  This
change makes VW run in 900ms.  If you skip even numbers from the sieve
altogether, then it runs slightly faster at about 870ms.

Using a byte array instead of a regular array (and using 0 and 1 for
flags) makes it even faster, running in about 720ms.  Using a
ByteArray is actually closer to what the Java implementation is doing
(as far as I could tell).

Now, your machine has a 3ghz processor, and must be at least a p4 or
something similar.  Mine is a p3/600 which is spending about 20% cpu
playing stuff in Winamp with DSP plugins.  I think it's ok to assume
that yours is about 10 times faster than mine.  This yields something
comparable to Java's time, if not better.

Best regards,
 Andres                            mailto:andresv at

More information about the Squeak-dev mailing list