This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of WP status.

3561. Issue with internal counter in discard_block_engine

Section: 28.5.5.2 [rand.adapt.disc] Status: WP Submitter: Ilya Burylov Opened: 2021-06-03 Last modified: 2021-10-14

Priority: Not Prioritized

View all other issues in [rand.adapt.disc].

View all issues with WP status.

Discussion:

A discard_block_engine engine adaptor is described in 28.5.5.2 [rand.adapt.disc]. It produces random numbers from the underlying engine discarding (p - r) last values of p - size block, where r and p are template parameters of std::size_t type:

template<class Engine, size_t p, size_t r>
class discard_block_engine;

The transition algorithm for discard_block_engine is described as follows (paragraph 2):

The transition algorithm discards all but r > 0 values from each block of p = r values delivered by ℯ. The state transition is performed as follows: If n = r, advance the state of e from e_i to e_i+p-r and set n to 0. In any case, then increment n and advance e's then-current state e_j to e_j+1.

Where n is of integer type. In the API of discard block engine, n is represented in the following way:

[…]
int n; // exposition only

In cases where int is equal to int32_t, overflow is possible for n that leads to undefined behavior. Such situation can happen when the p and r template parameters exceed INT_MAX.

This misleading exposition block leads to differences in implementations:

• GNU Libstdc++ uses size_t for n — in this case no overflow happened even if template parameters exceed INT_MAX

• LLVM Libcxx uses int for n together with a static_assert that is checking that p and r values are <= INT_MAX

Such difference in implementation makes code not portable and may potentially breaks random number sequence consistency between different implementors of C++ std lib.

The problematic use case is the following one:

#include <iostream>
#include <random>
#include <limits>

int main() {
  std::minstd_rand0 generator;

  constexpr std::size_t skipped_size = static_cast<std::size_t>(std::numeric_limits<int>::max());
  constexpr std::size_t block_size = skipped_size + 5;
  constexpr std::size_t used_block = skipped_size;

  std::cout << "block_size = " << block_size << std::endl;
  std::cout << "used_block = " << used_block << "\n" << std::endl;

  std::discard_block_engine<std::minstd_rand0, block_size, used_block> discard_generator;

  // Call discard procedures
  discard_generator.discard(used_block);
  generator.discard(block_size);

  // Call generation. Results should be equal
  for (std::int32_t i = 0; i < 10; ++i)
  {
    std::cout << discard_generator() << " should be equal " << generator() << std::endl;
  }
}

We see no solid reason for n to be an int, given that the relevant template parameters are std::size_t. It seems like a perfectly fine use case to generate random numbers in amounts larger than INT_MAX.

The proposal is to change exposition text to std::size_t:

size_t n; // exposition only

It will not mandate the existing libraries to break ABI, but at least guide for better implementation.

[2021-06-14; Reflector poll]

Set status to Tentatively Ready after six votes in favour during reflector poll.

[2021-10-14 Approved at October 2021 virtual plenary. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4885.

1. Modify 28.5.5.2 [rand.adapt.disc], class template discard_block_engine synopsis, as indicated:

     […]
     // generating functions
     result_type operator()();
     void discard(unsigned long long z);
     
     // property functions
     const Engine& base() const noexcept { return e; };
     
   private:
     Engine e; // exposition only
     intsize_t n; // exposition only
   };