[FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups

[Tom Boshoven <tom@jwplayer.com>]

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@jwplayer.com>
---
 libavformat/matroskadec.c | 64 +++++++++++++++++++++++----------------
 1 file changed, 38 insertions(+), 26 deletions(-)

diff --git a/libavformat/matroskadec.c b/libavformat/matroskadec.c
index d582f566a2..c81694c55b 100644
--- a/libavformat/matroskadec.c
+++ b/libavformat/matroskadec.c
@@ -4008,35 +4008,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
@@ -4110,7 +4120,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;
@@ -4138,7 +4149,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) {
@@ -4167,7 +4178,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;
@@ -4196,7 +4207,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;
@@ -4207,7 +4219,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.
@@ -4265,7 +4277,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.39.1

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".