Performance decrease with `-boundscheck=off`

[JohanEngelen]

The following code performs (a lot) worse with -boundscheck=off (ldc2 -release -O3):

module cmpBench;

import std.algorithm;
import std.range;
import std.stdio;
import std.traits;

void insertionSort(Range, Less)(Range r, Less l)
if (hasLength!Range && isRandomAccessRange!Range && hasSlicing!Range)
{
   foreach (immutable i; 1 .. r.length)
   {
      bringToFront(
            r[0 .. i].assumeSorted!((a,b) => l(a, b)).upperBound(r[i]),
            r[i .. i + 1]);
   }
}

struct Pair(T, U = T)
{
   T f;
   U s;

   this(const T a, const U b)
   {
      f = a;
      s = b;
   }

   bool opEquals(ref const Pair r) const
   {
      return f == r.f && s == r.s;
   }
}

alias IntPair = Pair!int;
alias IntPairPair = Pair!IntPair;

bool lt(int l, int r)
{
   return l < r;
}

bool lt(T, U)(ref const Pair!(T, U) l, ref const Pair!(T, U) r)
{
   if (l.f != r.f) return lt(l.f, r.f);
   return lt(l.s, r.s);
}

struct La(T)
{
   bool opCall(ref const T l, ref const T r) const
   {
      return lt(l, r);
   }
}


struct Ld(T)
{
   bool opCall(ref const T l, ref const T r) const
   {
      return lt(r, l);
   }
}

void main()
{
   enum N = 10;
   enum S = 1000;

   IntPairPair[] v;
   v.reserve(24 * S);
   for (auto i = 0; i < S; i++)
   {
      v ~= IntPairPair(IntPair(i + 0, i + 1), IntPair(i + 2, i + 3));
      v ~= IntPairPair(IntPair(i + 0, i + 1), IntPair(i + 3, i + 2));
      v ~= IntPairPair(IntPair(i + 0, i + 2), IntPair(i + 1, i + 3));
      v ~= IntPairPair(IntPair(i + 0, i + 2), IntPair(i + 3, i + 1));
      v ~= IntPairPair(IntPair(i + 0, i + 3), IntPair(i + 1, i + 2));
      v ~= IntPairPair(IntPair(i + 0, i + 3), IntPair(i + 2, i + 1));

   }

   La!IntPairPair la;
   Ld!IntPairPair ld;
   for (auto i = 0; i < N; i++)
   {
      insertionSort(v, la);
      insertionSort(v, ld);
   }

   writeln(v[v.length / 2].f.f);
}

Found on the D forums: https://forum.dlang.org/post/wfackprjkbyxqheszvvx@forum.dlang.org

[kinke]

This appears to be an LLVM optimizer issue. I can reproduce it with master on Linux x64, the -boundscheck=off variant is nearly perfectly half as fast (for the original testcase). When comparing the unoptimized IR between -release and -release -boundscheck=off, the only difference is, as expected, some omitted bounds checks in the latter.

[kinke]

cough I think I messed things up. I tested this on Linux because I was too lazy to figure out the time equivalent for the Windows command line (just in case: powershell -c Measure-Command {<command>}). I.e., with LLVM 4.0.
I then compared the IR on Windows though IIRC - with LLVM 3.9.1.

I just tested the original testcase on Win64 with LLVM 3.9.1, and there's no measurable runtime difference between the 2 variants (matching the safeonly boundscheck time on Linux with LLVM 4.0, ~5.6 secs on my box). So this may be specific to LLVM 4.0.

[kinke]

I recompared the -O0 IR generated by LLVM 4.0 - only differences are really a few omitted bounds checks in safe functions. I also checked LDC 1.2 and 1.1.1 on Linux x64 - and as expected, 1.2 with LLVM 4.0 also shows 50% speed for -boundscheck=off; 1.1 with LLVM 3.9 produces identically fast code.

[JohanEngelen]

Could it be that the default optimization pipeline has changed in LLVM 4.0 and that we forgot to add something?
(similar to #2156)