Le mar. 8 avr. 2025 à 05:20, Michael Niedermayer <mich...@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-requ...@ffmpeg.org with subject "unsubscribe".
