urand graph generation test fails on Ubuntu 22

[idanyani]

I upgraded my system from Ubuntu 20 to 22 and now all tests pass except for test-generate-u10.
This test runs ./bfs -u10 -n0 and compares it to a reference output.
The number of edges is 16104 on Ubuntu 20 and 16104 on Ubuntu 22.
Digging deeper, I think that the problem is that the uniform_int_distribution of libstdc++ was changed.
(Ubuntu 22 default gcc version is 11.2.0 whereas Ubuntu 20 uses gcc 9.4.0.)

To demonstrate the problem I slightly modified the code:

diff --git a/src/generator.h b/src/generator.h
index 3127f4b..77dbfb5 100644
--- a/src/generator.h
+++ b/src/generator.h
@@ -72,6 +72,7 @@ class Generator {
         rng.seed(kRandSeed + block/block_size);
         for (int64_t e=block; e < std::min(block+block_size, num_edges_); e++) {
           el[e] = Edge(udist(rng), udist(rng));
+          std::cout << "edge(" << e << ")=" << el[e].u << "," << el[e].v << std::endl;
         }
       }
     }

The diff between Ubuntu 20 and 22 outputs is:

4874c4874
< edge(4873)=662,102
---
> edge(4873)=661,102
5160c5160
< edge(5159)=942,269
---
> edge(5159)=941,269
7620c7620
< edge(7619)=263,264
---
> edge(7619)=263,263
15027c15027
< edge(15026)=641,856
---
> edge(15026)=641,855
16385,16387c16385,16387
< Generate Time:       0.07683 
< Build Time:          0.04481 
< Graph has 1024 nodes and 16104 undirected edges for degree: 15
---
> Generate Time:       0.06717 
> Build Time:          0.01616 
> Graph has 1024 nodes and 16103 undirected edges for degree: 15

You can see that some edges changed, probably due to the uniform random number engine. Specifically, Edge 7619 turned into a self loop, so it got squished, reducing the number of edges by 1.

I'm not sure how to fix this issue. Perhaps adding some tolerance to the edge count comparison in the tests?

[sbeamer]

This is an unfortunate situation that has been getting worse. Although C++ standards carefully specify how the random number generators should behave, they do not do the same for uniform_int_distribution (reddit post). With seeding, the generator will produce the same values, but the distribution will not. When this codebase was first constructed, gcc, clang, icc, and suncc used the same distribution algorithm. Recently, there has been some divergence. On a linux box, g++ 9.4 and clang++ 12 produce the same right answer. However, on my mac, Apple clang 14 and g++-12 produce different results.

Fortunately, for those concerned about running the exact same benchmark graphs, SuiteSparse captured the graphs a couple years ago (https://sparse.tamu.edu/GAP).

I'm going to leave this issue open, since the only solutions I can think of are unsatisfactory. I would be grateful if anyone has a better idea. So far, the options I can think of all have downsides:

1. Do nothing - Although randomly generated graphs will be subtly different, for most research purposes this is ok. The most worrisome part is a unit test not passing. For now, GitHub's CI is using a compiler that still has the same distribution function, so it is still passing.
2. Replace the distribution with % - This will be portable, however, modulus can add bias to the distribution. This is especially likely as the range gets close to the size of the random numbers, which someone might do with SCALE=29 or SCALE=30.
3. Write a portable distribution function - This might be the least bad but the most work. Doing it well involves both removing bias as well as being high-performance. Typically, I duplicate functionality from the standard library as a last result.
4. Make test case weaker - This might be an expedient solution, but then the test case may not be checking much.

[sbeamer]

With CI failing, I checked to see the current state of which distribution each compiler is using.

In my lab, I had Linux boxes with gcc 9,10,11,13 and clang 12 and 14. Gcc 9 & 10 behaved like the original reference output. Gcc 11 onwards as well as the clang versions all behaved the same. With any luck, gcc & clang will continue to have the same implementation behavior.

Thus, going with a slightly modified version of option 1 (via commit 30197cf).

[sbeamer]

Spoke too soon. Clang (14) on my Mac produces yet another answer.

Option 3 will probably be the best.

[sbeamer]

I went with option 3 to further standardize this reference code.