[FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups
Tom Boshoven
tom at jwplayer.com
Thu Mar 30 23:07:14 EEST 2023
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 <tom at 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
More information about the ffmpeg-devel
mailing list