[plt-scheme] Unexpected slowdown using memoized function

I don't know what your code is doing, but I'll answer in general.
Memoization adds extra overhead to your program (of course): creation
of a memoization table, looking up values for each program call,
adding new entries for new inputs, and extra garbage collection time
because of the table hanging around.

Memoization pays off if a lot of inputs are repeated, so the function
body gets called less often and the reduced runtime offsets the
memoization overhead.  If your function is called on mostly unique
inputs, or the function itself is not much slower than the memoization
overhead, then you won't gain and you might lose.

I don't know what happened with your function, if it's fast to begin
with, or gets a lot of unique inputs, or something else, but there are
a number of ways memoization might simply slow you down.

--Carl

On 8/11/07, Grant Rettke <grettke at acm.org> wrote:
> 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