[Sbcl-devel] Faster FIND and POSITION in unsafe code

[Douglas Katzman]

Hi all,

After eons of having our own homebrew FIND (in about 1.5e2 variations), I've implemented in 'seqtran' what we feel to be a reasonable replacement.  Attached is the patch.

But is it a known bug that the reduction of EQL to EQ is not commutative?

I discovered that in connection with the aforementioned patch.

It turns out that (FIND (THE FIXNUM X) (THE LIST L)) still uses GENERIC-EQL and we'd like it not to, without having to write :TEST #'EQ.

To wit:

* (disassemble '(lambda (x y) (eql x (the fixnum y))))

; disassembly for (LAMBDA (X Y))

; Size: 24 bytes

; 04ACCA0F:       4839FA           CMP RDX, RDI               ; no-arg-parsing entry point

;       12:       BA17001020       MOV EDX, 537919511

;       17:       41BB4F001020     MOV R11D, 537919567

;       1D:       490F44D3         CMOVEQ RDX, R11

...

* (disassemble '(lambda (x y) (eql (the fixnum x) y)))

; in: LAMBDA (X Y)

;     (EQL (THE FIXNUM SB-C::X) SB-C::Y)

; 

; note: forced to do GENERIC-EQL (cost 10)

;       unable to do inline fixnum comparison (cost 4) because:

;       The second argument is a T, not a FIXNUM.

; 

; compilation unit finished

;   printed 1 note

; disassembly for (LAMBDA (X Y))

; Size: 31 bytes

; 04AFA5BF:       488D0C2550040020 LEA RCX, [#x20000450]      ; GENERIC-EQL

                                                              ; no-arg-parsing entry point

;       C7:       FFD1             CALL RCX

;       C9:       BA17001020       MOV EDX, 537919511

;       CE:       41BB4F001020     MOV R11D, 537919567

;       D4:       490F44D3         CMOVEQ RDX, R11

... 

[Douglas Katzman]

to answer two of my own questions:

1) In the deftransform of eql it's a mistake to use COMMUTATIVE-ARG-SWAP to perform the switching of x,y since the latter might call give-up.

Probably better to write out the should-args-be-swapped test by hand:

diff --git a/src/compiler/srctran.lisp b/src/compiler/srctran.lisp

index f6369e6..89b2f5a 100644

--- a/src/compiler/srctran.lisp

+++ b/src/compiler/srctran.lisp

@@ -3715,10 +3715,10 @@

         ((and (csubtypep x-type char-type)

               (csubtypep y-type char-type))

          '(char= x y))

-        ((or (fixnum-type-p x-type) (fixnum-type-p y-type))

-         (commutative-arg-swap node))

         ((or (eq-comparable-type-p x-type) (eq-comparable-type-p y-type))

-         '(eq x y))

+ (if (and (constant-lvar-p x) (not (constant-lvar-p y)))

+     '(eq y x)

+     '(eq x y)))

         ((and (not (constant-lvar-p y))

               (or (constant-lvar-p x)

                   (and (csubtypep x-type y-type)

2) the index variable isn't actually elided in the fast code, it's that (a) I left out an INCF and (b) you no longer see a call to GENERIC-+

That's what I get for testing only with calls that don't need the index...

[Paul Khuong]

Douglas Katzman wrote:
> to answer two of my own questions:
>
> 1) In the deftransform of eql it's a mistake to use COMMUTATIVE-ARG-SWAP
> to perform the switching of x,y since the latter might call give-up.
> Probably better to write out the should-args-be-swapped test by hand:
>
> diff --git a/src/compiler/srctran.lisp b/src/compiler/srctran.lisp
> index f6369e6..89b2f5a 100644
> --- a/src/compiler/srctran.lisp
> +++ b/src/compiler/srctran.lisp
> @@ -3715,10 +3715,10 @@
> ((and (csubtypep x-type char-type)
> (csubtypep y-type char-type))
> '(char= x y))
> - ((or (fixnum-type-p x-type) (fixnum-type-p y-type))
> - (commutative-arg-swap node))
> ((or (eq-comparable-type-p x-type) (eq-comparable-type-p y-type))
> - '(eq x y))

> +(if (and (constant-lvar-p x) (not (constant-lvar-p y)))

> +'(eq y x)
> +'(eq x y)))
> ((and (not (constant-lvar-p y))
> (or (constant-lvar-p x)
> (and (csubtypep x-type y-type)

That part was committed in 9ce27ba (Exploit specialised VOPs for EQL of
anything/constant fixnum).

Thank you,

Paul Khuong

------------------------------------------------------------------------------
Try New Relic Now & We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service
that delivers powerful full stack analytics. Optimize and monitor your
browser, app, & servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may
_______________________________________________
Sbcl-devel mailing list
Sbcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel

[Douglas Katzman]

Would you believe that this EQL transform ruins my FOO example from the unboxed >32-bit constants patch?

It's consing now and it wasn't before.  Roll back this patch and we get the expected result.

How would one go about writing a unit test that asserts that this doesn't happen?

Martin suggests disassembling to a string stream and comparing literally the instruction sequence.

I've already nearly hacked up something to eliminate the address column, which, incidentally, displays addresses truncated anyway (apropos of nothing).

(disassemble '(lambda (x)

  (declare (fixnum x) (optimize speed (safety 0)))

  (zerop (logxor (ldb (byte 64 0) x) #xffffffff80aabbcc))))

; in: LAMBDA (X)

;     (ZEROP (LOGXOR (LDB (BYTE 64 0) SB-C::X) 18446744071573257164))

; --> = IF = EQL IF EQL EQ IF

; ==>

;   (EQ SB-C::X SB-C::Y)

;

; note: doing unsigned word to integer coercion (cost 20), for:

;       the first argument of IF-EQ

;

; compilation unit finished

;   printed 1 note

; disassembly for (LAMBDA (X))

; Size: 64 bytes

; 033FC642:       4881F2CCBBAA80   XOR RDX, -2136294452       ; no-arg-parsing entry point

;       49:       48B900000000000000C0 MOV RCX, -4611686018427387904

;       53:       4885D1           TEST RDX, RCX

;       56:       488D0C12         LEA RCX, [RDX+RDX]

;       5A:       740E             JEQ L0

;       5C:       488BCA           MOV RCX, RDX

;       5F:       4C8D1C25D9080020 LEA R11, [#x200008D9]      ; ALLOC-UNSIGNED-BIGNUM-IN-RCX

;       67:       41FFD3           CALL R11

;       6A: L0:   4885C9           TEST RCX, RCX

;       6D:       BA17001020       MOV EDX, 537919511

;       72:       41BB4F001020     MOV R11D, 537919567

;       78:       490F44D3         CMOVEQ RDX, R11

;       7C:       488BE5           MOV RSP, RBP

;       7F:       F8               CLC

;       80:       5D               POP RBP

;       81:       C3               RET

[Paul Khuong]

Douglas Katzman wrote:
> Would you believe that this [commit 9ce27ba] EQL transform ruins my FOO example from the

> unboxed >32-bit constants patch?
> It's consing now and it wasn't before. Roll back this patch and we get
> the expected result.

Likely a missing VOP (or bad cost info…). I'll look into it tomorrow
morning, after the SSE stuff.

> How would one go about writing a unit test that asserts that this
> doesn't happen?
> Martin suggests disassembling to a string stream and comparing literally
> the instruction sequence.

I believe that's what we currently do.

[Douglas Katzman]

EQL has a boatload of templates:

* (length (fun-info-templates (info :function :info 'eql)))

13

EQ has only one template, in particular nothing for any non-descriptor arg types. Fascinating.

* (fun-info-templates (info :function :info 'eq))

(#<VOP-INFO

   :NAME IF-EQ

   :ARG-TYPES (* *)

   :RESULT-TYPES (:CONDITIONAL :E)

   :LTN-POLICY :FAST-SAFE

   :COST 3>)

[Paul Khuong]

Douglas Katzman wrote:
> On Tue, May 21, 2013 at 1:50 AM, Paul Khuong <p...@pvk.ca
> <mailto:p...@pvk.ca>> wrote:
>
> Douglas Katzman wrote:
>
> Would you believe that this [commit 9ce27ba] EQL transform ruins
> my FOO example from the
> unboxed >32-bit constants patch?
> It's consing now and it wasn't before. Roll back this patch and
> we get
> the expected result.
>
>
> Likely a missing VOP (or bad cost info…). I'll look into it tomorrow
> morning, after the SSE stuff.

> EQL has a boatload of templates:
> * (length (fun-info-templates (info :function :info 'eql)))
> 13
>
> EQ has only one template, in particular nothing for any non-descriptor
> arg types. Fascinating.
> * (fun-info-templates (info :function :info 'eq))
> (#<VOP-INFO
> :NAME IF-EQ
> :ARG-TYPES (* *)
> :RESULT-TYPES (:CONDITIONAL :E)
> :LTN-POLICY :FAST-SAFE
> :COST 3>)
>

Fixed on x86 and x86-64 in 09f925d (Implement EQ of unboxed characters
and small integers on x86oids).

EQ presents the reverse situation of EQL: we try very hard in EQL to
detect when we can perform an EQ check... For EQ, we need to determine
when it makes sense to perform unboxed comparisons instead of the
fallback generic comparison. I believe it's most important for
characters and word-sized integers, with and without constants: these
are the cases that the compiler recognises. In fact, now that IR1
consistently downgrades EQL into EQ for EQ-comparable types, it might
make sense to remove some of the generic-EQL VOPs. In the meantime, the
commit simply marks a few EQL VOPs as also applicable for EQ.

* (disassemble '(lambda (x)

(declare (fixnum x) (optimize speed (safety 0)))
(zerop (logxor (ldb (byte 64 0) x) #xffffffff80aabbcc))))

; disassembly for (LAMBDA (X))
; Size: 31 bytes
; 039CFCC2: 4881F2CCBBAA80 XOR RDX, -2136294452 ;
no-arg-parsing entry point
; C9: 4885D2 TEST RDX, RDX ; This remaining test
still bothers me (:
; CC: BA17001020 MOV EDX, 537919511
; D1: 41BB4F001020 MOV R11D, 537919567
; D7: 490F44D3 CMOVEQ RDX, R11
; DB: 488BE5 MOV RSP, RBP
; DE: F8 CLC
; DF: 5D POP RBP
; E0: C3 RET

[Nikodemus Siivola]

On 21 May 2013 08:40, Douglas Katzman <do...@google.com> wrote:

> Would you believe that this EQL transform ruins my FOO example from the
> unboxed >32-bit constants patch?
> It's consing now and it wasn't before. Roll back this patch and we get the
> expected result.
>
> How would one go about writing a unit test that asserts that this doesn't
> happen?
> Martin suggests disassembling to a string stream and comparing literally the
> instruction sequence.

I realize this was already partially answered elsewhere, but see also
assert-no-consing, and count-full-calls, etc in
tests/compiler-test-utils.lisp

[Douglas Katzman]

So back to the original issue, can we agree that the 'index' variable in find/position may be declared as type 'index' regardless of compilation policy?

By doing so, there is a failure mode which is purely theoretical: safe code can overflow the INDEX to a bignum before circularity is detected. However, for that to happen, a list would need almost most-positive-fixnum items in it prior to a cyclical piece, and then a cycle; slow and fast would not meet all the while that index is being bumped to its highest legal value; and then you need to iterate over the cycle to find that the pointers meet, at which point index is too large.

For all intents and purposes this can not happen- memory will be exhausted while constructing a list which proves that the type violation exists.

Attached is a patch I have tried (unlike my previous one, sorry about that) for both find and position with high safety and no safety.

It's mostly whitespace, removal of the 'fast' pointer for no safety, and the fixnum declaration.

Under separate cover I will send mail on a related additional problem as well as a tangential one I found while looking into it this.

I'd prefer the other remaining issue not muddle the question of whether we can avoid generic-+ here.  Regards.

-d

On Wed, May 8, 2013 at 5:54 PM, Douglas Katzman <do...@google.com> wrote: