Unit test for media packet reordering in ForwardErrorCorrection.

webrtc/modules/rtp_rtcp/source/forward_error_correction.cc

Index: webrtc/modules/rtp_rtcp/source/forward_error_correction.cc
diff --git a/webrtc/modules/rtp_rtcp/source/forward_error_correction.cc b/webrtc/modules/rtp_rtcp/source/forward_error_correction.cc
index b60e3119f4145c262ef27bbc65c88fbf9a696b51..5d61a10499739352e09dee50321f2571ffe9e7a5 100644
--- a/webrtc/modules/rtp_rtcp/source/forward_error_correction.cc
+++ b/webrtc/modules/rtp_rtcp/source/forward_error_correction.cc
@@ -521,6 +521,7 @@ void ForwardErrorCorrection::InsertFecPacket(
         protected_packet->seq_num =
             static_cast<uint16_t>(seq_num_base + (byte_idx << 3) + bit_idx);
         protected_packet->pkt = nullptr;
+        // Note that |protected_packets| is sorted by construction.
         fec_packet->protected_packets.push_back(std::move(protected_packet));
       }
     }
@@ -532,6 +533,10 @@ void ForwardErrorCorrection::InsertFecPacket(
     AssignRecoveredPackets(fec_packet.get(), recovered_packets);
     // TODO(holmer): Consider replacing this with a binary search for the right
     // position, and then just insert the new packet. Would get rid of the sort.
+    //
+    // For correct decoding, |received_fec_packets_| does not necessarily
+    // need to be sorted (see decoding algorithm in AttemptRecover()), but
+    // by keeping it sorted we try to recover the oldest lost packets first.
     received_fec_packets_.push_back(std::move(fec_packet));
     received_fec_packets_.sort(SortablePacket::LessThan());

[stefan-webrtc, 2016/07/05 17:26:49]

Btw, what do you think of simply finding the right position manually and
inserting the packet in order instead of calling sort after?

[brandtr, 2016/07/07 14:59:12]

Yes, that makes a lot of sense. If the packets arrive in order, we could then
add them in constant time. When reordering happens, the insertion would be
linear time instead. I'll consider this in a different CL.

In a CL that I never sent out, I switched the backing data structure to a
std::deque, which allowed for O(log n) binary search here. In an ad hoc
benchmark, I saw ~15% performance improvement, but it turned out that the
benchmark did not necessarily represent the real world usage of the FEC in a
very good way.

     if (received_fec_packets_.size() > kMaxFecPackets) {