[racket] Question about hash table efficiency

hash-update is defined in Racket and, besides the error checking, is
basically the composition of those two functions. I expect it was written
as something to abstract over a common pattern, not speed things up.

Is this a bottleneck in some real program? Perhaps you'd share that (or
some inner loop of it)? I wonder if there is a better way to speed it up
than this.

Robby


On Thu, Feb 14, 2013 at 1:09 PM, J. Ian Johnson <ianj at ccs.neu.edu> wrote:

> If I am right, then it would make sense to use hash-update when the hash
> is big enough that a log-time traversal takes longer than a general
> procedure call's set-up and tear-down.
> -Ian
> ----- Original Message -----
> From: James Bergstra <james.bergstra at gmail.com>
> To: J. Ian Johnson <ianj at ccs.neu.edu>
> Cc: users at racket-lang.org
> Sent: Thu, 14 Feb 2013 13:47:51 -0500 (EST)
> Subject: Re: [racket] Question about hash table efficiency
>
> Thanks, I suppose I just had my hopes up. I thought the more compact
> form might involve fewer expression evaluations and require just one
> hash lookup instead of two, and therefore might run something like
> twice as fast, rather than slightly slower.
>
> On Thu, Feb 14, 2013 at 1:36 PM, J. Ian Johnson <ianj at ccs.neu.edu> wrote:
> > 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
> >
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130214/3bc731e7/attachment.html>