[plt-scheme] Unexpected slowdown using memoized function

The prime? predicate of math.ss precomputes and memoizes the primeness of all 
natural numbers <= 1000000.
Adding an extra layer of memoization necessarily slows down, assuming you dont 
often ask for the primeness of numbers greater than 1000000, which seems 
unlikely because you investigate the primeness of bitcounts.
Jos Koot

----- Original Message ----- 
From: "Grant Rettke" <grettke at acm.org>
To: "PLT Scheme Mailing List" <plt-scheme at list.cs.brown.edu>
Sent: Sunday, August 12, 2007 5:34 AM
Subject: [plt-scheme] Unexpected slowdown using memoized function


> Hi folks,
>
> I added memoization to a function and expected the code to run faster,
> but it didn't. Why was I wrong to expect it to speed up?
>
> Here are the programs version 381 and 383
>
> #|
> $LastChangedDate: 2007-08-11 22:20:12 -0500 (Sat, 11 Aug 2007) $
> $LastChangedRevision: 381 $
> $HeadURL: svn://osiris/prime_bits/trunk/prime_bits.ss $
> |#
> (module prime_bits mzscheme
>
>  (require (lib "60.ss" "srfi"))
>  (require (planet "math.ss" ("soegaard" "math.plt" 1 0)))
>
>  (provide (all-defined))
>
>  (define (prime_bits a b)
>    (let loop ([a a] [count 0])
>      (if (> a b) count
>          (loop (add1 a) (if (P a) (add1 count) count)))))
>
>  (define (P x)
>    (prime? (bit-count x))))
>
> #|
> $LastChangedDate: 2007-08-11 22:24:36 -0500 (Sat, 11 Aug 2007) $
> $LastChangedRevision: 383 $
> $HeadURL: svn://osiris/prime_bits/trunk/prime_bits.ss $
> |#
> ;;; ONLY CHANGE
>  (define/memo (P x)
>    (prime? (bit-count x))))
>
> 381 took 23 seconds
> 383 took 39 seconds
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>