commit 011bd692d591fa2ff67b63d2ddaf8a398c44a358
author birenroy <birenroy@google.com> Tue Apr 05 14:07:57 2022 -0700
committer Copybara-Service <copybara-worker@google.com> Tue Apr 05 14:09:03 2022 -0700
tree 3992655d420684dfb50eb13296d64c63e095520e
parent 8964fa85df01b0107f6182b8b1271f3baaa15671

Replaces std::deque with quiche::QuicheCircularDeque in http2::PriorityWriteScheduler.

std::deque allocates a 4kB block, even if it's only storing a single element:
  http://google3/third_party/crosstool/v18/stable/installs/llvm/include/c++/v1/deque;l=294;rcl=438152875

QuicheCircularDeque should be a much more efficient data type for small container sizes.

PiperOrigin-RevId: 439672104

http2/core/priority_write_scheduler.h

diff --git a/http2/core/priority_write_scheduler.h b/http2/core/priority_write_scheduler.h
index 87de3a7..cf1c77a 100644
--- a/http2/core/priority_write_scheduler.h
+++ b/http2/core/priority_write_scheduler.h
@@ -8,7 +8,6 @@
 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
-#include <deque>
 #include <string>
 #include <tuple>
 #include <unordered_map>
@@ -20,6 +19,7 @@
 #include "common/platform/api/quiche_bug_tracker.h"
 #include "common/platform/api/quiche_export.h"
 #include "common/platform/api/quiche_logging.h"
+#include "common/quiche_circular_deque.h"
 #include "spdy/core/spdy_protocol.h"
 
 namespace http2 {
@@ -294,7 +294,7 @@
   };
 
   // O(1) size lookup, O(1) insert at front or back (amortized).
-  using ReadyList = std::deque<StreamInfo*>;
+  using ReadyList = quiche::QuicheCircularDeque<StreamInfo*>;
 
   // State kept for each priority level.
   struct QUICHE_EXPORT_PRIVATE PriorityInfo {
@@ -306,15 +306,15 @@
 
   typedef std::unordered_map<StreamIdType, StreamInfo> StreamInfoMap;
 
-  // Erases first occurrence (which should be the only one) of |info| in
-  // |ready_list|, returning true if found (and erased), or false otherwise.
-  // Decrements |num_ready_streams_| if an entry is erased.
+  // Erases `info` from `ready_list`, returning true if found (and erased), or
+  // false otherwise. Decrements `num_ready_streams_` if an entry is erased.
   bool Erase(ReadyList* ready_list, const StreamInfo& info) {
-    auto it = std::find(ready_list->begin(), ready_list->end(), &info);
+    auto it = std::remove(ready_list->begin(), ready_list->end(), &info);
     if (it == ready_list->end()) {
+      // `info` was not found.
       return false;
     }
-    ready_list->erase(it);
+    ready_list->pop_back();
     --num_ready_streams_;
     return true;
   }