<div dir="ltr">Also on more than one occasion I've had to work around issues with entry scaling with even mutable hashtables, A few 100K entries, they are fine but rapidly grind to a halt. The Python folks have hash tables nailed, über performance and scaling.</div> <div class="gmail_extra"> <div class="gmail_quote">On Thu, Feb 14, 2013 at 2:20 PM, James Bergstra <<a href="mailto:james.bergstra@gmail.com" target="_blank">james.bergstra@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I was actually trying to understand the performance bottlenecks of the "knucleotide" challenge of the language shootout: <a href="http://benchmarksgame.alioth.debian.org/u64/program.php?test=knucleotide&lang=racket&id=4" target="_blank">http://benchmarksgame.alioth.debian.org/u64/program.php?test=knucleotide&lang=racket&id=4</a> Most of the time seems to be spent in the loop that builds the hash table. (Incidentally, in that same loop, I tried replacing the set! key with a for/fold and that helped on my home computer but not the one at work. Maybe I had different versions of racket, I'm not sure) - James <div class="im HOEnZb"> On Thu, Feb 14, 2013 at 2:15 PM, Robby Findler <<a href="mailto:robby@eecs.northwestern.edu">robby@eecs.northwestern.edu</a>> wrote: </div><div class="HOEnZb"><div class="h5">> 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 <<a href="mailto:ianj@ccs.neu.edu">ianj@ccs.neu.edu</a>> 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 <<a href="mailto:james.bergstra@gmail.com">james.bergstra@gmail.com</a>> >> To: J. Ian Johnson <<a href="mailto:ianj@ccs.neu.edu">ianj@ccs.neu.edu</a>> >> Cc: <a href="mailto:users@racket-lang.org">users@racket-lang.org</a> >> 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 <<a href="mailto:ianj@ccs.neu.edu">ianj@ccs.neu.edu</a>> wrote: >> > My guess would be the higher-orderness on hash-update causes the (minor) >> > slowdown. >> > -Ian >> > ----- Original Message ----- >> > From: James Bergstra <<a href="mailto:james.bergstra@gmail.com">james.bergstra@gmail.com</a>> >> > To: <a href="mailto:users@racket-lang.org">users@racket-lang.org</a> >> > 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: >> > <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> >> > >> >> ____________________ >> Racket Users list: >> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> > > ____________________ Racket Users list: <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a> </div></div></blockquote></div> </div>