From 49b2c3c4c43359bc86d8510d29d117f3d7a621a3 Mon Sep 17 00:00:00 2001 From: Per Kjellander Date: Tue, 11 Sep 2018 05:34:57 +0000 Subject: Revert "Decrease complexity of RtpPacketHistory::GetBestFittingPacket." MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This reverts commit 54caa4b68a0acb81c7f6ef60ffec45b473a7e1a2. Reason for revert: Crashes on some perf tests. https://logs.chromium.org/v/?s=chromium%2Fbb%2Fclient.webrtc.perf%2FLinux_Trusty%2F7170%2F%2B%2Frecipes%2Fsteps%2Fwebrtc_perf_tests%2F0%2Fstdout Original change's description: > Decrease complexity of RtpPacketHistory::GetBestFittingPacket. > Use a map of packet sizes in RtpPacketHistory instead of looping through the whole history for every call. > > Bug: webrtc:9731 > Change-Id: I44a4f6221e261a6cb3d5039edfa7556a102ee6f1 > Reviewed-on: https://webrtc-review.googlesource.com/98882 > Reviewed-by: Erik Språng > Reviewed-by: Danil Chapovalov > Commit-Queue: Per Kjellander > Cr-Commit-Position: refs/heads/master@{#24662} TBR=danilchap@webrtc.org,sprang@webrtc.org,perkj@webrtc.org Change-Id: Id183cd31a67117e9614d163e4388131fd88de07d No-Presubmit: true No-Tree-Checks: true No-Try: true Bug: webrtc:9731 Reviewed-on: https://webrtc-review.googlesource.com/99440 Reviewed-by: Per Kjellander Commit-Queue: Per Kjellander Cr-Commit-Position: refs/heads/master@{#24665} --- modules/rtp_rtcp/source/rtp_packet_history.cc | 43 +++++------- modules/rtp_rtcp/source/rtp_packet_history.h | 1 - .../rtp_rtcp/source/rtp_packet_history_unittest.cc | 77 ---------------------- 3 files changed, 15 insertions(+), 106 deletions(-) (limited to 'modules') diff --git a/modules/rtp_rtcp/source/rtp_packet_history.cc b/modules/rtp_rtcp/source/rtp_packet_history.cc index c1bbbaf452..62f1c824dc 100644 --- a/modules/rtp_rtcp/source/rtp_packet_history.cc +++ b/modules/rtp_rtcp/source/rtp_packet_history.cc @@ -27,7 +27,8 @@ constexpr size_t kMinPacketRequestBytes = 50; // Utility function to get the absolute difference in size between the provided // target size and the size of packet. -size_t SizeDiff(size_t packet_size, size_t size) { +size_t SizeDiff(const std::unique_ptr& packet, size_t size) { + size_t packet_size = packet->size(); if (packet_size > size) { return packet_size - size; } @@ -109,8 +110,6 @@ void RtpPacketHistory::PutRtpPacket(std::unique_ptr packet, if (!start_seqno_) { start_seqno_ = rtp_seq_no; } - // Store the sequence number of the last send packet with this size. - packet_size_[stored_packet.packet->size()] = rtp_seq_no; } std::unique_ptr RtpPacketHistory::GetPacketAndSetSendTime( @@ -187,34 +186,28 @@ std::unique_ptr RtpPacketHistory::GetBestFittingPacket( size_t packet_length) const { // TODO(sprang): Make this smarter, taking retransmit count etc into account. rtc::CritScope cs(&lock_); - if (packet_length < kMinPacketRequestBytes || packet_size_.empty()) { + if (packet_length < kMinPacketRequestBytes || packet_history_.empty()) { return nullptr; } - auto size_iter_upper = packet_size_.upper_bound(packet_length); - auto size_iter_lower = size_iter_upper; - if (size_iter_upper == packet_size_.end()) { - --size_iter_upper; - } - if (size_iter_lower != packet_size_.begin()) { - --size_iter_lower; + size_t min_diff = std::numeric_limits::max(); + RtpPacketToSend* best_packet = nullptr; + for (auto& it : packet_history_) { + size_t diff = SizeDiff(it.second.packet, packet_length); + if (!min_diff || diff < min_diff) { + min_diff = diff; + best_packet = it.second.packet.get(); + if (diff == 0) { + break; + } + } } - const size_t upper_bound_diff = - SizeDiff(size_iter_upper->first, packet_length); - const size_t lower_bound_diff = - SizeDiff(size_iter_lower->first, packet_length); - - const uint16_t seq_no = upper_bound_diff < lower_bound_diff - ? size_iter_upper->second - : size_iter_lower->second; - RtpPacketToSend* best_packet = - packet_history_.find(seq_no)->second.packet.get(); + return absl::make_unique(*best_packet); } void RtpPacketHistory::Reset() { packet_history_.clear(); - packet_size_.clear(); start_seqno_.reset(); } @@ -279,12 +272,6 @@ std::unique_ptr RtpPacketHistory::RemovePacket( start_seqno_.reset(); } - auto size_iterator = packet_size_.find(rtp_packet->size()); - RTC_CHECK(size_iterator != packet_size_.end()); - if (size_iterator->second == rtp_packet->SequenceNumber()) { - packet_size_.erase(size_iterator); - } - return rtp_packet; } diff --git a/modules/rtp_rtcp/source/rtp_packet_history.h b/modules/rtp_rtcp/source/rtp_packet_history.h index 1646ba7c76..433da0e7ee 100644 --- a/modules/rtp_rtcp/source/rtp_packet_history.h +++ b/modules/rtp_rtcp/source/rtp_packet_history.h @@ -136,7 +136,6 @@ class RtpPacketHistory { // Map from rtp sequence numbers to stored packet. std::map packet_history_ RTC_GUARDED_BY(lock_); - std::map packet_size_ RTC_GUARDED_BY(lock_); // The earliest packet in the history. This might not be the lowest sequence // number, in case there is a wraparound. diff --git a/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc b/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc index 6df21e85b4..ab5aeb0be6 100644 --- a/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc +++ b/modules/rtp_rtcp/source/rtp_packet_history_unittest.cc @@ -16,7 +16,6 @@ #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h" #include "modules/rtp_rtcp/source/rtp_packet_to_send.h" #include "system_wrappers/include/clock.h" -#include "test/gmock.h" #include "test/gtest.h" namespace webrtc { @@ -489,80 +488,4 @@ TEST_F(RtpPacketHistoryTest, GetBestFittingPacket) { EXPECT_EQ(target_packet_size, hist_.GetBestFittingPacket(target_packet_size)->size()); } - -TEST_F(RtpPacketHistoryTest, - GetBestFittingPacketReturnsNextPacketWhenBestPacketHasBeenCulled) { - hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10); - std::unique_ptr packet = CreateRtpPacket(kStartSeqNum); - packet->SetPayloadSize(50); - const size_t target_packet_size = packet->size(); - hist_.PutRtpPacket(std::move(packet), kAllowRetransmission, - fake_clock_.TimeInMilliseconds()); - - packet = hist_.GetBestFittingPacket(target_packet_size + 2); - ASSERT_THAT(packet.get(), ::testing::NotNull()); - - // Send the packet and advance time past where packet expires. - ASSERT_THAT(hist_.GetPacketAndSetSendTime(kStartSeqNum, false), - ::testing::NotNull()); - fake_clock_.AdvanceTimeMilliseconds( - RtpPacketHistory::kPacketCullingDelayFactor * - RtpPacketHistory::kMinPacketDurationMs); - - packet = CreateRtpPacket(kStartSeqNum + 1); - packet->SetPayloadSize(100); - hist_.PutRtpPacket(std::move(packet), kAllowRetransmission, - fake_clock_.TimeInMilliseconds()); - ASSERT_FALSE(hist_.GetPacketState(kStartSeqNum, false)); - - auto best_packet = hist_.GetBestFittingPacket(target_packet_size + 2); - ASSERT_THAT(best_packet.get(), ::testing::NotNull()); - EXPECT_EQ(best_packet->SequenceNumber(), kStartSeqNum + 1); -} - -TEST_F(RtpPacketHistoryTest, GetBestFittingPacketReturnLastPacketWhenSameSize) { - const size_t kTargetSize = 500; - hist_.SetStorePacketsStatus(StorageMode::kStore, 10); - - // Add two packets of same size. - std::unique_ptr packet = CreateRtpPacket(kStartSeqNum); - packet->SetPayloadSize(kTargetSize); - hist_.PutRtpPacket(std::move(packet), kAllowRetransmission, - fake_clock_.TimeInMilliseconds()); - packet = CreateRtpPacket(kStartSeqNum + 1); - packet->SetPayloadSize(kTargetSize); - hist_.PutRtpPacket(std::move(packet), kAllowRetransmission, - fake_clock_.TimeInMilliseconds()); - - auto best_packet = hist_.GetBestFittingPacket(123); - ASSERT_THAT(best_packet.get(), ::testing::NotNull()); - EXPECT_EQ(best_packet->SequenceNumber(), kStartSeqNum + 1); -} - -TEST_F(RtpPacketHistoryTest, - GetBestFittingPacketReturnsPacketWithSmallestDiff) { - const size_t kTargetSize = 500; - hist_.SetStorePacketsStatus(StorageMode::kStore, 10); - - // Add two packets of very different size. - std::unique_ptr small_packet = CreateRtpPacket(kStartSeqNum); - small_packet->SetPayloadSize(kTargetSize); - hist_.PutRtpPacket(std::move(small_packet), kAllowRetransmission, - fake_clock_.TimeInMilliseconds()); - - auto large_packet = CreateRtpPacket(kStartSeqNum + 1); - large_packet->SetPayloadSize(kTargetSize * 2); - hist_.PutRtpPacket(std::move(large_packet), kAllowRetransmission, - fake_clock_.TimeInMilliseconds()); - - ASSERT_THAT(hist_.GetBestFittingPacket(kTargetSize), ::testing::NotNull()); - EXPECT_EQ(hist_.GetBestFittingPacket(kTargetSize)->SequenceNumber(), - kStartSeqNum); - - ASSERT_THAT(hist_.GetBestFittingPacket(kTargetSize * 2), - ::testing::NotNull()); - EXPECT_EQ(hist_.GetBestFittingPacket(kTargetSize * 2)->SequenceNumber(), - kStartSeqNum + 1); -} - } // namespace webrtc -- cgit v1.2.3