Optimize QUIC's EntropyTracker in QuicReceivedPacketManager by using a

net/quic/quic_received_packet_manager_test.cc

 // 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.
 
 #include "net/quic/quic_received_packet_manager.h"
 
 #include <algorithm>
 #include <vector>
 
 #include "net/quic/quic_connection_stats.h"
@@ skipping 18 matching lines @@
       const QuicReceivedPacketManager::EntropyTracker& tracker) {
     return tracker.largest_observed_;
   }
   static int packets_entropy_size(
       const QuicReceivedPacketManager::EntropyTracker& tracker) {
     return tracker.packets_entropy_.size();
   }
   static bool IsTrackingPacket(
       const QuicReceivedPacketManager::EntropyTracker& tracker,
       QuicPacketSequenceNumber sequence_number) {
-    return tracker.packets_entropy_.find(sequence_number) !=
-        tracker.packets_entropy_.end();
+    return sequence_number >= tracker.first_gap_ &&
+        sequence_number <
+            (tracker.first_gap_ + tracker.packets_entropy_.size()) &&
+        tracker.packets_entropy_[sequence_number - tracker.first_gap_].second;
   }
 };
 
 namespace {
 
 // Entropy of individual packets is not tracked if there are no gaps.
 TEST(EntropyTrackerTest, NoGaps) {
   QuicReceivedPacketManager::EntropyTracker tracker;
 
   tracker.RecordPacketEntropyHash(1, 23);
@@ skipping 13 matching lines @@
 TEST(EntropyTrackerTest, FillGaps) {
   QuicReceivedPacketManager::EntropyTracker tracker;
 
   tracker.RecordPacketEntropyHash(2, 5);
   tracker.RecordPacketEntropyHash(5, 17);
   tracker.RecordPacketEntropyHash(6, 23);
   tracker.RecordPacketEntropyHash(9, 42);
 
   EXPECT_EQ(1u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
-  EXPECT_EQ(4, EntropyTrackerPeer::packets_entropy_size(tracker));
+  EXPECT_EQ(9, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   EXPECT_EQ(5, tracker.EntropyHash(2));
   EXPECT_EQ(5 ^ 17, tracker.EntropyHash(5));
   EXPECT_EQ(5 ^ 17 ^ 23, tracker.EntropyHash(6));
   EXPECT_EQ(5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
 
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 1));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 2));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
 
   // Fill the gap at 1.
   tracker.RecordPacketEntropyHash(1, 2);
 
   EXPECT_EQ(3u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
-  EXPECT_EQ(3, EntropyTrackerPeer::packets_entropy_size(tracker));
+  EXPECT_EQ(7, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   EXPECT_EQ(2 ^ 5 ^ 17, tracker.EntropyHash(5));
   EXPECT_EQ(2 ^ 5 ^ 17 ^ 23, tracker.EntropyHash(6));
   EXPECT_EQ(2 ^ 5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
 
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 1));
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 2));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
 
   // Fill the gap at 4.
   tracker.RecordPacketEntropyHash(4, 2);
 
   EXPECT_EQ(3u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
-  EXPECT_EQ(4, EntropyTrackerPeer::packets_entropy_size(tracker));
+  EXPECT_EQ(7, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   EXPECT_EQ(5, tracker.EntropyHash(4));
   EXPECT_EQ(5 ^ 17, tracker.EntropyHash(5));
   EXPECT_EQ(5 ^ 17 ^ 23, tracker.EntropyHash(6));
   EXPECT_EQ(5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
 
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 3));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 4));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
 
   // Fill the gap at 3.  Entropy for packets 3 to 6 are forgotten.
   tracker.RecordPacketEntropyHash(3, 2);
 
   EXPECT_EQ(7u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
-  EXPECT_EQ(1, EntropyTrackerPeer::packets_entropy_size(tracker));
+  EXPECT_EQ(3, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   EXPECT_EQ(2 ^ 5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
 
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 3));
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 4));
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
   EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
   EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
 
   // Fill in the rest.
@@ skipping 10 matching lines @@
 TEST(EntropyTrackerTest, SetCumulativeEntropyUpTo) {
   QuicReceivedPacketManager::EntropyTracker tracker;
 
   tracker.RecordPacketEntropyHash(2, 5);
   tracker.RecordPacketEntropyHash(5, 17);
   tracker.RecordPacketEntropyHash(6, 23);
   tracker.RecordPacketEntropyHash(9, 42);
 
   EXPECT_EQ(1u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
-  EXPECT_EQ(4, EntropyTrackerPeer::packets_entropy_size(tracker));
+  EXPECT_EQ(9, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   // Inform the tracker about value of the hash at a gap.
   tracker.SetCumulativeEntropyUpTo(3, 7);
   EXPECT_EQ(3u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
-  EXPECT_EQ(3, EntropyTrackerPeer::packets_entropy_size(tracker));
+  EXPECT_EQ(7, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   EXPECT_EQ(7 ^ 17, tracker.EntropyHash(5));
   EXPECT_EQ(7 ^ 17 ^ 23, tracker.EntropyHash(6));
   EXPECT_EQ(7 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
 
   // Inform the tracker about value of the hash at a known location.
   tracker.SetCumulativeEntropyUpTo(6, 1);
   EXPECT_EQ(7u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
-  EXPECT_EQ(1, EntropyTrackerPeer::packets_entropy_size(tracker));
+  EXPECT_EQ(3, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   EXPECT_EQ(1 ^ 23 ^ 42, tracker.EntropyHash(9));
 
   // Inform the tracker about value of the hash at the last location.
   tracker.SetCumulativeEntropyUpTo(9, 21);
   EXPECT_EQ(10u, EntropyTrackerPeer::first_gap(tracker));
   EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
   EXPECT_EQ(0, EntropyTrackerPeer::packets_entropy_size(tracker));
 
   EXPECT_EQ(42 ^ 21, tracker.EntropyHash(9));
@@ skipping 169 matching lines @@
   QuicAckFrame ack;
   received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
   EXPECT_TRUE(ack.missing_packets.empty());
   EXPECT_TRUE(ack.revived_packets.empty());
 }
 
 
 }  // namespace
 }  // namespace test
 }  // namespace net