Hacker News Reader

Comment by cperciva | Hacker News Reader

I'm sure RiderOfGiraffes doesn't want a third entry from me at this point, so I figure I might as well just post it here:

  #define C	char
  #define F	for
  #define R	condense_by_removing
  #define V	void

  V R(C*A,C B){F(C*J=A;*J=*A++;J+=*J!=B);}

or without #defines:

  void condense_by_removing(char*A,char B){for(char*J=A;*J=*A++;J+=*J!=B);}

View on HN

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().

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

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.

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.

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?

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.

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;
  }

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?

  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.

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.)

By all means send it in - it will be interesting to compare it against the others.

Reply on news.ycombinator.com