[9fans] Fun with libthread 1: The Sieve

[9fans] Fun with libthread 1: The Sieve

[Pietro Gagliardi]

Hello. I decided to teach myself the 33 libraries of Plan 9 (even  
those that I partially know), and I started with libthread, Sape's  
implementation of Newsqueak-esque threads in C.

One of Rob's favorite programs is Doug's Newsqueak Sieve of  
Eratosthenes. It's a simple Newsqueak program that uses filtration to  
wipe out prime numbers. I ported it to C: /n/sources/contrib/pietro/ 
sieve.c. The executable takes an argument determining how many prime  
numbers to print; the default is 100.

sieve() is spawned with a channel that is sent the prime numbers. It  
first spawns counter() with a new channel. This channel is given all  
integers n where n = 2, 3, ... . We will call the original channel  
"primes" and the new channel "c".

We now send primes the first value received from c. This is going to  
be a prime number. Now, a new thread called filter() is called with  
three components: this prime number, c, and a new channel newc. It  
reads values from c, and if they are not factors of the original prime  
number, sends them via newc. This next part is magic: c becomes newc.  
So the next time we get a value from c, it will give us the first  
prime returned from filter. Lather, rinse, repeat. Pike's video shows  
you this graphically.

So this is the part of the story subtitled "O Isn't That Big Anymore."  
This was all done yesterday, June 4, 2008. I decided to compare the  
running time of the sieve to primes(1), a program that, given start  
and end primes, prints all primes between start and end inclusive. The  
manual page claims it runs in time O(√(N)).

	% time sieve 205963 > sieve.out

That's right -- I'm finding the first 205,963 prime numbers. It runs  
from around 7:00 PM EST 4 June 2008 to around 9:00 PM or 10:00 PM 5  
June 2008, when I come home from band practice, when I notice that  
QEMU froze probably due to some other background processes (which is  
normal behavior, unfortunately) after storing the 25,511th prime  
(293,681). So to get that far, I would imagine Doug's program to be  
O(N^N) or O(N!). Who knows?

Note that due to primes' syntax I can't time that until I know what  
the 205,963rd prime number is.

Pietro

PS - I don't free channels, making sieve a memory hog as well as a CPU  
cycle hog.

Re: [9fans] Fun with libthread 1: The Sieve

[Martin Neubauer]

Very amusing. However, I'm not sure what you are trying to tell us, besides
that you haven't understood what the O(...) means.

* Pietro Gagliardi (pietro10@mac.com) wrote:
> Hello. I decided to teach myself the 33 libraries of Plan 9 (even  
> those that I partially know), and I started with libthread, Sape's  
> implementation of Newsqueak-esque threads in C.
> 
> One of Rob's favorite programs is Doug's Newsqueak Sieve of  
> Eratosthenes. It's a simple Newsqueak program that uses filtration to  
> wipe out prime numbers. I ported it to C: /n/sources/contrib/pietro/ 
> sieve.c. The executable takes an argument determining how many prime  
> numbers to print; the default is 100.
> 
> sieve() is spawned with a channel that is sent the prime numbers. It  
> first spawns counter() with a new channel. This channel is given all  
> integers n where n = 2, 3, ... . We will call the original channel  
> "primes" and the new channel "c".
> 
> We now send primes the first value received from c. This is going to  
> be a prime number. Now, a new thread called filter() is called with  
> three components: this prime number, c, and a new channel newc. It  
> reads values from c, and if they are not factors of the original prime  
> number, sends them via newc. This next part is magic: c becomes newc.  
> So the next time we get a value from c, it will give us the first  
> prime returned from filter. Lather, rinse, repeat. Pike's video shows  
> you this graphically.
> 
> So this is the part of the story subtitled "O Isn't That Big Anymore."  
> This was all done yesterday, June 4, 2008. I decided to compare the  
> running time of the sieve to primes(1), a program that, given start  
> and end primes, prints all primes between start and end inclusive. The  
> manual page claims it runs in time O(√(N)).
> 
> 	% time sieve 205963 > sieve.out
> 
> That's right -- I'm finding the first 205,963 prime numbers. It runs  
> from around 7:00 PM EST 4 June 2008 to around 9:00 PM or 10:00 PM 5  
> June 2008, when I come home from band practice, when I notice that  
> QEMU froze probably due to some other background processes (which is  
> normal behavior, unfortunately) after storing the 25,511th prime  
> (293,681). So to get that far, I would imagine Doug's program to be  
> O(N^N) or O(N!). Who knows?
> 
> Note that due to primes' syntax I can't time that until I know what  
> the 205,963rd prime number is.
> 
> Pietro
> 
> PS - I don't free channels, making sieve a memory hog as well as a CPU  
> cycle hog.

Re: [9fans] Fun with libthread 1: The Sieve

[roger peppe]

> Note that due to primes' syntax I can't time that until I know what the 205,963rd prime number is.

erm, what about

time rc -c 'primes 1 10000000000 | sed 205963q | tail -5'

takes just over 1 second on my laptop.

Re: [9fans] Fun with libthread 1: The Sieve

[Pietro Gagliardi]

I forgot to mention one simple detail: when I said we set c to newc,  
we only set sieve's copy. filter still uses the c we gave it, meaning  
it reads numbers from counter the first time around.

Martin: this was just an experiment. I'm really not sure how to count  
timed programs. Jon Bentley showed me how to count simple algorithms.  
I'm not so sure this is very simple at first glance.

On Jun 6, 2008, at 5:55 AM, Martin Neubauer wrote:

