[plt-scheme] hash table implementation?

At Thu, 20 Nov 2008 22:33:10 -0500, "Henk Boom" wrote:
> 2008/11/20 Matthew Flatt <mflatt at cs.utah.edu>:
> > That's correct for mutable hash tables. Immutable hash tables (with
> > functional updated) are implemented using a red--black tree.
> 
> Does this mean that if I am not planning to modify a hash table after
> construction, that it is preferable to use mutable hash tables for
> lookup speed? I've been using immutable ones simply because they have
> a ready-made constructor from alists.

No, I think immutable hash tables tend to be about as fast as immutable
ones for lookup. But my impression is that immutable hash tables can be
significantly slower to build.

[The difference, I think, is that the constant on rb-tree traversal is
low, while the constant on rb-tree rotation and intermediate-node
construction is much larger.]


I used the program below to check. If you make `sz' larger, then
construction of the immutable table takes proportionally more time. If
you make `sz' large enough (100000 on my machine) then lookup can be
faster with the mutable table, but not by much.

The usual caveat on a benchmark applies: a real program might differ
from the test below in many ways that affect performance.


Matthew

----------------------------------------

#lang scheme

(define sz 100)
(define iters 1000000)

(define ht1
  (for/hash ([i (in-range sz)])
    (values i (list i))))

(define ht2 (hash-copy ht1))

(define (t ht)
  (time
   (for ([i (in-range iters)])
     (hash-ref ht (modulo i sz)))))

'lookup-immutable
(t ht1)
'lookup-mutable
(t ht2)

'make-immutable
(time
 (void
  (for/fold ([ht #hasheq()]) ([i (in-range iters)])
    (hash-set ht (modulo i sz) i))))

'make-mutable
(time
 (void
  (let ([ht (make-hasheq)])
    (for ([i (in-range iters)])
      (hash-set! ht (modulo i sz) i)))))