Optimize execution time of RTPSender::UpdateDelayStatistics
Bug: webrtc:9439
Change-Id: I908e9ced10031c614678a89657d089cb9a66b9ce
Reviewed-on: https://webrtc-review.googlesource.com/92391
Commit-Queue: Björn Terelius <terelius@webrtc.org>
Reviewed-by: Åsa Persson <asapersson@webrtc.org>
Reviewed-by: Philip Eliasson <philipel@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#24295}diff --git a/modules/rtp_rtcp/source/rtp_sender.cc b/modules/rtp_rtcp/source/rtp_sender.cc
index e0347f0..740394b 100644
--- a/modules/rtp_rtcp/source/rtp_sender.cc
+++ b/modules/rtp_rtcp/source/rtp_sender.cc
@@ -136,6 +136,9 @@
packet_history_(clock),
flexfec_packet_history_(clock),
// Statistics
+ send_delays_(),
+ max_delay_it_(send_delays_.end()),
+ sum_delays_ms_(0),
rtp_stats_callback_(nullptr),
total_bitrate_sent_(kBitrateStatisticsWindowMs,
RateStatistics::kBpsScale),
@@ -970,12 +973,21 @@
return sent;
}
+void RTPSender::RecomputeMaxSendDelay() {
+ max_delay_it_ = send_delays_.begin();
+ for (auto it = send_delays_.begin(); it != send_delays_.end(); ++it) {
+ if (it->second >= max_delay_it_->second) {
+ max_delay_it_ = it;
+ }
+ }
+}
+
void RTPSender::UpdateDelayStatistics(int64_t capture_time_ms, int64_t now_ms) {
if (!send_side_delay_observer_ || capture_time_ms <= 0)
return;
uint32_t ssrc;
- int64_t avg_delay_ms = 0;
+ int avg_delay_ms = 0;
int max_delay_ms = 0;
{
rtc::CritScope lock(&send_critsect_);
@@ -985,24 +997,55 @@
}
{
rtc::CritScope cs(&statistics_crit_);
- // TODO(holmer): Compute this iteratively instead.
- send_delays_[now_ms] = now_ms - capture_time_ms;
- send_delays_.erase(
- send_delays_.begin(),
- send_delays_.lower_bound(now_ms - kSendSideDelayWindowMs));
- int num_delays = 0;
- for (auto it = send_delays_.upper_bound(now_ms - kSendSideDelayWindowMs);
- it != send_delays_.end(); ++it) {
- max_delay_ms = std::max(max_delay_ms, it->second);
- avg_delay_ms += it->second;
- ++num_delays;
+ // Compute the max and average of the recent capture-to-send delays.
+ // The time complexity of the current approach depends on the distribution
+ // of the delay values. This could be done more efficiently.
+
+ // Remove elements older than kSendSideDelayWindowMs.
+ auto lower_bound =
+ send_delays_.lower_bound(now_ms - kSendSideDelayWindowMs);
+ for (auto it = send_delays_.begin(); it != lower_bound; ++it) {
+ if (max_delay_it_ == it) {
+ max_delay_it_ = send_delays_.end();
+ }
+ sum_delays_ms_ -= it->second;
}
- if (num_delays == 0)
- return;
- avg_delay_ms = (avg_delay_ms + num_delays / 2) / num_delays;
+ send_delays_.erase(send_delays_.begin(), lower_bound);
+ if (max_delay_it_ == send_delays_.end()) {
+ // Removed the previous max. Need to recompute.
+ RecomputeMaxSendDelay();
+ }
+
+ // Add the new element.
+ int new_send_delay = rtc::dchecked_cast<int>(now_ms - capture_time_ms);
+ SendDelayMap::iterator it;
+ bool inserted;
+ std::tie(it, inserted) =
+ send_delays_.insert(std::make_pair(now_ms, new_send_delay));
+ if (!inserted) {
+ // TODO(terelius): If we have multiple delay measurements during the same
+ // millisecond then we keep the most recent one. It is not clear that this
+ // is the right decision, but it preserves an earlier behavior.
+ int previous_send_delay = it->second;
+ sum_delays_ms_ -= previous_send_delay;
+ it->second = new_send_delay;
+ if (max_delay_it_ == it && new_send_delay < previous_send_delay) {
+ RecomputeMaxSendDelay();
+ }
+ }
+ if (max_delay_it_ == send_delays_.end() ||
+ it->second >= max_delay_it_->second) {
+ max_delay_it_ = it;
+ }
+ sum_delays_ms_ += new_send_delay;
+
+ size_t num_delays = send_delays_.size();
+ max_delay_ms = rtc::dchecked_cast<int>(max_delay_it_->second);
+ avg_delay_ms =
+ rtc::dchecked_cast<int>((sum_delays_ms_ + num_delays / 2) / num_delays);
}
- send_side_delay_observer_->SendSideDelayUpdated(
- rtc::dchecked_cast<int>(avg_delay_ms), max_delay_ms, ssrc);
+ send_side_delay_observer_->SendSideDelayUpdated(avg_delay_ms, max_delay_ms,
+ ssrc);
}
void RTPSender::UpdateOnSendPacket(int packet_id,
diff --git a/modules/rtp_rtcp/source/rtp_sender.h b/modules/rtp_rtcp/source/rtp_sender.h
index 5ff4a0f..c59e62b 100644
--- a/modules/rtp_rtcp/source/rtp_sender.h
+++ b/modules/rtp_rtcp/source/rtp_sender.h
@@ -239,6 +239,7 @@
const PacketOptions& options,
const PacedPacketInfo& pacing_info);
+ void RecomputeMaxSendDelay() RTC_EXCLUSIVE_LOCKS_REQUIRED(statistics_crit_);
void UpdateDelayStatistics(int64_t capture_time_ms, int64_t now_ms);
void UpdateOnSendPacket(int packet_id,
int64_t capture_time_ms,
@@ -296,6 +297,8 @@
// Statistics
rtc::CriticalSection statistics_crit_;
SendDelayMap send_delays_ RTC_GUARDED_BY(statistics_crit_);
+ SendDelayMap::const_iterator max_delay_it_ RTC_GUARDED_BY(statistics_crit_);
+ int64_t sum_delays_ms_ RTC_GUARDED_BY(statistics_crit_);
FrameCounts frame_counts_ RTC_GUARDED_BY(statistics_crit_);
StreamDataCounters rtp_stats_ RTC_GUARDED_BY(statistics_crit_);
StreamDataCounters rtx_rtp_stats_ RTC_GUARDED_BY(statistics_crit_);
diff --git a/modules/rtp_rtcp/source/rtp_sender_unittest.cc b/modules/rtp_rtcp/source/rtp_sender_unittest.cc
index d143c87..58b30c2 100644
--- a/modules/rtp_rtcp/source/rtp_sender_unittest.cc
+++ b/modules/rtp_rtcp/source/rtp_sender_unittest.cc
@@ -133,6 +133,11 @@
MOCK_METHOD0(AllocateSequenceNumber, uint16_t());
};
+class MockSendSideDelayObserver : public SendSideDelayObserver {
+ public:
+ MOCK_METHOD3(SendSideDelayUpdated, void(int, int, uint32_t));
+};
+
class MockSendPacketObserver : public SendPacketObserver {
public:
MOCK_METHOD3(OnSendPacket, void(uint16_t, int64_t, uint32_t));
@@ -485,6 +490,71 @@
SendGenericPayload();
}
+TEST_P(RtpSenderTestWithoutPacer, OnSendSideDelayUpdated) {
+ testing::StrictMock<MockSendSideDelayObserver> send_side_delay_observer_;
+ rtp_sender_.reset(
+ new RTPSender(false, &fake_clock_, &transport_, nullptr, nullptr, nullptr,
+ nullptr, nullptr, nullptr, &send_side_delay_observer_,
+ &mock_rtc_event_log_, nullptr, nullptr, nullptr, false));
+ rtp_sender_->SetSSRC(kSsrc);
+
+ const uint8_t kPayloadType = 127;
+ const uint32_t kCaptureTimeMsToRtpTimestamp = 90; // 90 kHz clock
+ char payload_name[RTP_PAYLOAD_NAME_SIZE] = "GENERIC";
+ RTPVideoHeader video_header;
+ EXPECT_EQ(0, rtp_sender_->RegisterPayload(payload_name, kPayloadType,
+ 1000 * kCaptureTimeMsToRtpTimestamp,
+ 0, 1500));
+
+ // Send packet with 10 ms send-side delay. The average and max should be 10
+ // ms.
+ EXPECT_CALL(send_side_delay_observer_, SendSideDelayUpdated(10, 10, kSsrc))
+ .Times(1);
+ int64_t capture_time_ms = fake_clock_.TimeInMilliseconds();
+ fake_clock_.AdvanceTimeMilliseconds(10);
+ EXPECT_TRUE(rtp_sender_->SendOutgoingData(
+ kVideoFrameKey, kPayloadType,
+ capture_time_ms * kCaptureTimeMsToRtpTimestamp, capture_time_ms,
+ kPayloadData, sizeof(kPayloadData), nullptr, &video_header, nullptr,
+ kDefaultExpectedRetransmissionTimeMs));
+
+ // Send another packet with 20 ms delay. The average
+ // and max should be 15 and 20 ms respectively.
+ EXPECT_CALL(send_side_delay_observer_, SendSideDelayUpdated(15, 20, kSsrc))
+ .Times(1);
+ fake_clock_.AdvanceTimeMilliseconds(10);
+ EXPECT_TRUE(rtp_sender_->SendOutgoingData(
+ kVideoFrameKey, kPayloadType,
+ capture_time_ms * kCaptureTimeMsToRtpTimestamp, capture_time_ms,
+ kPayloadData, sizeof(kPayloadData), nullptr, &video_header, nullptr,
+ kDefaultExpectedRetransmissionTimeMs));
+
+ // Send another packet at the same time, which replaces the last packet.
+ // Since this packet has 0 ms delay, the average is now 5 ms and max is 10 ms.
+ // TODO(terelius): Is is not clear that this is the right behavior.
+ EXPECT_CALL(send_side_delay_observer_, SendSideDelayUpdated(5, 10, kSsrc))
+ .Times(1);
+ capture_time_ms = fake_clock_.TimeInMilliseconds();
+ EXPECT_TRUE(rtp_sender_->SendOutgoingData(
+ kVideoFrameKey, kPayloadType,
+ capture_time_ms * kCaptureTimeMsToRtpTimestamp, capture_time_ms,
+ kPayloadData, sizeof(kPayloadData), nullptr, &video_header, nullptr,
+ kDefaultExpectedRetransmissionTimeMs));
+
+ // Send a packet 1 second later. The earlier packets should have timed
+ // out, so both max and average should be the delay of this packet.
+ fake_clock_.AdvanceTimeMilliseconds(1000);
+ capture_time_ms = fake_clock_.TimeInMilliseconds();
+ fake_clock_.AdvanceTimeMilliseconds(1);
+ EXPECT_CALL(send_side_delay_observer_, SendSideDelayUpdated(1, 1, kSsrc))
+ .Times(1);
+ EXPECT_TRUE(rtp_sender_->SendOutgoingData(
+ kVideoFrameKey, kPayloadType,
+ capture_time_ms * kCaptureTimeMsToRtpTimestamp, capture_time_ms,
+ kPayloadData, sizeof(kPayloadData), nullptr, &video_header, nullptr,
+ kDefaultExpectedRetransmissionTimeMs));
+}
+
TEST_P(RtpSenderTestWithoutPacer, OnSendPacketUpdated) {
EXPECT_EQ(0, rtp_sender_->RegisterRtpHeaderExtension(
kRtpExtensionTransportSequenceNumber,
