Use background tasks for the compiler dispatcher

src/compiler-dispatcher/compiler-dispatcher.cc

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler-dispatcher/compiler-dispatcher.h"
 
 #include "include/v8-platform.h"
 #include "include/v8.h"
 #include "src/base/platform/time.h"
 #include "src/cancelable-task.h"
@@ skipping 48 matching lines @@
     try_catch.ReThrow();
   }
   return job->status() != CompileJobStatus::kFailed;
 }
 
 bool IsFinished(CompilerDispatcherJob* job) {
   return job->status() == CompileJobStatus::kDone ||
          job->status() == CompileJobStatus::kFailed;
 }
 
+bool CanRunOnAnyThread(CompilerDispatcherJob* job) {
+  return (job->status() == CompileJobStatus::kReadyToParse &&
+          job->can_parse_on_background_thread()) ||
+         (job->status() == CompileJobStatus::kReadyToCompile &&
+          job->can_compile_on_background_thread());
+}
+
+void DoNextStepOnBackgroundThread(CompilerDispatcherJob* job) {
+  DCHECK(CanRunOnAnyThread(job));
+  switch (job->status()) {
+    case CompileJobStatus::kReadyToParse:
+      job->Parse();
+      break;
+
+    case CompileJobStatus::kReadyToCompile:
+      job->Compile();
+      break;
+
+    default:
+      UNREACHABLE();
+  }
+}
+
 // Theoretically we get 50ms of idle time max, however it's unlikely that
 // we'll get all of it so try to be a conservative.
 const double kMaxIdleTimeToExpectInMs = 40;
 
 }  // namespace
 
