[FFmpeg-devel] [RFC] AVDictionary2

[FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

Hi all

As i have too many things to do already i did the most logic thing and
started thinking about a new and unrelated idea.

This is a list of problems and ideas, that everyone is welcome to add to and
comment on.

AVDictionary is just bad.

* its complicated internally with
  unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely used
  and probably not relevant for performance.

* all basic operations are as slow as possible.
  you want to find, update or remove an entry, search through all entries

* its heavy on memory allocations
  1 malloc for key, 1 malloc for value, 1 realloc on the AVDictionaryEntry array
  that makes 2+ malloc() for every "foo"="bar"

Ideas:
1. put the node struct (AVDictionaryEntry), the key and value in the same
   allocated block, 1 malloc() instead of 2.
   We can simply concatenate the key and value string, we could even use the
   0 terminator instead of the 2nd pointer. Either way the whole
   can go to the end of the Node structure for a tree
1b. Now if we did put the key and value together, we can order in the tree
   by this combined entity. Why ? because now we have a unique ordering
   and also the key+value could be required to be always unique. Simplifying
   things from what we have now and making it more replicatable, no
   more changes in output because order changed
2. We have a simple AVL tree implementation which we could use to make
   all operations O(log n) instead of O(n)
3. We could go with hash tables, splay trees, critbit trees or something
   else. hash tables have issues with malicious/odd input which would
   require more complexity to workaround.

Of course we could also go a step further and eliminate the malloc per
node and put it all in a linear array.
        As in, insert -> append at the end,
        realloc with every power of 2 size increase
        complete rebuild once enough elements are removed
    not sure this isnt overkill for a metadata string dictionary

I probably wont have time to implement this in the near future but as i
was thinking about this, it seemed to make sense to write this down and
post here

git grep av_dict | wc is 1436

So its used a bit, justifying looking at improving it


git grep AV_DICT_DONT_STRDUP | wc is 87
git grep AV_DICT_DONT_STRDUP libavutil/ tests doc | wc is 20

Seems not too common and one malloc/copy of a string once per metadata entry
which is once per file generally, seems a strange optimization to me

thx

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Those who would give up essential Liberty, to purchase a little
temporary Safety, deserve neither Liberty nor Safety -- Benjamin Franklin

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Romain Beauxis]

Le mar. 8 avr. 2025 à 05:20, Michael Niedermayer
<michael@niedermayer.cc> a écrit :
>
> Hi all
>
> As i have too many things to do already i did the most logic thing and
> started thinking about a new and unrelated idea.
>
> This is a list of problems and ideas, that everyone is welcome to add to and
> comment on.
>
> AVDictionary is just bad.
>
> * its complicated internally with
>   unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely used
>   and probably not relevant for performance.
>
> * all basic operations are as slow as possible.
>   you want to find, update or remove an entry, search through all entries
>
> * its heavy on memory allocations
>   1 malloc for key, 1 malloc for value, 1 realloc on the AVDictionaryEntry array
>   that makes 2+ malloc() for every "foo"="bar"
>
> Ideas:
> 1. put the node struct (AVDictionaryEntry), the key and value in the same
>    allocated block, 1 malloc() instead of 2.
>    We can simply concatenate the key and value string, we could even use the
>    0 terminator instead of the 2nd pointer. Either way the whole
>    can go to the end of the Node structure for a tree
> 1b. Now if we did put the key and value together, we can order in the tree
>    by this combined entity. Why ? because now we have a unique ordering
>    and also the key+value could be required to be always unique. Simplifying
>    things from what we have now and making it more replicatable, no
>    more changes in output because order changed
> 2. We have a simple AVL tree implementation which we could use to make
>    all operations O(log n) instead of O(n)
> 3. We could go with hash tables, splay trees, critbit trees or something
>    else. hash tables have issues with malicious/odd input which would
>    require more complexity to workaround.
>
> Of course we could also go a step further and eliminate the malloc per
> node and put it all in a linear array.
>         As in, insert -> append at the end,
>         realloc with every power of 2 size increase
>         complete rebuild once enough elements are removed
>     not sure this isnt overkill for a metadata string dictionary
>
> I probably wont have time to implement this in the near future but as i
> was thinking about this, it seemed to make sense to write this down and
> post here
>
> git grep av_dict | wc is 1436
>
> So its used a bit, justifying looking at improving it
>
>
> git grep AV_DICT_DONT_STRDUP | wc is 87
> git grep AV_DICT_DONT_STRDUP libavutil/ tests doc | wc is 20
>
> Seems not too common and one malloc/copy of a string once per metadata entry
> which is once per file generally, seems a strange optimization to me

Some questions that could be relevant:

* Any interest in storing binary data and not just NULL-terminated
strings? This could be used for many purposes including storing cover
art.

