Speed up congestion controller feedback fuzzer
When packet arrives with large gap majority of the time could be spend
in finding next received packet. Embedding such search into PacketArrivalMap
makes it faster
Bug: chromium:1373414
Change-Id: I2e0be0f2fc4ea96af081531d575a17c70b72b25b
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/279881
Reviewed-by: Emil Lundmark <lndmrk@webrtc.org>
Commit-Queue: Danil Chapovalov <danilchap@webrtc.org>
Cr-Commit-Position: refs/heads/main@{#38459}
diff --git a/modules/remote_bitrate_estimator/packet_arrival_map.h b/modules/remote_bitrate_estimator/packet_arrival_map.h
index d489a0c..e7086d0 100644
--- a/modules/remote_bitrate_estimator/packet_arrival_map.h
+++ b/modules/remote_bitrate_estimator/packet_arrival_map.h
@@ -31,6 +31,10 @@
// packets out-of-order.
class PacketArrivalTimeMap {
public:
+ struct PacketArrivalTime {
+ Timestamp arrival_time;
+ int64_t sequence_number;
+ };
// Impossible to request feedback older than what can be represented by 15
// bits.
static constexpr int kMaxNumberOfPackets = (1 << 15);
@@ -63,6 +67,21 @@
return arrival_times_[Index(sequence_number)];
}
+ // Returns timestamp and sequence number of the received packet with sequence
+ // number equal or larger than `sequence_number`. `sequence_number` must be in
+ // range [begin_sequence_number, end_sequence_number).
+ PacketArrivalTime FindNextAtOrAfter(int64_t sequence_number) const {
+ RTC_DCHECK_GE(sequence_number, begin_sequence_number());
+ RTC_DCHECK_LT(sequence_number, end_sequence_number());
+ while (true) {
+ Timestamp t = arrival_times_[Index(sequence_number)];
+ if (t >= Timestamp::Zero()) {
+ return {.arrival_time = t, .sequence_number = sequence_number};
+ }
+ ++sequence_number;
+ }
+ }
+
// Clamps `sequence_number` between [begin_sequence_number,
// end_sequence_number].
int64_t clamp(int64_t sequence_number) const {
diff --git a/modules/remote_bitrate_estimator/packet_arrival_map_test.cc b/modules/remote_bitrate_estimator/packet_arrival_map_test.cc
index 00c927f..73c532d 100644
--- a/modules/remote_bitrate_estimator/packet_arrival_map_test.cc
+++ b/modules/remote_bitrate_estimator/packet_arrival_map_test.cc
@@ -65,6 +65,23 @@
EXPECT_EQ(map.clamp(100), 46);
}
+TEST(PacketArrivalMapTest, FindNextAtOrAfterWithGaps) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, Timestamp::Zero());
+ map.AddPacket(45, Timestamp::Millis(11));
+ EXPECT_EQ(map.begin_sequence_number(), 42);
+ EXPECT_EQ(map.end_sequence_number(), 46);
+
+ PacketArrivalTimeMap::PacketArrivalTime packet = map.FindNextAtOrAfter(42);
+ EXPECT_EQ(packet.arrival_time, Timestamp::Zero());
+ EXPECT_EQ(packet.sequence_number, 42);
+
+ packet = map.FindNextAtOrAfter(43);
+ EXPECT_EQ(packet.arrival_time, Timestamp::Millis(11));
+ EXPECT_EQ(packet.sequence_number, 45);
+}
+
TEST(PacketArrivalMapTest, InsertsWithinBuffer) {
PacketArrivalTimeMap map;
diff --git a/modules/remote_bitrate_estimator/remote_estimator_proxy.cc b/modules/remote_bitrate_estimator/remote_estimator_proxy.cc
index b83720d..dd9fbbc 100644
--- a/modules/remote_bitrate_estimator/remote_estimator_proxy.cc
+++ b/modules/remote_bitrate_estimator/remote_estimator_proxy.cc
@@ -291,10 +291,11 @@
int64_t next_sequence_number = begin_sequence_number_inclusive;
for (int64_t seq = start_seq; seq < end_seq; ++seq) {
- Timestamp arrival_time = packet_arrival_times_.get(seq);
- if (arrival_time < Timestamp::Zero()) {
- // Packet not received.
- continue;
+ PacketArrivalTimeMap::PacketArrivalTime packet =
+ packet_arrival_times_.FindNextAtOrAfter(seq);
+ seq = packet.sequence_number;
+ if (seq >= end_seq) {
+ break;
}
if (feedback_packet == nullptr) {
@@ -306,12 +307,12 @@
// shall be the time of the first received packet in the feedback.
feedback_packet->SetBase(
static_cast<uint16_t>(begin_sequence_number_inclusive & 0xFFFF),
- arrival_time);
+ packet.arrival_time);
feedback_packet->SetFeedbackSequenceNumber(feedback_packet_count_++);
}
if (!feedback_packet->AddReceivedPacket(static_cast<uint16_t>(seq & 0xFFFF),
- arrival_time)) {
+ packet.arrival_time)) {
// Could not add timestamp, feedback packet might be full. Return and
// try again with a fresh packet.
break;
