Comment by colanderman | Hacker News Reader

Comment by colanderman | Hacker News Reader

Parent Full thread

I don't think anyone's mentioned that there are two functional benefits to Linus's version: testability and performance.

The author touched on testability. Dropping the "if" case eliminates one code path that may contain bugs.

But also, the revised code may perform a lot better if you're searching a lot of short lists. In that case, the target item has a large, though not likely, chance of being first in the list. This kills predictability of that "if" branch. Eliminating it can save ten cycles or so, possibly shaving 25% or so off the runtime of this function for short lists. (For large lists, the branch becomes predictable, and you start having cache issues due to the list's linked nature.)

My current side-project is an NES emulator. Nearly all my (non-algorithmic) performance enhancements have been of this nature: find some unpredictable branch nested inside a tight loop → eliminate the branch with "clever" logic → 25% performance gain on that loop.

(That there are no checks for "error" cases is a distraction. There aren't any in the original example either, because it's an example and the error cases aren't relevant to Linus's point.)

I agree partially w.r.t. testability of branchless code, but there's a flipside too: often the root cause of an edge case is in data-structure shape, so full coverage isn't necessarily sufficient. In other words, if an edge case is "folded into" the normal path via something like Linus' trick, you still need to actually test the case where (in this example) `head` is being removed, or else you aren't certain that the folding of cases is valid. And if you're testing that case, then you'll have full coverage of the original (branchy) code too.

Totally agree w.r.t. performance, though. Even if the branch is never taken, control flow can reduce the scope of other compiler optimizations.

Yes, this is a good point. I had thought of this too and somehow convinced myself that the "head" case disappeared (since the non-"head" case would fail if "indirect" weren't initialized properly), but I'll admit that's a shaky argument.

This comment thread was refreshing to read because it was technically enlightening, devoid of malice, and each party conceding arguments while expanding and clarifying places where it broke down or wasn't clear.

Something we can all strive for professionally and while commenting on HN.

I'd say branch mispredictions and cache misses are the two biggest factors to performance. Almost everything else is noise in comparison. I keep saying if your architecture doesn't account for these, you've wasted 90% of the CPU guaranteed.

I do the exact same techniques in my game engine (sadly proprietary) - even in JavaScript its dead easy to run circles around both Three.js and Babylon.js in terms of performance to the point I'm simply amazed at how fast JavaScript VMs can be if you really push them.

Eliminating branches, cache misses and allocations in the main loop yielded by far the biggest performance boost. (For the curious, we abused ArrayBuffers to guarantee contiguous memory allocations in JavaScript)

I'm not a low level programmer, so this is a honest question.

In the better version, why doesn't the while condition (that must be tested at least once) present predictability problems whereas the if check in parent does?

The first version had a while loop and a condition. On the other hand, the optimized version only has a while loop.

I can see that.

However, if I'm not mistaken, branches are costly only when they're mispredicted. Hence, the question (as I see it) is wether one can better predict the behavior of Linus' better version (which only has one conditional) or that presented above (where there's an early return condition followed by the while condition).

It seems to me that the version above (which has two conditionals but is not like Linus' worse version because it has an early return) should be similarly costly to predict. Consider the situations where either most of the calls are to remove the first element (A) or most of the calls aren't (B). Let's see what happens in these cases:

- On Linus' code, the while is evaluated the first time. In case A, the while is correctly predicted to exit the while, the swap is made and the function ends. In case B, where the while yields true many times before hitting our element, you should have to pay the cost of a misprediction when you finally find it.

- In the early return code above, the situation is... the same. In case A the early return if is predicted correctly to yield true, and the function ends. In case B, the early return if is correctly predicted to yield false and then the while predicts mostly trues until you finally hit your element, time at which you pay the same misprediction penalty than above.

So... aren't both functions similarly expensive in terms of branch misprediction costs? Am I fundamentally wrong on my understanding on this issue?

Thanks for the explanation!

Where is that early return you mention? I don't see the return keyword used in either examples. They both do the exact same while loop, but Linus' version adds a level of indirection to save a conditional later on. You're still touching the same memory in both cases so they should be identical in terms of cache misses.

From my understanding, the first version has two possible branch misprediction points while Linus' version only has one. This will probably only have a visible impact if the function is called in a loop however.

But to me the biggest advantage of the 2nd variant is its simplicity. This is the only way to stay sane with a growing codebase and keep shipping robust code.

Its no use getting a fast function if you can't integrate it optimally with the rest of the codebase. Raw performance isn't at the micro level but the macro one. This is where simplicity becomes critically important.

I was referring to the version in this thread's ancestor, which reads:

  remove_list_entry(entry)
  {
      if (head == entry) {
          head = head->next;
          return;
      }

      for (prev = head;  prev->next;  prev = prev->next) {
          if (prev->next == entry) {
              prev->next = prev->next->next;
              return;
          }
      }
  }

Reply on news.ycombinator.com