* Any interest in storing multiple values for the same key? This seems
like a niche case but, as you pointed out in another thread, typically
vorbis metadata do allow multiple key/values for the same field.

* Any interest in storing an optional encoding value for text strings?
This could be very useful to increase interoperability between legacy
systems. Typically, a lot of icecast ICY metadata are still passed as
latin1. This way, the library could pass them unchanged and let the
system decide what to do with them.

* Any interest in having alternative value for key names? Most
metadata systems carry their own naming conventions that are then
mapped to conventional/normalized names like TIT2 for title in ID3v2
frames. Having key name aliases could allow the library to refer to
their own normalized values while allowing a transparent end-to-end
handling of e.g. ID3v2 where you could dump the exact same frames
using their native keys.

* Similarly, any interest in carrying a source indicator? One of the
reasons the recent AV_DICT_DEDUP commit as suggested was to deal with
the same metadata key coming from two different sources. With a.
source indicator you can let the metadata flow end-to-end and let the
user make decisions about what to do in these cases.

These options could all be implemented with a flag system which would
then indicate how large the allocated memory should be for the
key/value pair so that you might still be able to get the memory
optimization you're hoping to get.

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of
> Michael Niedermayer
> Sent: Dienstag, 8. April 2025 12:20
> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
> Subject: [FFmpeg-devel] [RFC] AVDictionary2
> 
> Hi all
> 
> As i have too many things to do already i did the most logic thing and
> started thinking about a new and unrelated idea.
> 
> This is a list of problems and ideas, that everyone is welcome to add to
> and
> comment on.
> 
> AVDictionary is just bad.
> 
> * its complicated internally with
>   unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely
> used
>   and probably not relevant for performance.
> 
> * all basic operations are as slow as possible.
>   you want to find, update or remove an entry, search through all
> entries
> 
> * its heavy on memory allocations
>   1 malloc for key, 1 malloc for value, 1 realloc on the
> AVDictionaryEntry array
>   that makes 2+ malloc() for every "foo"="bar"
> 
> Ideas:
> 1. put the node struct (AVDictionaryEntry), the key and value in the
> same
>    allocated block, 1 malloc() instead of 2.
>    We can simply concatenate the key and value string, we could even use
> the
>    0 terminator instead of the 2nd pointer. Either way the whole
>    can go to the end of the Node structure for a tree
> 1b. Now if we did put the key and value together, we can order in the
> tree
>    by this combined entity. Why ? because now we have a unique ordering
>    and also the key+value could be required to be always unique.
> Simplifying
>    things from what we have now and making it more replicatable, no
>    more changes in output because order changed
> 2. We have a simple AVL tree implementation which we could use to make
>    all operations O(log n) instead of O(n)
> 3. We could go with hash tables, splay trees, critbit trees or something
>    else. hash tables have issues with malicious/odd input which would
>    require more complexity to workaround.
> 
> Of course we could also go a step further and eliminate the malloc per
> node and put it all in a linear array.
>         As in, insert -> append at the end,
>         realloc with every power of 2 size increase
>         complete rebuild once enough elements are removed
>     not sure this isnt overkill for a metadata string dictionary
> 
> I probably wont have time to implement this in the near future but as i
> was thinking about this, it seemed to make sense to write this down and
> post here
> 
> git grep av_dict | wc is 1436
> 
> So its used a bit, justifying looking at improving it
> 
> 
> git grep AV_DICT_DONT_STRDUP | wc is 87
> git grep AV_DICT_DONT_STRDUP libavutil/ tests doc | wc is 20
> 
> Seems not too common and one malloc/copy of a string once per metadata
> entry
> which is once per file generally, seems a strange optimization to me
> 
> thx
> 
> --
> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB


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?

In turn, my question would be whether we even have use cases with hundreds or thousands of dictionary entries?

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

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

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

