STL: Use normal for-loops when possible

[StephanTLavavej]

The STL's headers contain 7 occurrences of a strange pattern, originally noticed by @j6t in #663:

https://github.com/microsoft/STL/blob/3e8b26950f506d0720ffc39790740a26cd584e28/stl/inc/random#L832
https://github.com/microsoft/STL/blob/3e8b26950f506d0720ffc39790740a26cd584e28/stl/inc/random#L937
https://github.com/microsoft/STL/blob/3e8b26950f506d0720ffc39790740a26cd584e28/stl/inc/random#L1266
https://github.com/microsoft/STL/blob/3e8b26950f506d0720ffc39790740a26cd584e28/stl/inc/valarray#L323
https://github.com/microsoft/STL/blob/3e8b26950f506d0720ffc39790740a26cd584e28/stl/inc/valarray#L332
https://github.com/microsoft/STL/blob/3e8b26950f506d0720ffc39790740a26cd584e28/stl/inc/valarray#L343
https://github.com/microsoft/STL/blob/3e8b26950f506d0720ffc39790740a26cd584e28/stl/inc/valarray#L1002

These are just int and size_t. Instead of initializing with 0, preincrementing before comparing, and doing nothing at the end of each iteration, we should follow the normal pattern: initialize with 1, compare without modifying, and preincrement at the end of each iteration. (Note that these loops start by processing the value 1 because they occur after code that has effectively processed the value 0 in a special way.)

I looked for other occurrences in the STL and didn't find any more that would be easy to change. (There are several that superficially resemble this pattern, but are manipulating iterators where the strange pattern is slightly more convenient.)

[AlexGuteniev]

Maybe having odd loops comes from considering self-xoring a register and incrementing it as a part of the loop better, and being confident that compiler wouldn't do it by itself . (Still, this is not likely to be significant, even if it is still valid).

[StephanTLavavej]

This code is pretty old (especially <valarray>) and was presumably written for less capable optimizers. I would be astounded if this makes a codegen difference today. I suppose we could inspect the codegen to be extra sure.

[babhishek21]

Anyone working on this? I'd be happy to. 😄

[CaseyCarter]

Anyone working on this? I'd be happy to. 😄

Not that we know of - by all means please do!

[babhishek21]

Is there a way to run tests straight from Visual Studio? It won't discover any tests even after I did a Build all.

Looking at the readme, it looks like I have to follow the native tools step even after I followed the VS route.

[cbezault]

While there is no way to run the tests directly from the VS IDE there is no need to re-do all the steps from the command prompt.

You just need to open an x64 or x86 native tools command prompt (the right one for whichever configuration of the STL you built from VS) and navigate to the output directory. This would typically be C:\Users\<your username>\source\Repos\STL\out\build\[x64|x86] a which point you should be able to follow the readme.

[babhishek21]

Ok, I took the following steps (everything run in VS Developer Command Prompt):

1. Cloned the x64 target to x64_Test in CMake config with an additional -DBUILD_TESTING=TRUE flag for Cmake builds. That seemed to finally get me tests in the default build folder.
2. Trying to run ctest -V caused all tests to fail because it couldn't find clang-cl.
   
   
   
   • I noticed that the README mentions that the LLVM bin needs to be in PATH (presumably for clang). Does that mean I needed to build the llvm-project submodule as well (because that is not mentioned anywhere in the README)?
   
   
   • I decided to go ahead and follow the LLVM build guide anyway, and I noticed that it picked up my MinGW GCC installation. I expected the VS C++ toolchain to be picked up, especially since I am running everything from the VS Developer Command Prompt.
   
   

Building LLVM right now. Will update once that's done.

[cbezault]

