Use a std::deque in RemoteEstimatorProxy
Before this CL, the RemoteEstimatorProxy used a std::map to track which
arrival time a packet with a certain sequence number was received at.
While this works, it's fairly slow as most manipulations and insertions
are O(log(N)) and there were quite many of them.
By taking advantage that sequence numbers generally are received in
sequence, recording a packet is now amortized O(1). Also other
operations such as creating the periodic feedback reports, are also
much faster as it previously was done by searching quite a few times
in that map.
In highly loaded Media Servers, RemoteEstimatorProxy's usage of
std::map attributes to around 0.52% CPU.
Bug: webrtc:12689
Change-Id: I3dd58105f9fbfb111f176833cd4aa6b040c0e01d
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/217388
Reviewed-by: Björn Terelius <terelius@webrtc.org>
Reviewed-by: Erik Språng <sprang@webrtc.org>
Reviewed-by: Mirko Bonadei <mbonadei@webrtc.org>
Commit-Queue: Victor Boivie <boivie@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#33979}
diff --git a/modules/remote_bitrate_estimator/BUILD.gn b/modules/remote_bitrate_estimator/BUILD.gn
index 81aa1ef..8507703 100644
--- a/modules/remote_bitrate_estimator/BUILD.gn
+++ b/modules/remote_bitrate_estimator/BUILD.gn
@@ -21,6 +21,8 @@
"overuse_detector.h",
"overuse_estimator.cc",
"overuse_estimator.h",
+ "packet_arrival_map.cc",
+ "packet_arrival_map.h",
"remote_bitrate_estimator_abs_send_time.cc",
"remote_bitrate_estimator_abs_send_time.h",
"remote_bitrate_estimator_single_stream.cc",
@@ -106,6 +108,7 @@
"aimd_rate_control_unittest.cc",
"inter_arrival_unittest.cc",
"overuse_detector_unittest.cc",
+ "packet_arrival_map_test.cc",
"remote_bitrate_estimator_abs_send_time_unittest.cc",
"remote_bitrate_estimator_single_stream_unittest.cc",
"remote_bitrate_estimator_unittest_helper.cc",
diff --git a/modules/remote_bitrate_estimator/packet_arrival_map.cc b/modules/remote_bitrate_estimator/packet_arrival_map.cc
new file mode 100644
index 0000000..72696f6
--- /dev/null
+++ b/modules/remote_bitrate_estimator/packet_arrival_map.cc
@@ -0,0 +1,123 @@
+/*
+ * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+#include "modules/remote_bitrate_estimator/packet_arrival_map.h"
+
+#include <algorithm>
+
+#include "rtc_base/numerics/safe_minmax.h"
+
+namespace webrtc {
+
+constexpr size_t PacketArrivalTimeMap::kMaxNumberOfPackets;
+
+void PacketArrivalTimeMap::AddPacket(int64_t sequence_number,
+ int64_t arrival_time_ms) {
+ if (!has_seen_packet_) {
+ // First packet.
+ has_seen_packet_ = true;
+ begin_sequence_number_ = sequence_number;
+ arrival_times.push_back(arrival_time_ms);
+ return;
+ }
+
+ int64_t pos = sequence_number - begin_sequence_number_;
+ if (pos >= 0 && pos < static_cast<int64_t>(arrival_times.size())) {
+ // The packet is within the buffer - no need to expand it.
+ arrival_times[pos] = arrival_time_ms;
+ return;
+ }
+
+ if (pos < 0) {
+ // The packet goes before the current buffer. Expand to add packet, but only
+ // if it fits within kMaxNumberOfPackets.
+ size_t missing_packets = -pos;
+ if (missing_packets + arrival_times.size() > kMaxNumberOfPackets) {
+ // Don't expand the buffer further, as that would remove newly received
+ // packets.
+ return;
+ }
+
+ arrival_times.insert(arrival_times.begin(), missing_packets, 0);
+ arrival_times[0] = arrival_time_ms;
+ begin_sequence_number_ = sequence_number;
+ return;
+ }
+
+ // The packet goes after the buffer.
+
+ if (static_cast<size_t>(pos) >= kMaxNumberOfPackets) {
+ // The buffer grows too large - old packets have to be removed.
+ size_t packets_to_remove = pos - kMaxNumberOfPackets + 1;
+ if (packets_to_remove >= arrival_times.size()) {
+ arrival_times.clear();
+ begin_sequence_number_ = sequence_number;
+ pos = 0;
+ } else {
+ // Also trim the buffer to remove leading non-received packets, to
+ // ensure that the buffer only spans received packets.
+ while (packets_to_remove < arrival_times.size() &&
+ arrival_times[packets_to_remove] == 0) {
+ ++packets_to_remove;
+ }
+
+ arrival_times.erase(arrival_times.begin(),
+ arrival_times.begin() + packets_to_remove);
+ begin_sequence_number_ += packets_to_remove;
+ pos -= packets_to_remove;
+ RTC_DCHECK_GE(pos, 0);
+ }
+ }
+
+ // Packets can be received out-of-order. If this isn't the next expected
+ // packet, add enough placeholders to fill the gap.
+ size_t missing_gap_packets = pos - arrival_times.size();
+ if (missing_gap_packets > 0) {
+ arrival_times.insert(arrival_times.end(), missing_gap_packets, 0);
+ }
+ RTC_DCHECK_EQ(arrival_times.size(), pos);
+ arrival_times.push_back(arrival_time_ms);
+ RTC_DCHECK_LE(arrival_times.size(), kMaxNumberOfPackets);
+}
+
+void PacketArrivalTimeMap::RemoveOldPackets(int64_t sequence_number,
+ int64_t arrival_time_limit) {
+ while (!arrival_times.empty() && begin_sequence_number_ < sequence_number &&
+ arrival_times.front() <= arrival_time_limit) {
+ arrival_times.pop_front();
+ ++begin_sequence_number_;
+ }
+}
+
+bool PacketArrivalTimeMap::has_received(int64_t sequence_number) const {
+ int64_t pos = sequence_number - begin_sequence_number_;
+ if (pos >= 0 && pos < static_cast<int64_t>(arrival_times.size()) &&
+ arrival_times[pos] != 0) {
+ return true;
+ }
+ return false;
+}
+
+void PacketArrivalTimeMap::EraseTo(int64_t sequence_number) {
+ if (sequence_number > begin_sequence_number_) {
+ size_t count =
+ std::min(static_cast<size_t>(sequence_number - begin_sequence_number_),
+ arrival_times.size());
+
+ arrival_times.erase(arrival_times.begin(), arrival_times.begin() + count);
+ begin_sequence_number_ += count;
+ }
+}
+
+int64_t PacketArrivalTimeMap::clamp(int64_t sequence_number) const {
+ return rtc::SafeClamp(sequence_number, begin_sequence_number(),
+ end_sequence_number());
+}
+
+} // namespace webrtc
diff --git a/modules/remote_bitrate_estimator/packet_arrival_map.h b/modules/remote_bitrate_estimator/packet_arrival_map.h
new file mode 100644
index 0000000..10659e0
--- /dev/null
+++ b/modules/remote_bitrate_estimator/packet_arrival_map.h
@@ -0,0 +1,88 @@
+/*
+ * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+#ifndef MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_
+#define MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_
+
+#include <cstddef>
+#include <cstdint>
+#include <deque>
+
+#include "rtc_base/checks.h"
+
+namespace webrtc {
+
+// PacketArrivalTimeMap is an optimized map of packet sequence number to arrival
+// time, limited in size to never exceed `kMaxNumberOfPackets`. It will grow as
+// needed, and remove old packets, and will expand to allow earlier packets to
+// be added (out-of-order).
+//
+// Not yet received packets have the arrival time zero. The queue will not span
+// larger than necessary and the last packet should always be received. The
+// first packet in the queue doesn't have to be received in case of receiving
+// packets out-of-order.
+class PacketArrivalTimeMap {
+ public:
+ // Impossible to request feedback older than what can be represented by 15
+ // bits.
+ static constexpr size_t kMaxNumberOfPackets = (1 << 15);
+
+ // Indicates if the packet with `sequence_number` has already been received.
+ bool has_received(int64_t sequence_number) const;
+
+ // Returns the sequence number of the first entry in the map, i.e. the
+ // sequence number that a `begin()` iterator would represent.
+ int64_t begin_sequence_number() const { return begin_sequence_number_; }
+
+ // Returns the sequence number of the element just after the map, i.e. the
+ // sequence number that an `end()` iterator would represent.
+ int64_t end_sequence_number() const {
+ return begin_sequence_number_ + arrival_times.size();
+ }
+
+ // Returns an element by `sequence_number`, which must be valid, i.e.
+ // between [begin_sequence_number, end_sequence_number).
+ int64_t get(int64_t sequence_number) {
+ int64_t pos = sequence_number - begin_sequence_number_;
+ RTC_DCHECK(pos >= 0 && pos < static_cast<int64_t>(arrival_times.size()));
+ return arrival_times[pos];
+ }
+
+ // Clamps `sequence_number` between [begin_sequence_number,
+ // end_sequence_number].
+ int64_t clamp(int64_t sequence_number) const;
+
+ // Erases all elements from the beginning of the map until `sequence_number`.
+ void EraseTo(int64_t sequence_number);
+
+ // Records the fact that a packet with `sequence_number` arrived at
+ // `arrival_time_ms`.
+ void AddPacket(int64_t sequence_number, int64_t arrival_time_ms);
+
+ // Removes packets from the beginning of the map as long as they are received
+ // before `sequence_number` and with an age older than `arrival_time_limit`
+ void RemoveOldPackets(int64_t sequence_number, int64_t arrival_time_limit);
+
+ private:
+ // Deque representing unwrapped sequence number -> time, where the index +
+ // `begin_sequence_number_` represents the packet's sequence number.
+ std::deque<int64_t> arrival_times;
+
+ // The unwrapped sequence number for the first element in
+ // `arrival_times`.
+ int64_t begin_sequence_number_ = 0;
+
+ // Indicates if this map has had any packet added to it. The first packet
+ // decides the initial sequence number.
+ bool has_seen_packet_ = false;
+};
+
+} // namespace webrtc
+
+#endif // MODULES_REMOTE_BITRATE_ESTIMATOR_PACKET_ARRIVAL_MAP_H_
diff --git a/modules/remote_bitrate_estimator/packet_arrival_map_test.cc b/modules/remote_bitrate_estimator/packet_arrival_map_test.cc
new file mode 100644
index 0000000..afc7038
--- /dev/null
+++ b/modules/remote_bitrate_estimator/packet_arrival_map_test.cc
@@ -0,0 +1,252 @@
+/*
+ * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+#include "modules/remote_bitrate_estimator/packet_arrival_map.h"
+
+#include "test/gmock.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace {
+
+TEST(PacketArrivalMapTest, IsConsistentWhenEmpty) {
+ PacketArrivalTimeMap map;
+
+ EXPECT_EQ(map.begin_sequence_number(), map.end_sequence_number());
+ EXPECT_FALSE(map.has_received(0));
+ EXPECT_EQ(map.clamp(-5), 0);
+ EXPECT_EQ(map.clamp(5), 0);
+}
+
+TEST(PacketArrivalMapTest, InsertsFirstItemIntoMap) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ EXPECT_EQ(map.begin_sequence_number(), 42);
+ EXPECT_EQ(map.end_sequence_number(), 43);
+
+ EXPECT_FALSE(map.has_received(41));
+ EXPECT_TRUE(map.has_received(42));
+ EXPECT_FALSE(map.has_received(44));
+
+ EXPECT_EQ(map.clamp(-100), 42);
+ EXPECT_EQ(map.clamp(42), 42);
+ EXPECT_EQ(map.clamp(100), 43);
+}
+
+TEST(PacketArrivalMapTest, InsertsWithGaps) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ map.AddPacket(45, 11);
+ EXPECT_EQ(map.begin_sequence_number(), 42);
+ EXPECT_EQ(map.end_sequence_number(), 46);
+
+ EXPECT_FALSE(map.has_received(41));
+ EXPECT_TRUE(map.has_received(42));
+ EXPECT_FALSE(map.has_received(43));
+ EXPECT_FALSE(map.has_received(44));
+ EXPECT_TRUE(map.has_received(45));
+ EXPECT_FALSE(map.has_received(46));
+
+ EXPECT_EQ(map.get(42), 10);
+ EXPECT_EQ(map.get(43), 0);
+ EXPECT_EQ(map.get(44), 0);
+ EXPECT_EQ(map.get(45), 11);
+
+ EXPECT_EQ(map.clamp(-100), 42);
+ EXPECT_EQ(map.clamp(44), 44);
+ EXPECT_EQ(map.clamp(100), 46);
+}
+
+TEST(PacketArrivalMapTest, InsertsWithinBuffer) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ map.AddPacket(45, 11);
+
+ map.AddPacket(43, 12);
+ map.AddPacket(44, 13);
+
+ EXPECT_EQ(map.begin_sequence_number(), 42);
+ EXPECT_EQ(map.end_sequence_number(), 46);
+
+ EXPECT_FALSE(map.has_received(41));
+ EXPECT_TRUE(map.has_received(42));
+ EXPECT_TRUE(map.has_received(43));
+ EXPECT_TRUE(map.has_received(44));
+ EXPECT_TRUE(map.has_received(45));
+ EXPECT_FALSE(map.has_received(46));
+
+ EXPECT_EQ(map.get(42), 10);
+ EXPECT_EQ(map.get(43), 12);
+ EXPECT_EQ(map.get(44), 13);
+ EXPECT_EQ(map.get(45), 11);
+}
+
+TEST(PacketArrivalMapTest, GrowsBufferAndRemoveOld) {
+ PacketArrivalTimeMap map;
+
+ constexpr int64_t kLargeSeq = 42 + PacketArrivalTimeMap::kMaxNumberOfPackets;
+ map.AddPacket(42, 10);
+ map.AddPacket(43, 11);
+ map.AddPacket(44, 12);
+ map.AddPacket(45, 13);
+ map.AddPacket(kLargeSeq, 12);
+
+ EXPECT_EQ(map.begin_sequence_number(), 43);
+ EXPECT_EQ(map.end_sequence_number(), kLargeSeq + 1);
+ EXPECT_EQ(static_cast<size_t>(map.end_sequence_number() -
+ map.begin_sequence_number()),
+ PacketArrivalTimeMap::kMaxNumberOfPackets);
+
+ EXPECT_FALSE(map.has_received(41));
+ EXPECT_FALSE(map.has_received(42));
+ EXPECT_TRUE(map.has_received(43));
+ EXPECT_TRUE(map.has_received(44));
+ EXPECT_TRUE(map.has_received(45));
+ EXPECT_FALSE(map.has_received(46));
+ EXPECT_TRUE(map.has_received(kLargeSeq));
+ EXPECT_FALSE(map.has_received(kLargeSeq + 1));
+}
+
+TEST(PacketArrivalMapTest, GrowsBufferAndRemoveOldTrimsBeginning) {
+ PacketArrivalTimeMap map;
+
+ constexpr int64_t kLargeSeq = 42 + PacketArrivalTimeMap::kMaxNumberOfPackets;
+ map.AddPacket(42, 10);
+ // Missing: 43, 44
+ map.AddPacket(45, 13);
+ map.AddPacket(kLargeSeq, 12);
+
+ EXPECT_EQ(map.begin_sequence_number(), 45);
+ EXPECT_EQ(map.end_sequence_number(), kLargeSeq + 1);
+
+ EXPECT_FALSE(map.has_received(44));
+ EXPECT_TRUE(map.has_received(45));
+ EXPECT_FALSE(map.has_received(46));
+ EXPECT_TRUE(map.has_received(kLargeSeq));
+ EXPECT_FALSE(map.has_received(kLargeSeq + 1));
+}
+
+TEST(PacketArrivalMapTest, SequenceNumberJumpsDeletesAll) {
+ PacketArrivalTimeMap map;
+
+ constexpr int64_t kLargeSeq =
+ 42 + 2 * PacketArrivalTimeMap::kMaxNumberOfPackets;
+ map.AddPacket(42, 10);
+ map.AddPacket(kLargeSeq, 12);
+
+ EXPECT_EQ(map.begin_sequence_number(), kLargeSeq);
+ EXPECT_EQ(map.end_sequence_number(), kLargeSeq + 1);
+
+ EXPECT_FALSE(map.has_received(42));
+ EXPECT_TRUE(map.has_received(kLargeSeq));
+ EXPECT_FALSE(map.has_received(kLargeSeq + 1));
+}
+
+TEST(PacketArrivalMapTest, ExpandsBeforeBeginning) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ map.AddPacket(-1000, 13);
+
+ EXPECT_EQ(map.begin_sequence_number(), -1000);
+ EXPECT_EQ(map.end_sequence_number(), 43);
+
+ EXPECT_FALSE(map.has_received(-1001));
+ EXPECT_TRUE(map.has_received(-1000));
+ EXPECT_FALSE(map.has_received(-999));
+ EXPECT_TRUE(map.has_received(42));
+ EXPECT_FALSE(map.has_received(43));
+}
+
+TEST(PacketArrivalMapTest, ExpandingBeforeBeginningKeepsReceived) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ constexpr int64_t kSmallSeq =
+ static_cast<int64_t>(42) - 2 * PacketArrivalTimeMap::kMaxNumberOfPackets;
+ map.AddPacket(kSmallSeq, 13);
+
+ EXPECT_EQ(map.begin_sequence_number(), 42);
+ EXPECT_EQ(map.end_sequence_number(), 43);
+}
+
+TEST(PacketArrivalMapTest, ErasesToRemoveElements) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ map.AddPacket(43, 11);
+ map.AddPacket(44, 12);
+ map.AddPacket(45, 13);
+
+ map.EraseTo(44);
+
+ EXPECT_EQ(map.begin_sequence_number(), 44);
+ EXPECT_EQ(map.end_sequence_number(), 46);
+
+ EXPECT_FALSE(map.has_received(43));
+ EXPECT_TRUE(map.has_received(44));
+ EXPECT_TRUE(map.has_received(45));
+ EXPECT_FALSE(map.has_received(46));
+}
+
+TEST(PacketArrivalMapTest, ErasesInEmptyMap) {
+ PacketArrivalTimeMap map;
+
+ EXPECT_EQ(map.begin_sequence_number(), map.end_sequence_number());
+
+ map.EraseTo(map.end_sequence_number());
+ EXPECT_EQ(map.begin_sequence_number(), map.end_sequence_number());
+}
+
+TEST(PacketArrivalMapTest, IsTolerantToWrongArgumentsForErase) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ map.AddPacket(43, 11);
+
+ map.EraseTo(1);
+
+ EXPECT_EQ(map.begin_sequence_number(), 42);
+ EXPECT_EQ(map.end_sequence_number(), 44);
+
+ map.EraseTo(100);
+
+ EXPECT_EQ(map.begin_sequence_number(), 44);
+ EXPECT_EQ(map.end_sequence_number(), 44);
+}
+
+TEST(PacketArrivalMapTest, EraseAllRemembersBeginningSeqNbr) {
+ PacketArrivalTimeMap map;
+
+ map.AddPacket(42, 10);
+ map.AddPacket(43, 11);
+ map.AddPacket(44, 12);
+ map.AddPacket(45, 13);
+
+ map.EraseTo(46);
+
+ map.AddPacket(50, 10);
+
+ EXPECT_EQ(map.begin_sequence_number(), 46);
+ EXPECT_EQ(map.end_sequence_number(), 51);
+
+ EXPECT_FALSE(map.has_received(45));
+ EXPECT_FALSE(map.has_received(46));
+ EXPECT_FALSE(map.has_received(47));
+ EXPECT_FALSE(map.has_received(48));
+ EXPECT_FALSE(map.has_received(49));
+ EXPECT_TRUE(map.has_received(50));
+ EXPECT_FALSE(map.has_received(51));
+}
+
+} // namespace
+} // namespace webrtc
diff --git a/modules/remote_bitrate_estimator/remote_estimator_proxy.cc b/modules/remote_bitrate_estimator/remote_estimator_proxy.cc
index ba04775..7764e60 100644
--- a/modules/remote_bitrate_estimator/remote_estimator_proxy.cc
+++ b/modules/remote_bitrate_estimator/remote_estimator_proxy.cc
@@ -23,9 +23,6 @@
namespace webrtc {
-// Impossible to request feedback older than what can be represented by 15 bits.
-const int RemoteEstimatorProxy::kMaxNumberOfPackets = (1 << 15);
-
// The maximum allowed value for a timestamp in milliseconds. This is lower
// than the numerical limit since we often convert to microseconds.
static constexpr int64_t kMaxTimeMs =
@@ -54,21 +51,14 @@
RemoteEstimatorProxy::~RemoteEstimatorProxy() {}
-void RemoteEstimatorProxy::AddPacket(int64_t sequence_number,
- int64_t arrival_time_ms) {
- packet_arrival_times_[sequence_number] = arrival_time_ms;
-}
-
void RemoteEstimatorProxy::MaybeCullOldPackets(int64_t sequence_number,
int64_t arrival_time_ms) {
- if (periodic_window_start_seq_ &&
- packet_arrival_times_.lower_bound(*periodic_window_start_seq_) ==
- packet_arrival_times_.end()) {
- // Start new feedback packet, cull old packets.
- for (auto it = packet_arrival_times_.begin();
- it != packet_arrival_times_.end() && it->first < sequence_number &&
- arrival_time_ms - it->second >= send_config_.back_window->ms();) {
- it = packet_arrival_times_.erase(it);
+ if (periodic_window_start_seq_.has_value()) {
+ if (*periodic_window_start_seq_ >=
+ packet_arrival_times_.end_sequence_number()) {
+ // Start new feedback packet, cull old packets.
+ packet_arrival_times_.RemoveOldPackets(
+ sequence_number, arrival_time_ms - send_config_.back_window->ms());
}
}
}
@@ -96,23 +86,18 @@
}
// We are only interested in the first time a packet is received.
- if (packet_arrival_times_.find(seq) != packet_arrival_times_.end())
+ if (packet_arrival_times_.has_received(seq)) {
return;
+ }
- AddPacket(seq, arrival_time_ms);
+ packet_arrival_times_.AddPacket(seq, arrival_time_ms);
// Limit the range of sequence numbers to send feedback for.
- auto first_arrival_time_to_keep = packet_arrival_times_.lower_bound(
- packet_arrival_times_.rbegin()->first - kMaxNumberOfPackets);
- if (first_arrival_time_to_keep != packet_arrival_times_.begin()) {
- packet_arrival_times_.erase(packet_arrival_times_.begin(),
- first_arrival_time_to_keep);
- if (send_periodic_feedback_) {
- // |packet_arrival_times_| cannot be empty since we just added one
- // element and the last element is not deleted.
- RTC_DCHECK(!packet_arrival_times_.empty());
- periodic_window_start_seq_ = packet_arrival_times_.begin()->first;
- }
+ if (!periodic_window_start_seq_.has_value() ||
+ periodic_window_start_seq_.value() <
+ packet_arrival_times_.begin_sequence_number()) {
+ periodic_window_start_seq_ =
+ packet_arrival_times_.begin_sequence_number();
}
if (header.extension.feedback_request) {
@@ -124,8 +109,8 @@
if (network_state_estimator_ && header.extension.hasAbsoluteSendTime) {
PacketResult packet_result;
packet_result.receive_time = Timestamp::Millis(arrival_time_ms);
- // Ignore reordering of packets and assume they have approximately the same
- // send time.
+ // Ignore reordering of packets and assume they have approximately the
+ // same send time.
abs_send_timestamp_ += std::max(
header.extension.GetAbsoluteSendTimeDelta(previous_abs_send_time_),
TimeDelta::Millis(0));
@@ -194,9 +179,9 @@
}
void RemoteEstimatorProxy::SendPeriodicFeedbacks() {
- // |periodic_window_start_seq_| is the first sequence number to include in the
- // current feedback packet. Some older may still be in the map, in case a
- // reordering happens and we need to retransmit them.
+ // |periodic_window_start_seq_| is the first sequence number to include in
+ // the current feedback packet. Some older may still be in the map, in case
+ // a reordering happens and we need to retransmit them.
if (!periodic_window_start_seq_)
return;
@@ -210,16 +195,18 @@
}
}
- for (auto begin_iterator =
- packet_arrival_times_.lower_bound(*periodic_window_start_seq_);
- begin_iterator != packet_arrival_times_.cend();
- begin_iterator =
- packet_arrival_times_.lower_bound(*periodic_window_start_seq_)) {
- auto feedback_packet = BuildFeedbackPacket(
- /*include_timestamps=*/true, *periodic_window_start_seq_,
- begin_iterator, packet_arrival_times_.cend(),
+ int64_t packet_arrival_times_end_seq =
+ packet_arrival_times_.end_sequence_number();
+ while (periodic_window_start_seq_ < packet_arrival_times_end_seq) {
+ auto feedback_packet = MaybeBuildFeedbackPacket(
+ /*include_timestamps=*/true, periodic_window_start_seq_.value(),
+ packet_arrival_times_end_seq,
/*is_periodic_update=*/true);
+ if (feedback_packet == nullptr) {
+ break;
+ }
+
RTC_DCHECK(feedback_sender_ != nullptr);
std::vector<std::unique_ptr<rtcp::RtcpPacket>> packets;
@@ -229,9 +216,9 @@
packets.push_back(std::move(feedback_packet));
feedback_sender_(std::move(packets));
- // Note: Don't erase items from packet_arrival_times_ after sending, in case
- // they need to be re-sent after a reordering. Removal will be handled
- // by OnPacketArrival once packets are too old.
+ // Note: Don't erase items from packet_arrival_times_ after sending, in
+ // case they need to be re-sent after a reordering. Removal will be
+ // handled by OnPacketArrival once packets are too old.
}
}
@@ -244,16 +231,16 @@
int64_t first_sequence_number =
sequence_number - feedback_request.sequence_count + 1;
- auto begin_iterator =
- packet_arrival_times_.lower_bound(first_sequence_number);
- auto end_iterator = packet_arrival_times_.upper_bound(sequence_number);
- auto feedback_packet = BuildFeedbackPacket(
+ auto feedback_packet = MaybeBuildFeedbackPacket(
feedback_request.include_timestamps, first_sequence_number,
- begin_iterator, end_iterator, /*is_periodic_update=*/false);
+ sequence_number + 1, /*is_periodic_update=*/false);
+
+ // This is called when a packet has just been added.
+ RTC_DCHECK(feedback_packet != nullptr);
// Clear up to the first packet that is included in this feedback packet.
- packet_arrival_times_.erase(packet_arrival_times_.begin(), begin_iterator);
+ packet_arrival_times_.EraseTo(first_sequence_number);
RTC_DCHECK(feedback_sender_ != nullptr);
std::vector<std::unique_ptr<rtcp::RtcpPacket>> packets;
@@ -262,39 +249,54 @@
}
std::unique_ptr<rtcp::TransportFeedback>
-RemoteEstimatorProxy::BuildFeedbackPacket(
+RemoteEstimatorProxy::MaybeBuildFeedbackPacket(
bool include_timestamps,
- int64_t base_sequence_number,
- std::map<int64_t, int64_t>::const_iterator begin_iterator,
- std::map<int64_t, int64_t>::const_iterator end_iterator,
+ int64_t begin_sequence_number_inclusive,
+ int64_t end_sequence_number_exclusive,
bool is_periodic_update) {
- RTC_DCHECK(begin_iterator != end_iterator);
+ RTC_DCHECK_LT(begin_sequence_number_inclusive, end_sequence_number_exclusive);
- auto feedback_packet =
- std::make_unique<rtcp::TransportFeedback>(include_timestamps);
+ int64_t start_seq =
+ packet_arrival_times_.clamp(begin_sequence_number_inclusive);
- // TODO(sprang): Measure receive times in microseconds and remove the
- // conversions below.
- feedback_packet->SetMediaSsrc(media_ssrc_);
- // Base sequence number is the expected first sequence number. This is known,
- // but we might not have actually received it, so the base time shall be the
- // time of the first received packet in the feedback.
- feedback_packet->SetBase(static_cast<uint16_t>(base_sequence_number & 0xFFFF),
- begin_iterator->second * 1000);
- feedback_packet->SetFeedbackSequenceNumber(feedback_packet_count_++);
- int64_t next_sequence_number = base_sequence_number;
- for (auto it = begin_iterator; it != end_iterator; ++it) {
- if (!feedback_packet->AddReceivedPacket(
- static_cast<uint16_t>(it->first & 0xFFFF), it->second * 1000)) {
- // If we can't even add the first seq to the feedback packet, we won't be
- // able to build it at all.
- RTC_CHECK(begin_iterator != it);
+ int64_t end_seq = packet_arrival_times_.clamp(end_sequence_number_exclusive);
+ // Create the packet on demand, as it's not certain that there are packets
+ // in the range that have been received.
+ std::unique_ptr<rtcp::TransportFeedback> feedback_packet = nullptr;
+
+ int64_t next_sequence_number = begin_sequence_number_inclusive;
+
+ for (int64_t seq = start_seq; seq < end_seq; ++seq) {
+ int64_t arrival_time_ms = packet_arrival_times_.get(seq);
+ if (arrival_time_ms == 0) {
+ // Packet not received.
+ continue;
+ }
+
+ if (feedback_packet == nullptr) {
+ feedback_packet =
+ std::make_unique<rtcp::TransportFeedback>(include_timestamps);
+ // TODO(sprang): Measure receive times in microseconds and remove the
+ // conversions below.
+ feedback_packet->SetMediaSsrc(media_ssrc_);
+ // Base sequence number is the expected first sequence number. This is
+ // known, but we might not have actually received it, so the base time
+ // 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_ms * 1000);
+ feedback_packet->SetFeedbackSequenceNumber(feedback_packet_count_++);
+ }
+
+ if (!feedback_packet->AddReceivedPacket(static_cast<uint16_t>(seq & 0xFFFF),
+ arrival_time_ms * 1000)) {
// Could not add timestamp, feedback packet might be full. Return and
// try again with a fresh packet.
break;
}
- next_sequence_number = it->first + 1;
+
+ next_sequence_number = seq + 1;
}
if (is_periodic_update) {
periodic_window_start_seq_ = next_sequence_number;
diff --git a/modules/remote_bitrate_estimator/remote_estimator_proxy.h b/modules/remote_bitrate_estimator/remote_estimator_proxy.h
index 37ef7c4..4f89409 100644
--- a/modules/remote_bitrate_estimator/remote_estimator_proxy.h
+++ b/modules/remote_bitrate_estimator/remote_estimator_proxy.h
@@ -11,14 +11,15 @@
#ifndef MODULES_REMOTE_BITRATE_ESTIMATOR_REMOTE_ESTIMATOR_PROXY_H_
#define MODULES_REMOTE_BITRATE_ESTIMATOR_REMOTE_ESTIMATOR_PROXY_H_
+#include <deque>
#include <functional>
-#include <map>
#include <memory>
#include <vector>
#include "api/transport/network_control.h"
#include "api/transport/webrtc_key_value_config.h"
#include "modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
+#include "modules/remote_bitrate_estimator/packet_arrival_map.h"
#include "rtc_base/experiments/field_trial_parser.h"
#include "rtc_base/numerics/sequence_number_util.h"
#include "rtc_base/synchronization/mutex.h"
@@ -75,12 +76,6 @@
}
};
- static const int kMaxNumberOfPackets;
-
- // Records the fact that a packet with `sequence_number` arrived at
- // `arrival_time_ms`.
- void AddPacket(int64_t sequence_number, int64_t arrival_time_ms)
- RTC_EXCLUSIVE_LOCKS_REQUIRED(&lock_);
void MaybeCullOldPackets(int64_t sequence_number, int64_t arrival_time_ms)
RTC_EXCLUSIVE_LOCKS_REQUIRED(&lock_);
void SendPeriodicFeedbacks() RTC_EXCLUSIVE_LOCKS_REQUIRED(&lock_);
@@ -89,22 +84,21 @@
RTC_EXCLUSIVE_LOCKS_REQUIRED(&lock_);
// Returns a Transport Feedback packet with information about as many packets
- // that has been received between [`begin_iterator`, `end_iterator`) that can
- // fit in it. If `is_periodic_update`, this represents sending a periodic
- // feedback message, which will make it update the
- // `periodic_window_start_seq_` variable with the first packet that was not
- // included in the feedback packet, so that the next update can continue from
- // that sequence number.
+ // that has been received between [`begin_sequence_number_incl`,
+ // `end_sequence_number_excl`) that can fit in it. If `is_periodic_update`,
+ // this represents sending a periodic feedback message, which will make it
+ // update the `periodic_window_start_seq_` variable with the first packet that
+ // was not included in the feedback packet, so that the next update can
+ // continue from that sequence number.
+ //
+ // If no incoming packets were added, nullptr is returned.
//
// `include_timestamps` decide if the returned TransportFeedback should
// include timestamps.
- std::unique_ptr<rtcp::TransportFeedback> BuildFeedbackPacket(
+ std::unique_ptr<rtcp::TransportFeedback> MaybeBuildFeedbackPacket(
bool include_timestamps,
- int64_t base_sequence_number,
- std::map<int64_t, int64_t>::const_iterator
- begin_iterator, // |begin_iterator| is inclusive.
- std::map<int64_t, int64_t>::const_iterator
- end_iterator, // |end_iterator| is exclusive.
+ int64_t begin_sequence_number_inclusive,
+ int64_t end_sequence_number_exclusive,
bool is_periodic_update) RTC_EXCLUSIVE_LOCKS_REQUIRED(&lock_);
Clock* const clock_;
@@ -123,8 +117,10 @@
// The next sequence number that should be the start sequence number during
// periodic reporting. Will be absl::nullopt before the first seen packet.
absl::optional<int64_t> periodic_window_start_seq_ RTC_GUARDED_BY(&lock_);
- // Map unwrapped seq -> time.
- std::map<int64_t, int64_t> packet_arrival_times_ RTC_GUARDED_BY(&lock_);
+
+ // Packet arrival times, by sequence number.
+ PacketArrivalTimeMap packet_arrival_times_ RTC_GUARDED_BY(&lock_);
+
int64_t send_interval_ms_ RTC_GUARDED_BY(&lock_);
bool send_periodic_feedback_ RTC_GUARDED_BY(&lock_);
