[Try # 3] Scheduler refactoring to virtually eliminate redundant DoWorks

third_party/WebKit/Source/platform/scheduler/base/time_domain.cc

Index: third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
diff --git a/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc b/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
index 59e3e3476f776d525a833bef262c7a7a6f4d76a5..454678e5c7c8ae5d128a660a0cce681f94bf3c99 100644
--- a/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
+++ b/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc
@@ -27,32 +27,19 @@ void TimeDomain::RegisterQueue(internal::TaskQueueImpl* queue) {
 void TimeDomain::UnregisterQueue(internal::TaskQueueImpl* queue) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
   DCHECK_EQ(queue->GetTimeDomain(), this);
-  UnregisterAsUpdatableTaskQueue(queue);
 
-  // If no wakeup has been requested then bail out.
-  if (!queue->heap_handle().IsValid())
-    return;
-
-  DCHECK_NE(queue->scheduled_time_domain_wakeup(), base::TimeTicks());
-
-  // O(log n)
-  delayed_wakeup_queue_.erase(queue->heap_handle());
+  CancelDelayedWork(queue);
 }
 
-void TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue,
-                              TimeDomain* destination_time_domain) {
+base::TimeTicks TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue,
+                                         TimeDomain* destination_time_domain) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
   DCHECK_EQ(queue->GetTimeDomain(), this);
   DCHECK(destination_time_domain);
 
-  // Make sure we remember to update |queue| if it's got incoming immediate
-  // work.
-  if (UnregisterAsUpdatableTaskQueue(queue))
-    destination_time_domain->updatable_queue_set_.insert(queue);
-
   // If no wakeup has been requested then bail out.
   if (!queue->heap_handle().IsValid())
-    return;
+    return base::TimeTicks();
 
   base::TimeTicks wake_up_time = queue->scheduled_time_domain_wakeup();
   DCHECK_NE(wake_up_time, base::TimeTicks());
@@ -60,15 +47,14 @@ void TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue,
   // O(log n)
   delayed_wakeup_queue_.erase(queue->heap_handle());
 
-  base::TimeTicks destination_now = destination_time_domain->Now();
-  destination_time_domain->ScheduleDelayedWork(queue, wake_up_time,
-                                               destination_now);
+  return wake_up_time;
 }
 
 void TimeDomain::ScheduleDelayedWork(internal::TaskQueueImpl* queue,
                                      base::TimeTicks delayed_run_time,
                                      base::TimeTicks now) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
