win: Move Parallel.h off concrt to cross-platform code

[thakis]

Summary

r179397 added Parallel.h and implemented it terms of concrt in 2013.

In 2015, a cross-platform implementation of the functions has appeared and is in use everywhere but on Windows (r232419).
r246219 hints that <thread> had issues in MSVC2013, but r296906 suggests they've been fixed now that we require 2015+.

So remove the concrt code. It's less code, and it sounds like concrt has conceptual and performance issues, see PR41198.

I built blink_core.dll in a debug component build with full symbols and in a release component build without any symbols.
I couldn't measure a performance difference for linking blink_core.dll before and after this patch.
(Raw data: https://gist.github.com/nico/d4b02c7dd835bb96ed67e919f3558e6f)

[rnk]

Looks very good. :)

[aganea]

Looks slightly better without ConcRT, thanks Nico!
Here's some quick results showing the difference for the global hash parallelization in LLD, with MSVC OBJs. The algorithm is iterating on the .debug$T records, for a few thousands OBJs on 72 hyper threads:
(we're saving about 2 secs on this test)

Before:

After:

There's still this memory map lock eating half of the CPU time, I'm not too sure yet how to avoid it, if ever. Maybe touch the pages for the OBJ files in advance? Anyway, unrelated.

[BillyONeal]

llvm/include/llvm/Support/Parallel.h

124

If you get a chance to benchmark I'm curious how this compares to our std::sort(std::execution::par, ...) version :)

[aganea]

llvm/include/llvm/Support/Parallel.h

124

I ran a few AB/BA tests on LLD with my dataset. The cumulated time on all cores with ConcRT is consistently over by about 300ms on my 36-core Skylake (~1.9 sec for ConcRT version, ~1.6 sec after this patch). There are only three places where we parallelSort in LLD, so maybe this not representative. But the dataset is quite big, ~22 GB of OBJs and LIBs. This is a Unity build of the Editor Release target of one of our games. I can try also with no Unity files, usually the dataset is about an order of magnitude greater.

Before:

After:

[BillyONeal]

llvm/include/llvm/Support/Parallel.h

124

Not concrt; the std::sort(par...) standard parallel algorithm is an unrelated implementation.

[rnk]

llvm/lib/Support/Parallel.cpp

73

I've belatedly realized that this means that LLVM is doing thread management on its own, i.e. every linker invocation spawns hardware_concurrency() threads. My understanding is that ConCRT is built on the system worker thread pool, which helps prevent oversubscription of CPU resources.

While @aganea measured that this change improved benchmarks, this change could lead to bad throughput when multiple link jobs run concurrently. Today, LLD is not very parallel, but this may become more of an issue as we use more and more parallelism for debug info merging. At some point in the future, we should try measuring the impact of this change on the performance of three links running in parallel, and see if using the NT worker pool gives benefits in that case. For now, though, let's not get ahead of ourselves with unmeasured concerns and leave this as is.

[aganea]

llvm/lib/Support/Parallel.cpp

73

One cheap alternative is to always use heavyweight_hardware_concurrency() by default, and let the user do --threads=%NUMBER_OF_PROCESSORS% if they want hardware_concurrency().

In the absence of a global decision-maker, heavyweight_hardware_concurrency() is bit of a hack. Letting an external build system like Ninja doing that though static flags, ie --threads or /opt:lldltojobs doesn't work too well either. You can end up with large spans of time where nothing is happening, because that part of the application (LLD) isn't multi-threaded. Or because the ThreadPool's jobs are cooling down, as below at time 100:

I've tried increasing the number of threads, to see how it would react. It seems every extra ThinLTO thread above the my hardware threads, is adding roughly 150 ms to the execution. For example, running an input on 72 threads takes 108 sec, while the same input on 100 threads takes 113 sec. I don't know if the relation is linear, but it gives an idea. Probably context-switching between applications would be even more costly, I assume two lld-link running side-by-side using each 72 threads would cost even more.

I think a platform-independent solution is needed here. If we have several LLDs running, we could dynamically throttle the number of threads for each ThreadPool, through some kind of IPC. We "just" need to ensure there aren't more than N threads at one time, while taking into account: affinity, hyper-threading/cache affinity, core-local memory, and multi-socket machines.

How we would interface with Ninja? LLD wouldn't know how many free "lanes" Ninja has. Should we retain, increase, or remove LLVM_PARALLEL_LINK_JOBS ? We could build some kind of generic IPC API to be used in Ninja, but then what happens for build systems that don't implement it? make, Fastbuild, MSBuild, etc.

Another way would be to embed the the compiler & the linker into the build system (not necessarly in the way I was showing last year). There's value for doing so, one example is the usage of clang-scan-deps I was showing, it lets the build system extract dependency information very quickly, instead of invoking thousands of processes, while doing memoization as much as possible. The same thing can be achieved for pre-processing, compilation or linking. Lots of things to be done, not enough time :-)

[BillyONeal]

BTW ThreadPoolExecutor has undefined behavior since there's a detached thread touching the standard library when the program exits violating [basic.start.term]/6. Detached threads are almost never safe.

[aganea]

In D68820#2037557, @BillyONeal wrote:

BTW ThreadPoolExecutor has undefined behavior since there's a detached thread touching the standard library when the program exits violating [basic.start.term]/6. Detached threads are almost never safe.

This was fixed later by D70447.

llvm/include/llvm/Support/Parallel.h

 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/MathExtras.h"
 
 #include <algorithm>
 #include <condition_variable>
 #include <functional>
 #include <mutex>
 
-#if defined(_MSC_VER) && LLVM_ENABLE_THREADS
-#pragma warning(push)
-#pragma warning(disable : 4530)
-#include <concrt.h>
-#include <ppl.h>
-#pragma warning(pop)
-#endif
-
 namespace llvm {
 
 namespace parallel {
 struct sequential_execution_policy {};
 struct parallel_execution_policy {};
 
 template <typename T>
 struct is_execution_policy
public:
   TaskGroup();
   ~TaskGroup();
 
   void spawn(std::function<void()> f);
 
   void sync() const { L.sync(); }
 };
 
-#if defined(_MSC_VER)
-template <class RandomAccessIterator, class Comparator>
-void parallel_sort(RandomAccessIterator Start, RandomAccessIterator End,
-                   const Comparator &Comp) {
-  concurrency::parallel_sort(Start, End, Comp);
-}
-template <class IterTy, class FuncTy>
-void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
-  concurrency::parallel_for_each(Begin, End, Fn);
-}
-
-template <class IndexTy, class FuncTy>
-void parallel_for_each_n(IndexTy Begin, IndexTy End, FuncTy Fn) {
-  concurrency::parallel_for(Begin, End, Fn);
-}
-
-#else
 const ptrdiff_t MinParallelSize = 1024;
 
 /// Inclusive median.
 template <class RandomAccessIterator, class Comparator>
 RandomAccessIterator medianOf3(RandomAccessIterator Start,
                                RandomAccessIterator End,
                                const Comparator &Comp) {
   RandomAccessIterator Mid = Start + (std::distance(Start, End) / 2);
void parallel_quick_sort(RandomAccessIterator Start, RandomAccessIterator End,
   });
   parallel_quick_sort(Pivot + 1, End, Comp, TG, Depth - 1);
 }
 
 template <class RandomAccessIterator, class Comparator>
 void parallel_sort(RandomAccessIterator Start, RandomAccessIterator End,
                    const Comparator &Comp) {
   TaskGroup TG;
   parallel_quick_sort(Start, End, Comp, TG,
                       llvm::Log2_64(std::distance(Start, End)) + 1);
 }
 
 template <class IterTy, class FuncTy>
 void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
   // TaskGroup has a relatively high overhead, so we want to reduce
   // the number of spawn() calls. We'll create up to 1024 tasks here.
   // (Note that 1024 is an arbitrary number. This code probably needs
