Optimize QUIC's EntropyTracker in QuicReceivedPacketManager by using a

net/quic/quic_received_packet_manager.cc

Index: net/quic/quic_received_packet_manager.cc
diff --git a/net/quic/quic_received_packet_manager.cc b/net/quic/quic_received_packet_manager.cc
index 2a9665a1012ba183abd99a33a946413f429277e8..15030a4e5d9ab79b544ffb3d1f8f69b69bdc82f0 100644
--- a/net/quic/quic_received_packet_manager.cc
+++ b/net/quic/quic_received_packet_manager.cc
@@ -42,22 +42,12 @@ QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
   }
 
   DCHECK_GE(sequence_number, first_gap_);
-  ReceivedEntropyMap::const_iterator it =
-      packets_entropy_.upper_bound(sequence_number);
-  // When this map is empty we should only query entropy for
-  // largest_observed_, since no other entropy can be correctly
-  // calculated, because we're not storing the entropy for any prior packets.
-  // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
-  // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10)
-  LOG_IF(DFATAL, it == packets_entropy_.end())
-      << "EntropyHash may be unknown. largest_received: "
-      << largest_observed_
-      << " sequence_number: " << sequence_number;
-
-  // TODO(satyamshekhar): Make this O(1).
+  DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_);
   QuicPacketEntropyHash hash = packets_entropy_hash_;
-  for (; it != packets_entropy_.end(); ++it) {
-    hash ^= it->second;
+  ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin();
+  for (QuicPacketSequenceNumber i = 0;
+           i < (largest_observed_ - sequence_number); ++i, ++it) {
+    hash ^= it->first;
   }
   return hash;
 }
@@ -71,19 +61,35 @@ void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
              << first_gap_;
     return;
   }
+  // RecordPacketEntropyHash is only intended to be called once per packet.
+  DCHECK(sequence_number > largest_observed_ ||
+         !packets_entropy_[sequence_number - first_gap_].second);
 
+  packets_entropy_hash_ ^= entropy_hash;
+
+  // Optimize the typical case of no gaps.
+  if (sequence_number == largest_observed_ + 1 && packets_entropy_.empty()) {
+    ++first_gap_;
+    largest_observed_ = sequence_number;
+    return;
+  }
   if (sequence_number > largest_observed_) {
+    for (QuicPacketSequenceNumber i = 0;
+         i < (sequence_number - largest_observed_ - 1); ++i) {
+      packets_entropy_.push_back(make_pair(0, false));
+    }
+    packets_entropy_.push_back(make_pair(entropy_hash, true));
     largest_observed_ = sequence_number;
+  } else {
+    packets_entropy_[sequence_number - first_gap_] =
+        make_pair(entropy_hash, true);
+    AdvanceFirstGapAndGarbageCollectEntropyMap();
   }
 
-  packets_entropy_hash_ ^= entropy_hash;
   DVLOG(2) << "setting cumulative received entropy hash to: "
            << static_cast<int>(packets_entropy_hash_)
            << " updated with sequence number " << sequence_number
            << " entropy hash: " << static_cast<int>(entropy_hash);
-
-  packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
-  AdvanceFirstGapAndGarbageCollectEntropyMap();
 }
 
 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
@@ -95,19 +101,19 @@ void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
              << " less than first_gap_:" << first_gap_;
     return;
   }
-  // Compute the current entropy based on the hash.
+  while (first_gap_ < sequence_number) {
+    ++first_gap_;
+    if (!packets_entropy_.empty()) {
+      packets_entropy_.pop_front();
+    }
+  }
+  // Compute the current entropy by XORing in all entropies received including
+  // and since sequence_number.
   packets_entropy_hash_ = entropy_hash;
-  ReceivedEntropyMap::iterator it =
-      packets_entropy_.lower_bound(sequence_number);
-  // TODO(satyamshekhar): Make this O(1).
-  for (; it != packets_entropy_.end(); ++it) {
-    packets_entropy_hash_ ^= it->second;
+  for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin();
+           it != packets_entropy_.end(); ++it) {
+    packets_entropy_hash_ ^= it->first;
   }
-  // Update first_gap_ and discard old entropies.
-  first_gap_ = sequence_number;
-  packets_entropy_.erase(
-      packets_entropy_.begin(),
-      packets_entropy_.lower_bound(sequence_number));
 
   // Garbage collect entries from the beginning of the map.
   AdvanceFirstGapAndGarbageCollectEntropyMap();
@@ -115,14 +121,9 @@ void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
 
 void QuicReceivedPacketManager::EntropyTracker::
 AdvanceFirstGapAndGarbageCollectEntropyMap() {
-  while (!packets_entropy_.empty()) {
-    ReceivedEntropyMap::iterator it = packets_entropy_.begin();
-    if (it->first != first_gap_) {
-      DCHECK_GT(it->first, first_gap_);
-      break;
-    }
-    packets_entropy_.erase(it);
+  while (!packets_entropy_.empty() && packets_entropy_.front().second) {
     ++first_gap_;
+    packets_entropy_.pop_front();
   }
 }
 
@@ -259,12 +260,8 @@ void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
              peer_least_packet_awaiting_ack_);
 }
 
-bool QuicReceivedPacketManager::HasMissingPackets() {
-  return !ack_frame_.missing_packets.empty();
-}
-
 bool QuicReceivedPacketManager::HasNewMissingPackets() {
-  return HasMissingPackets() &&
+  return !ack_frame_.missing_packets.empty() &&
       (ack_frame_.largest_observed -
        *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
 }