From patchwork Tue Jul 5 20:26:50 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Rheinhardt X-Patchwork-Id: 36686 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:8b27:b0:88:1bbf:7fd2 with SMTP id l39csp3728602pzh; Tue, 5 Jul 2022 13:29:19 -0700 (PDT) X-Google-Smtp-Source: AGRyM1vhPNOINYsYcv+ByIKlW6QIMwVFcpTrJSq5ceLwqVrWbOY6Fdrga+EGToBBdk2jvyXSWkVw X-Received: by 2002:a05:6402:11d1:b0:435:d76d:f985 with SMTP id j17-20020a05640211d100b00435d76df985mr48480135edw.8.1657052959361; Tue, 05 Jul 2022 13:29:19 -0700 (PDT) Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id x4-20020a05640226c400b0043769e9d1bdsi6222239edd.467.2022.07.05.13.29.19; Tue, 05 Jul 2022 13:29:19 -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=@outlook.com header.s=selector1 header.b=Cl7EH8Mc; arc=fail (body hash mismatch); 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=NONE sp=QUARANTINE dis=NONE) header.from=outlook.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id D06E868B9C6; Tue, 5 Jul 2022 23:29:02 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from EUR05-DB8-obe.outbound.protection.outlook.com (mail-db8eur05olkn2087.outbound.protection.outlook.com [40.92.89.87]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id E649D68BA40 for ; Tue, 5 Jul 2022 23:28:55 +0300 (EEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=bWE2zTJcYJXJJ9ICYy3MxhJoROU/fR8SEWsCt+duy2ITvso4XgTe5bIqnnLlCJqafqj/W+pswu8kv3wSTk0PgCGJU2/DbPmcxVbBVcvtFRa/3hUTEtrEUb/6OgKl1Bi3tBRUhCLtfm9RNNAtzlf2k6fAdvJ3FOIO7e0h+DeuYGEvmzu+GoxMLR91NgRcQlIYANNApFtuM891FMlv9mt0BiwkMpG+QLKFoPd7f4javTSdKaH++AdM0EDcVpCnYXQ2LBYq1bgMZDZu4mheLmZsjrZbtU56/kLBDju5tsFI+DAsM1sXEuNjXxy4WlxJPwAVmjCJcOf/S5DCkCR6qmJiMw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=byy9pDnJ/0EYCIr9xEsJC8FrASzrrf2/UQztBxGj/Zg=; b=byE2zK4mIVzu0nMPeca8Pn8KshtSRKNJhXECvNs8lRpRJNbLobRTjzVVfeWLmqPaepb67ST9LLFWlyjdP/EAHaK3751D/ml43UkFx8D4gQ3NwjlD4TI8d16Maw7IvbkG1G/fh55idz2k1dsX7jDUnklP70RLX/Qs5OnLyaaz9wmEq3Z9pM1bqxDpMfEaxsVWTY4oAGsKa0i6YhPbC8he3bvDU/8gf+fCYb6MghufD+z1c5LZyyCilqLhwrhLh5OOf9WL/zKALQW3fxBWCXBnmryqULzyQbFFxpyMTcm6FLiJe59h0k9HTBL07jWcCIPgESfsksPc4KW4NbPTK7kSww== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=outlook.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=byy9pDnJ/0EYCIr9xEsJC8FrASzrrf2/UQztBxGj/Zg=; b=Cl7EH8Mcd+nXYBzTUcHY3HKsLQixLRjISwbGBCIDscljx/lomSYes+OSCJvf+MIXGP4Q41+3yFgo8gK6OG1Fp1uksRHaqhEGn2dtlgeuW+b0YH4zzSp2tybLsjmpjsnzLwIf/LuC7tvKd4zJW/4u10GbyCpCtsIdoIffC+SMgKak1b1RB6M4YMU1XWZ9I08AitR4MzKc62/cTdbzcibe33iO/esxdkdh1D8KdDw0TsWSY/9VjNzeQ7ssBw2OYTk/vz915XhY1VrRLJgtfJx4lkJBo+HAQlih90ap10nbAQp+7kZJN7caokswX8PkKVR1b04iMlwXGzyQ5Gbm/Btj9g== Received: from DB6PR0101MB2214.eurprd01.prod.exchangelabs.com (2603:10a6:4:42::27) by PA4PR01MB9452.eurprd01.prod.exchangelabs.com (2603:10a6:102:2af::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5395.21; Tue, 5 Jul 2022 20:28:46 +0000 Received: from DB6PR0101MB2214.eurprd01.prod.exchangelabs.com ([fe80::60b9:9f29:40cc:f01c]) by DB6PR0101MB2214.eurprd01.prod.exchangelabs.com ([fe80::60b9:9f29:40cc:f01c%10]) with mapi id 15.20.5395.021; Tue, 5 Jul 2022 20:28:46 +0000 From: Andreas Rheinhardt To: ffmpeg-devel@ffmpeg.org Date: Tue, 5 Jul 2022 22:26:50 +0200 Message-ID: X-Mailer: git-send-email 2.34.1 In-Reply-To: References: X-TMN: [7lfIArPzoyXp/mH0iZW+zXrviZwexQKC] X-ClientProxiedBy: AS9PR06CA0419.eurprd06.prod.outlook.com (2603:10a6:20b:461::15) To DB6PR0101MB2214.eurprd01.prod.exchangelabs.com (2603:10a6:4:42::27) X-Microsoft-Original-Message-ID: <20220705202650.797218-7-andreas.rheinhardt@outlook.com> MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 5443563f-b2c9-458b-b73d-08da5ec4f5eb X-MS-Exchange-SLBlob-MailProps: gjx25WM8ZNWDLNYE12708/FIJ0L6AOQdoXolL+mCVV546hnZIxjkj+mPipRR3TlCqbon8YmoRUl354w5vYAVG8WWT3WpoDt8Cc5fCfMu4NudmyKQDHgHGQQWUL40nja2jUYNlI9ChziV41qNRfI0qo8shI4RVbVXYeEJD7645bVe3e9dp3KOQB8vp6tOMmSJOsI9r2eH2MEEe5mb6Zv9zbc5Ny1tydy51P3Y9s/ipqa7Xxm1kT5uwpVgD4KXU37k8DtI2wCNENFRKDPlVahgvez9iBqmdHwW7PLPKlCSikp6Dns+c63nyDwMj0hL8cJkM3H/RXAuv6dO56ZyqsRWV/71ks0dR0uv9s7rEIPxVQWdPES9Qt2Y2MoSKvbs4/+Kysnl8osR6YZUgulK9Y4b8AUm3AlnJkBzrhlTuhPm2U3HztcNoU8xLN+3rOHL7q9NZiaQYsPVWU3iRIg8ANiy55d0OD5NVtbUUJsxjhkpUjMAtXui1GM0QPeA26i0gD126T3Efi/2l/tk5u4Yb7nZ+4YXLf00i1oVjG0z1OozgT9U62pNl4XxNaLzOUx7Ab50rtaAm9FT2uHQlH4g28jOR+m5EqOCEBR8GoDJDrx0OJ1VOBbF/dUdV4FtvlitN6hafOY7u6nQFMhqhNRw4lU3qswkLuRSF8hfbbf422rhbkVgY07dUiXkYJwTP+tMgEKD2igzLKzGWt7XBEmMsMiGs0ijpI8ApcApadITd6V6qB4= X-MS-TrafficTypeDiagnostic: PA4PR01MB9452:EE_ X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: YIAENH3NgQpNrHm8Qoxpyis934P4g2C9Dwhz0dcS+WtbvSchS7JpsfZf1LuibSNz1hMzq9gAImd6RuOExJRT8v/poRgtb4NTDzj1dYmsb7gGEm2vGXEjVC1bLwr2zqvZzkCfshzpUiGLQvazuylouFj7Fe0/DcSrG9EKULhAS9RrL4g8+GX/Aqfc9mp2EM8C3WesyknV1bldIsLDMBHmrxZQ+vC3xE1sS6X96ZYp0oqq9vaiTIzzUXCG8X5q6C67BsF40m+1SJEQ/S3R38w+EtRmiz3iEK+UJt2tIXPI+JUYFNNdqvW7shhpivn3A5zhRtq94X1TnNV2b49jeRIXaH6qOBqhnoPVfq7OmfwAVa6Y25dI3L1mj2cjitxdRKyLWh44VCr3CmblESGJugFFSS214Eq/exlxHZonYTGqRFr2YxqhMjlo9ZIuqQ1r55NRyT4/mQQNPPuFyBK4Zkn8J9aCddxqWbeHkoQswiv1ixHkN/F52b9vBFdaEGl8h53+Pk/yYzjIAxcd00Dwjlz5SSYl+zF31adNHSpK87WOHUv/7LEsT6o7PAe1lPc9W+1rt/yba+vN4U08YIhTQQTTWoNkzQ/3bSRLaXvWL60MUeqt9JpPAttJ2y9l57uPFYuKccaNLFIPUe1wsGBhIQvqnA== X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: I+pWYPboQoV0ZKYg4EHOJNo1zmZasrQGrKgLwKgZr9ue85to88QmmpmctRgwgcNDRJ3uWRlUHfHh75EXqJuW1ywjIAtBY5fDvzn3LYop6P2WmjcHqmehvc88JJNaA1MRNfEhlIpD1r+cnu018En2Pti+NKB6QxLafm77zM1vfmhGOJ/LEboVZVqMV/78Cg2YZPOQElYtbUMbVF03/H0cor+n8Tev5yFxqZ5YdohymYSdBefDcqwgBrFQjOhZsGzQiB8+oAgVRE7YnNMpjNtfiCM7T0c14P1BWufmdfiFS6rZnF2OFqANqEe7pRCICudEfselVs/zUZzI7AlY1f+rm7lH03pKmsqDEZG3XnGxwORn57A4nxQj3pf5rdqQ7TgvFrqwGILF/IHFLNRMeKrzt+K0K8TMfqBrjW1nvbHJHXSNqWfkiSc985E/iDHs0OgoFR/CxuwQ4QyN6otww2Ck5gCbF0zl4ndNY3ltk2EuVRlbn0+XplKSwc7ImD1pT1cQgZg44YtDSCLVCk3loVrXxAEqrkwqfTHFw2/f2yF44nafiMoXefyri0cmYu+8drPRROebjFvTnaDC8IjQoaNuX7c9M+LY0NK+dnadf8inWwdgp+9CKtdW/k3H2+fni2hjTIhfO8h/6h0nNlKPiIs4JLfgFq6+Fm5oDMKUhS545dwv4RfjLIg+oE+rSOcD8isIUNosaNpCUFQBBAeimB0FUOOuP6HNmgqpI10UfYNCyFl+jvarPoAFbrcVyu8ztP2dCUCnD199x9UivS2Gyt/zBjOLct1aTraDyymOky7mwgfhv7bp4IXE8EyyDIgQ8tWtS9Xhr02kk0L8ZrXBOsTvb7jlbkV5q+Tmqny+pPZJ+zjx+UEGyk6XjTAFHqgSxmpEARYDMLN7Jmnyvg/7lbuo2SCTfPu7n49zH/ze3uvMs+49jObpjFSQBrOfqQ1JtnmLxyZbXnY4MgVDhsVu6yEzBV+VtH0kLtA18twW9YeqW/wl8FvqtBUhx8LYgV18igR0OzUEWp9BHNAOEMSBtvK/d1ZBPT7dFQOV/TusYew0kauh8kYD0WiRZVNQgerhxRvnFIU+ya7ijCPg8/tSHEAZzmFxh3CypboYRonx90PUvFdyWVGyhoVQOUwjBdmWNJpLWcyU+krFU/unnrZKZWtSwH+56OS7IyEK3IN6H/rgYliwiAi0BE1T9YqmJ8yTzd54v+szY1yEH+ftP0T9qHn9/wOjXuzhbNo/DK1tcIG9BJSsKOqCAGguj8ilnGBa02Zr/djPcq6pv4bYByBRHhTWNCr3RQBmNbcJgjtwIM9MnMU= X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 5443563f-b2c9-458b-b73d-08da5ec4f5eb X-MS-Exchange-CrossTenant-AuthSource: DB6PR0101MB2214.eurprd01.prod.exchangelabs.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 Jul 2022 20:28:46.3261 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: PA4PR01MB9452 Subject: [FFmpeg-devel] [PATCH 8/8] avutil/fifo: Grow FIFO faster when growing automatically 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: Andreas Rheinhardt Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: Ls0+MnCIClQS Up until now, when the FIFO is grown automatically, it would be resized by double the amount needed (if possible, i.e. if compatible with the auto-grow limit). This implies that if e.g. the user always writes a single element to the FIFO, the FIFO will be reallocated once for every two writes (presuming no reads happen inbetween). This is potentially quadratic (depending upon the realloc implementation). This commit changes this by using av_fast_realloc_array to realloc the buffer. Its ability to not overallocate beyond a given size allows to honour the user-specified auto-grow limit. Signed-off-by: Andreas Rheinhardt --- libavutil/fifo.c | 35 +++++++++++++++++++++++------------ 1 file changed, 23 insertions(+), 12 deletions(-) diff --git a/libavutil/fifo.c b/libavutil/fifo.c index 53359a2112..04f4d057ca 100644 --- a/libavutil/fifo.c +++ b/libavutil/fifo.c @@ -96,6 +96,19 @@ size_t av_fifo_can_write(const AVFifo *f) return f->nb_elems - av_fifo_can_read(f); } +static void fifo_readjust_after_growing(AVFifo *f, size_t old_size) +{ + const size_t inc = f->nb_elems - old_size; + // move the data from the end of the ring buffer + // to the end of the newly allocated space + if (f->offset_w <= f->offset_r && !f->is_empty) { + memmove(f->buffer + (f->offset_r + inc) * f->elem_size, + f->buffer + f->offset_r * f->elem_size, + (old_size - f->offset_r) * f->elem_size); + f->offset_r += inc; + } +} + int av_fifo_grow2(AVFifo *f, size_t inc) { uint8_t *tmp; @@ -107,16 +120,8 @@ int av_fifo_grow2(AVFifo *f, size_t inc) if (!tmp) return AVERROR(ENOMEM); f->buffer = tmp; - - // move the data from the end of the ring buffer - // to the end of the newly allocated space - if (f->offset_w <= f->offset_r && !f->is_empty) { - memmove(tmp + (f->offset_r + inc) * f->elem_size, tmp + f->offset_r * f->elem_size, - (f->nb_elems - f->offset_r) * f->elem_size); - f->offset_r += inc; - } - f->nb_elems += inc; + fifo_readjust_after_growing(f, f->nb_elems - inc); return 0; } @@ -133,9 +138,15 @@ static int fifo_check_space(AVFifo *f, size_t to_write) can_grow = f->auto_grow_limit > f->nb_elems ? f->auto_grow_limit - f->nb_elems : 0; if ((f->flags & AV_FIFO_FLAG_AUTO_GROW) && need_grow <= can_grow) { - // allocate a bit more than necessary, if we can - const size_t inc = (need_grow < can_grow / 2 ) ? need_grow * 2 : can_grow; - return av_fifo_grow2(f, inc); + // Use av_fast_realloc_array() to allocate in a fast way + // while respecting the auto_grow_limit + const size_t old_size = f->nb_elems; + int ret = av_fast_realloc_array(&f->buffer, &f->nb_elems, f->nb_elems + need_grow, + f->auto_grow_limit, f->elem_size); + if (ret < 0) + return ret; + fifo_readjust_after_growing(f, old_size); + return 0; } return AVERROR(ENOSPC);