On Tue, Apr 08, 2025 at 11:10:21AM -0500, Romain Beauxis wrote:
> Le mar. 8 avr. 2025 à 05:20, Michael Niedermayer
> <michael@niedermayer.cc> a écrit :
> >
> > Hi all
> >
> > As i have too many things to do already i did the most logic thing and
> > started thinking about a new and unrelated idea.
> >
> > This is a list of problems and ideas, that everyone is welcome to add to and
> > comment on.
> >
> > AVDictionary is just bad.
> >
> > * its complicated internally with
> >   unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely used
> >   and probably not relevant for performance.
> >
> > * all basic operations are as slow as possible.
> >   you want to find, update or remove an entry, search through all entries
> >
> > * its heavy on memory allocations
> >   1 malloc for key, 1 malloc for value, 1 realloc on the AVDictionaryEntry array
> >   that makes 2+ malloc() for every "foo"="bar"
> >
> > Ideas:
> > 1. put the node struct (AVDictionaryEntry), the key and value in the same
> >    allocated block, 1 malloc() instead of 2.
> >    We can simply concatenate the key and value string, we could even use the
> >    0 terminator instead of the 2nd pointer. Either way the whole
> >    can go to the end of the Node structure for a tree
> > 1b. Now if we did put the key and value together, we can order in the tree
> >    by this combined entity. Why ? because now we have a unique ordering
> >    and also the key+value could be required to be always unique. Simplifying
> >    things from what we have now and making it more replicatable, no
> >    more changes in output because order changed
> > 2. We have a simple AVL tree implementation which we could use to make
> >    all operations O(log n) instead of O(n)
> > 3. We could go with hash tables, splay trees, critbit trees or something
> >    else. hash tables have issues with malicious/odd input which would
> >    require more complexity to workaround.
> >
> > Of course we could also go a step further and eliminate the malloc per
> > node and put it all in a linear array.
> >         As in, insert -> append at the end,
> >         realloc with every power of 2 size increase
> >         complete rebuild once enough elements are removed
> >     not sure this isnt overkill for a metadata string dictionary
> >
> > I probably wont have time to implement this in the near future but as i
> > was thinking about this, it seemed to make sense to write this down and
> > post here
> >
> > git grep av_dict | wc is 1436
> >
> > So its used a bit, justifying looking at improving it
> >
> >
> > git grep AV_DICT_DONT_STRDUP | wc is 87
> > git grep AV_DICT_DONT_STRDUP libavutil/ tests doc | wc is 20
> >
> > Seems not too common and one malloc/copy of a string once per metadata entry
> > which is once per file generally, seems a strange optimization to me
> 
> Some questions that could be relevant:
[...]

>
> * Any interest in storing multiple values for the same key? This seems
> like a niche case but, as you pointed out in another thread, typically
> vorbis metadata do allow multiple key/values for the same field.

For a single key multiple values should not be stored
You can do
Author1=Eve
Author2=Adam
or
Author=Adam and Eve

But dont do
Author=Eve
Author=Adam
because if you do that and then you get later a
Author=Lilith
what does that mean? that its now 1 Author or 3 Authors
or 2 and if 2 then which 2 ?

Or said another way, you cant have multiple identical keys like that AND
allow updates.



> 
> * Any interest in storing an optional encoding value for text strings?

encoding is UTF-8 unicode
you can use "Private Use Areas" within unicode if you want to export
characters that the source failed to map to unicode

How we do this exactly is up to debate. But it seems more powerfull
and simpler for te user than to require the user app to handle every
encoding

There are 4 potential cases, i think
1. We are sure what a symbol means and we return only that in unicode
2. We are sure what a symbol means and we return that in unicode AND the
   source 8bit char in a PUA
3. We are not sure what a symbol means and we return our best guess in
   unicode AND the source 8bit char in a PUA
4. We are not sure what a symbol means and we return the source 8bit char
   in a PUA only

If we do that we would need 512 values from a PUA 2 sets of 256 one to
follow up on the last unicode symbol and one that comes alone


> This could be very useful to increase interoperability between legacy
> systems. Typically, a lot of icecast ICY metadata are still passed as
> latin1. This way, the library could pass them unchanged and let the
> system decide what to do with them.

If we do the suggested PUA case above, the a muxer could use either the
standard unicode or PUA values


> 
> * Any interest in having alternative value for key names? Most
> metadata systems carry their own naming conventions that are then
> mapped to conventional/normalized names like TIT2 for title in ID3v2
> frames. Having key name aliases could allow the library to refer to
> their own normalized values while allowing a transparent end-to-end
> handling of e.g. ID3v2 where you could dump the exact same frames
> using their native keys.

maybe the native keys could be attached somehow as extra information
iam not sure about complexity though

Title(TIT2)=...


> 
> * Similarly, any interest in carrying a source indicator? One of the
> reasons the recent AV_DICT_DEDUP commit as suggested was to deal with
> the same metadata key coming from two different sources. With a.
> source indicator you can let the metadata flow end-to-end and let the
> user make decisions about what to do in these cases.

This feels like very similar to the "TIT2" case above

thx

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

Never trust a computer, one day, it may think you are the virus. -- Compn

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of
> Michael Niedermayer
> Sent: Dienstag, 8. April 2025 21:45
> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
> Subject: Re: [FFmpeg-devel] [RFC] AVDictionary2
> 
> 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.


All granted, and surely, the current implementation hardly deserves its name because it's definitely not what you would expect from a dictionary.

I'm not responding arbitrarily to this topic. I had just recently spent some thought on it, as you'll quickly find out what it does - at least when working inside the Ffmpeg source.
One of those cases is FFprobe output filtering by using -show_entries to select specific fields. There are two actual hot paths which are printing of frame and packet data (each including descendants). In case when -show_entries is specified, the desired fields are stored in an AVDictionary (per section).

