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

I've pushed the change that makes `assoc', `assv', and `assq'
implemented in Racket, including the new optional argument for `assoc'.

At Fri, 22 Apr 2011 19:52:34 -0400, Eli Barzilay wrote:
> 7 minutes ago, Matthew Flatt wrote:
> > 
> > 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.
> 
> Is there some obvious reason for the huge difference in improvement
> between the 32 and the 64 bits (Almost twice slower and roughly the
> same resp.)?

Like Noel, I thought at first it might be memory-bound. Now I think
it's just that the compiler on my machine (or the way the compiler is
configured) handles x86_64 not as well as x86.

> > 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'.
> 
> (Maybe it'll be feasible to dump jit-generated machine code at some
> point...?)

Just so you can see the generated code? I think Sam's tool is on the
right track. Otherwise, I'm not sure what you're suggesting.


> > 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.
> 
> If by "macro approach" you refer to what I was talking about, then
> isn't that needed to have versions with inlined comparators?

Every time I look into changing `map' or other functions into macros, I
conclude that it would be better to implement cross-module inlining.


At Fri, 22 Apr 2011 19:27:49 -0500, Robby Findler wrote:
> What are the non-JIT platforms nowadays?

Sparc and ARM, probably. I expect Sparc to fade away, and I imagine
adding ARM support to the JIT, eventually.

Currently, the Racket implementation of `assq', etc., is used always.
I've thought about ways to fall back to the C implementation when the
JIT is unavailable, but I haven't settled on anything yet.



Below are revised results for the performance test. The old
C-implemented `assq' is now `kernel:assq', and the Racket-implemented
`assq2' is now `assq'.

The improvements are from adjusting the Racket code slightly and
improving the JIT in various small ways. There's more room for
improvement, obviously, and I stopped only because I've had enough for
now.

For those who are *really* interested, I've included annotated,
disassembled JIT output at the end of this message. The JIT-generated
core loop and the gcc-generated core loop are very similar; there's
four times as much JIT-generated code because it unrolls the loop to
four copies. (Both versions test two elements of the list in each
iteration, because the "turtle" to detect cycles is incremented only with
the second test.)

----------------------------------------
32-bit run:

'kern:assq
cpu time: 23 real time: 23 gc time: 0
cpu time: 38 real time: 39 gc time: 0
cpu time: 39 real time: 38 gc time: 0
'assq
cpu time: 38 real time: 39 gc time: 0
cpu time: 60 real time: 61 gc time: 0
cpu time: 61 real time: 61 gc time: 0

'kern:assoc
cpu time: 60 real time: 60 gc time: 0
cpu time: 563 real time: 567 gc time: 0
cpu time: 554 real time: 555 gc time: 0
'assoc
cpu time: 74 real time: 74 gc time: 0
cpu time: 589 real time: 592 gc time: 0
cpu time: 582 real time: 584 gc time: 0

----------------------------------------
64-bit run:

'kern:assq
cpu time: 36 real time: 36 gc time: 0
cpu time: 117 real time: 117 gc time: 0
cpu time: 118 real time: 118 gc time: 0
'assq
cpu time: 39 real time: 39 gc time: 0
cpu time: 66 real time: 65 gc time: 0
cpu time: 65 real time: 65 gc time: 0

'kern:assoc
cpu time: 81 real time: 81 gc time: 0
cpu time: 860 real time: 860 gc time: 0
cpu time: 798 real time: 798 gc time: 0
'assoc
cpu time: 83 real time: 83 gc time: 0
cpu time: 782 real time: 789 gc time: 0
cpu time: 738 real time: 739 gc time: 0


----------------------------------------

The main `assq' loop.
Arguments: list, turtle; environment: value to find, original list.

0x0676707a:	mov    0xc(%ebx),%eax [get list off stack]
0x0676707d:	test   $0x1,%al
0x06767080:	jne    0x676756b      [to fail: fixnum instead of list]
0x06767086:	movswl (%eax),%ecx
0x06767089:	cmp    $0x34,%ecx
0x0676708f:	jne    0x676756b      [to fail: not a pair]
0x06767095:	mov    0x4(%eax),%eax [car => item]
0x06767098:	mov    %eax,-0x4(%ebx) [save item on stack]
0x0676709b:	add    $0xfffffffc,%ebx [adjust stack pointer]
0x0676709e:	test   $0x1,%al
0x067670a1:	jne    0x676752a      [to fail: item is fixnum]
0x067670a7:	movswl (%eax),%ecx
0x067670aa:	cmp    $0x34,%ecx
0x067670b0:	jne    0x676752a      [to fail: item is not a pair]
0x067670b6:	mov    0x4(%eax),%eax [car of item]
0x067670b9:	mov    %eax,%ecx
0x067670bb:	mov    0x8(%ebx),%eax [get key to find off stack]
0x067670be:	cmp    %ecx,%eax      [found key?]
0x067670c0:	jne    0x67670cd        [jump if not...]
0x067670c6:	mov    (%ebx),%eax    [yes... get item from stack]
0x067670c8:	jmp    0x6767525        [and return item]
0x067670cd:	mov    0x10(%ebx),%eax [no... get list from stack]
0x067670d0:	mov    0x8(%eax),%eax  [cdr of list]
0x067670d3:	mov    %eax,-0x4(%ebx) [save new list to stack]
0x067670d6:	add    $0xfffffffc,%ebx [adjust stack pointer]
0x067670d9:	mov    0x18(%ebx),%ecx [get turtle from stack]
0x067670dc:	cmp    %ecx,%eax       [(eq? turtle list)]
0x067670de:	jne    0x6767111         [normally jumps...]
0x067670e4:	mov    $0x67675c0,%eax [fail: found cycle...]
0x067670e9:	mov    (%eax),%eax       [... call error function ...]
0x067670eb:	mov    %eax,-0xc(%ebx)
0x067670ee:	mov    $0x67675c4,%eax
0x067670f3:	mov    (%eax),%eax
0x067670f5:	mov    %eax,-0x8(%ebx)
0x067670f8:	mov    0x10(%ebx),%eax
0x067670fb:	mov    %eax,-0x4(%ebx)
0x067670fe:	mov    $0x34540,%esi
0x06767103:	add    $0xfffffff4,%ebx
0x06767106:	mov    %ebx,0x44c(%edi)
0x0676710c:	jmp    0x376c90
0x06767111:	mov    (%ebx),%eax      [get list from stack... (redundant!)]
0x06767113:	test   $0x1,%al          [... starts another iteration of above]
0x06767116:	jne    0x67674e0         [... and there are 4 copies total]
0x0676711c:	movswl (%eax),%ecx
0x0676711f:	cmp    $0x34,%ecx
0x06767125:	jne    0x67674e0
0x0676712b:	mov    0x4(%eax),%eax
0x0676712e:	mov    %eax,-0x4(%ebx)
0x06767131:	add    $0xfffffffc,%ebx
0x06767134:	test   $0x1,%al
0x06767137:	jne    0x676749f
0x0676713d:	movswl (%eax),%ecx
0x06767140:	cmp    $0x34,%ecx
0x06767146:	jne    0x676749f
0x0676714c:	mov    0x4(%eax),%eax
0x0676714f:	mov    %eax,%ecx
0x06767151:	mov    0x10(%ebx),%eax
0x06767154:	cmp    %ecx,%eax
0x06767156:	jne    0x6767163
0x0676715c:	mov    (%ebx),%eax
0x0676715e:	jmp    0x676749a
0x06767163:	mov    0x1c(%ebx),%eax
0x06767166:	mov    0x8(%eax),%eax
0x06767169:	mov    %eax,-0x4(%ebx)
0x0676716c:	mov    0x4(%ebx),%eax
0x0676716f:	mov    0x8(%eax),%eax
0x06767172:	mov    %eax,-0x8(%ebx)
0x06767175:	add    $0xfffffff8,%ebx
0x06767178:	mov    0x4(%ebx),%ecx
0x0676717b:	cmp    %ecx,%eax
0x0676717d:	jne    0x67671b0
0x06767183:	mov    $0x67675c8,%eax
0x06767188:	mov    (%eax),%eax
0x0676718a:	mov    %eax,-0xc(%ebx)
0x0676718d:	mov    $0x67675cc,%eax
0x06767192:	mov    (%eax),%eax
0x06767194:	mov    %eax,-0x8(%ebx)
0x06767197:	mov    0x1c(%ebx),%eax
0x0676719a:	mov    %eax,-0x4(%ebx)
0x0676719d:	mov    $0x34540,%esi
0x067671a2:	add    $0xfffffff4,%ebx
0x067671a5:	mov    %ebx,0x44c(%edi)
0x067671ab:	jmp    0x376c90
0x067671b0:	mov    (%ebx),%eax       [get list from stack... (redundant!)]
0x067671b2:	test   $0x1,%al
0x067671b5:	jne    0x6767455
0x067671bb:	movswl (%eax),%ecx
0x067671be:	cmp    $0x34,%ecx
0x067671c4:	jne    0x6767455
0x067671ca:	mov    0x4(%eax),%eax
0x067671cd:	mov    %eax,-0x4(%ebx)
0x067671d0:	add    $0xfffffffc,%ebx
0x067671d3:	test   $0x1,%al
0x067671d6:	jne    0x6767414
0x067671dc:	movswl (%eax),%ecx
0x067671df:	cmp    $0x34,%ecx
0x067671e5:	jne    0x6767414
0x067671eb:	mov    0x4(%eax),%eax
0x067671ee:	mov    %eax,%ecx
0x067671f0:	mov    0x1c(%ebx),%eax
0x067671f3:	cmp    %ecx,%eax
0x067671f5:	jne    0x6767202
0x067671fb:	mov    (%ebx),%eax
0x067671fd:	jmp    0x676740f
0x06767202:	mov    0x4(%ebx),%eax
0x06767205:	mov    0x8(%eax),%eax
0x06767208:	mov    %eax,-0x4(%ebx)
0x0676720b:	add    $0xfffffffc,%ebx
0x0676720e:	mov    0xc(%ebx),%ecx
0x06767211:	cmp    %ecx,%eax
0x06767213:	jne    0x6767246
0x06767219:	mov    $0x67675d0,%eax
0x0676721e:	mov    (%eax),%eax
0x06767220:	mov    %eax,-0xc(%ebx)
0x06767223:	mov    $0x67675d4,%eax
0x06767228:	mov    (%eax),%eax
0x0676722a:	mov    %eax,-0x8(%ebx)
0x0676722d:	mov    0x24(%ebx),%eax
0x06767230:	mov    %eax,-0x4(%ebx)
0x06767233:	mov    $0x34540,%esi
0x06767238:	add    $0xfffffff4,%ebx
0x0676723b:	mov    %ebx,0x44c(%edi)
0x06767241:	jmp    0x376c90
0x06767246:	mov    (%ebx),%eax      [get list from stack... (redundant!)]
0x06767248:	test   $0x1,%al
0x0676724b:	jne    0x67673ca
0x06767251:	movswl (%eax),%ecx
0x06767254:	cmp    $0x34,%ecx
0x0676725a:	jne    0x67673ca
0x06767260:	mov    0x4(%eax),%eax
0x06767263:	mov    %eax,-0x4(%ebx)
0x06767266:	add    $0xfffffffc,%ebx
0x06767269:	test   $0x1,%al
0x0676726c:	jne    0x6767389
0x06767272:	movswl (%eax),%ecx
0x06767275:	cmp    $0x34,%ecx
0x0676727b:	jne    0x6767389
0x06767281:	mov    0x4(%eax),%eax
0x06767284:	mov    %eax,%ecx
0x06767286:	mov    0x24(%ebx),%eax
0x06767289:	cmp    %ecx,%eax
0x0676728b:	jne    0x6767298
0x06767291:	mov    (%ebx),%eax
0x06767293:	jmp    0x6767384
0x06767298:	mov    0x10(%ebx),%eax
0x0676729b:	mov    0x8(%eax),%eax
0x0676729e:	mov    %eax,-0x4(%ebx)
0x067672a1:	mov    0x4(%ebx),%eax
0x067672a4:	mov    0x8(%eax),%eax
0x067672a7:	mov    %eax,-0x8(%ebx)
0x067672aa:	add    $0xfffffff8,%ebx
0x067672ad:	mov    0x4(%ebx),%ecx
0x067672b0:	cmp    %ecx,%eax
0x067672b2:	jne    0x67672e5
0x067672b8:	mov    $0x67675d8,%eax
0x067672bd:	mov    (%eax),%eax
0x067672bf:	mov    %eax,-0xc(%ebx)
0x067672c2:	mov    $0x67675dc,%eax
0x067672c7:	mov    (%eax),%eax
0x067672c9:	mov    %eax,-0x8(%ebx)
0x067672cc:	mov    0x30(%ebx),%eax
0x067672cf:	mov    %eax,-0x4(%ebx)
0x067672d2:	mov    $0x34540,%esi
0x067672d7:	add    $0xfffffff4,%ebx
0x067672da:	mov    %ebx,0x44c(%edi)
0x067672e0:	jmp    0x376c90
0x067672e5:	mov    (%ebx),%eax      [get list from stack... (redundant!)]
0x067672e7:	mov    %eax,-0x8(%ebx)  [... save it(!) to prep recursive call]
0x067672ea:	mov    0x4(%ebx),%eax   [get turtle from stack]
0x067672ed:	add    $0xfffffff8,%ebx [adjust stack pointer]
0x067672f0:	lea    0x64(%edi),%edx  [check whether other threads needs to run...]
0x067672f3:	mov    (%edx),%edx
0x067672f5:	cmp    $0x0,%edx
0x067672fb:	jle    0x6767312        [to slow: for thread swap]
0x067672fd:	mov    -0x1c(%ebp),%edx [argv = end of orig argv (tail call)]
0x06767300:	add    $0xffffffec,%edx  [... minus orig argc for args in-place]
0x06767303:	mov    %eax,0x10(%edx)  [set turtle argument for recur]
0x06767306:	mov    (%ebx),%eax      [load list back]
0x06767308:	mov    %eax,0xc(%edx)   [... and set list argument for recur]
0x0676730b:	mov    %edx,%ebx        [set Racket stack to argv]
0x0676730d:	jmp    0x676707a        [recur]

----------------------------------------
For comparsion, the gcc-compiled `assq' function's loop:

