Currently codechef provides GDC 6.3 as the only implementation of the D programming language. This version had been released in 2016 and nowadays is missing some of the useful language features. Upgrade to a more recent version would be very much appreciated. But apparently this is not the only problem.
During the latest contest, doing binary search suffered from TLE and this forced me to do some investigation. I suspect that there may be something wrong with the used optimization settings for the GDC compiler on the codechef platform. The performance of the following reduced code snippet is very bad:
import std.algorithm, std.conv, std.range, std.stdio, std.string, std.stdint;
// calculate integer square root using binary search
static int64_t isqrt(int64_t x) {
return iota(0, min(x, 3037000499) + 1).map!(v => (v * v > x)).assumeSorted.lowerBound(true).length - 1;
}
void main() {
// calculate integer square roots for all numbers in the [0, 2000000) range and print their sum
2000000.iota.map!isqrt.sum.writeln;
}
If I paste it to codechef ide and run, then the execution time is around 1.3 seconds. If I paste it to AtCoder custom test page and run, then the execution time is only around 0.15 seconds. Yes, the version of GDC is different and AtCoder is using different hardware, but almost an order of magnitude difference still looks abnormal.
So in order to do an additional test, I have installed an old version of Debian Linux (so that it has the same GDC 6.3 as codechef) on my old laptop with a 2GHz Intel Core2 Duo processor and also tried to benchmark this code snippet there:
- If I compile this code without any optimizations by running “gdc test.d”, then the execution time is 2.2 seconds.
- If I compiler this code with -O2 optimizations by running “gdc -O2 -frelease test.d” (the same optimization settings as used by AtCoder), then the execution time reduces to 0.36 seconds.
This makes me think that codechef probably doesn’t enable optimizations for GDC. And if this is the case, then it is very unfortunate because the performance difference may be gigantic. And writing code in functional style apparently takes the biggest hit. I already encountered a very strange performance issue earlier (TLE vs. AC), which fortunately could be workarounded by rewriting the array printing code in imperative style during that contest.
If the root cause is indeed just a missing “-O2” compiler option for GDC, then I believe that the problem can be resolved very easily if @admin takes a look at it.