> Very amusing. However, I'm not sure what you are trying to tell us,  
> besides
> that you haven't understood what the O(...) means.
>
> * Pietro Gagliardi (pietro10@mac.com) wrote:
>> Hello. I decided to teach myself the 33 libraries of Plan 9 (even
>> those that I partially know), and I started with libthread, Sape's
>> implementation of Newsqueak-esque threads in C.
>>
>> One of Rob's favorite programs is Doug's Newsqueak Sieve of
>> Eratosthenes. It's a simple Newsqueak program that uses filtration to
>> wipe out prime numbers. I ported it to C: /n/sources/contrib/pietro/
>> sieve.c. The executable takes an argument determining how many prime
>> numbers to print; the default is 100.
>>
>> sieve() is spawned with a channel that is sent the prime numbers. It
>> first spawns counter() with a new channel. This channel is given all
>> integers n where n = 2, 3, ... . We will call the original channel
>> "primes" and the new channel "c".
>>
>> We now send primes the first value received from c. This is going to
>> be a prime number. Now, a new thread called filter() is called with
>> three components: this prime number, c, and a new channel newc. It
>> reads values from c, and if they are not factors of the original  
>> prime
>> number, sends them via newc. This next part is magic: c becomes newc.
>> So the next time we get a value from c, it will give us the first
>> prime returned from filter. Lather, rinse, repeat. Pike's video shows
>> you this graphically.
>>
>> So this is the part of the story subtitled "O Isn't That Big  
>> Anymore."
>> This was all done yesterday, June 4, 2008. I decided to compare the
>> running time of the sieve to primes(1), a program that, given start
>> and end primes, prints all primes between start and end inclusive.  
>> The
>> manual page claims it runs in time O(√(N)).
>>
>> 	% time sieve 205963 > sieve.out
>>
>> That's right -- I'm finding the first 205,963 prime numbers. It runs
>> from around 7:00 PM EST 4 June 2008 to around 9:00 PM or 10:00 PM 5
>> June 2008, when I come home from band practice, when I notice that
>> QEMU froze probably due to some other background processes (which is
>> normal behavior, unfortunately) after storing the 25,511th prime
>> (293,681). So to get that far, I would imagine Doug's program to be
>> O(N^N) or O(N!). Who knows?
>>
>> Note that due to primes' syntax I can't time that until I know what
>> the 205,963rd prime number is.
>>
>> Pietro
>>
>> PS - I don't free channels, making sieve a memory hog as well as a  
>> CPU
>> cycle hog.
>

Re: [9fans] Fun with libthread 1: The Sieve

[Martin Neubauer]

* Pietro Gagliardi (pietro10@mac.com) wrote:
> Martin: this was just an experiment. I'm really not sure how to count
> timed programs. Jon Bentley showed me how to count simple algorithms.
> I'm not so sure this is very simple at first glance.

I rest my case.

Re: [9fans] Fun with libthread 1: The Sieve

[roland.kaufmann]

Hello Pietro,
how many treads are created when you call
  sieve n ?

> Note that due to primes' syntax I can't time that until I know what
> the 205,963rd prime number is.
2837711

                                best regards
                                    Roland

Re: [9fans] Fun with libthread 1: The Sieve

[Pietro Gagliardi]

The program spawns n + 2 threads. sieve and counter are only spawned
once, but filter is spawned for every prime number.

With Roger's command line, primes took me about 91 seconds - possibly
because it isn't looking for a specific end. primes 1 2837711 takes 43
seconds.

Up next: what happens when you share libcontrol across threads. This
is where the graphical fun begins.

On Jun 6, 2008, at 10:00 AM, roland.kaufmann@space.at wrote:

> Hello Pietro,
> how many treads are created when you call
>  sieve n ?
>
>> Note that due to primes' syntax I can't time that until I know what
>> the 205,963rd prime number is.
> 2837711
>
>                                best regards
>                                    Roland
>

Re: [9fans] Fun with libthread 1: The Sieve

[erik quanstrom]

> The program spawns n + 2 threads. sieve and counter are only spawned
> once, but filter is spawned for every prime number.
>
> With Roger's command line, primes took me about 91 seconds - possibly
> because it isn't looking for a specific end. primes 1 2837711 takes 43
> seconds.
>

perhaps roger is using a different version of primes.  the version
on sources finds all the primes before any are printed.  the output
is not buffered so that may also contribute quite a bit to the run
time.  (hence 1.25s of system time.)

	; time rc -c 'primes 1 10000000000 | sed 205963q | tail -5'
	2837629
	2837633
	2837677
	2837693
	2837711
	3.64u 1.25s 4.29r 	 rc -c primes 1 10000000000 | sed 205963q | tail -5  # status= rc 42288: primes 42289: sys: write on closed pipe pc=0x00005ef5||

i would imagine that pietro is running in an emulator to be 20x
slower.

but all this performance stuff misses the point.

- erik

Re: [9fans] Fun with libthread 1: The Sieve

[Russ Cox]

>         % time sieve 205963 > sieve.out
>
>  That's right -- I'm finding the first 205,963 prime numbers. It runs from
> around 7:00 PM EST 4 June 2008 to around 9:00 PM or 10:00 PM 5 June 2008,
> when I come home from band practice, when I notice that QEMU froze probably
> due to some other background processes (which is normal behavior,
> unfortunately) after storing the 25,511th prime (293,681). So to get that
> far, I would imagine Doug's program to be O(N^N) or O(N!). Who knows?

More likely it froze because you ran it out of memory.
25,511 primes * 1024 stack size = 25MB of memory just to
hold the thread stacks.  The concurrent prime sieve may be
elegant, but efficient it is not.

Also, I promise you that the sieve run time is less than O(N^2)
if N is the maximum prime you want to get to (not the number of primes).
You'd have to work pretty hard to do prime generation in
O(N^N) or O(N!).

>  PS - I don't free channels, making sieve a memory hog as well as a CPU
> cycle hog.

It's a good thing you don't free channels, since they never stop being used.

Russ