From patchwork Wed Feb 15 22:01:26 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Boshoven X-Patchwork-Id: 40396 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:5494:b0:bf:7b3a:fd32 with SMTP id i20csp2343pzk; Wed, 15 Feb 2023 14:02:40 -0800 (PST) X-Google-Smtp-Source: AK7set+uIY8Do9T3YVk928ImQ2ELuDG42BTldthU8SZCAn7RyrgeHDJ/IEXxnTfhELmV6KmX+46i X-Received: by 2002:a17:907:98d9:b0:878:5524:e932 with SMTP id kd25-20020a17090798d900b008785524e932mr4628887ejc.5.1676498553428; Wed, 15 Feb 2023 14:02:33 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1676498553; cv=none; d=google.com; s=arc-20160816; b=x0LqRCsBQvYzvW2MOXXbUPfmKfXAIbIPTIEVwfjZKGCmXZKCF3hEvIqUA+Gf6gXFj6 5Pfn5HB77T2EX6y0K5Ewh1i79QTpS9yNVaQ9qWgC/CvNGbuWxGIqyS2SObCNSmj7os6y Hfx4Is7dTbtn6XJt0K0CoZbiKyXo/LrprT3wggLpnn4QjbwkwTHBN5mX9/93fBQo8Cm/ PB/DrhW4Xw0WxDmBCCcY1IHAaRfOwvzWbydtI5Bo2CgTJ752dh2i64I2iKNSLc3XlLm8 7B/NOzWoYo2iJ8/3+xcrcy6I8xorszMHJ/0j+7hc1wQYvxoLuZ6cIaP4CZA4Fbx+sEEZ LCFw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:cc:reply-to :list-subscribe:list-help:list-post:list-archive:list-unsubscribe :list-id:precedence:subject:mime-version:message-id:date:to:from :dkim-signature:delivered-to; bh=HPHRRxpLlR+TTmWIo90u4XtFZ0Q7hGGd3rhaRvSjZgE=; b=IVJb49QVh+ePMbOOlyHWMaVocouq4LMZk9c6qrnzNmruarLxdVoevXv6wfmQPEQPo6 kOTSsP6KgtM31m2WYcItuGHxbojtGZB3TmlvOFwPiLF/b/ZthvRPaW7G5JERCfkVzlTx Z9uflQ6OTOFDAvCP8ehN+HP3mSV7xMioEXiK1f3Eu+H8nutSDgqfbkr+SQhTpqzS9xG2 9h8N4KdGdaBk3LXyp7CSq6jvkaNzQ348jNizgTqXl0jt7apfZNtG184bF5QTkBO23wxO bDWAtWsKBdObHWtUu/7GOtSMjLRtRpPAwLuzqxvxbdhX64vX7v/lFYurgf5AV7uuSk/R BjDA== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@jwplayer.com header.s=google header.b=TfNEP0fd; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=QUARANTINE sp=NONE dis=NONE) header.from=jwplayer.com Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id p10-20020a170907910a00b008b14c79a92fsi1284491ejq.288.2023.02.15.14.02.03; Wed, 15 Feb 2023 14:02:33 -0800 (PST) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@jwplayer.com header.s=google header.b=TfNEP0fd; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=QUARANTINE sp=NONE dis=NONE) header.from=jwplayer.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id AF7FA68BE3B; Thu, 16 Feb 2023 00:01:49 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-qv1-f43.google.com (mail-qv1-f43.google.com [209.85.219.43]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id EAB1F68B838 for ; Thu, 16 Feb 2023 00:01:42 +0200 (EET) Received: by mail-qv1-f43.google.com with SMTP id q10so51964qvt.10 for ; Wed, 15 Feb 2023 14:01:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=jwplayer.com; s=google; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=yHgPL16uRh2aTadFXIdGsiljyiZVnnTkqZQgOzvMJ4c=; b=TfNEP0fdc+hNQvHmda8msyHo+MfnETwUIu8YnQN2OOc3DkHWWiETSYRtbLvU0rMSB0 odwBBDVDK7lqcO0Lk/9IHHhJ+3tBbbi7V5WUup6H6YvTyeo284mhUfII7QvMYv2tfmVK qWXsR/vFWuHmz1eZJINTYuqxDpriQIkAJin18= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=yHgPL16uRh2aTadFXIdGsiljyiZVnnTkqZQgOzvMJ4c=; b=UMlu5vet/Y6SJoaQnXagbCav5Soj9QXCKGg95H+zkoKz59lu89luZyTfYFN9bUGkmD QcDGQW+uSi77xZg8H7PY0CuFBEp1YguA3v+Qv4mjoQTO/yjcvKfvyp65kAK6tbAJfIUi AWRj8lt5wuE3jBQDC2tL04ejtI04BOh3NN8hX/AQoT07yd3rk6sBXs3XUAKCbRgEmKY2 RUJSXtwkJQZUJCJ6JF24UZz7yzp8coql+ceW0Ac7NiPEm0lZkIoxjZ27tdHtMsYIeYSE rn+lKfmYjYMnsOILAlq5zD5RwHsUUNopfCZJQERnIemGcv1EKocKyCPS2EcrpOFM0qGQ XE+A== X-Gm-Message-State: AO0yUKUTgHhwzqctS6WHyBHFijODjldQfvusoGRYkn2LbhNPWC0URjVe VPszIPAxD1IcvK9eGmG7CUUkjd9U2PeXS+tD X-Received: by 2002:a05:6214:400b:b0:56e:b33c:d990 with SMTP id kd11-20020a056214400b00b0056eb33cd990mr6399620qvb.24.1676498500968; Wed, 15 Feb 2023 14:01:40 -0800 (PST) Received: from brick.jwplatform.com ([142.154.221.148]) by smtp.gmail.com with ESMTPSA id e16-20020a05620a015000b0073b399700adsm7708788qkn.3.2023.02.15.14.01.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 15 Feb 2023 14:01:40 -0800 (PST) From: Tom Boshoven To: ffmpeg-devel@ffmpeg.org Date: Wed, 15 Feb 2023 17:01:26 -0500 Message-Id: <20230215220126.35923-1-tom@jwplayer.com> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH] avformat/matroskadec: Prevent expensive get_cue_desc lookups X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Cc: Tom Boshoven Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: f1dF5Uv37Rcp 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 --- 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;