Use idle time to make progress on scheduled compilation jobs

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 <queue>
+
+#include "include/v8-platform.h"
+#include "include/v8.h"
+#include "src/base/platform/time.h"
+#include "src/cancelable-task.h"
 #include "src/compiler-dispatcher/compiler-dispatcher-job.h"
 #include "src/compiler-dispatcher/compiler-dispatcher-tracer.h"
 #include "src/objects-inl.h"
 
 namespace v8 {
 namespace internal {
 
 namespace {
 
-bool DoNextStepOnMainThread(CompilerDispatcherJob* job) {
+enum class ExceptionHandling { kSwallow, kKeep };
+
+bool DoNextStepOnMainThread(Isolate* isolate, CompilerDispatcherJob* job,
+                            ExceptionHandling exception_handling) {
+  v8::TryCatch try_catch(reinterpret_cast<v8::Isolate*>(isolate));
   switch (job->status()) {
     case CompileJobStatus::kInitial:
       job->PrepareToParseOnMainThread();
       break;
 
     case CompileJobStatus::kReadyToParse:
       job->Parse();
       break;
 
     case CompileJobStatus::kParsed:
@@ skipping 10 matching lines @@
 
     case CompileJobStatus::kCompiled:
       job->FinalizeCompilingOnMainThread();
       break;
 
     case CompileJobStatus::kFailed:
     case CompileJobStatus::kDone:
       break;
   }
 
+  if (exception_handling == ExceptionHandling::kKeep && try_catch.HasCaught()) {
+    try_catch.ReThrow();
+  }

[marja, 2016/12/13 09:09:01]

Can we assert here that if the try catch has caught, the status is kFailed?

[jochen (gone - plz use gerrit), 2016/12/15 13:54:34]

done

   return job->status() != CompileJobStatus::kFailed;
 }
 
 bool IsFinished(CompilerDispatcherJob* job) {
   return job->status() == CompileJobStatus::kDone ||
          job->status() == CompileJobStatus::kFailed;
 }
 
 }  // namespace
 
-CompilerDispatcher::CompilerDispatcher(Isolate* isolate, size_t max_stack_size)
+class CompilerDispatcher::IdleTask : public CancelableIdleTask {
+ public:
+  IdleTask(Isolate* isolate, CompilerDispatcher* dispatcher);
+  ~IdleTask() override;
+
+  // CancelableIdleTask implementation.

[vogelheim, 2016/12/12 17:51:32]

I don't understand the comment. If the intention is to underline that this
implements a super-class method, doesn't override already say that?

[jochen (gone - plz use gerrit), 2016/12/12 20:28:25]

it's a common pattern in chromium code as it has multiple inheritance, so you
can easily see which methods come from which base class:
https://cs.chromium.org/search/?q=//%5C+.*%5C+implementation%5C.$+file:h$

[vogelheim, 2016/12/13 09:40:33]

Acknowledged.

+  void RunInternal(double deadline_in_seconds) override;
+
+ private:
+  CompilerDispatcher* dispatcher_;
+
+  DISALLOW_COPY_AND_ASSIGN(IdleTask);
+};
+
+CompilerDispatcher::IdleTask::IdleTask(Isolate* isolate,
+                                       CompilerDispatcher* dispatcher)
+    : CancelableIdleTask(isolate), dispatcher_(dispatcher) {}
+
+CompilerDispatcher::IdleTask::~IdleTask() {}
+
+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_)) {}
+      tracer_(new CompilerDispatcherTracer(isolate_)),
+      idle_task_scheduled_(false) {}
 
 CompilerDispatcher::~CompilerDispatcher() {}
 
 bool CompilerDispatcher::Enqueue(Handle<SharedFunctionInfo> function) {
   // 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::IsEnqueued(Handle<SharedFunctionInfo> function) const {
   return GetJobFor(function) != 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.
   while (!IsFinished(job->second.get())) {
-    DoNextStepOnMainThread(job->second.get());
+    DoNextStepOnMainThread(isolate_, job->second.get(),
+                           ExceptionHandling::kKeep);
   }
   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.
+  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_) {
+    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_);
+  if (!platform_->IdleTasksEnabled(v8_isolate)) return;
+  if (idle_task_scheduled_) return;
+  if (jobs_.empty()) return;
+  idle_task_scheduled_ = true;
+  platform_->CallIdleOnForegroundThread(v8_isolate,
+                                        new IdleTask(isolate_, this));
+}
+
+void CompilerDispatcher::DoIdleWork(double deadline_in_seconds) {
+  idle_task_scheduled_ = false;

[marja, 2016/12/13 09:09:01]

Could you add assert(we're on the main thread) to the relevant functions of this
class?

+
+  // Collect all candidates for running their respective next step during
+  // idle time and sort by how long they're likely to take.

[marja, 2016/12/13 09:09:01]

Hmm, it looks inefficient to iterate through all idle tasks every time we're
idle for a moment - can we cache some of this information?

+  auto cmp = [](const std::pair<double, JobMap::const_iterator>& a,
+                const std::pair<double, JobMap::const_iterator>& b) {
+    return a.first < b.first;
+  };
+  std::priority_queue<std::pair<double, JobMap::const_iterator>,
+                      std::vector<std::pair<double, JobMap::const_iterator>>,
+                      decltype(cmp)>
+      runtimes(cmp);
+  for (JobMap::const_iterator it = jobs_.begin(); it != jobs_.end(); ++it) {
+    if (IsFinished(it->second.get())) continue;
+    // TODO(jochen): Check if there's an in-flight background task working on
+    // this job.
+    runtimes.push(std::make_pair(
+        it->second->EstimateRuntimeOfNextStepInMs() /

[vogelheim, 2016/12/12 17:51:32]

Every one of these will look the same lock, right? Maybe lock it once outside
the loop?

[Probably won't be a big deal, though.]

[jochen (gone - plz use gerrit), 2016/12/12 20:28:25]

right, dunno how much of an issue that is?

+            static_cast<double>(base::Time::kMillisecondsPerSecond),
+        it));
+  }
+
+  for (double idle_time_in_seconds =

[marja, 2016/12/13 09:21:13]

What if coming up with the priority queue takes so long that we have no time
left here? What should happen - should we always advance at least one task?

+           deadline_in_seconds - platform_->MonotonicallyIncreasingTime();
+       idle_time_in_seconds > 0.0;
+       idle_time_in_seconds =
+           deadline_in_seconds - platform_->MonotonicallyIncreasingTime()) {

[marja, 2016/12/13 09:09:01]

This loop is mildly confusing.

Why not just:

while (double idle_time_in_seconds = deadline_in_seconds -
platform_->MonotonicallyIncreasingTime() > 0) {
...
}

+    // Skip jobs we can't do in the remaining time budget.
+    while (!runtimes.empty() && runtimes.top().first > idle_time_in_seconds) {
+      runtimes.pop();

[vogelheim, 2016/12/12 17:51:32]

If runtimes is a priority queue by expected runtime, wouldn't it suffice to exit
the loop when the 1st 'too large' job is encountered?

[vogelheim, 2016/12/12 17:51:32]

[Not sure:] What happens when there is a job whose runtime estimate is very
large? 

We'll re-consider it & drop it on every idle task, until the function is finally
run (&compiled) by the main thread?

[jochen (gone - plz use gerrit), 2016/12/12 20:28:25]

So far, the biggest task comes first. I guess I could invert the ordering and
let the smallest task be processed first.
either by the main thread, or a background thread.

the thing is, once a background thread made progress on a task, we have to do
the next step on the main thread again (and it's hopefully a small finalization
step), so I can't permanently remove jobs from being considered for idle time
compilation.

maybe there should be a list of jobs that are handled by the background part
(once it exists)

[vogelheim, 2016/12/13 09:40:33]

Ah, I misread that and assumed we'd process tasks in ascending order. When
sorted in descending order it makes sense.

+    }
+    if (runtimes.empty()) break;
+
+    JobMap::const_iterator job = runtimes.top().second;
+    runtimes.pop();
+    DoNextStepOnMainThread(isolate_, job->second.get(),
+                           ExceptionHandling::kSwallow);
+
+    if (IsFinished(job->second.get())) {
+      job->second->ResetOnMainThread();
+      jobs_.erase(job);
+      continue;
+    }
+
+    // Put the job back on the queue in case there is time left.
+    runtimes.push(std::make_pair(
+        job->second->EstimateRuntimeOfNextStepInMs() /
+            static_cast<double>(base::Time::kMillisecondsPerSecond),
+        job));

[vogelheim, 2016/12/12 17:51:32]

[Not sure:] It might make sense to store
  auto current = runtimes.top()
  JobMap::const_iterator job& = current.second;
up there, in which case you wouldn't need to rebuild the pair here (would drop
one mutex call).

[jochen (gone - plz use gerrit), 2016/12/12 20:28:25]

we still need the mutex, because after having made one step, we need to estimate
the length for the next step here

[vogelheim, 2016/12/13 09:40:33]

Ah.

For my understanding: Why would the time estimate change, vs the one the job had
assigned in line #220 ?

From reading the code, it seems to compute the average progress rate of the
various steps. So technically it would be a different value, but.. not by much,
right?

[jochen (gone - plz use gerrit), 2016/12/15 13:54:34]

in line 222 the job does one step, and i gets reinserted with the estimate for
the next step

+  }
+  ScheduleIdleTaskIfNeeded();
+}
+
 }  // namespace internal
 }  // namespace v8