-3
\$\begingroup\$

The task is simple: Create an if-statement from scratch in x86 assembly that runs in as few clock-cycles as possible.

  • Must be x86 assembly.
  • Can't use any of the conditional jump/branch instructions (e.g. je, jne, jz, jg, jge, jl, jle).
  • Can use jmp to jump to existing blocks of code.
  • Can use cmp if necessary.
  • Can't call any external libraries or functions.
  • Can't use call.
  • Free to use any of the other available instructions in the Intel docs.
  • No C.
  • Any of the ~7 Intel Core architectures are acceptable (listed on page 10). Ideally Nehalem (Intel Core i7).
  • The if statement needs to check arbitrary conditions. Basically replicating the functionality of any one of the je, jge, etc. conditional jumps.

The winning answer is one that uses the fewest clock cycles possible. That is, it can have the most operations per second. Approximate clock cycle summaries are here: http://www.agner.org/optimize/instruction_tables.pdf. Calculating clock cycles can happen after the answer is posted.

Improve this question
\$\endgroup\$
3
  • 2
    \$\begingroup\$ , fastest-algorithm is about asymptotic complexity, which can't apply here because everything is O(1). \$\endgroup\$ Commented Jul 6, 2018 at 2:01
  • \$\begingroup\$ Now... what exactly does "equivalent to an if-statement" mean? Would something like jmp [eax] be ok? \$\endgroup\$ Commented Jul 6, 2018 at 2:59
  • \$\begingroup\$ The if statement needs to check arbitrary conditions. Basically replicating the functionality of any one of the je, jge, etc. conditional jumps. \$\endgroup\$ Commented Jul 6, 2018 at 3:05

2 Answers 2

Reset to default
4
\$\begingroup\$

And then I realised that we can be faster, and use no additional registers:

cmp eax, ebx
mov eax, offset false_case
mov ebx, offset true_case
cmove eax, ebx ;or cmovb, etc.
jmp eax
Improve this answer
\$\endgroup\$
2
\$\begingroup\$ 
xor ecx, ecx
mov edx, 1
cmp eax, ebx
cmove ecx, edx ;or cmovb, etc.
jmp [false + ecx*4]

false dd offset false_case
true  dd offset true_case

Accepts eax and ebx for the comparison.
Replace the cmov with the corresponding check to perform.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Wonderful, thank you so much for this bit. \$\endgroup\$ Commented Jul 6, 2018 at 19:12

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.