# [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)))))