Consider codegen improvement for (a + b)/2

[danmoseley]

This diff (in a hot path binary search) seemed to give an improvement (albeit so small probably not worth loss in clarity)

-                iMid = (i + iMax) / 2;
+                iMid = (i & iMax) + ((i ^ iMax) >> 1); 

Of course ideally the JIT would take care of whatever the best codegen is. @AndyAyersMS suggested I open an issue here.

dotnet/corefx#28739 (comment)
https://sharplab.io/#v2:EYLgHgbALANALiAhgZwLYB8ACBmABJgJlwGFcBvAWAChdb88BLAOzlwHkAnBgc2cQBsAFM1YMYuERICyiMAEpy1OsvwB2XMNwBqabIUB6XAQDcSugF8ztHBJa4AcgFMA7sLtjbomfMU0V19U0AMl0fHUFNAD1QhQA+WNwARjlTP1pLKnMgA=

[mikedn]

Just use (i + iMax) >> 1 and call it a day 😄

Note that this particular way of computing the midpoint is problematic due to integer overflow. I suppose this doesn't matter in that particular regex code...

[danmoseley]

Would it be considered an invalid transformation if it avoided integer overflow?

[mikedn]

Would it be considered an invalid transformation if it avoided integer overflow?

Indeed, this might work in the C/C++ wild west, where integer overflow tends to come together with undefined behavior. However, C# is different in this regard and mandates a certain behavior:

In an unchecked context, overflows are ignored and any high-order bits that do not fit in the destination type are discarded.

I'm not familiar with this fancy way of computing the midpoint but a quick test shows that it does produce a different result than (a + b) / 2:

static int BrokenMid(int a, int b) => (a + b) / 2;
static int BrokenSafeMid(int a, int b) => a + (b - a) / 2;
static int SafeMid(int a, int b) => (int)(a + (uint)(b - a) / 2);
static int FancyMid(int a, int b) => (a & b) + ((a ^ b) >> 1);
static void Main()
{
    int a = int.MinValue;
    int b = int.MaxValue;

    Console.WriteLine(BrokenMid(a, b));
    Console.WriteLine(BrokenSafeMid(a, b));
    Console.WriteLine(SafeMid(a, b));
    Console.WriteLine(FancyMid(a, b));
}

prints

0
-2147483648
-1
-1

Apparently it's equivalent to the safe version. And it has one extra integer operation.

[AntonLapounov]

As @mikedn mentioned above, for int division those two expressions are not equivalent. For instance, they give different results for (-1, 0) and (1, int.MaxValue) pairs.

[erozenfeld]

@danmosemsft Looks like this issue can be closed since the proposed transformation is not legal?