No need to build LLVM!
Just download it from here (I'll be updating the README to resolve all this confusion later) https://github.com/llvm/llvm-project/releases/download/llvmorg-10.0.0/LLVM-10.0.0-win64.exe .

[babhishek21]

OK, installing an LLVM release directly helped. The tests are finally running (I see quite a bit of failures here and there). I'll get on to making the changes now.

Any pointers on how to identify tests that matter for the changes I make? I'm not too keen on running 11k tests. 😅

[cbezault]

I would suggest just making a PR with your changes and relying on our CI to run the tests. It's hard to tell exactly what tests would be affected by this change and so all of them must be run.

[babhishek21]

Some other cases I found:

.\stl/inc/algorithm:497:        for (auto _UNext = _UFirst; ++_UNext != _ULast; _UFirst = _UNext) {
.\stl/inc/algorithm:2556:        for (auto _UFirstb = _UFirst; ++_UFirst != _ULast; _UFirstb = _UFirst) {
.\stl/inc/algorithm:2979:    for (; ++_UTarget != _ULast; ++_Target_index) { // randomly place an element from [_First, _Target] at _Target
.\stl/inc/algorithm:3198:        for (auto _UNext = _UFirst; ++_UNext != _ULast;) {
.\stl/inc/algorithm:3225:    for (_FwdIt _Next = _First; ++_Next != _Last;) {
.\stl/inc/algorithm:4161:        for (_BidIt _Next = _First; ++_Next != _Last;) { // order next element
.\stl/inc/algorithm:4169:                for (_BidIt _First1 = _Next1; _DEBUG_LT_PRED(_Pred, _Val, *--_First1); _Next1 = _First1) {
.\stl/inc/algorithm:5448:        for (auto _UNext = _UFirst; ++_UNext != _ULast; ++_UFirst) {
.\stl/inc/charconv:1016:    for (int32_t _Iu = _Cu_quo; --_Iu >= 0;) {
.\stl/inc/execution:904:            for (_Diff _This_chunk_size = _Chunk_size; 0 < _This_chunk_size--;) {
.\stl/inc/execution:917:            for (_Diff _This_chunk_size = _Chunk_size; 0 < _This_chunk_size--;) {
.\stl/inc/execution:3399:        for (_FwdIt _Next = _First; ++_Next != _Last;) {
.\stl/inc/execution:5080:        for (auto _Next = _First; ++_Next != _Last; _First = _Next) {
.\stl/inc/istream:368:            for (; 0 < --_Count; _Meta = _Myios::rdbuf()->snextc()) {
.\stl/inc/xutility:1550:            for (auto _Next = _First; ++_Next != _Last; _First = _Next) {
.\stl/inc/xutility:1570:        for (_FwdIt _Next = _First; ++_Next != _Last; _First = _Next) {
.\stl/inc/xutility:5253:    for (; _UFirst != _ULast && _UFirst != --_ULast; ++_UFirst) {
.\stl/inc/xutility:5261:    for (; _First != _Last && _First != --_Last; ++_First) {
.\stl/src/ios.cpp:77:    for (_This->_Stdstr = 0; ++_This->_Stdstr < _Nstdstr;) {
.\stl/src/vector_algorithms.cpp:20:    for (; _First != _Last && _First != --_Last; ++_First) {
.\stl/src/xlpoly.cpp:13:    for (y = *tab; 0 <= --n;) {
.\stl/src/xpoly.cpp:13:    for (y = *tab; 0 <= --n;) {

I think @StephanTLavavej mentioned the iterator cases in https://github.com/microsoft/STL/issues/678#issue-593000182

[CaseyCarter]

Some other cases I found:

.\stl/inc/algorithm:497:        for (auto _UNext = _UFirst; ++_UNext != _ULast; _UFirst = _UNext) {
.\stl/inc/algorithm:2556:        for (auto _UFirstb = _UFirst; ++_UFirst != _ULast; _UFirstb = _UFirst) {
.\stl/inc/algorithm:2979:    for (; ++_UTarget != _ULast; ++_Target_index) { // randomly place an element from [_First, _Target] at _Target
.\stl/inc/algorithm:3198:        for (auto _UNext = _UFirst; ++_UNext != _ULast;) {
.\stl/inc/algorithm:3225:    for (_FwdIt _Next = _First; ++_Next != _Last;) {
.\stl/inc/algorithm:4161:        for (_BidIt _Next = _First; ++_Next != _Last;) { // order next element
.\stl/inc/algorithm:4169:                for (_BidIt _First1 = _Next1; _DEBUG_LT_PRED(_Pred, _Val, *--_First1); _Next1 = _First1) {
.\stl/inc/algorithm:5448:        for (auto _UNext = _UFirst; ++_UNext != _ULast; ++_UFirst) {
.\stl/inc/execution:3399:        for (_FwdIt _Next = _First; ++_Next != _Last;) {
.\stl/inc/execution:5080:        for (auto _Next = _First; ++_Next != _Last; _First = _Next) {
.\stl/inc/xutility:1550:            for (auto _Next = _First; ++_Next != _Last; _First = _Next) {
.\stl/inc/xutility:1570:        for (_FwdIt _Next = _First; ++_Next != _Last; _First = _Next) {

These all seem like relatively legitimate attempts to advance a pair of iterators in lockstep while avoiding instantiating std::next/std::prev. I'd leave these alone.

.\stl/inc/xutility:5253:    for (; _UFirst != _ULast && _UFirst != --_ULast; ++_UFirst) {
.\stl/inc/xutility:5261:    for (; _First != _Last && _First != --_Last; ++_First) {
.\stl/src/vector_algorithms.cpp:20:    for (; _First != _Last && _First != --_Last; ++_First) {

These are legitimate "I'm iterating from both ends toward the middle of this sequence" patterns. I'd leave these alone as well.

.\stl/inc/charconv:1016:    for (int32_t _Iu = _Cu_quo; --_Iu >= 0;) {
.\stl/inc/execution:904:            for (_Diff _This_chunk_size = _Chunk_size; 0 < _This_chunk_size--;) {
.\stl/inc/execution:917:            for (_Diff _This_chunk_size = _Chunk_size; 0 < _This_chunk_size--;) {
.\stl/inc/istream:368:            for (; 0 < --_Count; _Meta = _Myios::rdbuf()->snextc()) {
.\stl/src/xlpoly.cpp:13:    for (y = *tab; 0 <= --n;) {
.\stl/src/xpoly.cpp:13:    for (y = *tab; 0 <= --n;) {

Ignoring the "Yoda conditions" - comparisons formulated with the expected value on the left instead of the right side of the operator - these are fairly idiomatic "iterate over the values in [0, meow) in reverse order" patterns. Pre-decrement and >= 0 works only when meow has signed integer type (--meow >= 0), but is popularly considered more readable than the more-general post-decrement pattern (meow-- > 0) which works regardless of signed-ness.

I'd like to see the ordering of the Yoda conditions flipped to actual_value operator expected_value, but otherwise I'd leave these alone.

.\stl/src/ios.cpp:77:    for (_This->_Stdstr = 0; ++_This->_Stdstr < _Nstdstr;) {

This is another case of the pattern from the OP; I suggest including a change in your PR.