Re: [FFmpeg-devel] [RFC] AVDictionary2

["softworkz ." <softworkz-at-hotmail.com@ffmpeg.org>]

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

Best
sw

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