The frame section has 34 fields atm (https://softworkz.github.io/ffmpeg_output_apis/ffprobe_schema.html), so the maximum reasonable number of entries is 33, while in the typical case, the number is likely a lot less. Insert performance is irrelevant as it happens only once on start but the lookup count can be excessive - e.g. 34k lookups for 1k frames. 

In this context I was wondering whether a different dictionary implementation might provide any benefit and I concluded that it probably won't - at least not for small numbers of selected fields.

In that context I made another experiment, trying to find the fastest way to print all video keyframe times using packet data only. The keyframe packet-filter was hard-coded and I used show_entries, specifying only pts_time for packets. Packet section has 11 fields atm, so 11k dictionary lookup for 1k packets. I compared that to a patch which only prints pts_time, completely skipping the regular printing code (no dictionary lookups) and gained only 15% (3s instead of 3.5s). So, eventually, the cost of those 11k lookups (albeit in a single-entry dictionary) was a lot less than expected.

To tell you the truth - at that point I was thinking: "Ah, clever! That's why the AVDictionary is done like that" 😊 

So, this is the background of my previous replies - otherwise of course, I have nothing against a better dictionary.


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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Gerion Entrup]

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

Am Dienstag, 8. April 2025, 22:29:37 Mitteleuropäische Sommerzeit schrieb Michael Niedermayer:
> On Tue, Apr 08, 2025 at 11:10:21AM -0500, Romain Beauxis wrote:
> > Le mar. 8 avr. 2025 à 05:20, Michael Niedermayer
> > <michael@niedermayer.cc> a écrit :
>> [...]
> > * Any interest in storing multiple values for the same key? This seems
> > like a niche case but, as you pointed out in another thread, typically
> > vorbis metadata do allow multiple key/values for the same field.
> 
> For a single key multiple values should not be stored
> You can do
> Author1=Eve
> Author2=Adam
> or
> Author=Adam and Eve
> 
> But dont do
> Author=Eve
> Author=Adam
> because if you do that and then you get later a
> Author=Lilith
> what does that mean? that its now 1 Author or 3 Authors
> or 2 and if 2 then which 2 ?
> 
> Or said another way, you cant have multiple identical keys like that AND
> allow updates.

AFAIK, Matroska also has Metadata that are explicitly a tree and can have the same key.
A good example is the ACTOR tag: Most movies have more than one actor, the CHARACTER should be a subtag of ACTOR [1].
Currently, FFmpeg just seem to ignore keys with multiple values and display the first.

Best
Gerion

> [...]

[1] https://www.matroska.org/technical/tagging.html (search for ACTOR)

