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 52F714D322 for <ffmpegdev@gitmailbox.com>; Wed, 16 Apr 2025 21:48:21 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id D76A668A247; Thu, 17 Apr 2025 00:48:17 +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 45243687D73 for <ffmpeg-devel@ffmpeg.org>; Thu, 17 Apr 2025 00:48:11 +0300 (EEST) Received: by mail.gandi.net (Postfix) with ESMTPSA id 797C4433F1 for <ffmpeg-devel@ffmpeg.org>; Wed, 16 Apr 2025 21:48:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc; s=gm1; t=1744840090; 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=zicCCIOqNeFhiLnFPpzxFB4vj5UZ8/paK8I7k1GE8/c=; b=jz4gpgNV6BNB/HpiwbH0E+EQze46LfKxHx3FNMahX7jf2n6Et9nGZEitPT6jh+/1nh9GvA jB6tSZLIWCua4I9GZgn2XdMJSw+FsdUbm7wrUQOhSpbA6QqYx3fRIFI3zuLB89DY/jPjVs YcDOoHbIEeAZ3Yayoqdc7BuohV72MbNfwNYW7NL9IJJFeZUg3J78KWtIKOfWycwRsP0iU8 NucGb8VLSq+/jGBWzVchoZaz8jJTWC+KYjS7ooqEBwThMWcDSCzMSyWeBjwInw0PWEjJNk Ar1cHExb8tshS3c0wqhCUUQpN1Q03n88tYi2f2ueRGQkYuBQ+2xDWlT2X+xHbQ== Date: Wed, 16 Apr 2025 23:48:09 +0200 From: Michael Niedermayer <michael@niedermayer.cc> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> Message-ID: <20250416214809.GO4991@pb2> References: <pull.64.ffstaging.FFmpeg.1744470718.ffmpegagent@gmail.com> <fed846502d637bc6ecf9e1d27e71a1d8a2168868.1744470718.git.ffmpegagent@gmail.com> MIME-Version: 1.0 In-Reply-To: <fed846502d637bc6ecf9e1d27e71a1d8a2168868.1744470718.git.ffmpegagent@gmail.com> X-GND-State: clean X-GND-Score: -70 X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvvdejgeelucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdeftddmnecujfgurhepfffhvffukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefoihgthhgrvghlucfpihgvuggvrhhmrgihvghruceomhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtqeenucggtffrrghtthgvrhhnpeelkeeggfffiedufeejueffjeduhedttdduledtheevveevtdeiueelhfdtuedtkeenucfkphepgedurdeiiedrieejrdduudefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgedurdeiiedrieejrdduudefpdhhvghloheplhhotggrlhhhohhsthdpmhgrihhlfhhrohhmpehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgdpnhgspghrtghpthhtohepuddprhgtphhtthhopehffhhmphgvghdquggvvhgvlhesfhhfmhhpvghgrdhorhhg X-GND-Sasl: michael@niedermayer.cc Subject: Re: [FFmpeg-devel] [PATCH 2/3] doc/dict2: Add doc and api change for 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="===============4979783712266113237==" Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org> Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250416214809.GO4991@pb2/> List-Archive: <https://master.gitmailbox.com/ffmpegdev/> List-Post: <mailto:ffmpegdev@gitmailbox.com> --===============4979783712266113237== Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="WuJrrduqyFOt/jEl" Content-Disposition: inline --WuJrrduqyFOt/jEl Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Hi softworkz I think we should use AI to support us and reduce the workload on people. I think this here cost you money and iam not sure this isnt adding workload and maybe even increased disagreements between people can you get AI to do something nooone else is working on ? or to support someone on what she is working on. This here is a bit more a opposition submission. Id love it if AI would submit bugfixes to my code for example or if it would submit patches improving my code Or maybeit could fix a random ticket chance of collision with a human is pretty low thx On Sat, Apr 12, 2025 at 03:11:57PM +0000, softworkz wrote: [...] > +AVDictionary2 is a hash table-based key-value dictionary implementation = that provides significant performance improvements over the original AVDict= ionary implementation. > + > +## Overview > + > +The implementation uses: > + > +- Hash table with chaining for collision resolution > +- Automatic table resizing when load factor exceeds 0.75 > +- Optimized key/value storage management > +- Efficient iteration through entries > + > +## Performance > + > +### Time Complexity > +AVDictionary2 offers substantial time complexity improvements: > + > +| Operation | AVDictionary (Linked List) | AVDictionary2 (Hash Table) | > +|-----------|----------------------------|----------------------------| > +| Insert | O(n)* | O(1) avg, O(n) worst | > +| Lookup | O(n) | O(1) avg, O(n) worst | One of the issues with AVDictionary is that its very slow with crafted data, Classic hash tables dont improve that. Which is one reason why i did go for the tree and not a hash table also AV_DICT_IGNORE_SUFFIX, is not hash table friendly and not supported by this > +| Iteration | O(n) | O(n) | > + > +*Where n is current dictionary size due to duplicate checking > + > +### Memory Characteristics > + > +**Original AVDictionary (dict.c)** > +- 2 allocations per entry (key + value string duplicates) > +- Dynamic array with O(log n) reallocations > +- Total: ~2n + log=E2=82=82(n) allocations for n entries I dont think this is correct, not that this matters also another key question, who would maintain AI generated code ? and for the specific case of string based has tables, i wager a bet that theres some maintained code somewhere on github. thx [...] --=20 Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope --WuJrrduqyFOt/jEl Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABEKAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCaAAllQAKCRBhHseHBAsP q3kgAJ4koF1uYKpChG06adD742wJKtgMfwCfS/WUc2AunwSbRSQxnS3luG4JQio= =mY/0 -----END PGP SIGNATURE----- --WuJrrduqyFOt/jEl-- --===============4979783712266113237== 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". --===============4979783712266113237==--