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 040834C56F for <ffmpegdev@gitmailbox.com>; Tue, 8 Apr 2025 18:16:32 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id D359D688334; Tue, 8 Apr 2025 21:16:28 +0300 (EEST) Received: from relay8-d.mail.gandi.net (relay8-d.mail.gandi.net [217.70.183.201]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id F0276687B7E for <ffmpeg-devel@ffmpeg.org>; Tue, 8 Apr 2025 21:16:22 +0300 (EEST) Received: by mail.gandi.net (Postfix) with ESMTPSA id 2B8934444C for <ffmpeg-devel@ffmpeg.org>; Tue, 8 Apr 2025 18:16:21 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc; s=gm1; t=1744136182; 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=Fnc9jRrJKoiXe+y9lgyUmQYqQuOKTK2gG1tRbZ6vbSU=; b=CBRkK2E0136ypTfNCGdKpTroHFaFHOkK0UoPnTdBo+8aHbHmEzVndWex7xc9vYpGIAsTFc dDhx/s/BjKRxaCVYze+8+IKcJyXISsMpsqg3xzEzFJVnIsHuIGV3vdzLqhJ1se8Irb/2JW dtU5oVOciTcK6Clit3qW46wZKFv6fEUryRqxiLBgXAxGqkGPrDkFdpYdeWJVuJw6470tU0 Son4IOspaV0pD1fGmtwQx6f7g1To08RHurfeX8Wp6WthKgs+PaD9/VvReSJAuN1+umH27f wOk5GWwsnb7VdQkUxsYLup5okuHgl8BXjLxscQxJxDKKwWAIqk7g9YUE3z7Khg== Date: Tue, 8 Apr 2025 20:16:21 +0200 From: Michael Niedermayer <michael@niedermayer.cc> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> Message-ID: <20250408181621.GQ4991@pb2> References: <20250408101959.GP4991@pb2> <DM8P223MB03654302FB66A2EEB0039C45BAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> MIME-Version: 1.0 In-Reply-To: <DM8P223MB03654302FB66A2EEB0039C45BAB52@DM8P223MB0365.NAMP223.PROD.OUTLOOK.COM> X-GND-State: clean X-GND-Score: -70 X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvtdefjeelucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdeftddmnecujfgurhepfffhvffukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefoihgthhgrvghlucfpihgvuggvrhhmrgihvghruceomhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtqeenucggtffrrghtthgvrhhnpeeigeektdejudffjefhteegjedtgeettefggedthfejgfevhfetgeekjedtvdfhveenucfkphepgedurdeiiedrieejrdduudefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgedurdeiiedrieejrdduudefpdhhvghloheplhhotggrlhhhohhsthdpmhgrihhlfhhrohhmpehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgdpnhgspghrtghpthhtohepuddprhgtphhtthhopehffhhmphgvghdquggvvhgvlhesfhhfmhhpvghgrdhorhhg 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="===============0893395081630233869==" Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org> Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250408181621.GQ4991@pb2/> List-Archive: <https://master.gitmailbox.com/ffmpegdev/> List-Post: <mailto:ffmpegdev@gitmailbox.com> --===============0893395081630233869== Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="+HYotmkGnQ9YzYFv" Content-Disposition: inline --+HYotmkGnQ9YzYFv Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Hi softworkz On Tue, Apr 08, 2025 at 04:56:36PM +0000, softworkz . wrote: [...] > Hi Michael, >=20 > it's been a while, but as far as memory serves, wasn't a linear search ev= en 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 >=20 > In turn, my question would be whether we even have use cases with hundred= s 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 thx [...] --=20 Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB I have never wished to cater to the crowd; for what I know they do not approve, and what they approve I do not know. -- Epicurus --+HYotmkGnQ9YzYFv Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABEKAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCZ/Vn7gAKCRBhHseHBAsP q3ZKAJwIq+ZSTjnBYcZpmkecTb517ISblwCeKMi3gZhaEUXo+YaRB7lFjBIm/H4= =C/8Z -----END PGP SIGNATURE----- --+HYotmkGnQ9YzYFv-- --===============0893395081630233869== 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". --===============0893395081630233869==--