[-- Attachment #1.2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 659 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".

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

Hi

On Wed, Apr 09, 2025 at 12:18:10AM +0200, Gerion Entrup wrote:
> Am Dienstag, 8. April 2025, 22:29:37 Mitteleuropäische Sommerzeit schrieb Michael Niedermayer:
> > On Tue, Apr 08, 2025 at 11:10:21AM -0500, Romain Beauxis wrote:
> > > Le mar. 8 avr. 2025 à 05:20, Michael Niedermayer
> > > <michael@niedermayer.cc> a écrit :
> >> [...]
> > > * Any interest in storing multiple values for the same key? This seems
> > > like a niche case but, as you pointed out in another thread, typically
> > > vorbis metadata do allow multiple key/values for the same field.
> > 
> > For a single key multiple values should not be stored
> > You can do
> > Author1=Eve
> > Author2=Adam
> > or
> > Author=Adam and Eve
> > 
> > But dont do
> > Author=Eve
> > Author=Adam
> > because if you do that and then you get later a
> > Author=Lilith
> > what does that mean? that its now 1 Author or 3 Authors
> > or 2 and if 2 then which 2 ?
> > 
> > Or said another way, you cant have multiple identical keys like that AND
> > allow updates.
> 
> AFAIK, Matroska also has Metadata that are explicitly a tree and can have the same key.
> A good example is the ACTOR tag: Most movies have more than one actor, the CHARACTER should be a subtag of ACTOR [1].

The AVDictionary2 API doesnt need to represent multiple actors the same way as
the matroska bitstream.

Also it changes nothing on the conflict between "multiple identical keys" and
updates


> Currently, FFmpeg just seem to ignore keys with multiple values and display the first.

Since 80b77e8e8d0630710ad6069133f397459015f139, we have some
support for multiple values in id3, this has the problem with updates
described above though

thx

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

If the United States is serious about tackling the national security threats 
related to an insecure 5G network, it needs to rethink the extent to which it
values corporate profits and government espionage over security.-Bruce Schneier

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of Gerion
> Entrup
> Sent: Mittwoch, 9. April 2025 00:18
> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
> Subject: Re: [FFmpeg-devel] [RFC] AVDictionary2
> 
> Am Dienstag, 8. April 2025, 22:29:37 Mitteleuropäische Sommerzeit
> schrieb Michael Niedermayer:
> > On Tue, Apr 08, 2025 at 11:10:21AM -0500, Romain Beauxis wrote:
> > > Le mar. 8 avr. 2025 à 05:20, Michael Niedermayer
> > > <michael@niedermayer.cc> a écrit :
> >> [...]
> > > * Any interest in storing multiple values for the same key? This
> seems
> > > like a niche case but, as you pointed out in another thread,
> typically
> > > vorbis metadata do allow multiple key/values for the same field.
> >
> > For a single key multiple values should not be stored
> > You can do
> > Author1=Eve
> > Author2=Adam
> > or
> > Author=Adam and Eve
> >
> > But dont do
> > Author=Eve
> > Author=Adam
> > because if you do that and then you get later a
> > Author=Lilith
> > what does that mean? that its now 1 Author or 3 Authors
> > or 2 and if 2 then which 2 ?
> >
> > Or said another way, you cant have multiple identical keys like that
> AND
> > allow updates.
> 
> AFAIK, Matroska also has Metadata that are explicitly a tree and can
> have the same key.
> A good example is the ACTOR tag: Most movies have more than one actor,
> the CHARACTER should be a subtag of ACTOR [1].
> Currently, FFmpeg just seem to ignore keys with multiple values and
> display the first.

An AVDictionary can support duplicate keys via AV_DICT_MULTIKEY flag, but as Michael had pointed out, this gets messy. Whether such multiple key entries are displayed anywhere depends on the implementation.

ID3v2 tags can be multi-valued as well, in which case the values are null-separated.

In my patchset [1] enabling support for that, I'm not adding duplicate keys but appending values separated by semicolons, because that's how most audio tagging apps are presenting it (or even supporting this as input and saving that with null-separation eventually.

sw


[1] https://github.com/ffstaging/FFmpeg/pull/54/files#diff-e6bc3ebad40a50e6eed633fd2d6459e36ae9b38f468472d063e10e93abe7ccaaR345-R376






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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Leo Izen]

On 4/8/25 06:19, Michael Niedermayer wrote:
> Hi all
> 
> As i have too many things to do already i did the most logic thing and
> started thinking about a new and unrelated idea.
> 
> This is a list of problems and ideas, that everyone is welcome to add to and
> comment on.
> 
> AVDictionary is just bad.
> 
> * its complicated internally with
>    unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely used
>    and probably not relevant for performance.
> 

As far as I'm aware the main purpose of AV_DICT_DONT_STRDUP is to 
transfer ownership to the dictionary to save a call to malloc/free. If I 
construct a string e.g. with av_bprint API, and then I want to pass it 
as a value to an AVDictionary *, then without access to 
AV_DICT_DONT_STRDUP_VAL as an option, I will then have to free it.

Since your goal is to avoid malloc/free calls I feel like this is a 
reasonable interface to continue to support.

- Leo Izen (Traneptora)

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

On Tue, Apr 08, 2025 at 08:00:20PM -0400, Leo Izen wrote:
> On 4/8/25 06:19, Michael Niedermayer wrote:
> > Hi all
> > 
> > As i have too many things to do already i did the most logic thing and
> > started thinking about a new and unrelated idea.
> > 
> > This is a list of problems and ideas, that everyone is welcome to add to and
> > comment on.
> > 
> > AVDictionary is just bad.
> > 
> > * its complicated internally with
> >    unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely used
> >    and probably not relevant for performance.
> > 
> 
> As far as I'm aware the main purpose of AV_DICT_DONT_STRDUP is to transfer
> ownership to the dictionary to save a call to malloc/free. If I construct a
> string e.g. with av_bprint API, and then I want to pass it as a value to an
> AVDictionary *, then without access to AV_DICT_DONT_STRDUP_VAL as an option,
> I will then have to free it.
> 
> Since your goal is to avoid malloc/free calls I feel like this is a
> reasonable interface to continue to support.

git grep av_dict_set | wc is 690

git grep AV_DICT_DONT_STRDUP | wc is 87
git grep AV_DICT_DONT_STRDUP libavutil/ tests doc | wc is 20

We thus have 67 cases using one of the AV_DICT_DONT_STRDUP
and ~ 623 which do not

and we need 2*623 mallocs and 623 + 67 reallocs ATM
(not counting the ones outside av_dict_set())

teh proposed system would use 623 + 67 mallocs and 67 free and
log2(623 + 67) realloc. (or less if one used a single array)
It also could potentially avoid some of teh mallocs done outside
that just get freed then inside

now if you continue or not continue to support AV_DICT_DONT_STRDUP
doesnt change anything. The 2 externally allocated strings are not
in the right format and need to be freed. And even with freeing
its fewer mallocs (as shown above)

also the implied minimum allocation from AV_DICT_DONT_STRDUP is 2 per
call, we only need 1 with no extra complexity. Just dont allocate 2
seperate arrays, use 1
as a bonus its also 1 pointer less and 1 free less

thx

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

If a bugfix only changes things apparently unrelated to the bug with no
further explanation, that is a good sign that the bugfix is wrong.

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Nicolas George]

