Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to optimize range checking for integer intervals symmetric around zero in C?

Is there any way to optimize the following line of C code (to avoid branching)?

if (i < -threshold || i > threshold) { 
    counter++; 
}

All variables are 16-bit signed integers. An optimized version should be highly portable.

like image 796
psihodelia Avatar asked Oct 27 '10 14:10

psihodelia


1 Answers

How about the following:

counter += (i < -threshold) | (i > threshold);

Assuming the original code was valid, then this should work too, in a portable way. The standard says that relational operators (<, > and so on) return an int equal to 1 on success, or 0 on failure.

Update

To answer Sheen's comment below, the following code:

int main()
{
    short threshold = 10;
    short i = 20;
    short counter = 0;
    
    counter += (i < -threshold) | (i > threshold);
    
    return 0;
}

results in the following disassembler on x86 using GCC, with no optimisations:

  push   %rbp
  mov    %rsp,%rbp
  movw   $0xa,-6(%rbp)
  movw   $0x14,-4(%rbp)
  movw   $0x0,-2(%rbp)
  movswl -4(%rbp),%edx
  movswl -6(%rbp),%eax
  neg    %eax
  cmp    %eax,%edx
  setl   %dl
  movzwl -4(%rbp),%eax
  cmp    -6(%rbp),%ax
  setg   %al
  or     %edx,%eax
  movzbw %al,%dx
  movzwl -2(%rbp),%eax
  lea    (%rdx,%rax,1),%eax
  mov    %ax,-2(%rbp)
  mov    $0x0,%eax
  leaveq 
  retq  
like image 94
Oliver Charlesworth Avatar answered Sep 28 '22 10:09

Oliver Charlesworth