From mboxrd@z Thu Jan 1 00:00:00 1970 MIME-version: 1.0 Content-type: text/plain; charset=UTF-8; format=flowed; delsp=yes Message-id: <8BE506AC-687A-4D6B-AB03-7E9B75BBB0C4@mac.com> From: Pietro Gagliardi To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> Content-transfer-encoding: quoted-printable Date: Thu, 5 Jun 2008 23:09:04 -0400 Subject: [9fans] Fun with libthread 1: The Sieve Topicbox-Message-UUID: b45be434-ead3-11e9-9d60-3106f5b1d025 Hello. I decided to teach myself the 33 libraries of Plan 9 (even =20 those that I partially know), and I started with libthread, Sape's =20 implementation of Newsqueak-esque threads in C. One of Rob's favorite programs is Doug's Newsqueak Sieve of =20 Eratosthenes. It's a simple Newsqueak program that uses filtration to =20= wipe out prime numbers. I ported it to C: /n/sources/contrib/pietro/=20 sieve.c. The executable takes an argument determining how many prime =20 numbers to print; the default is 100. sieve() is spawned with a channel that is sent the prime numbers. It =20 first spawns counter() with a new channel. This channel is given all =20 integers n where n =3D 2, 3, ... . We will call the original channel =20 "primes" and the new channel "c". We now send primes the first value received from c. This is going to =20 be a prime number. Now, a new thread called filter() is called with =20 three components: this prime number, c, and a new channel newc. It =20 reads values from c, and if they are not factors of the original prime =20= number, sends them via newc. This next part is magic: c becomes newc. =20= So the next time we get a value from c, it will give us the first =20 prime returned from filter. Lather, rinse, repeat. Pike's video shows =20= you this graphically. So this is the part of the story subtitled "O Isn't That Big Anymore." =20= This was all done yesterday, June 4, 2008. I decided to compare the =20 running time of the sieve to primes(1), a program that, given start =20 and end primes, prints all primes between start and end inclusive. The =20= manual page claims it runs in time O(=E2=88=9A(N)). % time sieve 205963 > sieve.out That's right -- I'm finding the first 205,963 prime numbers. It runs =20 from around 7:00 PM EST 4 June 2008 to around 9:00 PM or 10:00 PM 5 =20 June 2008, when I come home from band practice, when I notice that =20 QEMU froze probably due to some other background processes (which is =20 normal behavior, unfortunately) after storing the 25,511th prime =20 (293,681). So to get that far, I would imagine Doug's program to be =20 O(N^N) or O(N!). Who knows? Note that due to primes' syntax I can't time that until I know what =20 the 205,963rd prime number is. Pietro PS - I don't free channels, making sieve a memory hog as well as a CPU =20= cycle hog.