+class CompilerDispatcher::BackgroundTask : public CancelableTask {
+ public:
+  BackgroundTask(Isolate* isolate, CompilerDispatcher* dispatcher);
+  ~BackgroundTask() override;
+
+  // CancelableTask implementation.
+  void RunInternal() override;
+
+ private:
+  CompilerDispatcher* dispatcher_;
+
+  DISALLOW_COPY_AND_ASSIGN(BackgroundTask);
+};
+
+CompilerDispatcher::BackgroundTask::BackgroundTask(
+    Isolate* isolate, CompilerDispatcher* dispatcher)
+    : CancelableTask(isolate), dispatcher_(dispatcher) {}
+
+CompilerDispatcher::BackgroundTask::~BackgroundTask() {}
+
+void CompilerDispatcher::BackgroundTask::RunInternal() {
+  dispatcher_->DoBackgroundWork();
+}
+
 class CompilerDispatcher::IdleTask : public CancelableIdleTask {
  public:
   IdleTask(Isolate* isolate, CompilerDispatcher* dispatcher);
   ~IdleTask() override;
 
   // CancelableIdleTask implementation.
   void RunInternal(double deadline_in_seconds) override;
 
  private:
   CompilerDispatcher* dispatcher_;
@@ skipping 10 matching lines @@
 void CompilerDispatcher::IdleTask::RunInternal(double deadline_in_seconds) {
   dispatcher_->DoIdleWork(deadline_in_seconds);
 }
 
 CompilerDispatcher::CompilerDispatcher(Isolate* isolate, Platform* platform,
                                        size_t max_stack_size)
     : isolate_(isolate),
       platform_(platform),
       max_stack_size_(max_stack_size),
       tracer_(new CompilerDispatcherTracer(isolate_)),
-      idle_task_scheduled_(false) {}
+      idle_task_scheduled_(false),
+      num_scheduled_background_tasks_(0),
+      num_available_background_jobs_(0),
+      main_thread_blocking_on_job_(nullptr) {}
 
 CompilerDispatcher::~CompilerDispatcher() {
   // To avoid crashing in unit tests due to unfished jobs.
   AbortAll(BlockingBehavior::kBlock);
 }
 
 bool CompilerDispatcher::Enqueue(Handle<SharedFunctionInfo> function) {
   if (!IsEnabled()) return false;
 
   // We only handle functions (no eval / top-level code / wasm) that are
   // attached to a script.
   if (!function->script()->IsScript() || !function->is_function() ||
       function->asm_function() || function->native()) {
     return false;
   }
 
   if (IsEnqueued(function)) return true;
   std::unique_ptr<CompilerDispatcherJob> job(new CompilerDispatcherJob(
       isolate_, tracer_.get(), function, max_stack_size_));
   std::pair<int, int> key(Script::cast(function->script())->id(),
                           function->function_literal_id());
   jobs_.insert(std::make_pair(key, std::move(job)));
   ScheduleIdleTaskIfNeeded();
   return true;
 }
 
 bool CompilerDispatcher::IsEnabled() const {
   v8::Isolate* v8_isolate = reinterpret_cast<v8::Isolate*>(isolate_);
-  return FLAG_compiler_dispatcher && platform_->IdleTasksEnabled(v8_isolate);
+  return FLAG_compiler_dispatcher && platform_->IdleTasksEnabled(v8_isolate) &&
+         platform_->NumberOfAvailableBackgroundThreads() > 0;

[vogelheim, 2017/01/02 17:16:24]

Generally speaking, it would be nice if the dispatcher could work on 'low-end'
devices to exploit idle time, and high-end to exploit idle time + multiple
cores. This looks like it will block the former.

An alternative might be to check for
   platform_->NumberOfAvailableBackgroundThreads() > 0;
in 
  CanRunOnAnyThread


That's admittedly a bit obtuse, since the platform isn't really a property of a
job. Not sure it's worthwhile, though. Or if it's worthwhile now.

[jochen (gone - plz use gerrit), 2017/01/02 19:39:39]

fair point. Since we only schedule background tasks up to
NumberOfAvailableBackgroundThreads() I guess I could just drop that here

 }
 
 bool CompilerDispatcher::IsEnqueued(Handle<SharedFunctionInfo> function) const {
   return GetJobFor(function) != jobs_.end();
 }
 
+void CompilerDispatcher::EnsureNotOnBackground(CompilerDispatcherJob* job) {
+  base::LockGuard<base::Mutex> lock(&mutex_);
+  if (running_background_jobs_.find(job) == running_background_jobs_.end()) {
+    pending_background_jobs_.erase(job);

[vogelheim, 2017/01/02 17:16:24]

Do you need to update num_available_background_jobs_ here?

[jochen (gone - plz use gerrit), 2017/01/02 19:39:39]

actually, I don't need that variable anymore, so I removed it

+    return;
+  }
+  DCHECK_NULL(main_thread_blocking_on_job_);
+  main_thread_blocking_on_job_ = job;
+  while (main_thread_blocking_on_job_ != nullptr) {
+    main_thread_blocking_signal_.Wait(&mutex_);
+  }
+  DCHECK(pending_background_jobs_.find(job) == pending_background_jobs_.end());
+}
+
 bool CompilerDispatcher::FinishNow(Handle<SharedFunctionInfo> function) {
   JobMap::const_iterator job = GetJobFor(function);
   CHECK(job != jobs_.end());
 
-  // TODO(jochen): Check if there's an in-flight background task working on this
-  // job.
+  EnsureNotOnBackground(job->second.get());
   while (!IsFinished(job->second.get())) {
     DoNextStepOnMainThread(isolate_, job->second.get(),
                            ExceptionHandling::kThrow);
   }
   bool result = job->second->status() != CompileJobStatus::kFailed;
   job->second->ResetOnMainThread();
   jobs_.erase(job);
   return result;
 }
 
 void CompilerDispatcher::Abort(Handle<SharedFunctionInfo> function,
                                BlockingBehavior blocking) {
   USE(blocking);
   JobMap::const_iterator job = GetJobFor(function);
   CHECK(job != jobs_.end());
 
-  // TODO(jochen): Check if there's an in-flight background task working on this
-  // job.
+  EnsureNotOnBackground(job->second.get());
   job->second->ResetOnMainThread();
   jobs_.erase(job);
 }
 
 void CompilerDispatcher::AbortAll(BlockingBehavior blocking) {
   USE(blocking);
-  // TODO(jochen): Check if there's an in-flight background task working on this
-  // job.
   for (auto& kv : jobs_) {
+    EnsureNotOnBackground(kv.second.get());
     kv.second->ResetOnMainThread();
   }
   jobs_.clear();
 }
 
 CompilerDispatcher::JobMap::const_iterator CompilerDispatcher::GetJobFor(
     Handle<SharedFunctionInfo> shared) const {
   if (!shared->script()->IsScript()) return jobs_.end();
   std::pair<int, int> key(Script::cast(shared->script())->id(),
                           shared->function_literal_id());
   auto range = jobs_.equal_range(key);
   for (auto job = range.first; job != range.second; ++job) {
     if (job->second->IsAssociatedWith(shared)) return job;
   }
   return jobs_.end();
 }
 
 void CompilerDispatcher::ScheduleIdleTaskIfNeeded() {
   v8::Isolate* v8_isolate = reinterpret_cast<v8::Isolate*>(isolate_);
   DCHECK(platform_->IdleTasksEnabled(v8_isolate));
   if (idle_task_scheduled_) return;
   if (jobs_.empty()) return;
   idle_task_scheduled_ = true;
   platform_->CallIdleOnForegroundThread(v8_isolate,
                                         new IdleTask(isolate_, this));
 }
 
+void CompilerDispatcher::ConsiderJobForBackgroundProcessing(
+    CompilerDispatcherJob* job) {
+  if (!CanRunOnAnyThread(job)) return;
+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    pending_background_jobs_.insert(job);
+    ++num_available_background_jobs_;
+  }
+  ScheduleMoreBackgroundTasksIfNeeded();
+}
+
+void CompilerDispatcher::ScheduleMoreBackgroundTasksIfNeeded() {
+  base::LockGuard<base::Mutex> lock(&mutex_);
+  if (num_available_background_jobs_ == 0) return;
+  if (platform_->NumberOfAvailableBackgroundThreads() <=
+      num_scheduled_background_tasks_) {
+    return;
+  }
+  ++num_scheduled_background_tasks_;
+  platform_->CallOnBackgroundThread(new BackgroundTask(isolate_, this),
+                                    v8::Platform::kShortRunningTask);
+}
+
+void CompilerDispatcher::DoBackgroundWork() {
+  CompilerDispatcherJob* job = nullptr;
+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    --num_scheduled_background_tasks_;
+    if (!pending_background_jobs_.empty()) {
+      auto it = pending_background_jobs_.begin();
+      job = *it;
+      pending_background_jobs_.erase(it);
+      running_background_jobs_.insert(job);
+      --num_available_background_jobs_;
+    }
+  }
+  if (job == nullptr) return;
+  DoNextStepOnBackgroundThread(job);
+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    running_background_jobs_.erase(job);
+
+    if (main_thread_blocking_on_job_ == job) {
+      main_thread_blocking_on_job_ = nullptr;
+      main_thread_blocking_signal_.NotifyOne();
+    }
+  }
+  ScheduleMoreBackgroundTasksIfNeeded();
+}
+
 void CompilerDispatcher::DoIdleWork(double deadline_in_seconds) {
   idle_task_scheduled_ = false;
 
   // Number of jobs that are unlikely to make progress during any idle callback
   // due to their estimated duration.
   size_t too_long_jobs = 0;
 
   // Iterate over all available jobs & remaining time. For each job, decide
   // whether to 1) skip it (if it would take too long), 2) erase it (if it's
   // finished), or 3) make progress on it.
   double idle_time_in_seconds =
       deadline_in_seconds - platform_->MonotonicallyIncreasingTime();
   for (auto job = jobs_.begin();
        job != jobs_.end() && idle_time_in_seconds > 0.0;
        idle_time_in_seconds =
            deadline_in_seconds - platform_->MonotonicallyIncreasingTime()) {
+    {
+      // Don't work on jobs that are being worked on by background tasks.
+      // Similarly, remove jobs we work on from the set of available background
+      // jobs.
+      base::LockGuard<base::Mutex> lock(&mutex_);
+      if (running_background_jobs_.find(job->second.get()) !=
+          running_background_jobs_.end()) {
+        ++job;
+        continue;
+      }
+      auto it = pending_background_jobs_.find(job->second.get());
+      if (it != pending_background_jobs_.end()) {
+        pending_background_jobs_.erase(it);
+        --num_available_background_jobs_;
+      }

[vogelheim, 2017/01/02 17:16:24]

This logic is a bit weird, because first we take it out of the
pending_background_jobs set, and then we might decide in the first if-branch to
put it back in. No big deal, but.. weird.

+    }

[vogelheim, 2017/01/02 17:16:24]

[opinion ahead; feel free to ignore:]


The can-idle or can-on-any-thread properties of the jobs don't really change...
I wonder if it would be simpler to record those properties in the jobs, have a
single mutex-locked queue of jobs, and then have the background and idle threads
'race' to pick available jobs of their respective type from that queue.

(I think the current logic tries to handle this more intelligently by putting
the different types of jobs into different queues/sets, but that 'distributes'
the information across many data structures. I find that difficult to follow.)


Related (and mostly arguing against my own proposal): It would be nice to have
some logic to make this --predictable, other than disabling the scheduler
entirely. The explicit assignment to queues probably makes that simpler. I'm not
really sure, though.

[jochen (gone - plz use gerrit), 2017/01/02 19:39:39]

the can-idle property can change, when the estimates get updated.

I don't think we can ever make this predictable, as idle time is just not
predictable..

[vogelheim, 2017/01/03 10:32:37]

Hmm. Not sure I'm willing to give this up yet. For --predictable, we could
implement a behaviour that it will always execute exactly one idle task
regardless of size for every DoIdleWork call, in strict enqueing order. That'd
be predictable, provided DoIdleWork calls are predictable.

Then d8 could have a platform implementation that has idle callbacks based on a
similarly predictable scheme.

That'd give us some test coverage for the scheduler & the idle tasks, while
(mostly?) preserving predictability.

[jochen (gone - plz use gerrit), 2017/01/03 12:59:35]

in d8, we do get predictable idle work calls, however, in chrome (or other
embedders) we don't.

I'd rather keep --predictable to be really predictable, as this helps with
debugging a lot

     double estimate_in_ms = job->second->EstimateRuntimeOfNextStepInMs();
     if (idle_time_in_seconds <
         (estimate_in_ms /
          static_cast<double>(base::Time::kMillisecondsPerSecond))) {
       // If there's not enough time left, try to estimate whether we would
       // have managed to finish the job in a large idle task to assess
       // whether we should ask for another idle callback.
       if (estimate_in_ms > kMaxIdleTimeToExpectInMs) ++too_long_jobs;
+      ConsiderJobForBackgroundProcessing(job->second.get());
       ++job;
     } else if (IsFinished(job->second.get())) {
       job->second->ResetOnMainThread();
       job = jobs_.erase(job);
       break;
     } else {
       // Do one step, and keep processing the job (as we don't advance the
       // iterator).
       DoNextStepOnMainThread(isolate_, job->second.get(),
                              ExceptionHandling::kSwallow);
     }
   }
   if (jobs_.size() > too_long_jobs) ScheduleIdleTaskIfNeeded();
 }
 
 }  // namespace internal
 }  // namespace v8