The Weird Concept of Branchless Programming

Interesting article. I remember have solved a leetcode problem called "Trapping Rain Water" https://leetcode.com/problems/trapping-rain-water/descriptio...

On leetcode the "elegant" and fastest solution was something like this:

  class Solution {
  public:
    int trap(vector<int>& height) {
        int i = 1;
        int n = height.size();
        int j = n - 1;
        int leftmax = height[0];
        int rightmax = height[n - 1];
        int tw = 0;
        while (i <= j) {
            if (leftmax <= rightmax) {
                if (leftmax > height[i]) {
                    tw += leftmax - height[i];
                } else {
                    leftmax = height[i];
                }
                i++;
            } else {
                if (rightmax > height[j]) {
                    tw += rightmax - height[j];
                } else {
                    rightmax = height[j];
                }
                j--;
            }
        }
        return tw;
    }
  };

My solution was this:

  class Solution {
  public:
    int trap(const vector<int>& height) {
        int mx = 0;
        long long sum = 0;

        for (const auto h : height) {
            mx = max(mx, h);
            sum += mx - h;
        }

        int rMx = 0, h, i;

        for (i = height.size() - 1; (h = height[i]) != mx; --i) {
            rMx = max(h, rMx);
            sum += rMx;
        }

        return sum - (height.size() - 1 - i) * mx;
    }
  };

However, I compiled and run some benchmarks on my local machine, and it turned out while on average my solution was slower, but in the worst case it was beating that solultion. My solution was less sensitive to the random input and the degradation was far less dramatic, around 2x, while that solution degraded much much more. I also thought that it was probably caused by the fact that my solution seem to be more predictable for the CPU branch predictor than that one, despite that it iterates twice.