Re: Comparing lowtags: slightly inefficient assembly code

Thank you very much!

As I said, I couldn't tell whether the bit shifts are actually a problem,
without comparing the sub-optimal code to the optimal one. (Maybe it's even
faster to XOR the objects and then mask the result with 15.)

The other intention of writing my original email was to point out a
possible improvement to the compiler.

Vasily Postnicov <[email protected]> schrieb am Do., 1. Mai 2025,
06:55:

> This can be an example (I do not guarantee correctness of this):
>
> (sb-c:defknown foo (t t) boolean
>     (sb-c:movable sb-c:foldable sb-c:flushable))
>
> (sb-c:define-vop (foo)
>   (:args (x :scs (sb-vm::any-reg sb-vm::descriptor-reg))
>          (y :scs (sb-vm::any-reg sb-vm::descriptor-reg)))
>   (:arg-types * *)
>   (:translate foo)
>   (:temporary (:sc sb-vm::unsigned-reg :from (:argument 0)) t1)
>   (:temporary (:sc sb-vm::unsigned-reg :from (:argument 1)) t2)
>   (:conditional :z)
>   (:save-p :compute-only)
>   (:policy :fast-safe)
>   (:generator
>    0
>    (sb-c:move t1 x)
>    (sb-c:move t2 y)
>    (sb-c::inst sb-c::and t1 sb-vm:other-pointer-lowtag)
>    (sb-c::inst sb-c::and t2 sb-vm:other-pointer-lowtag)
>    (sb-c::inst sb-x86-64-asm::cmp t1 t2)))
>
> (defun foo (x y)
>   (foo x y))
>
> Disassemble:
>
> ; disassembly for FOO
> ; Size: 39 bytes. Origin: #x1000C78D3F                        ; FOO
> ; 3F:       498B4510         MOV RAX, [R13+16]                ;
> thread.binding-stack-pointer
> ; 43:       488945F8         MOV [RBP-8], RAX
> ; 47:       498BC0           MOV RAX, R8
> ; 4A:       488BF7           MOV RSI, RDI
> ; 4D:       4883E00F         AND RAX, 15
> ; 51:       4883E60F         AND RSI, 15
> ; 55:       4839F0           CMP RAX, RSI
> ; 58:       498D5424C8       LEA RDX, [R12-56]                ; T
> ; 5D:       490F45D4         CMOVNE RDX, R12                  ; NIL
> ; 61:       C9               LEAVE
> ; 62:       F8               CLC
> ; 63:       C3               RET
> ; 64:       CC0F             INT3 15                          ; Invalid
> argument count trap
>
> Examples:
>
> CL-USER> (foo 3.0 5434.32)
> T
> CL-USER> (foo 3.0 5434/32)
> NIL
> CL-USER> (foo 3.0 3d0)
> NIL
> CL-USER> (foo '(1 2 3) '(4 5 6))
> T
> CL-USER> (foo (make-array 3) "dsfsd")
> T
> CL-USER> (foo (make-array 3) (make-hash-table))
> NIL
> CL-USER> (foo (make-hash-table) (make-hash-table))
> T
>
> This example must be improved to correctly handle fixnums. Also I doubt
> that 2 additional SHLs can be a bottleneck. Are you sure they are?
>
> ср, 30 апр. 2025 г. в 21:18, David Scherfgen <[email protected]>:
>
>> Thanks for the hint!
>> Can I define VOPs in my application's source code, or do I have to modify
>> SBCL itself?
>> The article you linked mentions it's possible to do it at "runtime", but
>> then says it's a bit "hairy".
>>
>> Regarding EQ/EQL/...: The comparison that's being done, unfortunately,
>> cannot rely on any of these. The comparison logic is a bit intricate.
>>
>> Am Mi., 30. Apr. 2025 um 22:48 Uhr schrieb Vasily Postnicov <
>> [email protected]>:
>>
>>> It's adding the fixnum's tag by shifting left.
>>>
>>> My guess would be to write a function which translates directly to a
>>> VOP. You can write any assembly code you wish there. See here for an
>>> example:
>>> https://pvk.ca/Blog/2014/08/16/how-to-define-new-intrinsics-in-sbcl/
>>>
>>> On the other hand, I'd recommend EQ/EQL/EQUAL/EQUALP for comparing
>>> objects whose types aren't known to be anything more narrow than T.
>>>
>>> ср, 30 апр. 2025 г., 23:03 David Scherfgen via Sbcl-help <
>>> [email protected]>:
>>>
>>>> The purpose of this code is to provide an "early exit" in a function
>>>> that compares two objects X and Y - it's the #1 function in terms of number
>>>> of calls and execution time in the application (determined by deterministic
>>>> and statistical profiling). If X and Y have different lowtags, then the
>>>> function can abort immediately. I can't tell whether the extra bit shifts
>>>> cause significant performance issues, I'd have to compare it to the
>>>> "optimal" code, but that's a bit difficult in practice.
>>>>
>>>> Am Mi., 30. Apr. 2025 um 21:51 Uhr schrieb Stas Boukarev <
>>>> [email protected]>:
>>>>
>>>>> Is that causing you some unexpected performance issues?
>>>>>
>>>>> On Wed, Apr 30, 2025 at 10:50 PM David Scherfgen via Sbcl-help
>>>>> <[email protected]> wrote:
>>>>> >
>>>>> > Hello,
>>>>> >
>>>>> > I have this SBCL-specific code to determine whether two objects X
>>>>> and Y have the same lowtag:
>>>>> >
>>>>> > (defun same-lowtag-p (x y)
>>>>> >   (= (sb-kernel:lowtag-of x) (sb-kernel:lowtag-of y)))
>>>>> >
>>>>> > The relevant part of the disassembly:
>>>>> >
>>>>> > MOV RDX, R8
>>>>> > SHL RDX, 1
>>>>> > AND EDX, 30
>>>>> > MOV RDI, RSI
>>>>> > SHL RDI, 1
>>>>> > AND EDI, 30
>>>>> > CMP RDI, RDX
>>>>> >
>>>>> > It shifts the address of X and Y to the left by 1 bit, then masks
>>>>> with 30 (= 15 << 1), then compares.
>>>>> > The bit shift is unnecessary. It could mask X and Y with 15 and
>>>>> directly compare without shifting.
>>>>> >
>>>>> > Is there any (hacky, using internals) way to modify the Lisp
>>>>> function so that it results in optimal assembly without bit shifts?
>>>>> >
>>>>> > Thank you.
>>>>> >
>>>>> > Best regards
>>>>> > David Scherfgen
>>>>> > _______________________________________________
>>>>> > Sbcl-help mailing list
>>>>> > [email protected]
>>>>> > https://lists.sourceforge.net/lists/listinfo/sbcl-help
>>>>>
>>>> _______________________________________________
>>>> Sbcl-help mailing list
>>>> [email protected]
>>>> https://lists.sourceforge.net/lists/listinfo/sbcl-help
>>>>
>>>

_______________________________________________
Sbcl-help mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/sbcl-help