0x008c6480 <assq+112>:	mov    -0x20(%ebp),%edx   [get l off stack]
0x008c6483 <assq+115>:	test   $0x1,%dl
0x008c6486 <assq+118>:	jne    0x8c6523 <assq+275> [to fail: l is fixnum]
0x008c648c <assq+124>:	cmpw   $0x34,(%edx)
0x008c6490 <assq+128>:	jne    0x8c6523 <assq+275> [to fail: not a pair]
0x008c6496 <assq+134>:	mov    0x4(%edx),%ecx      [item = car of l]
0x008c6499 <assq+137>:	mov    %ecx,-0x1c(%ebp)    [save item on stack]
0x008c649c <assq+140>:	test   $0x1,%cl
0x008c649f <assq+143>:	jne    0x8c6588 <assq+376> [to fail: item is fixnum]
0x008c64a5 <assq+149>:	cmpw   $0x34,(%ecx)
0x008c64a9 <assq+153>:	jne    0x8c6588 <assq+376> [to fail: item is not pair]
0x008c64af <assq+159>:	mov    0xc(%ebp),%esi      [get x arg off stack]
0x008c64b2 <assq+162>:	mov    (%esi),%eax         [found x?]
0x008c64b4 <assq+164>:	cmp    0x4(%ecx),%eax
0x008c64b7 <assq+167>:	je     0x8c6648 <scheme_get_thread_local_variables>
0x008c64bd <assq+173>:	mov    0x8(%edx),%edx      [no, so get cdr of l]
0x008c64c0 <assq+176>:	mov    %edx,-0x20(%ebp)
0x008c64c3 <assq+179>:	test   $0x1,%dl
0x008c64c6 <assq+182>:	jne    0x8c6480 <assq+112>  [to fail: cdr is fixnum]
0x008c64c8 <assq+184>:	cmpw   $0x34,(%edx)
0x008c64cc <assq+188>:	jne    0x8c6480 <assq+112> [to fail: cdr is not a pair]
0x008c64ce <assq+190>:	mov    0x4(%edx),%ecx      [item = car l]
0x008c64d1 <assq+193>:	mov    %ecx,-0x1c(%ebp)    
0x008c64d4 <assq+196>:	test   $0x1,%cl
0x008c64d7 <assq+199>:	jne    0x8c6480 <assq+112> [fail: item is a fixnum]
0x008c64d9 <assq+201>:	cmpw   $0x34,(%ecx)
0x008c64dd <assq+205>:	jne    0x8c6480 <assq+112> [fail: item is not a pair]
0x008c64df <assq+207>:	mov    (%esi),%eax         [get x off stack]
0x008c64e1 <assq+209>:	cmp    0x4(%ecx),%eax      [car of item == x ?]
0x008c64e4 <assq+212>:	je     0x8c6648 <scheme_get_thread_local_variables>
0x008c64ea <assq+218>:	mov    0x8(%edx),%eax
0x008c64ed <assq+221>:	mov    %eax,-0x20(%ebp)
0x008c64f0 <assq+224>:	mov    -0x24(%ebp),%edx  [get turtle off stack]
0x008c64f3 <assq+227>:	cmp    %edx,%eax         [is l == turtle?]
0x008c64f5 <assq+229>:	je     0x8c6523 <assq+275> [to fail: cycle]
0x008c64f7 <assq+231>:	mov    0x8(%edx),%eax    [cdr of turtle]
0x008c64fa <assq+234>:	mov    %eax,-0x24(%ebp)  [save new turtle to stack]
0x008c64fd <scheme_get_thread_local_variables+0>:	mov    (%edi),%eax
0x008c64ff <scheme_get_thread_local_variables+2>:	mov    %gs:0x48(,%eax,4),%eax
0x008c6507 <assq+247>:	mov    0x68(%eax),%eax
0x008c650a <assq+250>:	test   %eax,%eax           [other threads need to run?]
0x008c650c <assq+252>:	jg     0x8c6480 <assq+112> [to slow: other threads run]
0x008c6512 <assq+258>:	movl   $0x4,-0x50(%ebp)
0x008c6519 <assq+265>:	call   0x9e44a0 <scheme_out_of_fuel>
0x008c651e <assq+270>:	jmp    0x8c6480 <assq+112>  [recur]

