On Thu, Mar 30, 2023 at 4:07 PM Tom Boshoven <t...@jwplayer.com> wrote:
>
> Due to the way the bandwidth estimation code works, the get_cue_desc
> function was called many times over.
> This function did a from-scratch lookup using a timestamp.
> This lookup was done using linear iteration (O(n)), resulting in
> significant overhead when many cues exist.
>
> This change uses ff_index_search_timestamp (binary search, O(log n))
> for the lookup.
> Additionally, the lookup is prevented entirely in most cases by
> maintaining the indexes of the cues (O(1)).
>
> Signed-off-by: Tom Boshoven <t...@jwplayer.com>
> ---
> libavformat/matroskadec.c | 64 +++++++++++++++++++++++----------------
> 1 file changed, 38 insertions(+), 26 deletions(-)
>
> diff --git a/libavformat/matroskadec.c b/libavformat/matroskadec.c
> index 3a888e3ada..d974944945 100644
> --- a/libavformat/matroskadec.c
> +++ b/libavformat/matroskadec.c
> @@ -4038,35 +4038,45 @@ typedef struct {
> int64_t end_offset;
> } CueDesc;
>
> -/* This function searches all the Cues and returns the CueDesc corresponding
> to
> - * the timestamp ts. Returned CueDesc will be such that start_time_ns <= ts <
> - * end_time_ns. All 4 fields will be set to -1 if ts >= file's duration or
> - * if an error occurred.
> +/**
> + * Find the index of the cue corresponding to the timestamp ts.
> */
> -static CueDesc get_cue_desc(AVFormatContext *s, int64_t ts, int64_t
> cues_start) {
> +static int get_cue_index(AVFormatContext *s, int64_t ts) {
> + MatroskaDemuxContext *matroska = s->priv_data;
> + FFStream *const sti = ffstream(s->streams[0]);
> +
> + if (ts >= (int64_t)(matroska->duration * matroska->time_scale))
> + return -1;
> +
> + // Look up the index entry corresponding to the timestamp (dividing by
> timescale)
> + return ff_index_search_timestamp(
> + sti->index_entries,
> + sti->nb_index_entries,
> + ts / matroska->time_scale,
> + AVSEEK_FLAG_ANY | AVSEEK_FLAG_BACKWARD
> + );
> +}
> +
> +/**
> + * Get the CueDesc for a specific index.
> + * For a given timestamp, the index can be obtained using get_cue_index.
> + */
> +static CueDesc get_cue_desc_from_index(AVFormatContext *s, int idx, int64_t
> cues_start) {
> MatroskaDemuxContext *matroska = s->priv_data;
> FFStream *const sti = ffstream(s->streams[0]);
> AVIndexEntry *const index_entries = sti->index_entries;
> int nb_index_entries = sti->nb_index_entries;
> CueDesc cue_desc;
> - int i;
>
> - if (ts >= (int64_t)(matroska->duration * matroska->time_scale))
> + if (idx < 0 || idx >= nb_index_entries) {
> return (CueDesc) {-1, -1, -1, -1};
> - for (i = 1; i < nb_index_entries; i++) {
> - if (index_entries[i - 1].timestamp * matroska->time_scale <= ts &&
> - index_entries[i].timestamp * matroska->time_scale > ts) {
> - break;
> - }
> }
> - --i;
> - if (index_entries[i].timestamp > matroska->duration)
> - return (CueDesc) {-1, -1, -1, -1};
> - cue_desc.start_time_ns = index_entries[i].timestamp *
> matroska->time_scale;
> - cue_desc.start_offset = index_entries[i].pos - matroska->segment_start;
> - if (i != nb_index_entries - 1) {
> - cue_desc.end_time_ns = index_entries[i + 1].timestamp *
> matroska->time_scale;
> - cue_desc.end_offset = index_entries[i + 1].pos -
> matroska->segment_start;
> +
> + cue_desc.start_time_ns = index_entries[idx].timestamp *
> matroska->time_scale;
> + cue_desc.start_offset = index_entries[idx].pos - matroska->segment_start;
> + if (idx != nb_index_entries - 1) {
> + cue_desc.end_time_ns = index_entries[idx + 1].timestamp *
> matroska->time_scale;
> + cue_desc.end_offset = index_entries[idx + 1].pos -
> matroska->segment_start;
> } else {
> cue_desc.end_time_ns = matroska->duration * matroska->time_scale;
> // FIXME: this needs special handling for files where Cues appear
> @@ -4140,7 +4150,8 @@ static int buffer_size_after_time_downloaded(int64_t
> time_ns, double search_sec,
> int64_t time_to_search_ns = (int64_t)(search_sec *
> nano_seconds_per_second);
> int64_t end_time_ns = time_ns + time_to_search_ns;
> double sec_downloaded = 0.0;
> - CueDesc desc_curr = get_cue_desc(s, time_ns, cues_start);
> + int cue_idx = get_cue_index(s, time_ns);
> + CueDesc desc_curr = get_cue_desc_from_index(s, cue_idx, cues_start);
> if (desc_curr.start_time_ns == -1)
> return -1;
> *sec_to_download = 0.0;
> @@ -4168,7 +4179,7 @@ static int buffer_size_after_time_downloaded(int64_t
> time_ns, double search_sec,
> }
>
> // Get the next Cue.
> - desc_curr = get_cue_desc(s, desc_curr.end_time_ns, cues_start);
> + desc_curr = get_cue_desc_from_index(s, ++cue_idx, cues_start);
> }
>
> while (desc_curr.start_time_ns != -1) {
> @@ -4197,7 +4208,7 @@ static int buffer_size_after_time_downloaded(int64_t
> time_ns, double search_sec,
> break;
> }
>
> - desc_curr = get_cue_desc(s, desc_curr.end_time_ns, cues_start);
> + desc_curr = get_cue_desc_from_index(s, ++cue_idx, cues_start);
> }
> *buffer = *buffer + sec_downloaded;
> return rv;
> @@ -4226,7 +4237,8 @@ static int64_t
> webm_dash_manifest_compute_bandwidth(AVFormatContext *s, int64_t
> int64_t temp_prebuffer_ns = prebuffer_ns;
> int64_t pre_bytes, pre_ns;
> double pre_sec, prebuffer, bits_per_second;
> - CueDesc desc_beg = get_cue_desc(s, time_ns, cues_start);
> + int cue_idx = get_cue_index(s, time_ns);
> + CueDesc desc_beg = get_cue_desc_from_index(s, cue_idx, cues_start);
>
> // Start with the first Cue.
> CueDesc desc_end = desc_beg;
> @@ -4237,7 +4249,7 @@ static int64_t
> webm_dash_manifest_compute_bandwidth(AVFormatContext *s, int64_t
> // Prebuffered the entire Cue.
> prebuffer_bytes += desc_end.end_offset - desc_end.start_offset;
> temp_prebuffer_ns -= desc_end.end_time_ns -
> desc_end.start_time_ns;
> - desc_end = get_cue_desc(s, desc_end.end_time_ns, cues_start);
> + desc_end = get_cue_desc_from_index(s, ++cue_idx, cues_start);
> }
> if (desc_end.start_time_ns == -1) {
> // The prebuffer is larger than the duration.
> @@ -4295,7 +4307,7 @@ static int64_t
> webm_dash_manifest_compute_bandwidth(AVFormatContext *s, int64_t
> }
> }
>
> - desc_end = get_cue_desc(s, desc_end.end_time_ns, cues_start);
> + desc_end = get_cue_desc_from_index(s, ++cue_idx, cues_start);
> } while (desc_end.start_time_ns != -1);
> }
> if (bandwidth < bits_per_second) bandwidth = bits_per_second;
> --
> 2.40.0
>
Is there any interest in this matroskadec performance patch I proposed
earlier this year?
Happy to bring it up to date.
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-requ...@ffmpeg.org with subject "unsubscribe".
