* [FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups
@ 2023-02-15 22:01 Tom Boshoven
0 siblings, 0 replies; 4+ messages in thread
From: Tom Boshoven @ 2023-02-15 22:01 UTC (permalink / raw)
To: ffmpeg-devel; +Cc: Tom Boshoven
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".
^ permalink raw reply [flat|nested] 4+ messages in thread* [FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups
@ 2023-03-30 20:07 Tom Boshoven
2023-08-01 20:44 ` Tom Boshoven
2023-11-29 19:35 ` Tom Boshoven via ffmpeg-devel
0 siblings, 2 replies; 4+ messages in thread
From: Tom Boshoven @ 2023-03-30 20:07 UTC (permalink / raw)
To: ffmpeg-devel; +Cc: Tom Boshoven
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 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
_______________________________________________
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".
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups
2023-03-30 20:07 Tom Boshoven
@ 2023-08-01 20:44 ` Tom Boshoven
2023-11-29 19:35 ` Tom Boshoven via ffmpeg-devel
1 sibling, 0 replies; 4+ messages in thread
From: Tom Boshoven @ 2023-08-01 20:44 UTC (permalink / raw)
To: ffmpeg-devel
On Thu, Mar 30, 2023 at 4:07 PM Tom Boshoven <tom@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 <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 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 performance optimization?
I'd be happy to bring it up to date and make changes if needed.
_______________________________________________
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".
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups
2023-03-30 20:07 Tom Boshoven
2023-08-01 20:44 ` Tom Boshoven
@ 2023-11-29 19:35 ` Tom Boshoven via ffmpeg-devel
1 sibling, 0 replies; 4+ messages in thread
From: Tom Boshoven via ffmpeg-devel @ 2023-11-29 19:35 UTC (permalink / raw)
To: ffmpeg-devel; +Cc: Tom Boshoven
On Thu, Mar 30, 2023 at 4:07 PM Tom Boshoven <tom@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 <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 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-request@ffmpeg.org with subject "unsubscribe".
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2023-11-29 19:36 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-02-15 22:01 [FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups Tom Boshoven
2023-03-30 20:07 Tom Boshoven
2023-08-01 20:44 ` Tom Boshoven
2023-11-29 19:35 ` Tom Boshoven via ffmpeg-devel
Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
This inbox may be cloned and mirrored by anyone:
git clone --mirror https://master.gitmailbox.com/ffmpegdev/0 ffmpegdev/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 ffmpegdev ffmpegdev/ https://master.gitmailbox.com/ffmpegdev \
ffmpegdev@gitmailbox.com
public-inbox-index ffmpegdev
Example config snippet for mirrors.
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git