[FFmpeg-devel] [RFC] AVDictionary2

[Romain Beauxis]

Le mar. 8 avr. 2025 à 05:20, Michael Niedermayer
<michael at 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