commit ae1f8f59ac199e314cfb72ffdf40542ce2cfccb8
author Victor Boivie <boivie@webrtc.org> Tue May 04 13:52:32 2021
committer WebRTC LUCI CQ <webrtc-scoped@luci-project-accounts.iam.gserviceaccount.com> Tue May 11 10:19:06 2021
tree 45f6fa2961c74ad4b341f690939333ba51c7446f
parent 56e482541376a9fe7429826ca55bbd57f8b41c58

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}