TaskScheduler: Avoid Sequence refcount bump in GetWork()

base/task_scheduler/priority_queue.cc

 // 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"
 #include "base/memory/ptr_util.h"
 
 namespace base {
 namespace internal {
 
-PriorityQueue::SequenceAndSortKey::SequenceAndSortKey()
-    : sort_key(TaskPriority::LOWEST, TimeTicks()) {}
+// A class combining a Sequence and the SequenceSortKey that determines its
+// position in a PriorityQueue. Instances are only mutable via take_sequence()
+// which can only be called once and renders its instance invalid after the
+// call.
+class PriorityQueue::SequenceAndSortKey {
+ public:
+  SequenceAndSortKey(scoped_refptr<Sequence>&& sequence,
+                     const SequenceSortKey& sort_key)
+      : sequence_(sequence), sort_key_(sort_key) {
+    DCHECK(sequence_);
+  }
 
-PriorityQueue::SequenceAndSortKey::SequenceAndSortKey(
-    scoped_refptr<Sequence> sequence,
-    const SequenceSortKey& sort_key)
-    : sequence(std::move(sequence)), sort_key(sort_key) {}
+  // Note: while |sequence_| should always be non-null post-move (i.e. we
+  // shouldn't be moving an invalid SequenceAndSortKey around), there can't be a
+  // DCHECK(sequence_) on moves as the Windows STL moves elements on pop instead
+  // of overwriting them: resulting in the move of a SequenceAndSortKey with a
+  // null |sequence_| in Transaction::Pop()'s implementation.
+  SequenceAndSortKey::SequenceAndSortKey(SequenceAndSortKey&& other) = default;
+  SequenceAndSortKey& SequenceAndSortKey::operator=(
+      SequenceAndSortKey&& other) = default;
 
-PriorityQueue::SequenceAndSortKey::~SequenceAndSortKey() = default;
+  // Extracts |sequence_| from this object. This object is invalid after this
+  // call.
+  scoped_refptr<Sequence>&& take_sequence() {

[fdoray, 2016/04/27 01:05:10]

&& isn't required according to my test program:

struct A {
  A() = default;
  A(const A& other) { LOG(ERROR) << "copy"; }
  A(A&& other) { LOG(ERROR) << "move"; }
  void operator=(const A& other) { LOG(ERROR) << "copy assign"; }
  void operator=(A&& other) { LOG(ERROR) << "move assign"; }
};

struct B {
  A take_A() { return std::move(a); }
  A&& take_A_rvalue() { return std::move(a); }
  A copy_A() { return a; }
  A a;
};

B b;

A a1 = b.take_A_rvalue();
// output: move

A a2 = b.take_A();
// output: move

[gab, 2016/04/27 20:40:30]

The one thing it did is force the std::move in the impl, i.e.:

A&& take_A_rvalue() { return a; }  // doesn't compile
A take_A() { return a; }  // compiles if |a| has a copy constructor

In my code the compile error for this was:
d:\src\chrome\src\base\task_scheduler\priority_queue.cc(40): error C2440:
'return': cannot convert from 'scoped_refptr<base::internal::Sequence>' to
'scoped_refptr<base::internal::Sequence> &&'
d:\src\chrome\src\base\task_scheduler\priority_queue.cc(40): note: You cannot
bind an lvalue to an rvalue reference

Which means the user of the API can know for sure it's actually given the ref
(which is the contract) instead of a copy of it.

But anyways I just learnt yesterday on chromium-dev that rvalues aren't allowed
by style guide outside of move-constructor/move-assign. So this point is moot
and it's not much worse off without the explicit rvalue :-).

But not being allowed to use explicit rvalues makes this change fairly hard as
the whole point is avoiding a refbump yet this change would totally compile with
many std::move removed, causing more implicit refbumps than the one it's trying
to solve..!

+    DCHECK(sequence_);
+    return std::move(sequence_);
+  }
+
+  // Compares this SequenceAndSortKey to |other| based on their respective
+  // |sort_key_|.
+  bool operator<(const SequenceAndSortKey& other) const {
+    return sort_key_ < other.sort_key_;
+  }
+  bool operator>(const SequenceAndSortKey& other) const {
+    return other < *this;
+  }
+
+  const SequenceSortKey& sort_key() const { return sort_key_; }
+
+ private:
+  scoped_refptr<Sequence> sequence_;
+  SequenceSortKey sort_key_;
+
+  DISALLOW_COPY_AND_ASSIGN(SequenceAndSortKey);
+};
 
 PriorityQueue::Transaction::Transaction(PriorityQueue* outer_queue)
     : auto_lock_(outer_queue->container_lock_), outer_queue_(outer_queue) {
   DCHECK(CalledOnValidThread());
 }
 
 PriorityQueue::Transaction::~Transaction() {
   DCHECK(CalledOnValidThread());
 }
 
 void PriorityQueue::Transaction::Push(
-    std::unique_ptr<SequenceAndSortKey> sequence_and_sort_key) {
+    scoped_refptr<Sequence> sequence,
+    const SequenceSortKey& sequence_sort_key) {
   DCHECK(CalledOnValidThread());
-  DCHECK(!sequence_and_sort_key->is_null());
-
-  outer_queue_->container_.push(std::move(sequence_and_sort_key));
+  outer_queue_->container_.emplace(std::move(sequence), sequence_sort_key);
 }
 
-const PriorityQueue::SequenceAndSortKey& PriorityQueue::Transaction::Peek()
-    const {
+const SequenceSortKey& PriorityQueue::Transaction::PeekSortKey() const {
   DCHECK(CalledOnValidThread());
-
-  // TODO(fdoray): Add an IsEmpty() method to Transaction and require Peek() to
-  // be called on a non-empty PriorityQueue only.
-  if (outer_queue_->container_.empty())
-    return outer_queue_->empty_sequence_and_sort_key_;
-
-  return *outer_queue_->container_.top();
+  DCHECK(!outer_queue_->container_.empty());

[fdoray, 2016/04/27 01:05:10]

!IsEmpty()?

[gab, 2016/04/27 20:40:30]

Done.

+  return outer_queue_->container_.top().sort_key();
 }
 
-void PriorityQueue::Transaction::Pop() {
+scoped_refptr<Sequence> PriorityQueue::Transaction::PopSequence() {
   DCHECK(CalledOnValidThread());
   DCHECK(!outer_queue_->container_.empty());

[fdoray, 2016/04/27 01:05:10]

!IsEmpty()?

[gab, 2016/04/27 20:40:30]

Done.

+
+  // The const_cast on top() is okay since the SequenceAndSortKey is
+  // transactionally being popped from |container_| right after and taking its
+  // Sequence does not alter its sort order (a requirement for the Windows STL's
+  // consistency debug-checks for std::priority_queue::top()).
+  scoped_refptr<Sequence> sequence =
+      const_cast<PriorityQueue::SequenceAndSortKey&>(
+          outer_queue_->container_.top())
+          .take_sequence();
   outer_queue_->container_.pop();
+  return sequence;
+}
+
+bool PriorityQueue::Transaction::IsEmpty() {
+  return outer_queue_->container_.empty();
 }
 
 PriorityQueue::PriorityQueue() = default;
 
 PriorityQueue::PriorityQueue(const PriorityQueue* predecessor_priority_queue)
     : container_lock_(&predecessor_priority_queue->container_lock_) {
   DCHECK(predecessor_priority_queue);
 }
 
 PriorityQueue::~PriorityQueue() = default;
 
 std::unique_ptr<PriorityQueue::Transaction> PriorityQueue::BeginTransaction() {
   return WrapUnique(new Transaction(this));
 }
 
 }  // namespace internal
 }  // namespace base