www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - What happened to the monotonicity test in SortedRange?

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.com> writes:
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.
Jul 13 2020
parent reply Atila Neves <atila.neves gmail.com> writes:
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.
Jul 14 2020
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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?
Jul 14 2020
parent Atila Neves <atila.neves gmail.com> writes:
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.
Jul 15 2020