[IMPALA-5754] rand() algorithm is very non-random

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: Impala 2.12.0
• Component/s: Backend
• Labels: newbie
• Epic Color: ghx-label-8
• Assignee: Jin Chul Kim
• Reporter: Jim Apple
• Created: 02/Aug/17 22:26
• Updated: 19/Dec/17 00:04
• Resolved: 19/Dec/17 00:04

Description

MathFunctions::Rand includes the line *seed = rand_r(seed);. I think this is incorrect use of rand_r, which sets its seed during the call, and so doesn't seed to set it in an assignment. This produces very unrandom output; the following program which simulates this typically loops after less than 20k distinct items, while a good PRNG would produce somewhere in the neighborhood of RAND_MAX/2 items before looping.

#include <cstdlib>
#include <unordered_set>
#include <iostream>

using namespace std;

int main() {
  unsigned int seed;
  while(cin >> seed) {
    unordered_set<int> history;
    while (history.find(seed) == history.end()) {
      history.insert(seed);
      seed = rand_r(&seed);
      if (0 == (history.size() & (history.size() - 1))) {
        cout << history.size() << endl;
      }
    }
    cout << history.size() << endl;
  }
}

In any case, we should drop the use of rand_r; see IMPALA-4954.

Issue Links

• is related to: IMPALA-6117 Parallelization of sub execution plan could make incorrectness
• is related to: IMPALA-4954 rand() isn't random
• relates to: IMPALA-6168 Different result range of rand/random built-in function