Optimize QuicUnackedPacketMap by changing from a LinkedHashMap to a

net/quic/quic_sent_packet_manager.cc

Index: net/quic/quic_sent_packet_manager.cc
diff --git a/net/quic/quic_sent_packet_manager.cc b/net/quic/quic_sent_packet_manager.cc
index d2f825b0faf252263cc66a048d3233b969fa2afb..c18b456b26ec63558d7ae6550ccc9ed274d0729b 100644
--- a/net/quic/quic_sent_packet_manager.cc
+++ b/net/quic/quic_sent_packet_manager.cc
@@ -197,6 +197,7 @@ void QuicSentPacketManager::OnIncomingAck(const QuicAckFrame& ack_frame,
   HandleAckForSentPackets(ack_frame);
   InvokeLossDetection(ack_receive_time);
   MaybeInvokeCongestionEvent(largest_observed_acked, bytes_in_flight);
+  unacked_packets_.RemoveObsoletePackets();
 
   sustained_bandwidth_recorder_.RecordEstimate(
       send_algorithm_->InRecovery(),
@@ -260,15 +261,15 @@ void QuicSentPacketManager::HandleAckForSentPackets(
   // incoming_ack shows they've been seen by the peer.
   QuicTime::Delta delta_largest_observed =
       ack_frame.delta_time_largest_observed;
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    QuicPacketSequenceNumber sequence_number = it->first;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
     if (sequence_number > ack_frame.largest_observed) {
       // These packets are still in flight.
       break;
     }
 
-    if (IsAwaitingPacket(ack_frame, sequence_number)) {
+    if (ContainsKey(ack_frame.missing_packets, sequence_number)) {
       // Consider it multiple nacks when there is a gap between the missing
       // packet and the largest observed, since the purpose of a nack
       // threshold is to tolerate re-ordering.  This handles both StretchAcks
@@ -280,17 +281,16 @@ void QuicSentPacketManager::HandleAckForSentPackets(
         min_nacks = 1;
       }
       unacked_packets_.NackPacket(sequence_number, min_nacks);
-      ++it;
       continue;
     }
     // Packet was acked, so remove it from our unacked packet list.
     DVLOG(1) << ENDPOINT << "Got an ack for packet " << sequence_number;
     // If data is associated with the most recent transmission of this
     // packet, then inform the caller.
-    if (it->second.in_flight) {
-      packets_acked_[sequence_number] = it->second;
+    if (it->in_flight) {
+      packets_acked_[sequence_number] = *it;
     }
-    it = MarkPacketHandled(it, delta_largest_observed);
+    MarkPacketHandled(sequence_number, *it, delta_largest_observed);
   }
 
   // Discard any retransmittable frames associated with revived packets.
@@ -308,26 +308,25 @@ bool QuicSentPacketManager::HasRetransmittableFrames(
 
 void QuicSentPacketManager::RetransmitUnackedPackets(
     RetransmissionType retransmission_type) {
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
+    const RetransmittableFrames* frames = it->retransmittable_frames;
     // TODO(ianswett): Consider adding a new retransmission type which removes
     // all these old packets from unacked and retransmits them as new sequence
     // numbers with no connection to the previous ones.
     if (frames != NULL && (retransmission_type == ALL_PACKETS ||
                            frames->encryption_level() == ENCRYPTION_INITIAL)) {
-      MarkForRetransmission(it->first, ALL_UNACKED_RETRANSMISSION);
+      MarkForRetransmission(sequence_number, ALL_UNACKED_RETRANSMISSION);
     }
-    ++it;
   }
 }
 
 void QuicSentPacketManager::NeuterUnencryptedPackets() {
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
-    QuicPacketSequenceNumber sequence_number = it->first;
-    ++it;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
+    const RetransmittableFrames* frames = it->retransmittable_frames;
     if (frames != NULL && frames->encryption_level() == ENCRYPTION_NONE) {
       // Once you're forward secure, no unencrypted packets will be sent, crypto
       // or otherwise. Unencrypted packets are neutered and abandoned, to ensure
@@ -335,8 +334,6 @@ void QuicSentPacketManager::NeuterUnencryptedPackets() {
       // perspective.
       pending_retransmissions_.erase(sequence_number);
       unacked_packets_.RemoveFromInFlight(sequence_number);
-      // RemoveRetransmittibility is safe because only the newest sequence
-      // number can have frames.
       unacked_packets_.RemoveRetransmittability(sequence_number);
     }
   }
@@ -380,10 +377,10 @@ void QuicSentPacketManager::RecordSpuriousRetransmissions(
     ++stats_->spurious_rto_count;
   }
   for (SequenceNumberSet::const_iterator
-           it = all_transmissions.upper_bound(acked_sequence_number),
-           end = all_transmissions.end();
-       it != end;
-       ++it) {
+            it = all_transmissions.upper_bound(acked_sequence_number),
+            end = all_transmissions.end();
+        it != end;
+        ++it) {
     const TransmissionInfo& retransmit_info =
         unacked_packets_.GetTransmissionInfo(*it);
 
@@ -456,16 +453,12 @@ void QuicSentPacketManager::MarkPacketRevived(
   unacked_packets_.RemoveRetransmittability(sequence_number);
 }
 
-QuicUnackedPacketMap::const_iterator QuicSentPacketManager::MarkPacketHandled(
-    QuicUnackedPacketMap::const_iterator it,
+void QuicSentPacketManager::MarkPacketHandled(
+    QuicPacketSequenceNumber sequence_number,
+    const TransmissionInfo& info,
     QuicTime::Delta delta_largest_observed) {
-  LOG_IF(DFATAL, it == unacked_packets_.end())
-      << "MarkPacketHandled must be passed a valid iterator entry.";
-  const QuicPacketSequenceNumber sequence_number = it->first;
-  const TransmissionInfo& transmission_info = it->second;
-
   QuicPacketSequenceNumber newest_transmission =
-      *transmission_info.all_transmissions->rbegin();
+      *info.all_transmissions->rbegin();
   // Remove the most recent packet, if it is pending retransmission.
   pending_retransmissions_.erase(newest_transmission);
 
@@ -476,8 +469,7 @@ QuicUnackedPacketMap::const_iterator QuicSentPacketManager::MarkPacketHandled(
     ack_notifier_manager_.OnPacketAcked(newest_transmission,
                                         delta_largest_observed);
     if (newest_transmission != sequence_number) {
-      RecordSpuriousRetransmissions(*transmission_info.all_transmissions,
-                                    sequence_number);
+      RecordSpuriousRetransmissions(*info.all_transmissions, sequence_number);
     }
   }
 
@@ -496,13 +488,6 @@ QuicUnackedPacketMap::const_iterator QuicSentPacketManager::MarkPacketHandled(
   }
   unacked_packets_.RemoveFromInFlight(sequence_number);
   unacked_packets_.RemoveRetransmittability(sequence_number);
-
-  QuicUnackedPacketMap::const_iterator next_unacked = unacked_packets_.begin();
-  while (next_unacked != unacked_packets_.end() &&
-         next_unacked->first <= sequence_number) {
-    ++next_unacked;
-  }
-  return next_unacked;
 }
 
 bool QuicSentPacketManager::IsUnacked(
@@ -516,7 +501,7 @@ bool QuicSentPacketManager::HasUnackedPackets() const {
 
 QuicPacketSequenceNumber
 QuicSentPacketManager::GetLeastUnackedSentPacket() const {
-  return unacked_packets_.GetLeastUnackedSentPacket();
+  return unacked_packets_.GetLeastUnacked();
 }
 
 bool QuicSentPacketManager::OnPacketSent(
@@ -601,13 +586,12 @@ void QuicSentPacketManager::RetransmitCryptoPackets() {
       min(kMaxHandshakeRetransmissionBackoffs,
           consecutive_crypto_retransmission_count_ + 1);
   bool packet_retransmitted = false;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-       it != unacked_packets_.end(); ++it) {
-    QuicPacketSequenceNumber sequence_number = it->first;
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
     // Only retransmit frames which are in flight, and therefore have been sent.
-    if (!it->second.in_flight || frames == NULL ||
-        frames->HasCryptoHandshake() != IS_HANDSHAKE) {
+    if (!it->in_flight || it->retransmittable_frames == NULL ||
+        it->retransmittable_frames->HasCryptoHandshake() != IS_HANDSHAKE) {
       continue;
     }
     packet_retransmitted = true;
@@ -621,16 +605,15 @@ bool QuicSentPacketManager::MaybeRetransmitTailLossProbe() {
   if (pending_timer_transmission_count_ == 0) {
     return false;
   }
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-       it != unacked_packets_.end(); ++it) {
-    QuicPacketSequenceNumber sequence_number = it->first;
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
     // Only retransmit frames which are in flight, and therefore have been sent.
-    if (!it->second.in_flight || frames == NULL) {
+    if (!it->in_flight || it->retransmittable_frames == NULL) {
       continue;
     }
     if (!handshake_confirmed_) {
-      DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake());
+      DCHECK_NE(IS_HANDSHAKE, it->retransmittable_frames->HasCryptoHandshake());
     }
     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
     return true;
@@ -642,18 +625,17 @@ bool QuicSentPacketManager::MaybeRetransmitTailLossProbe() {
 
 void QuicSentPacketManager::RetransmitAllPackets() {
   DVLOG(1) << "RetransmitAllPackets() called with "
-           << unacked_packets_.GetNumUnackedPackets() << " unacked packets.";
+           << unacked_packets_.GetNumUnackedPacketsDebugOnly()
+           << " unacked packets.";
   // Request retransmission of all retransmittable packets when the RTO
   // fires, and let the congestion manager decide how many to send
   // immediately and the remaining packets will be queued.
   // Abandon any non-retransmittable packets that are sufficiently old.
   bool packets_retransmitted = false;
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
-    QuicPacketSequenceNumber sequence_number = it->first;
-    ++it;
-    if (frames != NULL) {
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
+    if (it->retransmittable_frames != NULL) {
       packets_retransmitted = true;
       MarkForRetransmission(sequence_number, RTO_RETRANSMISSION);
     } else {