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
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
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
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)
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
-----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-e6bc3ebad40a50e6eed63...
-----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
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
-----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
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
-----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-
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
devel@ffmpeg.org> 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
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.
-----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
-----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
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)
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.
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
-----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
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
participants (6)
-
Gerion Entrup -
Leo Izen -
Michael Niedermayer -
Nicolas George -
Romain Beauxis -
softworkz .