From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: Date: Fri, 6 Jun 2008 11:35:57 -0400 From: "Russ Cox" To: "Fans of the OS Plan 9 from Bell Labs" <9fans@9fans.net> Subject: Re: [9fans] Fun with libthread 1: The Sieve In-Reply-To: <8BE506AC-687A-4D6B-AB03-7E9B75BBB0C4@mac.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <8BE506AC-687A-4D6B-AB03-7E9B75BBB0C4@mac.com> Topicbox-Message-UUID: b569277e-ead3-11e9-9d60-3106f5b1d025 > % 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