+  DCHECK_EQ(queue->GetTimeDomain(), this);
   // We only want to store a single wakeup per queue, so we need to remove any
   // previously registered wake up for |queue|.
   if (queue->heap_handle().IsValid()) {
@@ -94,64 +80,23 @@ void TimeDomain::ScheduleDelayedWork(internal::TaskQueueImpl* queue,
     observer_->OnTimeDomainHasDelayedWork(queue);
 }
 
-void TimeDomain::RegisterAsUpdatableTaskQueue(internal::TaskQueueImpl* queue) {
-  {
-    base::AutoLock lock(newly_updatable_lock_);
-    newly_updatable_.push_back(queue);
-  }
-  if (observer_)
-    observer_->OnTimeDomainHasImmediateWork(queue);
-}
-
-bool TimeDomain::UnregisterAsUpdatableTaskQueue(
-    internal::TaskQueueImpl* queue) {
-  DCHECK(main_thread_checker_.CalledOnValidThread());
-
-  bool was_updatable = updatable_queue_set_.erase(queue) != 0;
-
-  base::AutoLock lock(newly_updatable_lock_);
-  // Remove all copies of |queue| from |newly_updatable_|.
-  for (size_t i = 0; i < newly_updatable_.size();) {
-    if (newly_updatable_[i] == queue) {
-      // Move last element into slot #i and then compact.
-      newly_updatable_[i] = newly_updatable_.back();
-      newly_updatable_.pop_back();
-      was_updatable = true;
-    } else {
-      i++;
-    }
-  }
-  return was_updatable;
-}
-
-void TimeDomain::UpdateWorkQueues(LazyNow lazy_now) {
+void TimeDomain::CancelDelayedWork(internal::TaskQueueImpl* queue) {
   DCHECK(main_thread_checker_.CalledOnValidThread());
+  DCHECK_EQ(queue->GetTimeDomain(), this);
 
-  // Move any ready delayed tasks into the Incoming queues.
-  WakeupReadyDelayedQueues(&lazy_now);
-
-  MoveNewlyUpdatableQueuesIntoUpdatableQueueSet();
+  // If no wakeup has been requested then bail out.
+  if (!queue->heap_handle().IsValid())
+    return;
 
-  std::set<internal::TaskQueueImpl*>::iterator iter =
-      updatable_queue_set_.begin();
-  while (iter != updatable_queue_set_.end()) {
-    std::set<internal::TaskQueueImpl*>::iterator queue_it = iter++;
-    internal::TaskQueueImpl* queue = *queue_it;
+  DCHECK_NE(queue->scheduled_time_domain_wakeup(), base::TimeTicks());
 
-    // Update the queue and remove from the set if subsequent updates are not
-    // required.
-    if (!queue->MaybeUpdateImmediateWorkQueues())
-      updatable_queue_set_.erase(queue_it);
-  }
+  // O(log n)
+  delayed_wakeup_queue_.erase(queue->heap_handle());
 }
 
-void TimeDomain::MoveNewlyUpdatableQueuesIntoUpdatableQueueSet() {
-  DCHECK(main_thread_checker_.CalledOnValidThread());
-  base::AutoLock lock(newly_updatable_lock_);
-  while (!newly_updatable_.empty()) {
-    updatable_queue_set_.insert(newly_updatable_.back());
-    newly_updatable_.pop_back();
-  }
+void TimeDomain::OnQueueHasImmediateWork(internal::TaskQueueImpl* queue) {
+  if (observer_)
+    observer_->OnTimeDomainHasImmediateWork(queue);
 }
 
 void TimeDomain::WakeupReadyDelayedQueues(LazyNow* lazy_now) {
@@ -162,10 +107,18 @@ void TimeDomain::WakeupReadyDelayedQueues(LazyNow* lazy_now) {
   while (!delayed_wakeup_queue_.empty() &&
          delayed_wakeup_queue_.min().time <= lazy_now->Now()) {
     internal::TaskQueueImpl* queue = delayed_wakeup_queue_.min().queue;
-    // O(log n)
-    delayed_wakeup_queue_.pop();
+    base::Optional<base::TimeTicks> next_wakeup =
+        queue->WakeUpForDelayedWork(lazy_now);
 
-    queue->WakeUpForDelayedWork(lazy_now);
+    if (next_wakeup) {
+      // O(log n)
+      delayed_wakeup_queue_.ReplaceMin({next_wakeup.value(), queue});
+      queue->set_scheduled_time_domain_wakeup(next_wakeup.value());
+    } else {
+      // O(log n)
+      delayed_wakeup_queue_.pop();
+      DCHECK_EQ(queue->scheduled_time_domain_wakeup(), base::TimeTicks());
+    }
   }
 }
 
@@ -190,10 +143,6 @@ bool TimeDomain::NextScheduledTaskQueue(TaskQueue** out_task_queue) const {
 void TimeDomain::AsValueInto(base::trace_event::TracedValue* state) const {
   state->BeginDictionary();
   state->SetString("name", GetName());
-  state->BeginArray("updatable_queue_set");
-  for (auto* queue : updatable_queue_set_)
-    state->AppendString(queue->GetName());
-  state->EndArray();
   state->SetInteger("registered_delay_count", delayed_wakeup_queue_.size());
   if (!delayed_wakeup_queue_.empty()) {
     base::TimeDelta delay = delayed_wakeup_queue_.min().time - Now();