Re: [Sbcl-devel] Faster DOLIST macro

[Teemu K. <ch...@s2...>]

Christophe Rhodes <cs...@ca...> writes:

> "Paul F. Dietz" <di...@dl...> writes:
> 
> > My microbenchmark does show that the modified dolist gives a faster assq,
> > though:
> 
> > * (disassemble 'old-assq-opt)
> >
> > ; 094917BE:       MOV EAX, EDI                ; no-arg-parsing entry point
> > ;       C0:       JMP L2
> > ;       C2: L0:   MOV ECX, [EAX-3]  ; ECX = CAR
> > ;       C5:       MOV EBX, [ECX-3]  ; EBX = CAAR
> > ;       C8:       CMP EBX, EDX      ; EQ test
> > ;       CA:       JEQ L4
> > ;       CC: L1:   MOV EAX, [EAX+1]  ; EAX = CDR
> > ;       CF: L2:   CMP EAX, 83886091 ; is the alist/next step NIL?
> > ;       D4:       JNE L0
> [...]
> > ;       EA: L4:   CMP EBX, 83886091 ; is the pair NIL?
> > ;       F0:       JEQ L1
> 
> > * (disassemble 'my-assq-opt)
> >
> > ; 094918BE:       MOV EAX, EDI                ; no-arg-parsing entry point
> > ;       C0:       JMP L2
> > ;       C2: L0:   MOV ECX, [EAX-3]  ; ECX = CAR
> > ;       C5:       MOV EAX, [EAX+1]  ; EAX = CDR
> > ;       C8:       MOV EBX, [ECX-3]  ; EBX = CAAR
> > ;       CB:       CMP EBX, EDX      ; EQ test
> > ;       CD:       JNE L2
> > ;       CF:       CMP ECX, 83886091 ; is the pair NIL?
> > ;       D5:       JEQ L2
> [...]
> > ;       E8: L2:   CMP EAX, 83886091 ; is the alist NIL?
> > ;       ED:       JNE L0
> 
> I'm no x86 expert, but I think these two segments are the inner loops
> of the two routines.  Here is really where we need an x86 expert,
> though, because I'm now going to have to resort to guesses: there are
> two differences between the compiled code that I can see: one is that
> in MY-ASSQ-OPT the branch to the extra test against NIL is closer to
> the main loop; the other is that the order of accessing CDR and CAAR
> (ECX and EBX) is potentially more pipeline-friendly in MY-ASSQ-OPT --
> there's a one instruction delay between getting ECX and using it.
> 
> Before I go any further, am I right so far?

I'd say the memory access ordering is the main optimization in the
second version, it seems significant.  The second version does two
branches per loop instead of the one per loop for the first, but for
modern processors branch prediction will make that difference go away.

Your reading of the code is correct.

For what it's worth, I've given up assembly programming ages ago, but
I still think I know what I'm talking about.

-- 
Teemu Kalvas