What happened to the monotonicity test in SortedRange?

[Atila Neves]

On Monday, 13 July 2020 at 18:23:27 UTC, Andrei Alexandrescu 
wrote:
> For a while we've had in Phobos a really nice monotnonicity 
> test in SortedRange: in debug mode, sortedness was checked in 
> O(n) time but not always (because that would ruin complexity), 
> but instead at random with 1/n probability. That means on 
> average the complexity was constant, yet we did get some 
> checking.
>
> From there, things have gotten progressively... different. 
> Various changes to the approach caused 
> https://issues.dlang.org/show_bug.cgi?id=15230. The solution to 
> that was https://github.com/dlang/phobos/pull/7205, which I 
> don't think it's very good because it is deterministic (i.e. 
> liable to systematic errors) and defaults to no checking at all 
> regardless of debug vs. release mode.
>
> As an aside, that PR has documentation issues (e.g. 
> disfluencies, too many commas) that should have been corrected 
> in review.
>
> What I think we should do is this: use a probabilistic 
> monotonicity testing as described in 
> http://www.cse.psu.edu/~sxr48/pubs/TestingSortednessEncyclopedia.pdf or one of the referenced papers, or just get back to what we used to do - make the O(n) test with 1/n probability.

I'm not sure if this was one of them, but a lot of version(debug) 
and version(assert) checks in Phobos caused linker errors because 
Phobos is distributed in binary form and not compiled with 
-debug. The "solution" was to always emit template code with 
-debug, which meant incredibly long compile times for importing 
anything from Phobos. I'm still trying to get rid of the similar 
-unittest hack.