Michael Niedermayer (HE12025-04-08):
> As i have too many things to do already i did the most logic thing and
> started thinking about a new and unrelated idea.
> 
> This is a list of problems and ideas, that everyone is welcome to add to and
> comment on.
> 
> AVDictionary is just bad.

A few notes on the topic:

Steal a few ideas from BPrint, adapt them to a dictionary:

Include an initial buffer in the root structure.

Make the code tolerant to the size of the included buffer.

That ensures that the root structure can be allocated by the caller on
the stack.

Use a flat data structure with low overhead as long as the data fits in
the initial buffer and switch to a more efficient data structure when
dynamic allocation becomes needed.

A few points to decide:

Do we want only string → string, or do we want string → any or any →
any?

To handle any data structure, we can do:

	const struct {
	    int (*clone)(void *, const void *);
	    void (*free)(void *);
	    void (*ref)(void *);
	    void (*unref)(void *);
	    int (*compare)(const void *, const void *);
	    unsigned (*hash)(const void *);
	} *key_ops, *val_ops;

Supporting any kind of key or data can make it harder to use a flat data
structure, but we can manage.

The API should be designed to allow to avoid dynamic allocations, both
when adding and querying data. For query, consider all cases: if the
result is short lived, we can return the value inside the structure
itself; if the entry is removed from the structure immediately we can
return it (“my $v = delete $h{$k}” in perl).

Regards,

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of
> Nicolas George
> Sent: Donnerstag, 10. April 2025 10:40
> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
> Subject: Re: [FFmpeg-devel] [RFC] AVDictionary2
> 
> Michael Niedermayer (HE12025-04-08):
> > As i have too many things to do already i did the most logic thing and
> > started thinking about a new and unrelated idea.
> >
> > This is a list of problems and ideas, that everyone is welcome to add
> to and
> > comment on.
> >
> > AVDictionary is just bad.
> 
> A few notes on the topic:
> 
> Steal a few ideas from BPrint, adapt them to a dictionary:
> 
> Include an initial buffer in the root structure.
> 
> Make the code tolerant to the size of the included buffer.
> 
> That ensures that the root structure can be allocated by the caller on
> the stack.

The technique from BPrint is nice, but I'm not sure whether there are many usages of AVDictionary where stack allocation would be feasible or advantageous over the current way of "lazy init on first use", no?

Also, same like BPrint, a stack-alloc dictionary would be prone to forgotten uninit.

> Do we want only string → string, or do we want string → any or any →
> any?
> 
> To handle any data structure, we can do:
> 
> 	const struct {
> 	    int (*clone)(void *, const void *);
> 	    void (*free)(void *);
> 	    void (*ref)(void *);
> 	    void (*unref)(void *);
> 	    int (*compare)(const void *, const void *);
> 	    unsigned (*hash)(const void *);
> 	} *key_ops, *val_ops;
>

What if values are integers for example?

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

Hi

On Tue, Apr 08, 2025 at 09:30:16PM +0000, softworkz . wrote:
[...]

> To tell you the truth - at that point I was thinking: "Ah, clever! That's why the AVDictionary is done like that" 😊 

The dictionary implementation is not clever
look at copy for example it iterates over av_dict_set() which itself calls
av_dict_get() which it itself iterates over the dictionary
so av_dict_copy() is O(n^2) for example

also a single fate run, calls av_dict_iterate() 4921207 times
and fate should mostly be short small files and minimal self contained testcases

thx

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

Avoid a single point of failure, be that a person or equipment.

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[Michael Niedermayer]

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

