[ADT][Expensive checks] Create a /dev/random seed only once when shuffling the range before sorting it to avoid bot timeouts

[arphaman]

Summary

The expensive checks enabled bot on green dragon (http://lab.llvm.org:8080/green/job/clang-stage1-cmake-RA-expensive/) has been failing to pass the libFuzzer :: large.test ever since the test was enabled on Darwin (i.e. REQUIRES: linux was removed). It's failing because it's timing out, and it's timing out because the compiler is too slow. I sampled the clang invocations and was shocked to see that the majority of the time was spent in calls to std::random_device inside of llvm::sort.

This patch changes the expensive checking behavior to compute a single std::random_device shuffle seed, per an invocation of clang, rather than computing it for every sort. This fixes the test failure on the bot. On my machine, this improved the performance of building compiler-rt with clang that has expensive checks enabled by 50-100x!

[grandinj]

haha, nice catch.

Random idea: Maybe the clang build-bots needs to run some background stack-sampling by default, and generate a flame-graph for people to check?

[mgrang]

Thanks for fixing this. LGTM.

[delcypher]

@arphaman Nice catch!

[arphaman]

Unfortunately my jubilation was premature. While this speed up the build of compiler-rt and the test file as well dramatically, the test file still takes way too long to compile and still times out. Most of the time now is spend in IR/MIR verifiers when building the test file. I'll commit this and keep looking into why they're so slow for that file.

llvm/include/llvm/ADT/STLExtras.h

 /// get_array_pod_sort_comparator - This is an internal helper function used to
 /// get type deduction of T right.
 template<typename T>
 inline int (*get_array_pod_sort_comparator(const T &))
              (const void*, const void*) {
   return array_pod_sort_comparator<T>;
 }
 
+#ifdef EXPENSIVE_CHECKS
+namespace detail {
+
+inline unsigned presortShuffleEntropy() {
+  static unsigned Result(std::random_device{}());
+  return Result;
+}
+
+template <class IteratorTy>
+inline void presortShuffle(IteratorTy Start, IteratorTy End) {
+  std::mt19937 Generator(presortShuffleEntropy());
+  std::shuffle(Start, End, Generator);
+}
+
+} // end namespace detail
+#endif
+
 /// array_pod_sort - This sorts an array with the specified start and end
 /// extent.  This is just like std::sort, except that it calls qsort instead of
 /// using an inlined template.  qsort is slightly slower than std::sort, but
 /// most sorts are not performance critical in LLVM and std::sort has to be
 /// template instantiated for each type, leading to significant measured code
 /// bloat.  This function should generally be used instead of std::sort where
 /// possible.
 ///
 /// This function assumes that you have simple POD-like types that can be
 /// compared with std::less and can be moved with memcpy.  If this isn't true,
 /// you should use std::sort.
 ///
 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
 /// default to std::less.
 template<class IteratorTy>
 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
   // Don't inefficiently call qsort with one element or trigger undefined
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
 #ifdef EXPENSIVE_CHECKS
-  std::mt19937 Generator(std::random_device{}());
-  std::shuffle(Start, End, Generator);
+  detail::presortShuffle<IteratorTy>(Start, End);
 #endif
   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
 }
 
 template <class IteratorTy>
 inline void array_pod_sort(
     IteratorTy Start, IteratorTy End,
     int (*Compare)(
         const typename std::iterator_traits<IteratorTy>::value_type *,
         const typename std::iterator_traits<IteratorTy>::value_type *)) {
   // Don't inefficiently call qsort with one element or trigger undefined
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
 #ifdef EXPENSIVE_CHECKS
-  std::mt19937 Generator(std::random_device{}());
-  std::shuffle(Start, End, Generator);
+  detail::presortShuffle<IteratorTy>(Start, End);
 #endif
   qsort(&*Start, NElts, sizeof(*Start),
         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 }
 
 // Provide wrappers to std::sort which shuffle the elements before sorting
 // to help uncover non-deterministic behavior (PR35135).
 template <typename IteratorTy>
 inline void sort(IteratorTy Start, IteratorTy End) {
 #ifdef EXPENSIVE_CHECKS
-  std::mt19937 Generator(std::random_device{}());
-  std::shuffle(Start, End, Generator);
+  detail::presortShuffle<IteratorTy>(Start, End);
 #endif
   std::sort(Start, End);
 }
 
 template <typename Container> inline void sort(Container &&C) {
   llvm::sort(adl_begin(C), adl_end(C));
 }
 
 template <typename IteratorTy, typename Compare>
 inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
 #ifdef EXPENSIVE_CHECKS
-  std::mt19937 Generator(std::random_device{}());
-  std::shuffle(Start, End, Generator);
+  detail::presortShuffle<IteratorTy>(Start, End);
 #endif
   std::sort(Start, End, Comp);
 }
 
 template <typename Container, typename Compare>
 inline void sort(Container &&C, Compare Comp) {
   llvm::sort(adl_begin(C), adl_end(C), Comp);
 }