[plt-scheme] Effect of caching using hash-tables vs vectors

Hi everyone,


Just for fun, I did a solution for the 3n+1 problem from Programming 
Challenges:

     http://acm.uva.es/p/v1/100.html

I'll try to avoid spoiling other people from trying this out, and will 
just talk about an interesting performance issue I hit.


One of the things I used to make the solution fast is to memoize results, 
to avoid the cost of recomputation.  I initially tried using dherman's 
memoize module (for its DEFINE/MEMO*), but found that it did a little too 
much caching.

I needed finer control over the domain of inputs that I wanted to memoize, 
so I defined the following macro:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (define *MAXIMUM-CACHED* 1000000)
   (define-syntax (define/memo* stx)
     (syntax-case stx ()
       [(_ (name var) body)
        (syntax/loc stx
          (define name
            (let* ([table (make-hash-table 'equal)]
                   [in-domain? (lambda (n) (< n *MAXIMUM-CACHED*))]
                   [lookup (lambda (n)
                             (hash-table-get table n #f))]
                   [cached? (lambda (n) (and (lookup n) #t))]
                   [store! (lambda (n val)
                             (when (in-domain? n)
                               (hash-table-put! table n val)))])
              (lambda (var)
                (if (cached? var)
                    (lookup var)
                    (let ([result body])
                      (store! var result)
                      result))))))]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

With this, computing the maximum Collatz chain length between 1 and 
1000000 took about 20 seconds on my machine.  Not too bad.  (If I didn't 
control the domain of cached inputs, the runtime ballooned so badly that I 
didn't have the patience to wait it out.)


But actually this wasn't my original macro: I had used a vector instead as 
my first shot at the problem:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (define *MAXIMUM-CACHED* 1000000)
   (define-syntax (define/memo* stx)
     (syntax-case stx ()
       [(_ (name var) body)
        (syntax/loc stx
          (define name
            (let* ([table (make-vector *MAXIMUM-CACHED* 0)]
                   [in-domain? (lambda (n) (< n *MAXIMUM-CACHED*))]
                   [lookup (lambda (n)
                             (if (in-domain? n)
                                 (vector-ref table n)
                                 0))]
                   [cached? (lambda (n) (> (lookup n) 0))]
                   [store! (lambda (n val)
                             (when (in-domain? n)
                               (vector-set! table n val)))])
              (lambda (var)
                (if (cached? var)
                    (lookup var)
                    (let ([result body])
                      (store! var result)
                      result))))))]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Using vectors as my lookup structure: I timed about 3 seconds here!  It 
was just out of curiosity that I redid the macro to use hash-tables, and 
that's where the performance results surprised me: the vector lookup went 
much faster than the hash-table approach.

I was wondering if this is consistent with what other people would expect 
as far as hash-table performance is concerned: I did expect an overhead in 
comparing hash-tables to vectors as lookup structures, but not such a 
large one.


Happy St. Patrick's Day!