<algorithm>: shuffle() was critically damaged by the attempt to implement Batched Ranged Random Integer Generation #6112
Description
#5932 was completely broken. I reviewed the code, but I didn't manually check the output, or verify the benchmarks, so I failed here.
C:\Temp>type meow.cpp
#include <algorithm>
#include <numeric>
#include <print>
#include <random>
#include <vector>
using namespace std;
int main() {
println("_MSVC_STL_UPDATE: {}", _MSVC_STL_UPDATE);
mt19937_64 urng(6);
vector<int> v(100);
iota(v.begin(), v.end(), 0);
println("Iota: {}", v);
shuffle(v.begin(), v.end(), urng);
println("First Shuffle: {}", v);
println();
const auto first_shuffle = v;
iota(v.begin(), v.end(), 0);
println("Iota: {}", v);
shuffle(v.begin(), v.end(), urng);
println("Second Shuffle: {}", v);
println();
if (v == first_shuffle) {
println("First and Second Shuffles were identical, this should be vanishingly impossible!");
} else {
println("First and Second Shuffles were different, good.");
}
}Before:
C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /MTd /Od meow.cpp && meow
meow.cpp
_MSVC_STL_UPDATE: 202511
Iota: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
First Shuffle: [21, 34, 47, 22, 95, 51, 76, 52, 78, 17, 84, 90, 88, 53, 89, 23, 97, 0, 28, 4, 10, 11, 45, 54, 48, 3, 24, 96, 31, 39, 66, 70, 56, 94, 77, 91, 85, 99, 60, 36, 67, 38, 50, 46, 64, 14, 43, 5, 37, 26, 16, 40, 81, 83, 63, 18, 65, 86, 87, 69, 27, 92, 1, 93, 9, 7, 2, 82, 72, 75, 15, 30, 12, 33, 74, 49, 29, 6, 32, 25, 73, 20, 62, 57, 61, 13, 71, 79, 59, 35, 98, 58, 55, 41, 44, 8, 19, 80, 68, 42]
Iota: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
Second Shuffle: [26, 27, 83, 22, 41, 61, 52, 66, 25, 80, 2, 16, 72, 96, 68, 65, 95, 58, 51, 88, 29, 78, 28, 60, 36, 35, 46, 55, 70, 13, 15, 32, 98, 19, 17, 34, 64, 62, 50, 40, 67, 6, 43, 20, 23, 84, 9, 57, 75, 79, 21, 59, 89, 81, 86, 1, 30, 56, 11, 48, 53, 69, 10, 5, 24, 3, 97, 99, 8, 87, 47, 63, 37, 54, 0, 76, 90, 94, 93, 38, 18, 7, 39, 42, 31, 85, 14, 91, 49, 4, 44, 45, 33, 71, 73, 92, 12, 74, 82, 77]
First and Second Shuffles were different, good.
After:
C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /MTd /Od meow.cpp && meow
meow.cpp
_MSVC_STL_UPDATE: 202602
Iota: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
First Shuffle: [98, 0, 1, 3, 2, 4, 6, 5, 7, 9, 8, 10, 12, 11, 13, 15, 14, 16, 18, 17, 19, 21, 20, 22, 24, 23, 25, 27, 26, 28, 30, 29, 31, 33, 32, 34, 36, 35, 37, 39, 38, 40, 42, 41, 43, 45, 44, 46, 48, 47, 49, 51, 50, 52, 54, 53, 55, 57, 56, 58, 60, 59, 61, 63, 62, 64, 66, 65, 67, 69, 68, 70, 72, 71, 73, 75, 74, 76, 78, 77, 79, 81, 80, 82, 84, 83, 85, 87, 86, 88, 90, 89, 91, 93, 92, 94, 96, 95, 97, 99]
Iota: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
Second Shuffle: [98, 0, 1, 3, 2, 4, 6, 5, 7, 9, 8, 10, 12, 11, 13, 15, 14, 16, 18, 17, 19, 21, 20, 22, 24, 23, 25, 27, 26, 28, 30, 29, 31, 33, 32, 34, 36, 35, 37, 39, 38, 40, 42, 41, 43, 45, 44, 46, 48, 47, 49, 51, 50, 52, 54, 53, 55, 57, 56, 58, 60, 59, 61, 63, 62, 64, 66, 65, 67, 69, 68, 70, 72, 71, 73, 75, 74, 76, 78, 77, 79, 81, 80, 82, 84, 83, 85, 87, 86, 88, 90, 89, 91, 93, 92, 94, 96, 95, 97, 99]
First and Second Shuffles were identical, this should be vanishingly impossible!
We're lucky this was broken in such an obvious way, found by libigl in the Real World Code (RWC) test suite.
@FranciscoThiesen I'm not sure how this happened, but I need to emergency revert your PR. Did you manually inspect your implementation's behavior (as I should have)? Did you rely on AI in the development of your PR? Thanks.