From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id EEA2843A1D for ; Tue, 5 Jul 2022 20:29:17 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id A7E3E68BA47; Tue, 5 Jul 2022 23:29:02 +0300 (EEST) 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: =?us-ascii?Q?I+pWYPboQoV0ZKYg4EHOJNo1zmZasrQGrKgLwKgZr9ue85to88QmmpmctRgw?= =?us-ascii?Q?gcNDRJ3uWRlUHfHh75EXqJuW1ywjIAtBY5fDvzn3LYop6P2WmjcHqmehvc88?= =?us-ascii?Q?JJNaA1MRNfEhlIpD1r+cnu018En2Pti+NKB6QxLafm77zM1vfmhGOJ/LEboV?= =?us-ascii?Q?ZVqMV/78Cg2YZPOQElYtbUMbVF03/H0cor+n8Tev5yFxqZ5YdohymYSdBefD?= =?us-ascii?Q?cqwgBrFQjOhZsGzQiB8+oAgVRE7YnNMpjNtfiCM7T0c14P1BWufmdfiFS6rZ?= =?us-ascii?Q?nF2OFqANqEe7pRCICudEfselVs/zUZzI7AlY1f+rm7lH03pKmsqDEZG3XnGx?= =?us-ascii?Q?wORn57A4nxQj3pf5rdqQ7TgvFrqwGILF/IHFLNRMeKrzt+K0K8TMfqBrjW1n?= =?us-ascii?Q?vbHJHXSNqWfkiSc985E/iDHs0OgoFR/CxuwQ4QyN6otww2Ck5gCbF0zl4ndN?= =?us-ascii?Q?Y3ltk2EuVRlbn0+XplKSwc7ImD1pT1cQgZg44YtDSCLVCk3loVrXxAEqrkwq?= =?us-ascii?Q?fTHFw2/f2yF44nafiMoXefyri0cmYu+8drPRROebjFvTnaDC8IjQoaNuX7c9?= =?us-ascii?Q?M+LY0NK+dnadf8inWwdgp+9CKtdW/k3H2+fni2hjTIhfO8h/6h0nNlKPiIs4?= =?us-ascii?Q?JLfgFq6+Fm5oDMKUhS545dwv4RfjLIg+oE+rSOcD8isIUNosaNpCUFQBBAei?= =?us-ascii?Q?mB0FUOOuP6HNmgqpI10UfYNCyFl+jvarPoAFbrcVyu8ztP2dCUCnD199x9Ui?= =?us-ascii?Q?vS2Gyt/zBjOLct1aTraDyymOky7mwgfhv7bp4IXE8EyyDIgQ8tWtS9Xhr02k?= =?us-ascii?Q?k0L8ZrXBOsTvb7jlbkV5q+Tmqny+pPZJ+zjx+UEGyk6XjTAFHqgSxmpEARYD?= =?us-ascii?Q?MLN7Jmnyvg/7lbuo2SCTfPu7n49zH/ze3uvMs+49jObpjFSQBrOfqQ1JtnmL?= =?us-ascii?Q?xyZbXnY4MgVDhsVu6yEzBV+VtH0kLtA18twW9YeqW/wl8FvqtBUhx8LYgV18?= =?us-ascii?Q?igR0OzUEWp9BHNAOEMSBtvK/d1ZBPT7dFQOV/TusYew0kauh8kYD0WiRZVNQ?= =?us-ascii?Q?gerhxRvnFIU+ya7ijCPg8/tSHEAZzmFxh3CypboYRonx90PUvFdyWVGyhoVQ?= =?us-ascii?Q?OUwjBdmWNJpLWcyU+krFU/unnrZKZWtSwH+56OS7IyEK3IN6H/rgYliwiAi0?= =?us-ascii?Q?BE1T9YqmJ8yTzd54v+szY1yEH+ftP0T9qHn9/wOjXuzhbNo/DK1tcIG9BJSs?= =?us-ascii?Q?KOqCAGguj8ilnGBa02Zr/djPcq6pv4bYByBRHhTWNCr3RQBmNbcJgjtwIM9M?= =?us-ascii?Q?nMU=3D?= 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 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: 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); -- 2.34.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".