Bug 1410096 - Move labeled queues to SchedulerGroup. r=smaug
☠☠ backed out by d1b45fb8d204 ☠ ☠
authorAndreas Farre <farre@mozilla.com>
Mon, 27 Nov 2017 06:45:00 -0500
changeset 449164 4418485f0512638f30cc43c62c16dd97ba1f2c69
parent 449163 87fdf9ff384320cb621944bbfcb3aa4b01362e25
child 449165 d0f561d1bf62a9a286273961debdeedda9526d42
push id1648
push usermtabara@mozilla.com
push dateThu, 01 Mar 2018 12:45:47 +0000
treeherdermozilla-release@cbb9688c2eeb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssmaug
bugs1410096
milestone59.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1410096 - Move labeled queues to SchedulerGroup. r=smaug This improves the performance of GetEvent and PutEvent in LabeledEventQueue by removing a hash table mapping groups to queues.
xpcom/threads/AbstractEventQueue.h
xpcom/threads/EventQueue.cpp
xpcom/threads/EventQueue.h
xpcom/threads/LabeledEventQueue.cpp
xpcom/threads/LabeledEventQueue.h
xpcom/threads/MainThreadQueue.h
xpcom/threads/PrioritizedEventQueue.cpp
xpcom/threads/SchedulerGroup.h
--- a/xpcom/threads/AbstractEventQueue.h
+++ b/xpcom/threads/AbstractEventQueue.h
@@ -14,17 +14,19 @@ class nsIRunnable;
 
 namespace mozilla {
 
 enum class EventPriority
 {
   High,
   Input,
   Normal,
-  Idle
+  Idle,
+
+  Count
 };
 
 // AbstractEventQueue is an abstract base class for all our unsynchronized event
 // queue implementations:
 // - EventQueue: A queue of runnables. Used for non-main threads.
 // - PrioritizedEventQueue: Contains a queue for each priority level.
 //       Has heuristics to decide which queue to pop from. Events are
 //       pushed into the queue corresponding to their priority.
--- a/xpcom/threads/EventQueue.cpp
+++ b/xpcom/threads/EventQueue.cpp
@@ -4,17 +4,17 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mozilla/EventQueue.h"
 #include "nsIRunnable.h"
 
 using namespace mozilla;
 
-EventQueue::EventQueue()
+EventQueue::EventQueue(EventPriority aPriority)
 {
 }
 
 void
 EventQueue::PutEvent(already_AddRefed<nsIRunnable>&& aEvent,
                      EventPriority aPriority,
                      const MutexAutoLock& aProofOfLock)
 {
--- a/xpcom/threads/EventQueue.h
+++ b/xpcom/threads/EventQueue.h
@@ -13,17 +13,18 @@
 
 class nsIRunnable;
 
 namespace mozilla {
 
 class EventQueue final : public AbstractEventQueue
 {
 public:
-  EventQueue();
+  EventQueue() {}
+  explicit EventQueue(EventPriority aPriority);
 
   void PutEvent(already_AddRefed<nsIRunnable>&& aEvent,
                 EventPriority aPriority,
                 const MutexAutoLock& aProofOfLock) final;
   already_AddRefed<nsIRunnable> GetEvent(EventPriority* aPriority,
                                          const MutexAutoLock& aProofOfLock) final;
 
   bool IsEmpty(const MutexAutoLock& aProofOfLock) final;
--- a/xpcom/threads/LabeledEventQueue.cpp
+++ b/xpcom/threads/LabeledEventQueue.cpp
@@ -8,21 +8,24 @@
 #include "mozilla/dom/TabChild.h"
 #include "mozilla/dom/TabGroup.h"
 #include "mozilla/Scheduler.h"
 #include "mozilla/SchedulerGroup.h"
 #include "nsQueryObject.h"
 
 using namespace mozilla::dom;
 
+using EpochQueueEntry = SchedulerGroup::EpochQueueEntry;
+
 LinkedList<SchedulerGroup>* LabeledEventQueue::sSchedulerGroups;
 size_t LabeledEventQueue::sLabeledEventQueueCount;
 SchedulerGroup* LabeledEventQueue::sCurrentSchedulerGroup;
 
-LabeledEventQueue::LabeledEventQueue()
+LabeledEventQueue::LabeledEventQueue(EventPriority aPriority)
+  : mPriority(aPriority)
 {
   // LabeledEventQueue should only be used by one consumer since it uses a
   // single static sSchedulerGroups field. It's hard to assert this, though, so
   // we assert NS_IsMainThread(), which is a reasonable proxy.
   MOZ_ASSERT(NS_IsMainThread());
 
   if (sLabeledEventQueueCount++ == 0) {
     sSchedulerGroups = new LinkedList<SchedulerGroup>();
@@ -72,16 +75,18 @@ IsReadyToRun(nsIRunnable* aEvent, Schedu
   return labelable->IsReadyToRun();
 }
 
 void
 LabeledEventQueue::PutEvent(already_AddRefed<nsIRunnable>&& aEvent,
                             EventPriority aPriority,
                             const MutexAutoLock& aProofOfLock)
 {
+  MOZ_ASSERT(aPriority == mPriority);
+
   nsCOMPtr<nsIRunnable> event(aEvent);
 
   MOZ_ASSERT(event.get());
 
   SchedulerGroup* group = GetSchedulerGroup(event);
   bool isLabeled = !!group;
 
   // Create a new epoch if necessary.
@@ -95,18 +100,18 @@ LabeledEventQueue::PutEvent(already_AddR
     } else {
       epoch = &lastEpoch;
     }
   }
 
   mNumEvents++;
   epoch->mNumEvents++;
 
-  RunnableEpochQueue* queue = isLabeled ? mLabeled.LookupOrAdd(group) : &mUnlabeled;
-  queue->Push(QueueEntry(event.forget(), epoch->mEpochNumber));
+  RunnableEpochQueue& queue = isLabeled ? group->GetQueue(aPriority) : mUnlabeled;
+  queue.Push(EpochQueueEntry(event.forget(), epoch->mEpochNumber));
 
   if (group && group->EnqueueEvent() == SchedulerGroup::NewlyQueued) {
     // This group didn't have any events before. Add it to the
     // sSchedulerGroups list.
     MOZ_ASSERT(!group->isInList());
     sSchedulerGroups->insertBack(group);
     if (!sCurrentSchedulerGroup) {
       sCurrentSchedulerGroup = group;
@@ -145,23 +150,23 @@ LabeledEventQueue::GetEvent(EventPriorit
                             const MutexAutoLock& aProofOfLock)
 {
   if (mEpochs.IsEmpty()) {
     return nullptr;
   }
 
   Epoch epoch = mEpochs.FirstElement();
   if (!epoch.IsLabeled()) {
-    QueueEntry& first = mUnlabeled.FirstElement();
+    EpochQueueEntry& first = mUnlabeled.FirstElement();
     if (!IsReadyToRun(first.mRunnable, nullptr)) {
       return nullptr;
     }
 
     PopEpoch();
-    QueueEntry entry = mUnlabeled.Pop();
+    EpochQueueEntry entry = mUnlabeled.Pop();
     MOZ_ASSERT(entry.mEpochNumber == epoch.mEpochNumber);
     MOZ_ASSERT(entry.mRunnable.get());
     return entry.mRunnable.forget();
   }
 
   if (!sCurrentSchedulerGroup) {
     return nullptr;
   }
@@ -192,27 +197,25 @@ LabeledEventQueue::GetEvent(EventPriorit
   }
 
   // Iterate over each SchedulerGroup once, starting at sCurrentSchedulerGroup.
   SchedulerGroup* firstGroup = sCurrentSchedulerGroup;
   SchedulerGroup* group = firstGroup;
   do {
     mAvoidActiveTabCount--;
 
-    auto queueEntry = mLabeled.Lookup(group);
-    if (!queueEntry) {
+    RunnableEpochQueue& queue = group->GetQueue(mPriority);
+
+    if (queue.IsEmpty()) {
       // This can happen if |group| is in a different LabeledEventQueue than |this|.
       group = NextSchedulerGroup(group);
       continue;
     }
 
-    RunnableEpochQueue* queue = queueEntry.Data();
-    MOZ_ASSERT(!queue->IsEmpty());
-
-    QueueEntry& first = queue->FirstElement();
+    EpochQueueEntry& first = queue.FirstElement();
     if (first.mEpochNumber == epoch.mEpochNumber &&
         IsReadyToRun(first.mRunnable, group)) {
       sCurrentSchedulerGroup = NextSchedulerGroup(group);
 
       PopEpoch();
 
       if (group->DequeueEvent() == SchedulerGroup::NoLongerQueued) {
         // Now we can take group out of sSchedulerGroups.
@@ -221,20 +224,17 @@ LabeledEventQueue::GetEvent(EventPriorit
           // if |group| was the only element in sSchedulerGroups. In that case
           // set sCurrentSchedulerGroup to null.
           MOZ_ASSERT(group->getNext() == nullptr);
           MOZ_ASSERT(group->getPrevious() == nullptr);
           sCurrentSchedulerGroup = nullptr;
         }
         group->removeFrom(*sSchedulerGroups);
       }
-      QueueEntry entry = queue->Pop();
-      if (queue->IsEmpty()) {
-        queueEntry.Remove();
-      }
+      EpochQueueEntry entry = queue.Pop();
       return entry.mRunnable.forget();
     }
 
     group = NextSchedulerGroup(group);
   } while (group != firstGroup);
 
   return nullptr;
 }
@@ -256,32 +256,34 @@ LabeledEventQueue::HasReadyEvent(const M
 {
   if (mEpochs.IsEmpty()) {
     return false;
   }
 
   Epoch& frontEpoch = mEpochs.FirstElement();
 
   if (!frontEpoch.IsLabeled()) {
-    QueueEntry& entry = mUnlabeled.FirstElement();
+    EpochQueueEntry& entry = mUnlabeled.FirstElement();
     return IsReadyToRun(entry.mRunnable, nullptr);
   }
 
-  // Go through the labeled queues and look for one whose head is from the
-  // current epoch and is allowed to run.
+  // Go through the scheduler groups and look for one that has events
+  // for the priority of this labeled queue that is in the current
+  // epoch and is allowed to run.
   uintptr_t currentEpoch = frontEpoch.mEpochNumber;
-  for (auto iter = mLabeled.Iter(); !iter.Done(); iter.Next()) {
-    SchedulerGroup* key = iter.Key();
-    RunnableEpochQueue* queue = iter.Data();
-    MOZ_ASSERT(!queue->IsEmpty());
+  for (SchedulerGroup* group : *sSchedulerGroups) {
+    RunnableEpochQueue& queue = group->GetQueue(mPriority);
+    if (queue.IsEmpty()) {
+      continue;
+    }
 
-    QueueEntry& entry = queue->FirstElement();
+    EpochQueueEntry& entry = queue.FirstElement();
     if (entry.mEpochNumber != currentEpoch) {
       continue;
     }
 
-    if (IsReadyToRun(entry.mRunnable, key)) {
+    if (IsReadyToRun(entry.mRunnable, group)) {
       return true;
     }
   }
 
   return false;
 }
--- a/xpcom/threads/LabeledEventQueue.h
+++ b/xpcom/threads/LabeledEventQueue.h
@@ -5,16 +5,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef mozilla_LabeledEventQueue_h
 #define mozilla_LabeledEventQueue_h
 
 #include <stdint.h>
 #include "mozilla/AbstractEventQueue.h"
 #include "mozilla/LinkedList.h"
+#include "mozilla/SchedulerGroup.h"
 #include "mozilla/Queue.h"
 #include "nsClassHashtable.h"
 #include "nsHashKeys.h"
 
 namespace mozilla {
 
 class SchedulerGroup;
 
@@ -25,17 +26,17 @@ class SchedulerGroup;
 // event is fetched, we heuristically pick a SchedulerGroup and return an event
 // from its queue. Ideally the heuristic should give precedence to
 // SchedulerGroups corresponding to the foreground tabs. The correctness of this
 // data structure relies on the invariant that events from different
 // SchedulerGroups cannot affect each other.
 class LabeledEventQueue final : public AbstractEventQueue
 {
 public:
-  LabeledEventQueue();
+  explicit LabeledEventQueue(EventPriority aPriority);
   ~LabeledEventQueue();
 
   void PutEvent(already_AddRefed<nsIRunnable>&& aEvent,
                 EventPriority aPriority,
                 const MutexAutoLock& aProofOfLock) final;
   already_AddRefed<nsIRunnable> GetEvent(EventPriority* aPriority,
                                          const MutexAutoLock& aProofOfLock) final;
 
@@ -78,27 +79,16 @@ private:
   // runnable and the epoch number into the appopriate queue.
   //
   // To pop an event, we look at the epoch at the front of the epoch queue. If
   // it is unlabeled, then we pop the first event in the unlabeled queue. If it
   // is labeled, we can pop from any of the SchedulerGroup queues. Then we
   // decrement the number of events in the current epoch. If this number reaches
   // zero, we pop from the epoch queue.
 
-  struct QueueEntry
-  {
-    nsCOMPtr<nsIRunnable> mRunnable;
-    uintptr_t mEpochNumber;
-
-    QueueEntry(already_AddRefed<nsIRunnable> aRunnable, uintptr_t aEpoch)
-      : mRunnable(aRunnable)
-      , mEpochNumber(aEpoch)
-    {}
-  };
-
   struct Epoch
   {
     static Epoch First(bool aIsLabeled)
     {
       // Odd numbers are labeled, even are unlabeled.
       uintptr_t number = aIsLabeled ? 1 : 0;
       return Epoch(number, aIsLabeled);
     }
@@ -126,36 +116,35 @@ private:
       MOZ_ASSERT(aIsLabeled == !IsLabeled());
       return Epoch(mEpochNumber + 1, aIsLabeled);
     }
   };
 
   void PopEpoch();
   static SchedulerGroup* NextSchedulerGroup(SchedulerGroup* aGroup);
 
-  using RunnableEpochQueue = Queue<QueueEntry, 32>;
-  using LabeledMap = nsClassHashtable<nsRefPtrHashKey<SchedulerGroup>, RunnableEpochQueue>;
+  using RunnableEpochQueue = SchedulerGroup::RunnableEpochQueue;
   using EpochQueue = Queue<Epoch, 8>;
 
   // List of SchedulerGroups that might have events. This is static, so it
   // covers all LabeledEventQueues. If a SchedulerGroup is in this list, it may
   // not have an event in *this* LabeledEventQueue (although it will have an
   // event in *some* LabeledEventQueue). sCurrentSchedulerGroup cycles through
   // the elements of sSchedulerGroups in order.
   static LinkedList<SchedulerGroup>* sSchedulerGroups;
   static size_t sLabeledEventQueueCount;
   static SchedulerGroup* sCurrentSchedulerGroup;
 
-  LabeledMap mLabeled;
   RunnableEpochQueue mUnlabeled;
   EpochQueue mEpochs;
   size_t mNumEvents = 0;
 
   // Number of SchedulerGroups that must be processed before we prioritize an
   // active tab. This field is designed to guarantee a 1:1 interleaving between
   // foreground and background SchedulerGroups. For details, see its usage in
   // LabeledEventQueue.cpp.
   int64_t mAvoidActiveTabCount = 0;
+  EventPriority mPriority;
 };
 
 } // namespace mozilla
 
 #endif // mozilla_LabeledEventQueue_h
--- a/xpcom/threads/MainThreadQueue.h
+++ b/xpcom/threads/MainThreadQueue.h
@@ -18,20 +18,20 @@ namespace mozilla {
 
 template<typename SynchronizedQueueT, typename InnerQueueT>
 inline already_AddRefed<nsThread>
 CreateMainThread(nsIIdlePeriod* aIdlePeriod, SynchronizedQueueT** aSynchronizedQueue = nullptr)
 {
   using MainThreadQueueT = PrioritizedEventQueue<InnerQueueT>;
 
   auto queue = MakeUnique<MainThreadQueueT>(
-    MakeUnique<InnerQueueT>(),
-    MakeUnique<InnerQueueT>(),
-    MakeUnique<InnerQueueT>(),
-    MakeUnique<InnerQueueT>(),
+    MakeUnique<InnerQueueT>(EventPriority::High),
+    MakeUnique<InnerQueueT>(EventPriority::Input),
+    MakeUnique<InnerQueueT>(EventPriority::Normal),
+    MakeUnique<InnerQueueT>(EventPriority::Idle),
     do_AddRef(aIdlePeriod));
 
   MainThreadQueueT* prioritized = queue.get();
 
   RefPtr<SynchronizedQueueT> synchronizedQueue = new SynchronizedQueueT(Move(queue));
 
   prioritized->SetMutexRef(synchronizedQueue->MutexRef());
 
--- a/xpcom/threads/PrioritizedEventQueue.cpp
+++ b/xpcom/threads/PrioritizedEventQueue.cpp
@@ -60,16 +60,19 @@ PrioritizedEventQueue<InnerQueueT>::PutE
     mInputQueue->PutEvent(event.forget(), priority, aProofOfLock);
     break;
   case EventPriority::Normal:
     mNormalQueue->PutEvent(event.forget(), priority, aProofOfLock);
     break;
   case EventPriority::Idle:
     mIdleQueue->PutEvent(event.forget(), priority, aProofOfLock);
     break;
+  case EventPriority::Count:
+    MOZ_CRASH("EventPriority::Count isn't a valid priority");
+    break;
   }
 }
 
 template<class InnerQueueT>
 TimeStamp
 PrioritizedEventQueue<InnerQueueT>::GetIdleDeadline()
 {
   // If we are shutting down, we won't honor the idle period, and we will
--- a/xpcom/threads/SchedulerGroup.h
+++ b/xpcom/threads/SchedulerGroup.h
@@ -4,16 +4,17 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef mozilla_SchedulerGroup_h
 #define mozilla_SchedulerGroup_h
 
 #include "mozilla/AlreadyAddRefed.h"
 #include "mozilla/LinkedList.h"
+#include "mozilla/Queue.h"
 #include "mozilla/TaskCategory.h"
 #include "mozilla/ThreadLocal.h"
 #include "mozilla/TimeStamp.h"
 #include "nsCOMPtr.h"
 #include "nsILabelableRunnable.h"
 #include "nsISupportsImpl.h"
 #include "nsThreadUtils.h"
 
@@ -163,16 +164,35 @@ public:
   bool IsRunning() const { return mIsRunning; }
 
   enum ValidationType {
     StartValidation,
     EndValidation,
   };
   static void SetValidatingAccess(ValidationType aType);
 
+  struct EpochQueueEntry
+  {
+    nsCOMPtr<nsIRunnable> mRunnable;
+    uintptr_t mEpochNumber;
+
+    EpochQueueEntry(already_AddRefed<nsIRunnable> aRunnable, uintptr_t aEpoch)
+      : mRunnable(aRunnable)
+      , mEpochNumber(aEpoch)
+    {
+    }
+  };
+
+  using RunnableEpochQueue = Queue<EpochQueueEntry, 32>;
+
+  RunnableEpochQueue& GetQueue(EventPriority aPriority)
+  {
+    return mEventQueues[size_t(aPriority)];
+  }
+
 protected:
   static nsresult InternalUnlabeledDispatch(TaskCategory aCategory,
                                             already_AddRefed<Runnable>&& aRunnable);
 
   // Implementations are guaranteed that this method is called on the main
   // thread.
   virtual AbstractThread* AbstractMainThreadForImpl(TaskCategory aCategory);
 
@@ -198,15 +218,16 @@ protected:
   bool mIsRunning;
 
   // Number of events that are currently enqueued for this SchedulerGroup
   // (across all queues).
   size_t mEventCount = 0;
 
   nsCOMPtr<nsISerialEventTarget> mEventTargets[size_t(TaskCategory::Count)];
   RefPtr<AbstractThread> mAbstractThreads[size_t(TaskCategory::Count)];
+  RunnableEpochQueue mEventQueues[size_t(EventPriority::Count)];
 };
 
 NS_DEFINE_STATIC_IID_ACCESSOR(SchedulerGroup::Runnable, NS_SCHEDULERGROUPRUNNABLE_IID);
 
 } // namespace mozilla
 
 #endif // mozilla_SchedulerGroup_h