for (; I + TaskSize < End; I += TaskSize) {
     });
   }
   for (IndexTy J = I; J < End; ++J)
     Fn(J);
 }
 
 #endif
 
-#endif
-
 template <typename Iter>
 using DefComparator =
     std::less<typename std::iterator_traits<Iter>::value_type>;
 
 } // namespace detail
 
 // sequential algorithm implementations.
 template <class Policy, class RandomAccessIterator,

llvm/lib/Support/Parallel.cpp

 class Executor {
 public:
   virtual ~Executor() = default;
   virtual void add(std::function<void()> func) = 0;
 
   static Executor *getDefaultExecutor();
 };
 
-#if defined(_MSC_VER)
-/// An Executor that runs tasks via ConcRT.
-class ConcRTExecutor : public Executor {
-  struct Taskish {
-    Taskish(std::function<void()> Task) : Task(Task) {}
-
-    std::function<void()> Task;
-
-    static void run(void *P) {
-      Taskish *Self = static_cast<Taskish *>(P);
-      Self->Task();
-      concurrency::Free(Self);
-    }
-  };
-
-public:
-  virtual void add(std::function<void()> F) {
-    Concurrency::CurrentScheduler::ScheduleTask(
-        Taskish::run, new (concurrency::Alloc(sizeof(Taskish))) Taskish(F));
-  }
-};
-
-Executor *Executor::getDefaultExecutor() {
-  static ConcRTExecutor exec;
-  return &exec;
-}
-
-#else
 /// An implementation of an Executor that runs closures on a thread pool
 ///   in filo order.
 class ThreadPoolExecutor : public Executor {
 public:
   explicit ThreadPoolExecutor(unsigned ThreadCount = hardware_concurrency())
       : Done(ThreadCount) {
     // Spawn all but one of the threads in another thread as spawning threads
     // can take a while.
     std::thread([&, ThreadCount] {
       for (size_t i = 1; i < ThreadCount; ++i) {
         std::thread([=] { work(); }).detach();
       }
       work();
     }).detach();
   }
 
   ~ThreadPoolExecutor() override {
     std::unique_lock<std::mutex> Lock(Mutex);
     Stop = true;
private:
   std::condition_variable Cond;
   parallel::detail::Latch Done;
 };
 
 Executor *Executor::getDefaultExecutor() {
   static ThreadPoolExecutor exec;
   return &exec;
 }
-#endif
-}
+} // namespace
 
 static std::atomic<int> TaskGroupInstances;
 
 // Latch::sync() called by the dtor may cause one thread to block. If is a dead
 // lock if all threads in the default executor are blocked. To prevent the dead
 // lock, only allow the first TaskGroup to run tasks parallelly. In the scenario
 // of nested parallel_for_each(), only the outermost one runs parallelly.
 TaskGroup::TaskGroup() : Parallel(TaskGroupInstances++ == 0) {}