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 98F504C591 for <ffmpegdev@gitmailbox.com>; Tue, 8 Apr 2025 19:45:15 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 5B4E96883DD; Tue, 8 Apr 2025 22:45:11 +0300 (EEST) Received: from relay7-d.mail.gandi.net (relay7-d.mail.gandi.net [217.70.183.200]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 47D0B687CCB for <ffmpeg-devel@ffmpeg.org>; Tue, 8 Apr 2025 22:45:04 +0300 (EEST) Received: by mail.gandi.net (Postfix) with ESMTPSA id 708F044318 for <ffmpeg-devel@ffmpeg.org>; Tue, 8 Apr 2025 19:45:03 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc; s=gm1; t=1744141503; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=jN9hc8mUlUBt+FmV/neEFLe67SI1XrjxNJpJA3VDrgk=; b=QE/o7UQd8oiXfHKEebxquaQOdE0AAYASsky5dVImAssWiEXLn1FtEWERKKISlbFTN/hmVc ootZVuGP85ZY+BIUXngw+YKhZWvSTx26bBM4TurSyO20Sh22vextjIx7guTfLtfh2PzihO 2BgZU6mK7mxmj/5adhDX9ARghmcDYeoFRenUK9ZYv8xUxOz5cxXicKWE8Zhfk3kmH7ZJf1 L2BxjvzUOM8kkyj07ij6+/1sx59/XcNGfo0iUedoJa9T31vFnKXJdXku8J3FZXR+BiKf6+ Z/1p1+Eb2R6YNljVnS7HqRx47uEOOoWEVB4VX/+BkgEzEsMPbWbqjblheRouKg== Date: Tue, 8 Apr 2025 21:45:02 +0200 From: Michael Niedermayer <michael@niedermayer.cc> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> Message-ID: <20250408194502.GR4991@pb2> References: <20250408101959.GP4991@pb2> <DM8P223MB03654302FB66A2EEB0039C45BAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> <20250408181621.GQ4991@pb2> <DM8P223MB0365F368CEF792DBBD091ABABAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> MIME-Version: 1.0 In-Reply-To: <DM8P223MB0365F368CEF792DBBD091ABABAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> X-GND-State: clean X-GND-Score: -85 X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvtdefleejucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdduhedmnecujfgurhepfffhvffukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefoihgthhgrvghlucfpihgvuggvrhhmrgihvghruceomhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtqeenucggtffrrghtthgvrhhnpeeigeektdejudffjefhteegjedtgeettefggedthfejgfevhfetgeekjedtvdfhveenucfkphepgedurdeiiedrieejrdduudefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgedurdeiiedrieejrdduudefpdhhvghloheplhhotggrlhhhohhsthdpmhgrihhlfhhrohhmpehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgdpnhgspghrtghpthhtohepuddprhgtphhtthhopehffhhmphgvghdquggvvhgvlhesfhhfmhhpvghgrdhorhhg X-GND-Sasl: michael@niedermayer.cc 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: multipart/mixed; boundary="===============7322489509356467987==" Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org> Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250408194502.GR4991@pb2/> List-Archive: <https://master.gitmailbox.com/ffmpegdev/> List-Post: <mailto:ffmpegdev@gitmailbox.com> --===============7322489509356467987== Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="D+Z89kqmm79+t97K" Content-Disposition: inline --D+Z89kqmm79+t97K Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, Apr 08, 2025 at 06:36:55PM +0000, softworkz . wrote: >=20 >=20 > > -----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 > >=20 > > Hi softworkz > >=20 > > 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? > >=20 > > a dozen is 12, so a few dozen would minimally be 24 > >=20 > > at average to find an entry in a list of 24 you need 12 comparisions > > with a > > linear search and 24 in worst case > >=20 > > an AVL tree with 24 entries i think needs 7 comparisions in the worst > > case > > So its certainly faster in number of comparisions > >=20 > > 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 > >=20 > >=20 > > > > > > In turn, my question would be whether we even have use cases with > > hundreds or thousands of dictionary entries? > >=20 > > 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 >=20 > LOL, sorry I really didn't want to make it even more complicated. >=20 > Sticking on that side for a moment though, what you have skipped in the c= omparison above is the insertion cost, because the insertion cost is what b= uys you the 7 instead of 24 (worst) or x instead of 12 (average) comparison= s on lookup. One of my takeaways in that area was that there's always a bre= ak-even point below of which there's nothing to win. >=20 > 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? I know that years ago there was some case in the command line option handli= ng where some linear search resulted in some O(n^3) which was noticable I dont remember if that was a AVDictionary also, if we use a linear search, what should we do with a file that contains 10k or 100k+ entries ? and then something checks for example for each of these entries if theres a corresponidng one in the local language, so for 100k entries someone could do a linear lookup that fails thus 100k * 100k This is a constructed case but it sounds plausible to me with such a file If we do a linear search then everyone needs to be carefull what they use AVDictionary for. thx [...] --=20 Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB "You are 36 times more likely to die in a bathtub than at the hands of a terrorist. Also, you are 2.5 times more likely to become a president and 2 times more likely to become an astronaut, than to die in a terrorist attack." -- Thoughty2 --D+Z89kqmm79+t97K Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABEKAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCZ/V8uwAKCRBhHseHBAsP q0QTAJ92VwWKg3SDocnCrgTCSJjZMr5OFwCcDaj99MZ/FrFW8pC8qgGoBH45n3U= =aR0W -----END PGP SIGNATURE----- --D+Z89kqmm79+t97K-- --===============7322489509356467987== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ 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". --===============7322489509356467987==--