[FFmpeg-devel] [PATCH 2/3] doc/dict2: Add doc and api change for AVDictionary2

[Michael Niedermayer]

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 AVDictionary 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₂(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

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20250416/e005303c/attachment.sig>