News for hackers. Stuff that matters.
Re:Interviewing programmers: coding test example explained by nkurz on Friday June 04, 2010 @05:31PM (#1405729)
I just tossed together a quick branchless version, and was a little surprised to see that it was significantly slower than the straightforward pointer version on random data: about 1.5x the cycles. Presumably this gap would narrow if checking for char_to_remove was less predictable.

Here's the code I tested. I think it works, but I barely checked it. I'm sure there are better ways to calculate 'increment'. Not sure if these would be enough to close the gap, though.

  void condense_by_removing_branchless(char *z_terminated,  char char_to_remove) { 
    char *condensed = z_terminated;
    while (*z_terminated) {
        *condensed = *z_terminated;
        int diff = *condensed - char_to_remove;
        int increment = -((diff | -diff) >> ((sizeof(int) * 8) - 1)); 
        condensed += increment;
        z_terminated++;
    }
    *condensed = 0;
  }

There are no comments on this comment yet.