dict performance

[Matthias Felleisen]

I ran across the snippet of code below (I turned it into a performance benchmark) and was amazed at how much slower the code ran after making it readable with dict!: I am seeing a factor of 20x and 40x depending on what exactly is run. Can anything be done about this?


#lang racket

(define (create n)
(define i 0)
(define sample (make-vector n))
(lambda (item)
(set! i (+ i 1))
(vector-set! sample (if (<= i n) (sub1 i) (quotient n 2)) item)
sample))

(define counts (make-vector 10 0))

(define-syntax-rule
(measure n d update)
(begin
(collect-garbage)
(collect-garbage)
(collect-garbage)
(time
(for ([i n])
(define f (create 3))
(define sample (for/last ([digit 10]) (f digit)))
(for ([d sample])
update)))))

;; I don't want more HO overhead
(define n 1000000)
(measure n d (vector-set! counts d (add1 (vector-ref counts d))))
(measure n d (dict-update! counts d add1))

[Robby Findler]

Looks like all but about 2x of the overhead is in the dict-update!
contract, which is this:

(->i ([d (dict-implements/c 'dict-set!)]
[k (d) (dict-key-contract d)]
[update (d) (-> (dict-value-contract d) (dict-value-contract d))])
([default (d) (or/c (dict-value-contract d) (->
(dict-value-contract d)))]) ;; use if/c
[_r void?])

Looks like some improvements (probably 7056cd5f2) since 6.3 have
shaved 10% of the time off. Not enough, I know.

->i doesn't participate in a relevant contract-system optimization
that -> and ->* do, but it could. That would improve things by about
2x I guess.

Robby

Robby

> --
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/62F7A4E7-4AA2-4F73-9686-C84F2FF52CF7%40ccs.neu.edu.
> For more options, visit https://groups.google.com/d/optout.

[Sam Tobin-Hochstadt]

It looks like most of the overhead is the contracts on the dict
functions -- if you switch to using `racket/private/dict` (which has
no contracts) the overhead goes down a lot.

Also, using `in-range` and `in-vector` in the implementation of
`measure` has a big impact on performance, so I think it's worth doing
when measuring.

Sam

On Wed, Jan 6, 2016 at 10:23 AM, Matthias Felleisen