Fastest way to perform the equivalent of an if-statement in x86 assembly

-4

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.

Lance Pollard

Posted 2018-07-05T22:09:15.717

Reputation: 223

2, [tag:fastest-algorithm] is about asymptotic complexity, which can't apply here because everything is O(1). – user202729 – 2018-07-06T02:01:49.777

Now... what exactly does "equivalent to an if-statement" mean? Would something like jmp [eax] be ok? – user202729 – 2018-07-06T02:59:51.783

The if statement needs to check arbitrary conditions. Basically replicating the functionality of any one of the je, jge, etc. conditional jumps. – Lance Pollard – 2018-07-06T03:05:08.657

Answers

3

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

peter ferrie

Posted 2018-07-05T22:09:15.717

Reputation: 804

2

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.

peter ferrie

Posted 2018-07-05T22:09:15.717

Reputation: 804

Wonderful, thank you so much for this bit. – Lance Pollard – 2018-07-06T19:12:42.540