[racket-dev] Optional equality predicate for assoc and member

What are the non-JIT platforms nowadays?

Robby

On Fri, Apr 22, 2011 at 6:39 PM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> Here's a performance experiment (code enclosed).
>
> Functions:
>
>  assq2 = plain Racket implementation of `assq'
>  assq-via-assf = `assq' via `assf' in same module
>  assq-via-library-assf = `assq' via imported `assf'
>
>  assoc2 = plain Racket implementation of `assoc'
>  assoc2/opt = like `assoc2', but taking `equal? as an optional argument
>  assoc-via-assf = `assoc' via `assf' in same module
>  assoc-via-imported-assf = `assoc' via imported `assf'
>
> Arguments:
>
>  '((x . 8))
>  (build-list 1000 (lambda (i) (if (= i 999) '(x . 10) '(y . 8))))
>  (build-list 1000 (lambda (i) (if (= i 999) '("x" . 10) '("y" . 8))))
>
> Timings:
>
> See below for 32-bit and 64-bit results.
>
> Observations:
>
> The docs are wrong. The `assq', `assv', and `assoc' functions don't
> currently require a list. The enclosed implementations reflect the C
> implementations, not the docs.
>
> Switching to a Racket implementation costs time, but (with the JIT)
> it's not a huge difference --- similar to the cost of switching the C
> code from 32-bit to 64-bit mode on my machine. The JIT even manages to
> make `assq' slightly faster than C in 64-bit mode.
>
> The compiler is doing its job within a module, as illustrated by
> `assq-via-assf' versus `assq-via-library-assf'. Cross-module inlining
> would be nice.
>
> Although not shown below, the cost is high on a platform where the JIT
> is not available. (I didn't have the patience to wait for results.)
>
> Switching to a Racket implementation solves immediate problems using
> `assq', `assv', and `assoc' with futures.
>
> Opinions:
>
> The cost for a non-JIT platform is why I hadn't changed `assq', `assv',
> and `assoc' before. But a plain-Racket implementation is surely better
> in the long run, and we can keep the C code and bind functions
> conditionally when the JIT is disabled. Maybe we can eventually close
> the gap between the JIT-generated code and C. Also, I think the JIT
> could be smarter about `equal?', which could tilt the balance in favor
> of the JIT for `assoc'.
>
> I'm happy that the compiler is doing its job, but inlining
> optimizations are fragile, so I'm a little reluctant to rely on them.
> Sad but true: the macro approach feels more comfortable for now.
>
> Before switching, we should check the effect on traditional benchmarks.
> Probably it will be small.
>
> ----------------------------------------
> 32-bit run:
>
> 'assq
> cpu time: 24 real time: 24 gc time: 0
> cpu time: 45 real time: 45 gc time: 0
> cpu time: 45 real time: 45 gc time: 0
> 'assq2
> cpu time: 44 real time: 44 gc time: 0
> cpu time: 85 real time: 85 gc time: 0
> cpu time: 85 real time: 86 gc time: 0
> 'assq-via-assf
> cpu time: 41 real time: 41 gc time: 0
> cpu time: 84 real time: 83 gc time: 0
> cpu time: 83 real time: 84 gc time: 0
> 'assq-via-library-assf
> cpu time: 162 real time: 164 gc time: 13
> cpu time: 320 real time: 319 gc time: 0
> cpu time: 373 real time: 373 gc time: 0
>
> 'assoc
> cpu time: 57 real time: 57 gc time: 0
> cpu time: 583 real time: 583 gc time: 0
> cpu time: 590 real time: 589 gc time: 0
> 'assoc2
> cpu time: 94 real time: 94 gc time: 0
> cpu time: 693 real time: 695 gc time: 0
> cpu time: 680 real time: 679 gc time: 0
> 'assoc2/opt
> cpu time: 91 real time: 91 gc time: 0
> cpu time: 679 real time: 678 gc time: 0
> cpu time: 674 real time: 674 gc time: 0
> 'assoc-via-assf
> cpu time: 101 real time: 102 gc time: 11
> cpu time: 682 real time: 682 gc time: 0
> cpu time: 674 real time: 674 gc time: 0
> 'assoc-via-library-assf
> cpu time: 211 real time: 221 gc time: 12
> cpu time: 1105 real time: 1115 gc time: 0
> cpu time: 1054 real time: 1079 gc time: 0
>
> ----------------------------------------
> 64-bit run:
>
> 'assq
> cpu time: 40 real time: 40 gc time: 0
> cpu time: 118 real time: 118 gc time: 0
> cpu time: 118 real time: 118 gc time: 0
> 'assq2
> cpu time: 45 real time: 44 gc time: 0
> cpu time: 91 real time: 92 gc time: 0
> cpu time: 91 real time: 91 gc time: 0
> 'assq-via-assf
> cpu time: 44 real time: 43 gc time: 0
> cpu time: 96 real time: 97 gc time: 0
> cpu time: 96 real time: 96 gc time: 0
> 'assq-via-library-assf
> cpu time: 202 real time: 203 gc time: 33
> cpu time: 306 real time: 306 gc time: 0
> cpu time: 305 real time: 305 gc time: 0
>
> 'assoc
> cpu time: 82 real time: 82 gc time: 0
> cpu time: 884 real time: 892 gc time: 0
> cpu time: 818 real time: 819 gc time: 0
> 'assoc2
> cpu time: 100 real time: 100 gc time: 0
> cpu time: 921 real time: 921 gc time: 0
> cpu time: 908 real time: 909 gc time: 0
> 'assoc2/opt
> cpu time: 102 real time: 101 gc time: 0
> cpu time: 908 real time: 908 gc time: 0
> cpu time: 896 real time: 896 gc time: 0
> 'assoc-via-assf
> cpu time: 136 real time: 138 gc time: 29
> cpu time: 929 real time: 929 gc time: 0
> cpu time: 876 real time: 876 gc time: 0
> 'assoc-via-library-assf
> cpu time: 277 real time: 283 gc time: 26
> cpu time: 1479 real time: 1478 gc time: 0
> cpu time: 1439 real time: 1458 gc time: 0
>
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/dev
>