From patchwork Thu Mar 30 20:07:14 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Boshoven X-Patchwork-Id: 40934 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:4645:b0:e3:3194:9d20 with SMTP id eb5csp192524pzb; Thu, 30 Mar 2023 13:07:33 -0700 (PDT) X-Google-Smtp-Source: AKy350ZHMChvEiG62ibxyUcYZKFOMtCuIjfiWkVOJHlSV1WbGGyt7mM99FHRw2DpiJNzVIbELjH+ X-Received: by 2002:a17:906:da02:b0:8b2:c2fc:178e with SMTP id fi2-20020a170906da0200b008b2c2fc178emr26465041ejb.74.1680206853747; Thu, 30 Mar 2023 13:07:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1680206853; cv=none; d=google.com; s=arc-20160816; b=SMVFwd2mBR5fkU6y8vgzYMYiRdFFD3PHTeQ+8+arQ8zpA9kAE8/1feRaqmxaAiNfVE WoMF6Mhmujus1P4YqhWQvDtLyCpbSH7orR17iaAFisykY9lMAY68A5WXbEUhPQTAvtDp G6/FvuE9RBzaAUupTHp0mtz4QWRxkkj2H8y/qGCg2ILhlFO7TmoHk+DDki6Qv+1EwMg2 +7aufjw9arw7snMmzbIn61hZ31muDWmhL2sgcjmrgcqiFlj6vbWkFrFwSmJNmEk0Blz+ SlOFCpkgnXDPFfEogQp3KTigelmC96O841VXdsermKz4QzK+GseNt1ElEDMH8PH5wsT5 lO5A== 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=EsDwmgnT3WTzRanXz8bIAhk0HcXAaAMmimfvxqHB/MU=; b=Tai61b8r/rXj6PA31aSQejC3ZcaVq3uzpRU/PdH/Ildy+h7EqIRVDmiZ5pFqbe5UNp Qdff377SDj8ArXjUPiwoMF+yEI4hiqdizYzSx6bp43BryTvL1Dgqo6LQf6iSRQQpSdS7 e5MBQ+10h58TtymvTWlMSKcSx2JnyGYHSLURY8xsypVZAJgHmbrKEK+l8STKOfloqJ85 VEmZMrrzCgKwCi5t0Z7KIXG0hAZ6rM4cYTmUfBFbL8SYrCf0dpy2LhJJSyNH6jQNl4pB yLdzUVVp6Di3QqhnOdySew4C4rSbdLgMzjqwL2mSJISBdeA0sFn3xyTULjB7F6HhWjB6 VNCw== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@jwplayer.com header.s=google header.b=af+fnCGb; 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 y14-20020a17090629ce00b00920f334f50csi401745eje.78.2023.03.30.13.07.31; Thu, 30 Mar 2023 13:07:33 -0700 (PDT) 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=af+fnCGb; 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 366C268C3A5; Thu, 30 Mar 2023 23:07:28 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-qv1-f44.google.com (mail-qv1-f44.google.com [209.85.219.44]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 391E168C206 for ; Thu, 30 Mar 2023 23:07:22 +0300 (EEST) Received: by mail-qv1-f44.google.com with SMTP id q88so14905167qvq.13 for ; Thu, 30 Mar 2023 13:07:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=jwplayer.com; s=google; t=1680206840; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=0Ri+zkvWqSIfRi08juAyJX6oq6HWTdxST1yEKlJaFps=; b=af+fnCGbt9AX32+WLr+G57wRhV45+BcTdRAvFO/ySAkEP62HaxTo/FFmN5Mtviv8IJ eq3m+FVpC6Xn7eUkLBipyzeafW6LIJn6i3yckcGbRTSSasru8S/KN2ns9zvqDECPBoq/ DGTZgO2NM0YVgmE8ePNL276eVyWb4lQUp7fbs= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1680206840; 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=0Ri+zkvWqSIfRi08juAyJX6oq6HWTdxST1yEKlJaFps=; b=5W4lNkwI9W+NjavlW7wWI5ZjxK3tqmJZNN1PhteiE3pMf5LTUpoGNPUreGtkgX9RkL 7SDnFMp6aK3n7I1S+zN2JzHfuz0I7PWDn2vvLtviWw6+ANK6Cq5AaqW88Oil7IpJzHRo szEpadZWxW7BcrqBWKsxCsj+mOtJ3GrUZI2h5V+3Rp78mX8NVpb5pU4UjD5bz5uW3wx+ QhMCB8dps3LRzPLuLwa7cB8q6RksOAvoQ9zf3jyZn0qApFpq6I6WvUuy0rcDMh2FZk5z DDHfPieZavL3coIaey6wXt4858GlNQ1KpIz6/4k4gILxN4XjBdUhX/7sV3yYrXO6+VoK EVAw== X-Gm-Message-State: AAQBX9cOO0ctEbuy9Etj8x/oAOZLfUwLJAUjqcM7Uvr/h/BtL5Qz/Ho6 wKgc1zpw8kQpWPnK7PtpJI8+vIMMA4jk5tvyNOE= X-Received: by 2002:a05:6214:2a88:b0:5d9:a36d:3ed2 with SMTP id jr8-20020a0562142a8800b005d9a36d3ed2mr40969870qvb.45.1680206840089; Thu, 30 Mar 2023 13:07:20 -0700 (PDT) Received: from brick.jwplatform.com (cpe-24-193-25-53.nyc.res.rr.com. [24.193.25.53]) by smtp.gmail.com with ESMTPSA id v12-20020ad4528c000000b005dd8b9345e0sm69068qvr.120.2023.03.30.13.07.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 30 Mar 2023 13:07:19 -0700 (PDT) From: Tom Boshoven To: ffmpeg-devel@ffmpeg.org Date: Thu, 30 Mar 2023 16:07:14 -0400 Message-Id: <20230330200714.36221-1-tom@jwplayer.com> X-Mailer: git-send-email 2.40.0 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: DTKEYMqXLBzx 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 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;