On Tue, Apr 08, 2025 at 12:19:59PM +0200, Michael Niedermayer wrote:
> Hi all
> 
> As i have too many things to do already i did the most logic thing and
> started thinking about a new and unrelated idea.
> 
> This is a list of problems and ideas, that everyone is welcome to add to and
> comment on.
> 
> AVDictionary is just bad.
> 
> * its complicated internally with
>   unneeded alternative (AV_DICT_DONT_STRDUP_VAL/KEY) these are rarely used
>   and probably not relevant for performance.
> 
> * all basic operations are as slow as possible.
>   you want to find, update or remove an entry, search through all entries
> 
> * its heavy on memory allocations
>   1 malloc for key, 1 malloc for value, 1 realloc on the AVDictionaryEntry array
>   that makes 2+ malloc() for every "foo"="bar"
> 
> Ideas:
> 1. put the node struct (AVDictionaryEntry), the key and value in the same
>    allocated block, 1 malloc() instead of 2.
>    We can simply concatenate the key and value string, we could even use the
>    0 terminator instead of the 2nd pointer. Either way the whole
>    can go to the end of the Node structure for a tree
> 1b. Now if we did put the key and value together, we can order in the tree
>    by this combined entity. Why ? because now we have a unique ordering
>    and also the key+value could be required to be always unique. Simplifying
>    things from what we have now and making it more replicatable, no
>    more changes in output because order changed
> 2. We have a simple AVL tree implementation which we could use to make
>    all operations O(log n) instead of O(n)
> 3. We could go with hash tables, splay trees, critbit trees or something
>    else. hash tables have issues with malicious/odd input which would
>    require more complexity to workaround.
> 
> Of course we could also go a step further and eliminate the malloc per
> node and put it all in a linear array.
>         As in, insert -> append at the end,
>         realloc with every power of 2 size increase
>         complete rebuild once enough elements are removed
>     not sure this isnt overkill for a metadata string dictionary
> 
> I probably wont have time to implement this in the near future but as i
> was thinking about this, it seemed to make sense to write this down and
> post here
> 
> git grep av_dict | wc is 1436
> 
> So its used a bit, justifying looking at improving it
> 
> 
> git grep AV_DICT_DONT_STRDUP | wc is 87
> git grep AV_DICT_DONT_STRDUP libavutil/ tests doc | wc is 20
> 
> Seems not too common and one malloc/copy of a string once per metadata entry
> which is once per file generally, seems a strange optimization to me

If anyone wants a testcase that shows dictionary speed issues, try to do
anything with this file:
https://samples.ffmpeg.org/nut/meta.nut

its a single image 256x256 jpeg with a lot of metadata

thx

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Its not that you shouldnt use gotos but rather that you should write
readable code and code with gotos often but not always is less readable

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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of
> Michael Niedermayer
> Sent: Freitag, 11. April 2025 21:06
> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
> Subject: Re: [FFmpeg-devel] [RFC] AVDictionary2
> 
> Hi
> 
> On Tue, Apr 08, 2025 at 09:30:16PM +0000, softworkz . wrote:
> [...]
> 
> > To tell you the truth - at that point I was thinking: "Ah, clever!
> That's why the AVDictionary is done like that" 😊
> 
> The dictionary implementation is not clever
> look at copy for example it iterates over av_dict_set() which itself
> calls
> av_dict_get() which it itself iterates over the dictionary
> so av_dict_copy() is O(n^2) for example

I meant "clever" in the sense of "intentionally kept simple" and using linear lookup in order to be fast in cases like FFprobe where there's just a very small number of items.


> also a single fate run, calls av_dict_iterate() 4921207 times
> and fate should mostly be short small files and minimal self contained
> testcases

That's 1.2k per test in average..

Now - look at this masterpiece of a sentence:

    Isn't it an inevitable FATE for an iterator implementation 
    to see such high invocation counts?


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

