From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <ffmpeg-devel-bounces@ffmpeg.org> Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTPS id 2385B4C64B for <ffmpegdev@gitmailbox.com>; Tue, 8 Apr 2025 16:56:49 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id D2DED68B271; Tue, 8 Apr 2025 19:56:45 +0300 (EEST) Received: from NAM12-DM6-obe.outbound.protection.outlook.com (mail-dm6nam12olkn2062.outbound.protection.outlook.com [40.92.22.62]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 5842368B253 for <ffmpeg-devel@ffmpeg.org>; Tue, 8 Apr 2025 19:56:39 +0300 (EEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=LTeZ2lY8sYWAKot3tAVjZa+PnomaKyXQR/MoIfOddNeHvg781FfkpH34DSA2R2Nz8QhLYaOU/JYnenKx/esWjJlYowT9W3Erj8VJ2X6eR8f6vPxqBvxr7iF9pN/WbZNraqu89/a/d6xRHGFRG/0A3DmgLLZWZQZGXXroj1onRAH/E5sHBnJDPAk/OUgFioblZ5svJdncx6EcAGC+7B5w3+oeQj0tBof4GrBAdZpULoakOoqNQZms5u6ARvrh6z4u2wuPyZsF7LOutOqsskFk/xMukA/R2xummgk2yMBxkECyjH9tTyUkOZSaKvZhaU9M8TRm4HfaHrKYkV5pEJnmHg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; 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=nG2hTUTyaOX1XDnygRPsrmPURhw4P2y+qKXOPgt4YVk=; b=B1c6xnYwo+foGtJxtPVGRV9QuEf3qXN1NdVwpYGf01NcH1v7Q7XU2VyCzWZ+VSVfcxFWokdtSCez5UH9BCeI5G0jI4Ehv9/+2fUzv0a0Qg2tuMqum3RNhVOrqJrJNztpZNPdZ7dgEdU8JSxgwvGNHgtRXEAOg9ysrrkPiTxlsvPxE13tCrxQBgaVMqlz6cA32Ah6Qv39Slj7bTqcXzSRvu/5jK81drnegla7NH8NHPRp6Uqq86KbqGDbJuzqVZ6CeDlVaKR726kehiDPnsSBfXR/OBxiInITUr4zjTy1Lv4/B2DT4zPuM1mIUF/JTOO0z6A73ayHRSE/BbkN3hkVOA== 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=hotmail.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=nG2hTUTyaOX1XDnygRPsrmPURhw4P2y+qKXOPgt4YVk=; b=tqkM6HfB9yKb6P8gHwedSEUXeieumt/P6dggfjasDqDt7XqnOsoiWflKh24x0CQL5nYqBO6V3Dawbw1piPSxkFQYmsj8sN6Kl2+U5MRc7Lnqsj6kLVysjIRsHsR9cRlk1FEqv2N5oQlxI6o72qX6Fx7h+RK7W1D4cQFmNBpmfEc0Ls45/ApWy4GBlhP161OIriH6CAVeFsjpsmY1Ixzawtik3aOR0+sTErhsAJ/MPBMPbnSWNQtD12h010433ZpcxPZIfRtqE8nJs23pflQm+x17IG6bF+18f8fUBOxGJqKshE6PTQILMLjrZApV2jzPyCZpRcXpRn1LqBDYnN8COg== Received: from DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM (2603:10b6:8:b::20) by DM8P223MB0367.NAMP223.PROD.OUTLOOK.COM (2603:10b6:5:316::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8606.34; Tue, 8 Apr 2025 16:56:36 +0000 Received: from DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM ([fe80::bf09:8e9:b07f:98a7]) by DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM ([fe80::bf09:8e9:b07f:98a7%4]) with mapi id 15.20.8606.033; Tue, 8 Apr 2025 16:56:36 +0000 From: "softworkz ." <softworkz-at-hotmail.com@ffmpeg.org> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> Thread-Topic: [FFmpeg-devel] [RFC] AVDictionary2 Thread-Index: AQHbqG/RC945j8SkUUWxeNzx/WS92bOZ+5mA Date: Tue, 8 Apr 2025 16:56:36 +0000 Message-ID: <DM8P223MB03654302FB66A2EEB0039C45BAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> References: <20250408101959.GP4991@pb2> In-Reply-To: <20250408101959.GP4991@pb2> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-publictraffictype: Email x-ms-traffictypediagnostic: DM8P223MB0365:EE_|DM8P223MB0367:EE_ x-ms-office365-filtering-correlation-id: fdb4f2f8-1961-466d-c0ff-08dd76be52f3 x-microsoft-antispam: BCL:0; ARA:14566002|15080799006|8060799006|19110799003|7092599003|461199028|8062599003|56899033|3412199025|440099028|102099032; x-microsoft-antispam-message-info: =?us-ascii?Q?iGZZQ66sT8QNeyKIHav4wUtBD6mvSKr0TdV7/K8nYsvRgC+PB+IaGDsOWXFs?= =?us-ascii?Q?WIc7Xi/XFV87gzaWCdmz1psWM/pqMrxvpzPUiJKiDhKZ2Av6SxYwDdJVRh2k?= =?us-ascii?Q?5mW+V/AtfKRNQEcdmIDoszI7nrPaW9RFo8J+/TxtCS1D3yyXaKgsYNOnlJVF?= =?us-ascii?Q?NSsuMsrTYTzFTSSLVvMOp4ANoMLpTc2tirzY0I9JUYQeuR4YmkpLvtx9Wg+b?= =?us-ascii?Q?37taesvJTTXI8juD8SNiq3htSY5lZJYHgeHYXE/lBA0YMzeMiSIDnshL8bMY?= =?us-ascii?Q?33tzfjabaUlkOvzVTjnm9EF53fvKs+oPYkiemDQajpbZ/Orad94Aa+is0vXt?= =?us-ascii?Q?1Mv5y+0JHUgx8wHZEEcnWj+1bfNnjSiQ/Rkmw/AMBEQY/y2Fzh5zZsVIF/aU?= =?us-ascii?Q?j83Wlk2cUvu3h/R9hg1KtljPYa4dIkBVMusaJjkWmjXMXeCSZ4+YvbKU4Lkh?= =?us-ascii?Q?rqewJ3QH23YOs/81nnKnjNA8Y2drnUnfXJY//vyRpYvGXb5/oPnSZXIUP7LI?= =?us-ascii?Q?8y0aTjYD8G0rqmrgGZ5POssggReIxBV8cB1PfmA5kGPI0KhaHkOEJsMq6LzP?= =?us-ascii?Q?ylHOuFf/qK+OaVxubs9V6+/E9SQsH5Dx3JvE1ekp3MRrp+lWjkQjOnMXiDGy?= =?us-ascii?Q?JfFTW9ghWVlyCYA2lvZohsI+X4C5uM6uVwLyOnN/QcVtRH6Itph8we+SeM89?= =?us-ascii?Q?ATEDhszr6jat01Vm9Ulyo0sKg96uLw7Wk+QxmbS2ae8v2ZNUPsHj0/yl0Q7V?= =?us-ascii?Q?uc6GHDusviwv8HddzIvReKrmETkvnHYwhJK8sZlCSCpEY50nIFnV89k0SeoL?= =?us-ascii?Q?wHwzC28dUp8saWSnJ1LWDwL3zSAx5LGliDm7zHFOcwF0tiuK0KyL1tff0F5p?= =?us-ascii?Q?u7Sf6Zeia6WvhCcThb3GkdKCGd3FIWLdcZ721CNwZD0XFmyH8Zf2XKtyLzvR?= =?us-ascii?Q?pxw/tBWbNWoNxy5xp/0uxyXWC2HOiZ0649Zn+Y9ekZ4BhXLN7oEs0TN5wH+N?= =?us-ascii?Q?7E90M7l/NNuYkHCS0LeLTP6RjxdCAzQasNGTW03cw9gCI3wpn6SzeKiLc9+l?= =?us-ascii?Q?6iEp47DzH0elZk+bj2om/X/w9SHzhDYEUMFCsOF+kbIuj81OQa8=3D?= x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?0BcTITVd0EQFOxVopnoGs/4k2h+jKK+6B40gOVNAkVjRsxs/EVnisDOCQR4g?= =?us-ascii?Q?faUy2G41FEGYyo+Q0xoPadfpKLdr2Br0Yg4/GJa6c46j8TTeDB7DMxTwl/Oi?= =?us-ascii?Q?8NlM436CY3TXSi7HQHEQOmlIafY6YoPC5Oko3RGbM8jcFNXhVA7USsC2n57d?= =?us-ascii?Q?MGArIx+ZfRBOI49mL9tz9CzjxX9wXWw6tUJrpxV5zorTp15FcBMvb0+TrIFE?= =?us-ascii?Q?VzIXKZB3MLzRiB+T8zFneQrefJ04e2hdtAfowqAF3m6t9FrVSIHwgMLGvAcP?= =?us-ascii?Q?rAgVynJk6C0cydqhWK+eMW54ezYVNNMDlzEfDONamHMSYCF3q3DxsQVonsp6?= =?us-ascii?Q?8vK0qCjbMk0ZaFkZz0T8vAD9wJNQGy7Nflz+YJ+JY9vTOUEIH3Ck+BJX9VJg?= =?us-ascii?Q?oE/RIyy7qtYNLIIjT8SB9Mq7oehMckVnNI9eDONovFddZXfa4htiFaN91/kD?= =?us-ascii?Q?Nf/gNGmxE1jqANSUx/SJdqPhTQn0ctFCSVLFxZFaes5dyOnem2JFhwSu7iBU?= =?us-ascii?Q?8MHcCljCrB+eFLu+2+/OxbdAg7oSsg+/2ccAxtfe1cdsvwIHuvwN2+7Ai9gV?= =?us-ascii?Q?+ZEs9TD7v/hoGVG7fjx5RqsI+KywV8Oj2l/ooFNxdtSM/Zte2E4GO7FueZ8u?= =?us-ascii?Q?Mqdac6G+A14DlKwii7yPO6JTjsPvbhQ5nYPz7D/lAANrKgZwkQ5GdYR7aU9W?= =?us-ascii?Q?kA4rIp1vOguk7IE9RtGMAYrRYOZpk5vHGzor9cygSi5dNr3O65SnM8YvvPN6?= =?us-ascii?Q?ypwYhDdZbC/SnU9tolghuluf34qlQjbQYEKEos0OEGU9zoXYrEQRjWjliOn4?= =?us-ascii?Q?iGYecgb8xbg3L3gTiIpHlByCIL89yikozQUU9Bm9IOGmqdOmynfnmu5amxNY?= =?us-ascii?Q?wwUwTk9bkIpPT/TVmoQWOAt0u3FGrQjYpvF1ttE3C9SV/OulyLoGn7+QdAAg?= =?us-ascii?Q?GhjtTdN9GrhzDWvw1MGVR2R21HksMenw+MwBlba3zHlGsuifN9h61RIYXLc7?= =?us-ascii?Q?LDyz8YHSMShIE9tgdr9nTF9NGTYOSiuzM4afGyj01lk097E2U7owsUMHcjal?= =?us-ascii?Q?mp8sj28MDyn4Y7gWSeRjvyNLm9gp/jY1eSC8/sDxSxbShoO3S2+6F9G9Ov0h?= =?us-ascii?Q?WSClXAwTmTcjSIfV7rwK+B9pARqaTQbm1+K1nCOZiHhO60/LyS7izLxuvYQ+?= =?us-ascii?Q?ZlRerBlnlXmB3nWmAJHQhiuLvC6Q2WjjGLb/5srQPJsPJlhXalZO9X3+gBs?= =?us-ascii?Q?=3D?= MIME-Version: 1.0 X-OriginatorOrg: sct-15-20-7719-20-msonline-outlook-92255.templateTenant X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-CrossTenant-Network-Message-Id: fdb4f2f8-1961-466d-c0ff-08dd76be52f3 X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Apr 2025 16:56:36.3485 (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: DM8P223MB0367 Subject: Re: [FFmpeg-devel] [RFC] AVDictionary2 X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches <ffmpeg-devel.ffmpeg.org> List-Unsubscribe: <https://ffmpeg.org/mailman/options/ffmpeg-devel>, <mailto:ffmpeg-devel-request@ffmpeg.org?subject=unsubscribe> List-Archive: <https://ffmpeg.org/pipermail/ffmpeg-devel> List-Post: <mailto:ffmpeg-devel@ffmpeg.org> List-Help: <mailto:ffmpeg-devel-request@ffmpeg.org?subject=help> List-Subscribe: <https://ffmpeg.org/mailman/listinfo/ffmpeg-devel>, <mailto:ffmpeg-devel-request@ffmpeg.org?subject=subscribe> Reply-To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org> Archived-At: <https://master.gitmailbox.com/ffmpegdev/DM8P223MB03654302FB66A2EEB0039C45BAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM/> List-Archive: <https://master.gitmailbox.com/ffmpegdev/> List-Post: <mailto:ffmpegdev@gitmailbox.com> > -----Original Message----- > From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of > Michael Niedermayer > Sent: Dienstag, 8. April 2025 12:20 > To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> > Subject: [FFmpeg-devel] [RFC] AVDictionary2 > > Hi all > > As i have too many things to do already i did the most logic thing and > started thinking about a new and unrelated idea. > > This is a list of problems and ideas, that everyone is welcome to add to > and > comment on. > > AVDictionary is just bad. > > * its complicated internally with > unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely > used > and probably not relevant for performance. > > * all basic operations are as slow as possible. > you want to find, update or remove an entry, search through all > entries > > * its heavy on memory allocations > 1 malloc for key, 1 malloc for value, 1 realloc on the > AVDictionaryEntry array > that makes 2+ malloc() for every "foo"="bar" > > Ideas: > 1. put the node struct (AVDictionaryEntry), the key and value in the > same > allocated block, 1 malloc() instead of 2. > We can simply concatenate the key and value string, we could even use > the > 0 terminator instead of the 2nd pointer. Either way the whole > can go to the end of the Node structure for a tree > 1b. Now if we did put the key and value together, we can order in the > tree > by this combined entity. Why ? because now we have a unique ordering > and also the key+value could be required to be always unique. > Simplifying > things from what we have now and making it more replicatable, no > more changes in output because order changed > 2. We have a simple AVL tree implementation which we could use to make > all operations O(log n) instead of O(n) > 3. We could go with hash tables, splay trees, critbit trees or something > else. hash tables have issues with malicious/odd input which would > require more complexity to workaround. > > Of course we could also go a step further and eliminate the malloc per > node and put it all in a linear array. > As in, insert -> append at the end, > realloc with every power of 2 size increase > complete rebuild once enough elements are removed > not sure this isnt overkill for a metadata string dictionary > > I probably wont have time to implement this in the near future but as i > was thinking about this, it seemed to make sense to write this down and > post here > > git grep av_dict | wc is 1436 > > So its used a bit, justifying looking at improving it > > > git grep AV_DICT_DONT_STRDUP | wc is 87 > git grep AV_DICT_DONT_STRDUP libavutil/ tests doc | wc is 20 > > Seems not too common and one malloc/copy of a string once per metadata > entry > which is once per file generally, seems a strange optimization to me > > thx > > -- > Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Hi Michael, it's been a while, but as far as memory serves, wasn't a linear search even more efficient than other methods as long as we're dealing with no more than a few dozens of items? In turn, my question would be whether we even have use cases with hundreds or thousands of dictionary entries? Best, sw _______________________________________________ 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".