Why is lazy faster than memo here?

Questions & Answers
1

Hi. I'm new to Racket and I'm learning functional programming. I was reading about lazy evaluation and memoize and I was testing it on this program.

#lang lazy
;; #lang racket/base

;; (require memo)

;; (define/memoize (efib n)
(define (efib n)
  (if (<= n 1)
      (list-ref (list 2 8) n)
      (+ (* (efib (- n 1)) 4)
         (efib (- n 2)))))

(for ([i 10000])
  (displayln (efib i)))

This might be a very noob question but when I think about it, it seems like memo should be faster because it's caching all the previous values that were returned. On the other hand, the actual results make me think I've misunderstood how lazy evaluation works. Of course, using neither does take noticeably long.

Using racket/base and (require memo): 4997268μs
Using lazy and no memo: 299663μs
Using both lazy and memo: 472486μs

Lazy by itself is the fastest. Combining it with memo is slower. Using only memo is a little slower than that. What is going on here? I would also appreciate some links because I couldn't find any resources that properly answered my question. Also would this be different for much larger projects?

Thanks.

2

Does the #lang lazy variant do what you want? Does it print anything at all to the screen?

Here are my thoughts:

  1. If you print a lot to the screen, IO will become the bottleneck. If you want to contrast the performance between many programs, try to print only a few values. E.g. print the sum
(displayln
 (apply +
        (for/list ([i 30])
          (efib i))))
  1. With that (30 iterations), #lang lazy takes 1.50s. memo takes 0.13s.

The issue with your earlier #lang lazy program is that the whole (for ...) is delayed, so essentially nothing is computed.

  1. From a quick glance of the memo documentation (it’s a user package, so I’m not familiar with it), it supports a lot of features that you might not need. If you write your own memoizer, it could even be faster.
#lang racket/base

(define (memoize f)
  (define mem (make-hash))
  (λ args
    (hash-ref! mem args (λ () (apply f args)))))

(define-syntax-rule (define/memoize (f args ...) body ...)
  (define f (memoize (λ (args ...) body ...))))

(define/memoize (efib n)
  (if (<= n 1)
      (list-ref (list 2 8) n)
      (+ (* (efib (- n 1)) 4)
         (efib (- n 2)))))

(apply + (for/list ([i 30]) (efib i)))

takes 0.03s.

2 Likes
3

What if you use Racket time and look at all three timing values, including the one for GC?

I ask because my first hunch would be that memoization means using a hash-table behind the scenes, with (IIUC) as many as 10,000 entries. The allocation and lookup times could become non-trivial. There could even be enough memory pressure that it causes more-frequent major garbage collections?

Caching can be tricky. I think someone said it's one of the two hardest problems in computing, along with (b) naming things and 3. off-by-one-errors? :smile:

EDIT: I wrote that while @sorawee was writing, and posted before noticing theirs -- which is better thought out.

1 Like
4

@Greg Hendershott

What is the off-by-one error?

DC369554041A4649A528B20B10730B39.png
DC369554041A4649A528B20B10730B39.png708×1 76 Bytes

5

That I said there would be 2 things but listed 3.

One source for related silliness seems to be: TwoHardThings

1 Like
6

So I changed stuff around and here's my updated code. I'm printing the sum here (it ends up being a really large number).

#lang racket/base
;;#lang lazy

;;(require memo)

(define (memoize f)
  (define mem (make-hash))
  (λ args
    (hash-ref! mem args (λ () (apply f args)))))

(define-syntax-rule (define/memoize (f args ...) body ...)
  (define f (memoize (λ (args ...) body ...))))

(define/memoize (efib n)
  (if (<= n 1)
      (list-ref (list 2 8) n)
      (+ (* (efib (- n 1)) 4)
         (efib (- n 2)))))

(displayln
 (apply +
        (for/list ([i 10000])
          (efib i))))

This time, using just lazy or using lazy with custom memoize takes a long time.

Using (require memo): 632554μs
Using (require memo) and lazy: 666103μs
Using custom memoize: 281063μs

Using just a custom memoizer is the fastest and interestingly, it is very close to my original result for lazy without memo (299663μs). I should read more about how lazy actually works. Thanks for the help!

1 Like