Re: [FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of
> Michael Niedermayer
> Sent: Freitag, 11. April 2025 21:06
> To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
> Subject: Re: [FFmpeg-devel] [RFC] AVDictionary2
> 
> Hi
> 
> On Tue, Apr 08, 2025 at 09:30:16PM +0000, softworkz . wrote:
> [...]
> 
> > To tell you the truth - at that point I was thinking: "Ah, clever!
> That's why the AVDictionary is done like that" 😊
> 
> The dictionary implementation is not clever
> look at copy for example it iterates over av_dict_set() which itself
> calls
> av_dict_get() which it itself iterates over the dictionary
> so av_dict_copy() is O(n^2) for example
> 
> also a single fate run, calls av_dict_iterate() 4921207 times
> and fate should mostly be short small files and minimal self contained
> testcases
> 
> thx
> 
> [...]
> --
> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB


Hi Michael,


here are the benchmark results from your new AVDictionary2;



$ ./dict2_benchmark 5
Benchmarking AVDictionary vs AVDictionary2 with 5 entries

1. Insertion Performance:
   AVDictionary:  0.009 ms
   AVDictionary2: 0.004 ms (44.4% of original time)

2. Lookup Performance (100% existing keys):
   AVDictionary:  0.076 ms
   AVDictionary2: 0.292 ms (384.2% of original time)

3. Lookup Performance (50% existing keys):
   AVDictionary:  0.074 ms
   AVDictionary2: 0.320 ms (432.4% of original time)

4. Iteration Performance:
   AVDictionary:  0.000 ms
   AVDictionary2: 0.000 ms (-nan(ind)% of original time)

Benchmark completed successfully

admin@it UCRT64 /v/ffbuild/source/ffmpeg
$ ./dict2_benchmark 10
Benchmarking AVDictionary vs AVDictionary2 with 10 entries

1. Insertion Performance:
   AVDictionary:  0.014 ms
   AVDictionary2: 0.013 ms (92.9% of original time)

2. Lookup Performance (100% existing keys):
   AVDictionary:  0.154 ms
   AVDictionary2: 0.370 ms (240.3% of original time)

3. Lookup Performance (50% existing keys):
   AVDictionary:  0.155 ms
   AVDictionary2: 0.291 ms (187.7% of original time)

4. Iteration Performance:
   AVDictionary:  0.000 ms
   AVDictionary2: 0.000 ms (-nan(ind)% of original time)

Benchmark completed successfully

admin@it UCRT64 /v/ffbuild/source/ffmpeg
$ ./dict2_benchmark 100
Benchmarking AVDictionary vs AVDictionary2 with 100 entries

1. Insertion Performance:
   AVDictionary:  0.083 ms
   AVDictionary2: 0.094 ms (113.3% of original time)

2. Lookup Performance (100% existing keys):
   AVDictionary:  1.025 ms
   AVDictionary2: 0.308 ms (30.0% of original time)

3. Lookup Performance (50% existing keys):
   AVDictionary:  1.024 ms
   AVDictionary2: 0.331 ms (32.3% of original time)

4. Iteration Performance:
   AVDictionary:  0.001 ms
   AVDictionary2: 0.002 ms (200.0% of original time)

Benchmark completed successfully

admin@it UCRT64 /v/ffbuild/source/ffmpeg
$ ./dict2_benchmark 1000
Benchmarking AVDictionary vs AVDictionary2 with 1000 entries

1. Insertion Performance:
   AVDictionary:  1.830 ms
   AVDictionary2: 0.605 ms (33.1% of original time)

2. Lookup Performance (100% existing keys):
   AVDictionary:  10.704 ms
   AVDictionary2: 0.446 ms (4.2% of original time)

3. Lookup Performance (50% existing keys):
   AVDictionary:  12.905 ms
   AVDictionary2: 0.614 ms (4.8% of original time)

4. Iteration Performance:
   AVDictionary:  0.026 ms
   AVDictionary2: 0.028 ms (107.7% of original time)

Benchmark completed successfully

admin@it UCRT64 /v/ffbuild/source/ffmpeg
$ ./dict2_benchmark 10000
Benchmarking AVDictionary vs AVDictionary2 with 10000 entries

1. Insertion Performance:
   AVDictionary:  141.084 ms
   AVDictionary2: 4.874 ms (3.5% of original time)

2. Lookup Performance (100% existing keys):
   AVDictionary:  31.234 ms
   AVDictionary2: 0.653 ms (2.1% of original time)

3. Lookup Performance (50% existing keys):
   AVDictionary:  77.258 ms
   AVDictionary2: 0.809 ms (1.0% of original time)

4. Iteration Performance:
   AVDictionary:  0.094 ms
   AVDictionary2: 0.222 ms (236.2% of original time)

Benchmark completed successfully

admin@it UCRT64 /v/ffbuild/source/ffmpeg
$ ./dict2_benchmark 100000
Benchmarking AVDictionary vs AVDictionary2 with 100000 entries

1. Insertion Performance:
   AVDictionary:  16893.151 ms
   AVDictionary2: 80.074 ms (0.5% of original time)

2. Lookup Performance (100% existing keys):
   AVDictionary:  31.368 ms
   AVDictionary2: 0.580 ms (1.8% of original time)

3. Lookup Performance (50% existing keys):
   AVDictionary:  919.646 ms
   AVDictionary2: 0.688 ms (0.1% of original time)

4. Iteration Performance:
   AVDictionary:  0.773 ms
   AVDictionary2: 2.021 ms (261.4% of original time)

Benchmark completed successfully


---


> The dictionary implementation is not clever

No - but faster than the usual dictionary implementation approaches for small numbers of items.
In the context of FFprobe and when used with -show_entries for example, this is operating right within a range where linear is better.

And 3.8 / 4.4 are quite some factors:

2. Lookup Performance (100% existing keys):
   AVDictionary:  0.076 ms
   AVDictionary2: 0.292 ms (384.2% of original time)

3. Lookup Performance (50% existing keys):
   AVDictionary:  0.074 ms
   AVDictionary2: 0.320 ms (432.4% of original time)


I just had thought that it would have been done like this by intention..

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