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 e84c5c6f46ebbcf6c254ef35aaabc478ed4c0016..cf58f57815ddef18da54a0fb57fe589dac274eb3 100644 |
--- a/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc |
+++ b/third_party/WebKit/Source/platform/scheduler/base/time_domain.cc |
@@ -13,6 +13,13 @@ |
namespace blink { |
namespace scheduler { |
+std::ostream& operator<<( |
+ std::ostream& os, |
+ const std::pair<base::TimeTicks, internal::TaskQueueImpl*>& pair) { |
+ os << "[" << pair.first << ", " << pair.second << "]"; |
+ return os; |
+} |
+ |
TimeDomain::TimeDomain(Observer* observer) : observer_(observer) {} |
TimeDomain::~TimeDomain() { |
@@ -22,6 +29,8 @@ TimeDomain::~TimeDomain() { |
void TimeDomain::RegisterQueue(internal::TaskQueueImpl* queue) { |
DCHECK(main_thread_checker_.CalledOnValidThread()); |
DCHECK_EQ(queue->GetTimeDomain(), this); |
+ |
+ queues_.insert(queue); |
} |
void TimeDomain::UnregisterQueue(internal::TaskQueueImpl* queue) { |
@@ -29,17 +38,15 @@ void TimeDomain::UnregisterQueue(internal::TaskQueueImpl* queue) { |
DCHECK_EQ(queue->GetTimeDomain(), this); |
UnregisterAsUpdatableTaskQueue(queue); |
- // If present remove |task_queue| from delayed_wakeup_multimap_. |
- // O(log n) |
- QueueToDelayedWakeupMultimapIteratorMap::iterator it = |
- queue_to_delayed_wakeup_multimap_iterator_map_.find(queue); |
- |
- if (it == queue_to_delayed_wakeup_multimap_iterator_map_.end()) |
+ // If no wakeup has been requested then bail out. |
+ if (queue->time_domain_wakeup().is_null()) |
return; |
- // O(1) amortized. |
- delayed_wakeup_multimap_.erase(it->second); |
- queue_to_delayed_wakeup_multimap_iterator_map_.erase(it); |
+ // O(log n + n / 2) |
+ delayed_wakeup_set_.erase(std::make_pair(queue->time_domain_wakeup(), queue)); |
+ queue->set_time_domain_wakeup(base::TimeTicks()); |
+ |
+ queues_.erase(queue); |
} |
void TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue, |
@@ -53,21 +60,17 @@ void TimeDomain::MigrateQueue(internal::TaskQueueImpl* queue, |
if (UnregisterAsUpdatableTaskQueue(queue)) |
destination_time_domain->updatable_queue_set_.insert(queue); |
- // If present remove |task_queue| from delayed_wakeup_multimap_. |
- // O(log n) |
- QueueToDelayedWakeupMultimapIteratorMap::iterator it = |
- queue_to_delayed_wakeup_multimap_iterator_map_.find(queue); |
- |
- if (it == queue_to_delayed_wakeup_multimap_iterator_map_.end()) |
+ // If no wakeup has been requested then bail out. |
+ if (queue->time_domain_wakeup().is_null()) |
return; |
- base::TimeTicks destination_now = destination_time_domain->Now(); |
- destination_time_domain->ScheduleDelayedWork(queue, it->second->first, |
- destination_now); |
+ // O(log n + n / 2) |
+ delayed_wakeup_set_.erase(std::make_pair(queue->time_domain_wakeup(), queue)); |
+ queue->set_time_domain_wakeup(base::TimeTicks()); |
- // O(1) amortized. |
- delayed_wakeup_multimap_.erase(it->second); |
- queue_to_delayed_wakeup_multimap_iterator_map_.erase(it); |
+ base::TimeTicks destination_now = destination_time_domain->Now(); |
+ destination_time_domain->ScheduleDelayedWork( |
+ queue, queue->time_domain_wakeup(), destination_now); |
} |
void TimeDomain::ScheduleDelayedWork(internal::TaskQueueImpl* queue, |
@@ -76,27 +79,20 @@ void TimeDomain::ScheduleDelayedWork(internal::TaskQueueImpl* queue, |
DCHECK(main_thread_checker_.CalledOnValidThread()); |
// We only want to store a single wakeup per queue, so we need to remove any |
// previously registered wake up for |queue|. |
- QueueToDelayedWakeupMultimapIteratorMap::iterator it = |
- queue_to_delayed_wakeup_multimap_iterator_map_.find(queue); |
- |
- if (it != queue_to_delayed_wakeup_multimap_iterator_map_.end()) |
- delayed_wakeup_multimap_.erase(it->second); |
+ if (!queue->time_domain_wakeup().is_null()) { |
+ delayed_wakeup_set_.erase( |
+ std::make_pair(queue->time_domain_wakeup(), queue)); |
+ queue->set_time_domain_wakeup(base::TimeTicks()); |
+ } |
- if (delayed_wakeup_multimap_.empty() || |
- delayed_run_time < delayed_wakeup_multimap_.begin()->first) { |
+ if (delayed_wakeup_set_.empty() || |
+ delayed_run_time < delayed_wakeup_set_.begin()->first) { |
base::TimeDelta delay = std::max(base::TimeDelta(), delayed_run_time - now); |
RequestWakeup(now, delay); |
} |
- if (it != queue_to_delayed_wakeup_multimap_iterator_map_.end()) { |
- // TODO(alexclarke): Use C++17 extract & insert to more efficiently modify |
- // |queue_to_delayed_wakeup_multimap_iterator_map_|. |
- it->second = delayed_wakeup_multimap_.insert({delayed_run_time, queue}); |
- } else { |
- // Insert the wakeup and store the map iterator for later convenience. |
- queue_to_delayed_wakeup_multimap_iterator_map_.insert( |
- {queue, delayed_wakeup_multimap_.insert({delayed_run_time, queue})}); |
- } |
+ delayed_wakeup_set_.insert(std::make_pair(delayed_run_time, queue)); |
+ queue->set_time_domain_wakeup(delayed_run_time); |
if (observer_) |
observer_->OnTimeDomainHasDelayedWork(queue); |
@@ -167,38 +163,31 @@ void TimeDomain::WakeupReadyDelayedQueues(LazyNow* lazy_now) { |
// Wake up any queues with pending delayed work. Note std::multipmap stores |
// the elements sorted by key, so the begin() iterator points to the earliest |
// queue to wakeup. |
- while (!delayed_wakeup_multimap_.empty()) { |
- DelayedWakeupMultimap::iterator next_wakeup = |
- delayed_wakeup_multimap_.begin(); |
- if (next_wakeup->first > lazy_now->Now()) |
- break; |
- |
- internal::TaskQueueImpl* queue = next_wakeup->second; |
- |
- // O(1) amortized. |
- delayed_wakeup_multimap_.erase(next_wakeup); |
- // O(log n). |
- queue_to_delayed_wakeup_multimap_iterator_map_.erase(queue); |
+ while (!delayed_wakeup_set_.empty() && |
+ delayed_wakeup_set_.begin()->first <= lazy_now->Now()) { |
+ internal::TaskQueueImpl* queue = delayed_wakeup_set_.begin()->second; |
+ delayed_wakeup_set_.erase(delayed_wakeup_set_.begin()); |
+ queue->set_time_domain_wakeup(base::TimeTicks()); |
queue->WakeUpForDelayedWork(lazy_now); |
} |
} |
bool TimeDomain::NextScheduledRunTime(base::TimeTicks* out_time) const { |
DCHECK(main_thread_checker_.CalledOnValidThread()); |
- if (delayed_wakeup_multimap_.empty()) |
+ if (delayed_wakeup_set_.empty()) |
return false; |
- *out_time = delayed_wakeup_multimap_.begin()->first; |
+ *out_time = delayed_wakeup_set_.begin()->first; |
return true; |
} |
bool TimeDomain::NextScheduledTaskQueue(TaskQueue** out_task_queue) const { |
DCHECK(main_thread_checker_.CalledOnValidThread()); |
- if (delayed_wakeup_multimap_.empty()) |
+ if (delayed_wakeup_set_.empty()) |
return false; |
- *out_task_queue = delayed_wakeup_multimap_.begin()->second; |
+ *out_task_queue = delayed_wakeup_set_.begin()->second; |
return true; |
} |
@@ -209,9 +198,9 @@ void TimeDomain::AsValueInto(base::trace_event::TracedValue* state) const { |
for (auto* queue : updatable_queue_set_) |
state->AppendString(queue->GetName()); |
state->EndArray(); |
- state->SetInteger("registered_delay_count", delayed_wakeup_multimap_.size()); |
- if (!delayed_wakeup_multimap_.empty()) { |
- base::TimeDelta delay = delayed_wakeup_multimap_.begin()->first - Now(); |
+ state->SetInteger("registered_delay_count", delayed_wakeup_set_.size()); |
+ if (!delayed_wakeup_set_.empty()) { |
+ base::TimeDelta delay = delayed_wakeup_set_.begin()->first - Now(); |
state->SetDouble("next_delay_ms", delay.InMillisecondsF()); |
} |
AsValueIntoInternal(state); |