<random>: std::piecewise_linear_distribution incorrectly normalizes densities

[Cory-Kramer]

Describe the bug
A std::piecewise_linear_distribution is described as accepting discrete pairs of values and densities. The densities are normalized such that the distribution becomes valid (specifically the distribution integrates to 1.0).

Command-line test case

C:\Temp>type repro.cpp

#include <array>
#include <iostream>
#include <random>

int main()
{
    std::array<double, 2> values{ 5.0, 10.0 };
    std::array<double, 2> densities{ 0.0, 1.0 };

    std::piecewise_linear_distribution<double> dist(values.begin(), values.end(), densities.begin());
    std::cout << "x:    " << dist.intervals()[0] << " to " << dist.intervals()[1] << '\n'
              << "p(x): " << dist.densities()[0] << " to " << dist.densities()[1];
}

C:\Temp>cl /EHsc /W4 /WX .\repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.26.28806 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

repro.cpp
Microsoft (R) Incremental Linker Version 14.26.28806.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repro.exe
repro.obj

C:\Temp>.\repro.exe
x: 5 to 10
p(x): 0 to 2

Expected behavior
In the above example Visual Studio will (incorrectly) output

x: 5 to 10
p(x): 0 to 2

whereas Clang and GCC will (correctly) output

x: 5 to 10
p(x): 0 to 0.4

In this example you can verify the distribution simply makes a triangle of area 1.0, which since the width is 5.0 (10.0 - 5.0) the second density value must be 0.4 for the area to sum to 1.0.

STL version
Microsoft Visual Studio Enterprise 2019
Version 16.6.5

Additional context
This bug was also reported to the Visual Studio Developer Community: https://developercommunity.visualstudio.com/content/problem/1125176/stdpiecewise-linear-distribution-incorrectly-norma.html

For context here is the relevant MSVC implementation related to this bug:
https://github.com/microsoft/STL/blob/master/stl/inc/random#L4829-L4854

and Clang's implementation:
https://github.com/llvm/llvm-project/blob/master/libcxx/include/random#L6568-L6590

[fsb4000]

Hi @Cory-Kramer !

Thank you for your report! The bug will be fixed soon! I tried your code with applied the pull request: #1032

And I got the result:

[StephanTLavavej]

I've linked this to the PR (we can just keep this open until it's merged, instead of closing as duplicate). Thanks!

@statementreply's PR is one of a few that I want to prioritize for review and merging for VS 2019 16.8 Preview 3.

[Cory-Kramer]

Any chance this bug fix will be merged into a 15.9.x patch release too?

[StephanTLavavej]

That seems extremely unlikely. From what I can tell, 15.9.x is receiving a small but steady stream of compiler backend fixes for silent bad codegen - such bugs are often regressions, sometimes hard to work around, and usually extremely hard to notice what situations might trigger them. While the behavior of the distribution here is incorrect at runtime (and thus this qualifies as silent bad codegen too), it's not a regression (the library has misbehaved for 10 years) and it is possible to notice when code is affected (grep for the identifier) and work around (e.g. use Boost.Random). For this reason, we haven't backported any library fixes to 15.9.x, although it isn't completely impossible.

Basically if we tried to backport this, we'd have to (conceptually) stand in front of a panel of mega-bosses and explain to them why this is suddenly so bad that we need to risk destabilizing the product with a fix that might have unintended side effects - and for this bug the answer would be no.