Website up again

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Website up again

karl-8
Seems like I managed to get the website running again :-)
Karl

Reply | Threaded
Open this post in threaded view
|

Sieve of Eratosthenes

Davide Varvello-2
Hi All,
I did some performance tests comparing java and squeak. The java code is this:
public class GeneratePrimes {
        public static double generate(int n) {
                long start = System.currentTimeMillis();
                boolean sieve[] = new boolean[n];
                Arrays.fill(sieve, true);
                sieve[0] = false;
                sieve[1] = false;
                for (int i = 2; i < n; i++) {
                        if (sieve[i]) {
                                for (int j = 2 * i; j < n; j += i) {
                                        sieve[j] = false;
                                }
                        }
                }

                return (System.currentTimeMillis() - start);
        }

The Squeak one is:

runOn: aNumber
        | sieve |

        sieve := Array new: aNumber withAll: true.
        sieve at: 1 put: false.

        (2 to: aNumber) do: [:i | (sieve at: i) ifTrue: [(i to: aNumber by: i) do: [:k | sieve at: k put: false] ]

The Squeak code is better (of course) but on a number of 1000000 Java spends 94 msec instead Squeak 2650!
Am I using the right approach or should I change something in my squeak code to make it perform better (but preserving clearness)?

Win xp, 3 ghz, Squeak 3.8, jdk 1.4.2

Thanks
 Davide



winmail.dat (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: Sieve of Eratosthenes

Ramon Leon-5
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On
> Behalf Of Davide Varvello
> Sent: Monday, October 09, 2006 1:53 PM
> To: The general-purpose Squeak developers list
> Subject: Sieve of Eratosthenes
>
> Hi All,
> I did some performance tests comparing java and squeak. The
> java code is this:
> public class GeneratePrimes {
> public static double generate(int n) {
> long start = System.currentTimeMillis();
> boolean sieve[] = new boolean[n];
> Arrays.fill(sieve, true);
> sieve[0] = false;
> sieve[1] = false;
> for (int i = 2; i < n; i++) {
> if (sieve[i]) {
> for (int j = 2 * i; j < n; j += i) {
> sieve[j] = false;
> }
> }
> }
>
> return (System.currentTimeMillis() - start);
> }
>
> The Squeak one is:
>
> runOn: aNumber
> | sieve |
>
> sieve := Array new: aNumber withAll: true.
> sieve at: 1 put: false.
>
> (2 to: aNumber) do: [:i | (sieve at: i) ifTrue: [(i to:
> aNumber by: i) do: [:k | sieve at: k put: false] ]
>
> The Squeak code is better (of course) but on a number of
> 1000000 Java spends 94 msec instead Squeak 2650!
> Am I using the right approach or should I change something in
> my squeak code to make it perform better (but preserving clearness)?

Here's my implementation, it's a little faster, but not much.

Integer>>sieveOfEratosthenes
        "generates primes up to self, educational algorithm, not for
production use"
        | primes |
        primes := ByteArray new: self.
        2 to: self do: [:each |
                (primes at: each) = 0 ifTrue: [each + each to: self
                        by: each do: [:notPrime |
                                                primes at: notPrime put:
1]]].
        ^(2 to: self) select: [:each | (primes at: each) = 0]



Reply | Threaded
Open this post in threaded view
|

Re: Sieve of Eratosthenes

Mathieu SUEN
In reply to this post by Davide Varvello-2
Davide Varvello a écrit :

> Hi All,
> I did some performance tests comparing java and squeak. The java code is this:
> public class GeneratePrimes {
> public static double generate(int n) {
> long start = System.currentTimeMillis();
> boolean sieve[] = new boolean[n];
> Arrays.fill(sieve, true);
> sieve[0] = false;
> sieve[1] = false;
> for (int i = 2; i < n; i++) {
> if (sieve[i]) {
> for (int j = 2 * i; j < n; j += i) {
> sieve[j] = false;
> }
> }
> }
>
> return (System.currentTimeMillis() - start);
> }
>
> The Squeak one is:
>
> runOn: aNumber
> | sieve |
>
> sieve := Array new: aNumber withAll: true.
> sieve at: 1 put: false.
>
> (2 to: aNumber) do: [:i | (sieve at: i) ifTrue: [(i to: aNumber by: i) do: [:k | sieve at: k put: false] ]
>
> The Squeak code is better (of course) but on a number of 1000000 Java spends 94 msec instead Squeak 2650!
> Am I using the right approach or should I change something in my squeak code to make it perform better (but preserving clearness)?
>
> Win xp, 3 ghz, Squeak 3.8, jdk 1.4.2
>
> Thanks
>  Davide
>
>
> ------------------------------------------------------------------------
>
>

Wy do you use Interval this slowdown a lote the test. Prefer this:

runOn: aNumber
  | sieve |

  sieve := Array new: aNumber withAll: true.
  sieve at: 1 put: false.

  2 to: aNumber do: [:i | (sieve at: i) ifTrue: [i to: aNumber by: i do: [:k | sieve at: k put: false] ]


Interval creation take a bit time for me with your first solution I have got 1444ms and with the
second only 1051ms.

        Math

Reply | Threaded
Open this post in threaded view
|

Re: Sieve of Eratosthenes

Andres Valloud-2
In reply to this post by Davide Varvello-2
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:[hidden email]


Reply | Threaded
Open this post in threaded view
|

Re[2]: Sieve of Eratosthenes

Andres Valloud-2
Hello Andres,

Monday, October 9, 2006, 6:13:56 PM, you wrote:

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

In addition, it seems the Smalltalk code had a bug because it would
mark primes as composites.  Fixing this with

  i + i to: limit by: i do:...

makes VW run in under 700ms.  The Java code does not seem to have this
problem.

--
Best regards,
 Andres                            mailto:[hidden email]


Reply | Threaded
Open this post in threaded view
|

Re: Sieve of Eratosthenes

Davide Varvello-2
In reply to this post by Andres Valloud-2
Thank you guys, your replies are good.

For Andres, you should compare the vw code with the java one on your  
machine (without any other running stuff), so you can have more  
realistic data to analyze.

Davide



On 10 Oct 2006, at 01:13, Andres Valloud wrote:

> 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:[hidden email]
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Sieve of Eratosthenes

Davide Varvello-2
Hi All,
  Moreover, there was a mistake in my code, the right one is this:

runOn: aNumber
  | sieve |

  sieve := Array new: aNumber withAll: true.
  sieve at: 1 put: false.

  2 to: aNumber do: [:i | (sieve at: i) ifTrue: [2*i to: aNumber by:  
i do: [:k | sieve at: k put: false] ]


bye
  Davide