* [9fans] Fun with libthread 1: The Sieve
@ 2008-06-06 3:09 Pietro Gagliardi
2008-06-06 9:55 ` Martin Neubauer
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: Pietro Gagliardi @ 2008-06-06 3:09 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 3:09 [9fans] Fun with libthread 1: The Sieve Pietro Gagliardi
@ 2008-06-06 9:55 ` Martin Neubauer
2008-06-06 10:19 ` roger peppe
2008-06-06 10:23 ` Pietro Gagliardi
2008-06-06 14:00 ` roland.kaufmann
2008-06-06 15:35 ` Russ Cox
2 siblings, 2 replies; 9+ messages in thread
From: Martin Neubauer @ 2008-06-06 9:55 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 9:55 ` Martin Neubauer
@ 2008-06-06 10:19 ` roger peppe
2008-06-06 10:23 ` Pietro Gagliardi
1 sibling, 0 replies; 9+ messages in thread
From: roger peppe @ 2008-06-06 10:19 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
> 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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 9:55 ` Martin Neubauer
2008-06-06 10:19 ` roger peppe
@ 2008-06-06 10:23 ` Pietro Gagliardi
2008-06-06 11:29 ` Martin Neubauer
1 sibling, 1 reply; 9+ messages in thread
From: Pietro Gagliardi @ 2008-06-06 10:23 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
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.
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 10:23 ` Pietro Gagliardi
@ 2008-06-06 11:29 ` Martin Neubauer
0 siblings, 0 replies; 9+ messages in thread
From: Martin Neubauer @ 2008-06-06 11:29 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
* 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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 3:09 [9fans] Fun with libthread 1: The Sieve Pietro Gagliardi
2008-06-06 9:55 ` Martin Neubauer
@ 2008-06-06 14:00 ` roland.kaufmann
2008-06-06 19:02 ` Pietro Gagliardi
2008-06-06 15:35 ` Russ Cox
2 siblings, 1 reply; 9+ messages in thread
From: roland.kaufmann @ 2008-06-06 14:00 UTC (permalink / raw)
To: 9fans
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 3:09 [9fans] Fun with libthread 1: The Sieve Pietro Gagliardi
2008-06-06 9:55 ` Martin Neubauer
2008-06-06 14:00 ` roland.kaufmann
@ 2008-06-06 15:35 ` Russ Cox
2 siblings, 0 replies; 9+ messages in thread
From: Russ Cox @ 2008-06-06 15:35 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
> % 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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 14:00 ` roland.kaufmann
@ 2008-06-06 19:02 ` Pietro Gagliardi
2008-06-06 19:28 ` erik quanstrom
0 siblings, 1 reply; 9+ messages in thread
From: Pietro Gagliardi @ 2008-06-06 19:02 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
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
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [9fans] Fun with libthread 1: The Sieve
2008-06-06 19:02 ` Pietro Gagliardi
@ 2008-06-06 19:28 ` erik quanstrom
0 siblings, 0 replies; 9+ messages in thread
From: erik quanstrom @ 2008-06-06 19:28 UTC (permalink / raw)
To: pietro10, 9fans
> 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
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2008-06-06 19:28 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-06-06 3:09 [9fans] Fun with libthread 1: The Sieve Pietro Gagliardi
2008-06-06 9:55 ` Martin Neubauer
2008-06-06 10:19 ` roger peppe
2008-06-06 10:23 ` Pietro Gagliardi
2008-06-06 11:29 ` Martin Neubauer
2008-06-06 14:00 ` roland.kaufmann
2008-06-06 19:02 ` Pietro Gagliardi
2008-06-06 19:28 ` erik quanstrom
2008-06-06 15:35 ` Russ Cox
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).