[plt-scheme] Unexpected slowdown using memoized function

From: Grant Rettke (grettke at acm.org)
Date: Sat Aug 11 23:34:47 EDT 2007

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


Posted on the users mailing list.