[racket] Question about hash table efficiency

From: J. Ian Johnson (ianj at ccs.neu.edu)
Date: Thu Feb 14 13:36:19 EST 2013

My guess would be the higher-orderness on hash-update causes the (minor) slowdown.
-Ian
----- Original Message -----
From: James Bergstra <james.bergstra at gmail.com>
To: users at racket-lang.org
Sent: Thu, 14 Feb 2013 13:16:47 -0500 (EST)
Subject: [racket] Question about hash table efficiency

Hi list, just discovered racket and having fun learning about scheme
again. Haven't used it since undergrad. Thanks!

I was wondering about the efficiency of hash-update vs. hash-set and
hash-ref. I thought the former would be faster, otherwise why have it?
A little benchmark script reveals the same surprising result as my
actual application though:

"""
#lang racket

;; warm-up
(time (void
 (for/fold ([table (make-immutable-hasheq '())])
  ([ii (in-range 100000)])
  (hash-update table (modulo ii 100) add1 ii))))

;; update
(newline)
(time (void
 (for/fold ([table (make-immutable-hasheq '())])
  ([ii (in-range 100000)])
  (hash-update table (modulo ii 100) add1 ii))))

;; set/ref
(newline)
(time (void
 (for/fold ([table (make-immutable-hasheq '())])
  ([ii (in-range 100000)])
  (hash-set table (modulo ii 100) (add1 (hash-ref table (modulo ii 100) ii))))))

"""

This prints out:

cpu time: 112 real time: 114 gc time: 32

cpu time: 80 real time: 82 gc time: 0

cpu time: 76 real time: 75 gc time: 4


My original application used mutable hash tables and the same effect
was observed (if not more dramatically). Any thoughts on why the
update form is slower? I'm running this in Racket v5.1.1.

- James
____________________
  Racket Users list:
  http://lists.racket-lang.org/users


Posted on the users mailing list.