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 D1A144C539 for <ffmpegdev@gitmailbox.com>; Tue, 8 Apr 2025 18:37:10 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 55E2968A417; Tue, 8 Apr 2025 21:37:06 +0300 (EEST) Received: from NAM04-MW2-obe.outbound.protection.outlook.com (mail-mw2nam04olkn2084.outbound.protection.outlook.com [40.92.46.84]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 34AA5687DE3 for <ffmpeg-devel@ffmpeg.org>; Tue, 8 Apr 2025 21:36:59 +0300 (EEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=BCsaCnDoey/wURit90q7vA+rjcyulZHXNvmnCQXJoZYsFLGcQWf/ze3q26R0ztz7G0SRvGM+PoL7qWBVWeQu3lLRXa2LC2Hk2ZbtqWlh0IiUtk1xAhQieMXRyL4gvf3g6hTqvuLcmz+yZmt64WwRIvxyQkBGbfKos3d15j61SBE3mBQziwRifMm27qPD4NBrmnLJlxDWfHUxnjC5Fy3c69IEqL9TcHUxUYNFyFobnBMBkg75JSJXULK95+itvPiae6s4GraV1h9YWzuA0QrAeZCwnA5dJP4Mbti6ux/qnOliBG64zMG0ppBamk5hETvbsIxwKnYzQDcTbl4U/t64Yw== 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=6C3AUsXc5Uxrx+ckDFa2DZIbMOoO0ocY+BcETMl08DI=; b=nTuGsp/05S3YO17UEbZOscD8twHmn6IdyFKU80zuqjb5vu4DxS/gl8d59kiElEsX55qVF1lqfumL5KfC76hxVeSaRCKe6hGK4b9wR7ZIqYdVnGewG7iHqYlfhZFtoW0oxbtQ9oq77wSXiEXua2TVrx8fFH//BXTMVt76MAnkM91LRXZn+HzptoVoWtKSTeKSk2EeKw1SUCpYeIi7Dki4qj8yQyPMElwPkJd0AHDdZmiB2hsZ2BwjFQVvbz2iZlO5riv9kYnXWSp5/gS60JyVdtYcCQJ76Wq3gEWVu0VK6I4TnH2HLdiJLh2A9WjUwPfzOkiWhNmcayCubuFdZlpcHg== 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=6C3AUsXc5Uxrx+ckDFa2DZIbMOoO0ocY+BcETMl08DI=; b=TxTXQsx82DwNx6Pt8OK6Paj6Ucpmy1Fs1j09s+wTCY2cFl9iwFCXSOt2ULrDC5JWy77mG1Ml3P1BNcEi2wGqmxdssbU4e8zmko1aLps6asYd+H6JPE9nxU1l2TpvgW97/rEQSyolLt0VRJSjNpxIY9PPYjwYlobG3NuqgzojAIQfcbuUnI5SkxSZ1YRzqtGOFGhVJ5Smm+U1mjmKxiqwan8rvARqlP4Ry+6/tGv/htWqrU//h241Qja2g6WZTuvyDbquQWXCfxX1KqD3OwcG8Y5g/hL92IOlfDThAd9pvW2QLtJXBV8XrDU3fsp2kHcYc28qCNmd1ztXL9nynoKJhA== Received: from DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM (2603:10b6:8:b::20) by BL3P223MB0178.NAMP223.PROD.OUTLOOK.COM (2603:10b6:208:348::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8632.21; Tue, 8 Apr 2025 18:36:55 +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 18:36:55 +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+5mAgAAYMICAAAEgMA== Date: Tue, 8 Apr 2025 18:36:55 +0000 Message-ID: <DM8P223MB0365F368CEF792DBBD091ABABAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> References: <20250408101959.GP4991@pb2> <DM8P223MB03654302FB66A2EEB0039C45BAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> <20250408181621.GQ4991@pb2> In-Reply-To: <20250408181621.GQ4991@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_|BL3P223MB0178:EE_ x-ms-office365-filtering-correlation-id: ea036cc3-f955-44f6-6c78-08dd76cc5676 x-microsoft-antispam: BCL:0; ARA:14566002|461199028|19110799003|8062599003|8060799006|15080799006|7092599003|3412199025|440099028|102099032|56899033; x-microsoft-antispam-message-info: =?us-ascii?Q?vPR7CHv1p9DcMzDZYZRWfIMHOpY3QsATT/V1dhVinIGYG7u/Ox5GnYWFoQ6o?= =?us-ascii?Q?oJDQrmxeEa6O0YSpiyeny6b9qImtF9f+mN5UUi5Gq5GNQGlh8539P7Cgj6Wd?= =?us-ascii?Q?y2ofEW+c4p/H/vkQm0doWiMkaJNqmN7n2HOQZA1lL4YwAAQ91mGEGIm4pJ83?= =?us-ascii?Q?quGKl+EyEV3VsouHp/s5YXc9L16Mtx4WkGn3CQ4SgKJnpUCQifcXnXm+Zc69?= =?us-ascii?Q?W/pzZkJMGlEVBH5Y9YGE8GPO1ptLw+2+oaU1v2G2aK07jigpGY74661veqPG?= =?us-ascii?Q?+elOYPwD/2U0vPIx9WIx2X/pW+7s984IF34gn2d7uwtrLGMion4ZbscPjvxD?= =?us-ascii?Q?+ypBCjxDmOsvAIJdzF/YfRlO1ZQ9uLZIix6iL9TQaWnqW+VA2gBdkmPjmOOB?= =?us-ascii?Q?YiQvLU1XVWrICVH8Zh2zIbyEG2gdJOfCcOJrw9ciS+1BB3WfhImD7hZO73yF?= =?us-ascii?Q?ln9sTOX3OJUnS1jnnrpajjAncnlzJwSCjUhFM/HaYy7E1PYzMmBCUSua6mQy?= =?us-ascii?Q?SpoSSWXHX/NgYHPqtSz/xaQ92/HX2lyIC+etGKzRhC+6aV7RmXN4Xgd1oXX+?= =?us-ascii?Q?S/lFRhq77ewRmPdQHwK0/epzAirwvQhm2cgOnHaV3ubh2f+ElbLCYOCcqcxY?= =?us-ascii?Q?ZtqP5GYakpJkadCs3tZHey78X4Afm7C27jNVj/uI5g/xKKQkrnKclJJ6B+Xh?= =?us-ascii?Q?dbbQnDjw4KMDDQ0SNQphlfS5Wz53GM1GvNW9eGTZmhr3tDK65SZgBM89/xdE?= =?us-ascii?Q?XrJY/bAbyLL3d4jfLLnUxemgIj+fY0AI7S+KvRIh19AsPc7ukOr80qVB+BV4?= =?us-ascii?Q?MZf0Ftn6DjRO9Ox0f+gmZ5sng9l9Rzd5FE1L1joLM75a9PAgHb+RvyQqCPzx?= =?us-ascii?Q?+lEaSrpL9Jx+uEMTTEDroyjfpYHU61qErqy4aLYgW6GCBSt7eXroz3Vwf0T6?= =?us-ascii?Q?G9bO0TGICcv2OAUQ3V4IH2DJUj3icPjqCIGJkuj2bXgTPV6shLv1VtI1aBSN?= =?us-ascii?Q?X15urcACMRx2aIiwhENyq3f6psMQlSnwlMeVdsBfAzLsKJg9rBEB8bNhcybp?= =?us-ascii?Q?WwD+NCwlOFcsf+7l/PeYaJCOKOKMpNWhqvkpJWBL33L7K2hLCCk=3D?= x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?gJv/jaKHoQxO59SEsEqwO88WrsILO1FQqvFX8x1PaOe+QmjMADsSWwTax+9n?= =?us-ascii?Q?MrroEAR7KYZBPaNSJadg8uh76apvFGdVbVsO/v1nua2Ydqc3u0QEsgIoUZt0?= =?us-ascii?Q?TjbwXzEh38Lz5Y660t47i4JQmhcFoz8fJiwMtb2Bfg2v9VAE+CFgvCd65zJ3?= =?us-ascii?Q?riTaKCCH1RFyyXnQhDqSL9h52gKMgNthOLOHzMj1+u7zPXowQ42nwpQMFj9y?= =?us-ascii?Q?H2VSn/E/HWBAHmOkWwQFR/3SG4z1x68MaFTyB8lo+qkcko3nG3rV3Y2YZqAT?= =?us-ascii?Q?XXn2F61KaWFNnZWiwb3P9QmCAovbuTtyzUrdjjwOCw1DsW87NMW4GXLJOx0M?= =?us-ascii?Q?AzzNlP7D6fYzeWwWHZXHbS4Z/tx0ukQ0yfirEZYX9DjS0I99Cfg0oCgA7dsQ?= =?us-ascii?Q?mXw5jT/OUU++x7O6e6cDqVK1jzdLngr3zUcyEENRcZqNycLmdLwj1L+UFrIX?= =?us-ascii?Q?X3Pq1dD5+36mBux2u4HY+vbN4hcBR1pa6k20Xo9D8eHU3lZSdrvhmgR+LAdV?= =?us-ascii?Q?8OSYrs2bSAuWg2RY/9506ea7WrzyOFnOxH8ZFgbMIrRVNkewkLY9LvsDZlKL?= =?us-ascii?Q?Xbl1/HQdtZRxik2tP72T2gu+MN48uifLLM1AekyeuOvnjiDRwepWOmSHAUri?= =?us-ascii?Q?aKk6Evs+FfSrpsmlXkGllHeJC+/oGQ+8YX0K78fH0aaUopOr/6RQ9NF5STVh?= =?us-ascii?Q?TYM6KXI/qWhdOsoAkExOqD/8l7jUAbmGoCRuVUa6O/HhHpAPJ6PSsFRRH7p6?= =?us-ascii?Q?k340qxj6br8BBadEnkxLMqWIgCrqAtPZ4q0PiNdgOKuP15xrzGWcje3m0qGr?= =?us-ascii?Q?YrbzN+aZ5/ASoihbqCq9R5Qmx3JkZ6S0O4XALjTETGfG5Zi5ZXCxFuVcbOio?= =?us-ascii?Q?X0M400Ak2OMsjwyRyBEBZjHpadq5LqtfJj4ZtF35pcfOahYEb+InkXid/vBM?= =?us-ascii?Q?hKsbU650n78IjNgYCpNTzmbpY51hd9ak+NoOtB8QhXMBo3vueqZxo+FMwY0n?= =?us-ascii?Q?3Dk0PDxuXLyRbjlex1N+WV9DSemmkXN9QGr/YUiMhqDO6Wljo0HZ8rbaSVDx?= =?us-ascii?Q?iia/crwzA85J3MLyjiaqMHUSI/s607XfoYxHoZktwPvwDT0mVrAg2ErZpi9V?= =?us-ascii?Q?lizQDewFeWkhJ8hvVXssDwq4EnCu29dN24dQCX3AVYjuxilV5jMhBFGS8DaB?= =?us-ascii?Q?O66YYmsFUjhEQsVMKz6SDZEAmyqAaIQqVRbs3rEkuRPgZtnjQiML+lbxihw?= =?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: ea036cc3-f955-44f6-6c78-08dd76cc5676 X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Apr 2025 18:36:55.2061 (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: BL3P223MB0178 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/DM8P223MB0365F368CEF792DBBD091ABABAB52@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 20:16 > To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> > Subject: Re: [FFmpeg-devel] [RFC] AVDictionary2 > > Hi softworkz > > On Tue, Apr 08, 2025 at 04:56:36PM +0000, softworkz . wrote: > [...] > > 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? > > a dozen is 12, so a few dozen would minimally be 24 > > at average to find an entry in a list of 24 you need 12 comparisions > with a > linear search and 24 in worst case > > an AVL tree with 24 entries i think needs 7 comparisions in the worst > case > So its certainly faster in number of comparisions > > the cost of strcmp() and overhead then come into play but small sets > arent really what seperates the 2 choices. > The seperation happens with there are many entries. dictionary is > generic > if you had a million entries a linear search will take about a million > comparisions, the AVL tree should need less than ~30 in the worst case > thats 5 orders of magnitude difference > > > > > > In turn, my question would be whether we even have use cases with > hundreds or thousands of dictionary entries? > > We use dictionary for metadata and options mainly. > It would be possible to also use a linear list until the number of > entries reaches a threshold LOL, sorry I really didn't want to make it even more complicated. Sticking on that side for a moment though, what you have skipped in the comparison above is the insertion cost, because the insertion cost is what buys you the 7 instead of 24 (worst) or x instead of 12 (average) comparisons on lookup. One of my takeaways in that area was that there's always a break-even point below of which there's nothing to win. At the bottom line, I love optimizations and for dictionaries with larger amounts, everything you said is perfectly valid of course. What I tried to ask is just whether we actually have any case of dictionary use that would benefit from that kind of optimization? 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".