TaskScheduler [4/9] Priority Queue

base/task_scheduler/priority_queue.cc

Index: base/task_scheduler/priority_queue.cc
diff --git a/base/task_scheduler/priority_queue.cc b/base/task_scheduler/priority_queue.cc
new file mode 100644
index 0000000000000000000000000000000000000000..180371f649adf7462f8fc38b12ed09af01ee9edf
--- /dev/null
+++ b/base/task_scheduler/priority_queue.cc
@@ -0,0 +1,95 @@
+// Copyright 2016 The Chromium 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 "base/task_scheduler/priority_queue.h"
+
+#include <utility>
+
+#include "base/logging.h"
+
+namespace base {
+namespace internal {
+
+PriorityQueue::SequenceAndSortKey::SequenceAndSortKey()
+    : sort_key(TaskPriority::LOWEST, TimeTicks()) {}
+
+PriorityQueue::SequenceAndSortKey::SequenceAndSortKey(
+    scoped_refptr<Sequence> sequence,
+    SequenceSortKey sort_key)
+    : sequence(sequence), sort_key(sort_key) {}

[danakj, 2016/03/17 21:32:14]

move the sequence

[fdoray, 2016/03/18 16:06:55]

Done.

+
+PriorityQueue::SequenceAndSortKey::~SequenceAndSortKey() = default;
+
+bool PriorityQueue::SequenceAndSortKey::is_null() const {

[danakj, 2016/03/17 21:32:14]

hacker_style methods should be inline. otherwise it's IsNull.

[fdoray, 2016/03/18 16:06:55]

Done.

+  return sequence.get() == nullptr;

[danakj, 2016/03/17 21:32:14]

fwiw, return !!sequence also works, either way.

[fdoray, 2016/03/18 16:06:55]

Done.

+}
+
+PriorityQueue::PriorityQueue(const Closure& sequence_inserted_callback)
+    : sequence_inserted_callback_(sequence_inserted_callback) {
+  DCHECK(!sequence_inserted_callback_.is_null());
+}
+
+PriorityQueue::PriorityQueue(const Closure& sequence_inserted_callback,
+                             const PriorityQueue* predecessor_priority_queue)
+    : lock_(&predecessor_priority_queue->lock_),
+      sequence_inserted_callback_(sequence_inserted_callback) {
+  DCHECK(!sequence_inserted_callback_.is_null());
+  DCHECK(predecessor_priority_queue);
+}
+
+PriorityQueue::~PriorityQueue() = default;
+
+PriorityQueue::Transaction::~Transaction() {
+  DCHECK(CalledOnValidThread());
+
+  // Run the sequence insertion callback once for each Sequence that was
+  // inserted in the PriorityQueue during the lifetime of this Transaction.
+  // Perform this outside the scope of PriorityQueue's lock to avoid imposing an
+  // unnecessary lock dependency on |sequence_inserted_callback_|'s destination.
+  auto_lock_.reset();
+  for (size_t i = 0; i < num_pushed_sequences_; ++i)
+    outer_->sequence_inserted_callback_.Run();
+}
+
+void PriorityQueue::Transaction::Push(
+    scoped_ptr<SequenceAndSortKey> sequence_and_sort_key) {
+  DCHECK(CalledOnValidThread());
+  DCHECK(!sequence_and_sort_key->is_null());
+
+  outer_->container_.push(std::move(sequence_and_sort_key));
+  ++num_pushed_sequences_;
+}
+
+PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::Peek() const {

[danakj, 2016/03/17 21:32:14]

why not return a const reference?

[fdoray, 2016/03/18 16:06:55]

I changed the code to return a const reference. However, I don't think it's a
good idea because we'll have to be extremely careful not to use the reference
after it has been popped from the pq (see code below).

Alternative solutions (I prefer solution 3):
1. Return by value. No questions about lifetime.
2. Return a pointer. Same questions about lifetime, but we can return nullptr
instead of |empty_sequence_and_sort_key_| to indicate that the pq is empty.
3. Change the API to return a "SequenceSortKey" (instead of SequenceAndSortKey)
in Peek and a scoped_refptr<Sequence> in Pop(). SequenceSortKey is a struct with
TaskPriority+TimeTicks so it is less costly to copy than a SequenceAndSortKey
with a scoped_refptr<Sequence>. 

With solution 3, the WorkerThread::GetWork code would look like this:

scoped_refptr<Sequence> GetWork() {
  auto single_thread_transaction = single_thread_pq_->BeginTransaction();
  auto shared_transaction = shared_pq_->BeginTransaction();
  auto single_thread_key = single_thread_transaction->Peek();
  auto shared_key = shared_transaction->Peek();

  // Make sure that Peek() returns a key which compares less than any other
  // key when the pq is empty.

  if (single_thread_key > shared_key)
    return single_thread_transaction->Pop();
  return shared_transaction->Pop();
}

instead of like this with the current API (solution 1):

scoped_refptr<Sequence> GetWork() {
  auto single_thread_transaction = single_thread_pq_->BeginTransaction();
  auto shared_transaction = shared_pq_->BeginTransaction();
  auto single_thread_seq_and_key = single_thread_transaction->Peek();
  auto shared_key_seq_and_key = shared_transaction->Peek();

  if (single_thread_seq_and_key.is_null() &&
single_thread_seq_and_key.is_null())
    return scoped_ref_ptr<Sequence>();

  if (single_thread_seq_and_key.key > shared_seq_and_key.key) {
    single_thread_transaction->Pop();

    // If |single_thread_seq_and_key| was a reference, it couldn't be used after
    // the Pop().
    return single_thread_seq_and_key.seq;
  }

  shared_transaction->Pop();
  return shared_seq_and_key.seq;
}

WDYT?

[robliao, 2016/03/18 17:11:55]

Is the cost of having the Sequence with the sort key that high? It was nice to
have these two elements logically grouped.

[danakj, 2016/03/18 17:44:17]

If you look at container_.top(), it returns a const reference. It's normal for
methods like this to do so. If you remove it from the container you can't use
the reference, yeah, but that seems okay to me. You need to think about that
whenever you store a reference.

Normally you wouldn't store a ref, but it's nice for code like Peek().foo(). Now
you didn't need to copy the result of Peek() just to call foo() on it.

[fdoray, 2016/03/18 19:35:28]

OK, makes sense. In the latest patch set, Peek() returns a const ref as you
suggested.

+  DCHECK(CalledOnValidThread());
+
+  if (outer_->container_.empty())
+    return SequenceAndSortKey();
+
+  return *outer_->container_.top();
+}
+
+void PriorityQueue::Transaction::Pop() {
+  DCHECK(CalledOnValidThread());
+  DCHECK(!outer_->container_.empty());
+  outer_->container_.pop();
+}
+
+PriorityQueue::Transaction::Transaction(PriorityQueue* outer)

[danakj, 2016/03/17 21:32:14]

can you put this constructor above the destructor in this file?

[fdoray, 2016/03/18 16:06:55]

Done.

+    : outer_(outer), auto_lock_(new AutoSchedulerLock(outer_->lock_)) {
+  DCHECK(CalledOnValidThread());
+}
+
+scoped_ptr<PriorityQueue::Transaction> PriorityQueue::BeginTransaction() {
+  return make_scoped_ptr(new Transaction(this));
+}
+
+bool PriorityQueue::SequenceAndSortKeyComparator::operator()(
+    const scoped_ptr<SequenceAndSortKey>& left,
+    const scoped_ptr<SequenceAndSortKey>& right) const {
+  return left->sort_key < right->sort_key;

[danakj, 2016/03/17 21:32:14]

i think you could inline this in the header

[fdoray, 2016/03/18 16:06:55]

Done.

+}
+
+}  // namespace internal
+}  // namespace base