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