----------------------------------------

The `assq' wrapper that jumps to the above loop. The argument
juggling here --- turning the arg sequence `x l' to `l l l x'
--- may be part of the slowdown.

0x0037e41c:	cmp    $0x2,%ecx        [arity check]
0x0037e422:	jne    0x372e80
0x0037e428:	mov    %eax,-0x4(%ebx)  [save closure (but no GC possible!)]
0x0037e42b:	add    $0xfffffffc,%ebx
0x0037e42e:	mov    0x4(%ebx),%eax   [get x arg]
0x0037e431:	mov    %eax,-0x10(%ebx) [prep x arg to `loop']
0x0037e434:	mov    0x8(%ebx),%eax   [get l arg]
0x0037e437:	mov    %eax,-0xc(%ebx)  [prep l arg to `loop']
0x0037e43a:	mov    %eax,-0x8(%ebx)  [prep orig-l arg to `loop']
0x0037e43d:	mov    %eax,-0x4(%ebx)  [prep turtle arg to `loop']
0x0037e440:	mov    $0x37e47c,%esi
0x0037e445:	mov    (%esi),%esi      [esi now has `loop' closure pointer]
0x0037e447:	add    $0xfffffff0,%ebx [update Racket stack register]
0x0037e44a:	mov    -0x1c(%ebp),%edx [get Racket stack base for tail calls]
0x0037e44d:	add    $0xfffffff0,%edx [4 argument => subtract 16]
0x0037e450:	mov    0xc(%ebx),%ecx   [move arg1 into place...]
0x0037e453:	mov    %ecx,0xc(%edx)
0x0037e456:	mov    0x8(%ebx),%ecx
0x0037e459:	mov    %ecx,0x8(%edx)
0x0037e45c:	mov    0x4(%ebx),%ecx
0x0037e45f:	mov    %ecx,0x4(%edx)
0x0037e462:	mov    (%ebx),%ecx
0x0037e464:	mov    %ecx,(%edx)
0x0037e466:	mov    %edx,%ebx        [runstack = argv]
0x0037e468:	mov    %esi,%eax
0x0037e46a:	mov    $0x4,%ecx        [argc = 4]
0x0037e46f:	mov    %ebx,%edx        [argv = runstack (redundant!)]
0x0037e471:	jmp    0x0676707a

----------------------------------------
Then again, here's a comparable section of the gcc-compiled `assq'
function's preamble that cooperates with the GC and sets up the loop.

0x008c641f <scheme_get_thread_local_variables+0>:	mov    0x176c06(%ebx),%edi
0x008c6425 <scheme_get_thread_local_variables+6>:	mov    (%edi),%eax
0x008c6427 <scheme_get_thread_local_variables+8>:	mov    %gs:0x48(,%eax,4),%edx
0x008c642f <assq+31>:	mov    0x4(%edx),%edx
0x008c6432 <assq+34>:	mov    %edx,-0x54(%ebp)
0x008c6435 <scheme_get_thread_local_variables+0>:	mov    %gs:0x48(,%eax,4),%eax
0x008c643d <assq+45>:	lea    -0x54(%ebp),%edx
0x008c6440 <assq+48>:	mov    %edx,0x4(%eax)
0x008c6443 <assq+51>:	lea    0xc(%ebp),%eax
0x008c6446 <assq+54>:	mov    %eax,-0x4c(%ebp)
0x008c6449 <assq+57>:	lea    -0x1c(%ebp),%eax
0x008c644c <assq+60>:	mov    %eax,-0x48(%ebp)
0x008c644f <assq+63>:	lea    -0x24(%ebp),%eax
0x008c6452 <assq+66>:	mov    %eax,-0x44(%ebp)
0x008c6455 <assq+69>:	lea    -0x20(%ebp),%eax
0x008c6458 <assq+72>:	mov    %eax,-0x40(%ebp)
0x008c645b <assq+75>:	movl   $0x0,-0x1c(%ebp)
0x008c6462 <assq+82>:	movl   $0x0,-0x20(%ebp)
0x008c6469 <assq+89>:	movl   $0x0,-0x24(%ebp)
0x008c6470 <assq+96>:	mov    0xc(%ebp),%eax
0x008c6473 <assq+99>:	mov    0x4(%eax),%eax
0x008c6476 <assq+102>:	mov    %eax,-0x24(%ebp)
0x008c6479 <assq+105>:	mov    %eax,-0x20(%ebp)
0x008c647c <assq+108>:	nopl   0x0(%eax)

Note the NOP, which aligns the gcc-generated loop start. The JIT
doesn't try to align loop starts, because past experiments suggested
that it doesn't matter. That's worth another look.