3
\$\begingroup\$

Languages, such as C++, have introduced a new comparison operator: <=>.

This operator returns -1, 0, or 1 when comparing two items together:

  • −1 means the left-hand side is smaller,
  •  0 when both values are equal,
  • +1 means the right-hand side is smaller.

Here is what I have been coming up with in x86-64:

556:    48 8b 15 d3 04 00 00    mov    0x4d3(%rip),%rdx        # 0xa30 (left handside)
55d:    33 c0                   xor    %eax,%eax
55f:    48 3b 15 9a 04 00 00    cmp    0x49a(%rip),%rdx        # 0xa00 (right handside)
566:    74 08                   je     0x570
568:    0f 9f c0                setg   %al
56b:    d1 e0                   shl    %eax
56d:    48 ff c8                dec    %rax
570:    48 89 45 90             mov    %rax,-0x70(%rbp)        # output

The mov and cmp instructions are not important here since these could as well all be registers. At some point, though, you would have had to load those registers. They are there to show all the details. So my code uses five instructions at the moment.

The final result is expected to be a 64 bits integer.

Two challenges:

  • Reduce the number of instructions
  • Avoid the need for a branch without increasing the number of instructions

The top winner is the one with the smallest number of instructions. Eliminating the branch adds a bonus point. So two answers with the same number of instructions, the one without a branch wins.


: The C++ and possibly other implementations of <=> do not mandate specific values, but refer to the sign. The C++ implementation of <=> returns any negative value, a (mathematically speaking) sign-less value (i. e. 0 [zero]), or any positive value.

\$\endgroup\$
10
  • \$\begingroup\$ In what way is the cmp instruction “not important” to implementing a comparator? (Our default I/O methods allow writing a complete function but not a snippet.) \$\endgroup\$ Commented Mar 13, 2023 at 4:02
  • \$\begingroup\$ What is the winning condition? What is the relation between the two challenges? \$\endgroup\$ Commented Mar 13, 2023 at 4:03
  • \$\begingroup\$ @AndersKaseorg It's not important in the challenge. Of course, there is going to be a cmp instruction. \$\endgroup\$ Commented Mar 13, 2023 at 4:04
  • 4
    \$\begingroup\$ My point is that if one can get a better score simply by deciding certain instructions are “not important”, then you don’t have an objective winning criterion. The number of instructions in a complete function is an objective criterion. The number of “important” instructions in a snippet is not. \$\endgroup\$ Commented Mar 13, 2023 at 4:06
  • 3
    \$\begingroup\$ @AlexisWilke "especially if the branch was eliminated." is quite vague. Suppose there is a solution with 3 instructions and a branch, and a solution with 4 instructions with no branch. Which one win? \$\endgroup\$ Commented Mar 13, 2023 at 4:26

4 Answers 4

3
\$\begingroup\$

If you specifically want to return -1, 0 or 1 as a 64-bit integer, then I believe you can follow your cmp instruction with a sequence such as this:

0:  0f 9f c0                setg   al
3:  0f 9c c1                setl   cl
6:  28 c8                   sub    al, cl
8:  48 0f be c0             movsx  rax, al

The final 64-bit value can be stored in any register, not just rax of course.

\$\endgroup\$
3
\$\begingroup\$

Comparing unsigned integers can be done in three instructions:

0:  0f 97 c1                seta   cl
3:  48 19 c0                sbb    rax, rax
6:  08 c8                   or     al, cl
\$\endgroup\$
2
\$\begingroup\$

Assuming I can use non-instruction data for free, this can be done in 3 extra instructions:

    xor %rax,%rax
    cmp %rsi,%rdi // assume this is free
    cmovl s2,%rax
    cmovg s1,%rax

// in another section
s1: .long 1, 0
s2: .long -1, -1

Demo on Godbolt, which has another approach that uses constant data.

\$\endgroup\$
3
  • \$\begingroup\$ Oh, interesting and you don't actually need the xor since you load the entire register with the cmov. That means you have 3 instructions! \$\endgroup\$ Commented Mar 14, 2023 at 4:22
  • 1
    \$\begingroup\$ @AlexisWilke You need it, as rax simply won't change if neither cmov is run (and may contain garbage instead of 0). \$\endgroup\$
    – Bubbler
    Commented Mar 14, 2023 at 4:27
  • \$\begingroup\$ Marking your answer as the winner since you found an answer with just 3 instructions! Although I think the answers by Neil are better for a compiler. Either way I like all those answers better than what I came up with. \$\endgroup\$ Commented Mar 14, 2023 at 23:01
2
\$\begingroup\$
cmp esi, edi
seta al
sbb al, 0
movsx rax, al

Like Neil's but I found after writing

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.