[FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

thx


[...]
-- 
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
-------------- 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/20250408/2db583a5/attachment.sig>