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

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: assocs.rkt
Type: application/octet-stream
Size: 2522 bytes
Desc: not available
URL: <http://lists.racket-lang.org/dev/archive/attachments/20110422/7e2d64e0/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: time-assocs.rkt
Type: application/octet-stream
Size: 628 bytes
Desc: not available
URL: <http://lists.racket-lang.org/dev/archive/attachments/20110422/7e2d64e0/attachment-0001.obj>