4 ms·

Here is the same code, without syntactic obfuscation: void condense_by_removing(char* s, char c) { char* d = s; while (d = s++) d += *d !=

Here is the same code, without syntactic obfuscation: void condense_by_removing(char* s, char c) { char* d = s; while (*d = *s++) d += *d != c; } I would have sworn I found a bug. There is none. Brilliant. Now, I wonder if we could further optimize it. For instance by accessing memory several bytes at a time, in a fashion similar to strcmp().

cperciva 16y ago
Optimizing for performance, sure. But I was trying to optimize for character count. :-)
- loup-vaillant 16y ago
  Yes, but in doing so, you traded a memory write for a branch. And memory accesses are linear, so that's likely faster than the cannon. So surely we could go further? That's how I got the idea.
  - Daniel_Newby 16y ago
    Many compilers will implement d += *d != c; with a branch, and depending on the data pattern the branch predictor will be bamboozled. The branchless version would involve a pair of subtractions and some bit banging.
    - loup-vaillant 16y ago
      Gasp! I thought it would be easy to just transfer the compare flag to a general purpose register. I suppose x86 doesn't have such an instruction?
      - Daniel_Newby 16y ago
        I lied! A quick test shows that GCC uses the x86 SETE instruction (set register on condition equal). Cool. However, code like this: if (x == 14) { y = 10; } else { y = 20; } uses branches, although I think x86-64 has conditional load instructions.
    - nkurz 16y ago
      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; }
gorrepati 16y ago
I get access violation with VC, when trying to see how this works. Works with gcc though. Can somebody throw some light on how this works?
- RiderOfGiraffes 16y ago
  void condense_by_removing(char* s, char c) { char* d = s; while (*d = *s++) d += *d != c; } It always does the copy, then evaluates *d!=c. If what it just copied is equal to the forbidden character this evaluates as false, which in C is 0, and hence d is left unchanged. If what it copied is not equal then this evaluates as true, which is 1, and hence d is incremented.
pbiggar 16y ago
I believe there is a bug here. If the first character is an instance of c, then it will still be copied. For example, calling the function as condense_by_removing ("loup-vailiant", 'l'), will return "loup-vaiiant", where it should return "oup-vaiiant". (I've not tested this though, I may be wrong.)

Here is the same code, without syntactic obfuscation: void condense_by_removing(char* s, char c) { char* d = s; while (*d = *s++) d += *d !=

cperciva 16y ago

Optimizing for performance, sure. But I was trying to optimize for character count. :-)

loup-vaillant 16y ago
Yes, but in doing so, you traded a memory write for a branch. And memory accesses are linear, so that's likely faster than the cannon. So surely we could go further? That's how I got the idea.
- Daniel_Newby 16y ago
  Many compilers will implement d += *d != c; with a branch, and depending on the data pattern the branch predictor will be bamboozled. The branchless version would involve a pair of subtractions and some bit banging.
  - loup-vaillant 16y ago
    Gasp! I thought it would be easy to just transfer the compare flag to a general purpose register. I suppose x86 doesn't have such an instruction?
    - Daniel_Newby 16y ago
      I lied! A quick test shows that GCC uses the x86 SETE instruction (set register on condition equal). Cool. However, code like this: if (x == 14) { y = 10; } else { y = 20; } uses branches, although I think x86-64 has conditional load instructions.
  - nkurz 16y ago
    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; }

gorrepati 16y ago

I get access violation with VC, when trying to see how this works. Works with gcc though. Can somebody throw some light on how this works?

RiderOfGiraffes 16y ago
void condense_by_removing(char* s, char c) { char* d = s; while (*d = *s++) d += *d != c; } It always does the copy, then evaluates *d!=c. If what it just copied is equal to the forbidden character this evaluates as false, which in C is 0, and hence d is left unchanged. If what it copied is not equal then this evaluates as true, which is 1, and hence d is incremented.

pbiggar 16y ago

I believe there is a bug here. If the first character is an instance of c, then it will still be copied. For example, calling the function as condense_by_removing ("loup-vailiant", 'l'), will return "loup-vaiiant", where it should return "oup-vaiiant". (I've not tested this though, I may be wrong.)