Optimize QUIC's EntropyTracker in QuicReceivedPacketManager by using a

net/quic/quic_received_packet_manager.h

 // Copyright 2013 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.
 //
 // Manages the packet entropy calculation for both sent and received packets
 // for a connection.
 
 #ifndef NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
 #define NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
 
+#include <deque>
+
 #include "net/quic/congestion_control/receive_algorithm_interface.h"
 #include "net/quic/quic_framer.h"
 #include "net/quic/quic_protocol.h"
 
 namespace net {
 
 namespace test {
 class EntropyTrackerPeer;
 class QuicConnectionPeer;
 class QuicReceivedPacketManagerPeer;
@@ skipping 31 matching lines @@
 
     // Sets the entropy hash up to but not including a sequence number based
     // on the hash provided by a StopWaiting frame.  Clears older packet
     // entropy entries and performs garbage collection up to the first gap.
     void SetCumulativeEntropyUpTo(QuicPacketSequenceNumber sequence_number,
                                   QuicPacketEntropyHash entropy_hash);
 
    private:
     friend class test::EntropyTrackerPeer;
 
-    typedef std::map<QuicPacketSequenceNumber,
-                     QuicPacketEntropyHash> ReceivedEntropyMap;
+    // A deque indexed by sequence number storing the packet's hash and whether
+    // a hash was recorded for that sequence number.
+    typedef std::deque<std::pair<QuicPacketEntropyHash, bool>>
+        ReceivedEntropyHashes;
 
     // Recomputes first_gap_ and removes packets_entropy_ entries that are no
     // longer needed to compute EntropyHash.
     void AdvanceFirstGapAndGarbageCollectEntropyMap();
 
-    // TODO(satyamshekhar): Can be optimized using an interval set like data
-    // structure.
     // Map of received sequence numbers to their corresponding entropy.
     // Stores an entry for every received packet whose sequence_number is larger
     // than first_gap_.  Packets without the entropy bit set have an entropy
     // value of 0.
-    // TODO(ianswett): When the entropy flag is off, the entropy
-    // should not be 0.
-    ReceivedEntropyMap packets_entropy_;
+    ReceivedEntropyHashes packets_entropy_;
 
     // Cumulative hash of entropy of all received packets.
     QuicPacketEntropyHash packets_entropy_hash_;
 
     // Sequence number of the first packet that we do not know the entropy of.
     // If there are no gaps in the received packet sequence,
     // packets_entropy_ will be empty and first_gap_ will be equal to
     // 'largest_observed_ + 1' since that's the first packet for which
     // entropy is unknown.  If there are gaps, packets_entropy_ will
     // contain entries for all received packets with sequence_number >
@@ skipping 40 matching lines @@
   // QuicReceivedEntropyHashCalculatorInterface
   // Called by QuicFramer, when the outgoing ack gets truncated, to recalculate
   // the received entropy hash for the truncated ack frame.
   virtual QuicPacketEntropyHash EntropyHash(
       QuicPacketSequenceNumber sequence_number) const OVERRIDE;
 
   // Updates internal state based on |stop_waiting|.
   void UpdatePacketInformationSentByPeer(
       const QuicStopWaitingFrame& stop_waiting);
 
-  // Returns whether the peer is missing packets.
-  bool HasMissingPackets();
-
   // Returns true when there are new missing packets to be reported within 3
   // packets of the largest observed.
   bool HasNewMissingPackets();
 
   QuicPacketSequenceNumber peer_least_packet_awaiting_ack() {
     return peer_least_packet_awaiting_ack_;
   }
 
  private:
   friend class test::QuicConnectionPeer;
@@ skipping 23 matching lines @@
   scoped_ptr<ReceiveAlgorithmInterface> receive_algorithm_;
 
   QuicConnectionStats* stats_;
 
   DISALLOW_COPY_AND_ASSIGN(QuicReceivedPacketManager);
 };
 
 }  // namespace net
 
 #endif  // NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_