Index: lib/Fuzzer/FuzzerInternal.h
===================================================================
--- lib/Fuzzer/FuzzerInternal.h
+++ lib/Fuzzer/FuzzerInternal.h
@@ -17,6 +17,7 @@
 #include <chrono>
 #include <cstddef>
 #include <cstdlib>
+#include <random>
 #include <string>
 #include <string.h>
 #include <vector>
@@ -241,6 +242,9 @@
   void WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix);
   void PrintStats(const char *Where, const char *End = "\n");
   void PrintStatusForNewUnit(const Unit &U);
+  // Updates the probability distribution for the units in the corpus.
+  // Must be called whenever the corpus or unit weights are changed.
+  void UpdateCorpusDistribution();
 
   void SyncCorpus();
 
@@ -280,6 +284,8 @@
     return Res;
   }
 
+  std::mt19937 Generator;
+  std::piecewise_constant_distribution<double> CorpusDistribution;
   UserSuppliedFuzzer &USF;
   FuzzingOptions Options;
   system_clock::time_point ProcessStartTime = system_clock::now();
Index: lib/Fuzzer/FuzzerLoop.cpp
===================================================================
--- lib/Fuzzer/FuzzerLoop.cpp
+++ lib/Fuzzer/FuzzerLoop.cpp
@@ -56,7 +56,7 @@
 static Fuzzer *F;
 
 Fuzzer::Fuzzer(UserSuppliedFuzzer &USF, FuzzingOptions Options)
-    : USF(USF), Options(Options) {
+    : Generator(USF.GetRand()(RAND_MAX)), USF(USF), Options(Options) {
   SetDeathCallback();
   InitializeTraceState();
   assert(!F);
@@ -163,6 +163,7 @@
     if (UnitHashesAddedToCorpus.insert(Hash(X)).second) {
       if (RunOne(X)) {
         Corpus.push_back(X);
+        UpdateCorpusDistribution();
         PrintStats("RELOAD");
       }
     }
@@ -200,6 +201,7 @@
     }
   }
   Corpus = NewCorpus;
+  UpdateCorpusDistribution();
   for (auto &X : Corpus)
     UnitHashesAddedToCorpus.insert(Hash(X));
   PrintStats("INITED");
@@ -347,6 +349,7 @@
 
 void Fuzzer::ReportNewCoverage(const Unit &U) {
   Corpus.push_back(U);
+  UpdateCorpusDistribution();
   UnitHashesAddedToCorpus.insert(Hash(U));
   USF.GetMD().RecordSuccessfulMutationSequence();
   PrintStatusForNewUnit(U);
@@ -411,20 +414,9 @@
 // Hypothesis: units added to the corpus last are more likely to be interesting.
 // This function gives more wieght to the more recent units.
 size_t Fuzzer::ChooseUnitIdxToMutate() {
-    size_t N = Corpus.size();
-    size_t Total = (N + 1) * N / 2;
-    size_t R = USF.GetRand()(Total);
-    size_t IdxBeg = 0, IdxEnd = N;
-    // Binary search.
-    while (IdxEnd - IdxBeg >= 2) {
-      size_t Idx = IdxBeg + (IdxEnd - IdxBeg) / 2;
-      if (R > (Idx + 1) * Idx / 2)
-        IdxBeg = Idx;
-      else
-        IdxEnd = Idx;
-    }
-    assert(IdxBeg < N);
-    return IdxBeg;
+    size_t Idx = size_t(CorpusDistribution(Generator));
+    assert(Idx < Corpus.size());
+    return Idx;
 }
 
 // Experimental search heuristic: drilling.
@@ -447,6 +439,7 @@
   std::vector<Unit> SavedCorpus;
   SavedCorpus.swap(Corpus);
   Corpus.push_back(U);
+  UpdateCorpusDistribution();
   assert(Corpus.size() == 1);
   RunOne(U);
   PrintStats("DRILL ");
@@ -510,4 +503,15 @@
   ExecuteCommand(Options.SyncCommand + " " + Options.OutputCorpus);
 }
 
+void Fuzzer::UpdateCorpusDistribution() {
+  std::vector<double> Intervals { 0 };
+  std::vector<double> Weights;
+  for (size_t i = 0; i < Corpus.size(); i++) {
+    Intervals.push_back(i+1);
+    Weights.push_back(i+1);
+  }
+  CorpusDistribution = std::piecewise_constant_distribution<double>(
+      Intervals.begin(), Intervals.end(), Weights.begin());
+}
+
 }  // namespace fuzzer
Index: lib/Fuzzer/test/fuzzer-traces.test
===================================================================
--- lib/Fuzzer/test/fuzzer-traces.test
+++ lib/Fuzzer/test/fuzzer-traces.test
@@ -19,7 +19,7 @@
 RUN: not LLVMFuzzer-SimpleHashTest -use_traces=1 -seed=1 -runs=10000000  2>&1 | FileCheck %s
 RUN:     LLVMFuzzer-SimpleHashTest               -seed=1 -runs=10000000 2>&1 | FileCheck %s --check-prefix=Done10000000
 
-RUN: LLVMFuzzer-RepeatedMemcmp -seed=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=RECOMMENDED_DICT
+RUN: LLVMFuzzer-RepeatedMemcmp -seed=2 -runs=100000 2>&1 | FileCheck %s --check-prefix=RECOMMENDED_DICT
 RECOMMENDED_DICT:###### Recommended dictionary. ######
 RECOMMENDED_DICT-DAG: "foo"
 RECOMMENDED_DICT-DAG: "bar"