> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-boun...@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-requ...@ffmpeg.org with subject "unsubscribe".
