Bit Twiddle & Branch Removal

Performance Tuning
#1

These are more interesting for other languages since the JDK does not do a good job of inline/reg-alloc & schedule.



public static final int clampPositive(int a)
{
  // return (a >= 0) ? a : 0;
  return a & ~(a >> 31); 
}

public static final int abs(int a)
{
  // return (a >= 0) ? a : -a;
  int s = a >> 31;
  a ^= s;
  a -= s;
  return a;
}

public static final int min(int a, int b)
{
  // return (a <= b) ? a : b;
  a -= b;
  a &= (a >> 31);
  a += b;

  return a;
}

public static final int max(int a, int b)
{
  // return (a >= b) ? a : b;
  a -= b;    
  a &= ~(a >> 31);
  a += b;    

  return a;
}

public static final int select(int a, int b, int c, int d)
{
  // return (a<b) ?c : d
  return (((a-b)>>31) & (c^d))^d;
}

public static final int sgn(int a)
{
  // return (a > 0) ? 1 : (a < 0) ? -1 : 0;
  return (-a >>> 31) | (a >> 31);
}
#2

I especially like sgn(…) ;D
Surely that must be faster than the 1.5 branches needed ordinarily?

#3

AFAIK, the shifts are some expensive for Java …

#4

The shifts are JVM opcodes and the cost will be strongly related to the hardware cost of performing a shift.

#5

At that level of execution, it’s more about what (surrounding) native code the JIT generates, not so much the cost of the single instruction.

#6

This is a different issue related to the execution of a sequence of instructions and is what my opening comment was attempting to say. As individual operations, shifts are very fast.

#7

??? That’s equivalent to

return (a >= 0) ? 0 : -1;
#8

Indeed; classic case of TGTBT =)

Also, clampPositive is doing more work than it needs to.


public static final int clampPositive(int a)
{
  // return (a >= 0) ? a : 0;
  return a & ~(a >> 31); 
}
#9

Classic case of screwing up when deleting a cast from C. Nuked the negate. And yeah, the &= should just be and.

(edit: I update the original code to reflect these changes)

#10

Can’t that one just be:

return (a >>> 31) ^ 1

Edit: that was for sgn(a), incase it wasn’t clear

#11

sgn(int) => [-1, 0, +1]

Your code returns either a 0 or 1, never -1

#12

I blame it on the early morning. First I thought sgn returned 1 or -1 only, then I was working in 1’s complement instead of 2’s complement. Duh.