Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer <michael@niedermayer.cc>]

[-- Attachment #1.1: Type: text/plain, Size: 3470 bytes --]

On Tue, Apr 08, 2025 at 06:36:55PM +0000, softworkz . wrote:
> 
> 
> > -----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
> > 
> > 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
> 
> LOL, sorry I really didn't want to make it even more complicated.
> 
> Sticking on that side for a moment though, what you have skipped in the comparison above is the insertion cost, because the insertion cost is what buys you the 7 instead of 24 (worst) or x instead of 12 (average) comparisons on lookup. One of my takeaways in that area was that there's always a break-even point below of which there's nothing to win.
> 
> 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 handling
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

[...]

-- 
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


[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
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".