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.

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.

On 7/14/20 8:02 AM, Atila Neves wrote:
> 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.

I see, thanks. I assume unittests can't cover that kind of stuff. Are these problems checked for by our CI testing? I.e. if we make changes can we be certain they won't cause regressions?

On Tuesday, 14 July 2020 at 15:14:03 UTC, Andrei Alexandrescu wrote:
> On 7/14/20 8:02 AM, Atila Neves wrote:
>> 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.
>
> I see, thanks. I assume unittests can't cover that kind of stuff.

Kind of. There were dmd test files with code similar to the one in Phobos. I deleted them as part of cleaning up (the code in Phobos no longer even exists). I'm sure a proper unit test could be added, but the main issue here is linkability so I'd avise against it instead of just trying to link a binary.

> Are these problems checked for by our CI testing? I.e. if we make changes can we be certain they won't cause regressions?

buildkite checks several dub projects to see if their CI still passes. It's possible some other code out there breaks, but widespread breakage is highly unlikely.

The reason I haven't been able to do away with the -unittest hack is exactly a buildkite failure.