[FFmpeg-devel] AVDictionary vs. AVSet (AVDictionary2 approximation)

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces at ffmpeg.org> On Behalf Of
> softworkz .
> Sent: Montag, 14. April 2025 14:40
> To: FFmpeg development discussions and patches <ffmpeg-
> devel at ffmpeg.org>
> Subject: Re: [FFmpeg-devel] AVDictionary vs. AVSet (AVDictionary2
> approximation)
> 
> 
> 
> > -----Original Message-----
> > From: ffmpeg-devel <ffmpeg-devel-bounces at ffmpeg.org> On Behalf Of
> > Michael Niedermayer
> > Sent: Montag, 14. April 2025 13:33
> > To: FFmpeg development discussions and patches <ffmpeg-
> > devel at ffmpeg.org>
> > Subject: [FFmpeg-devel] AVDictionary vs. AVSet (AVDictionary2
> > approximation)
> >
> > Hi
> >
> > I just posted a AVSet implementation i wrote in the last 2 days (yes
> > thats
> > why i did dissapear for the last 2 days)
> >
> > My plan was to use that AVSet as basis for AVDictionary2 in case
> > benchmarks indicate that its worth it, so is it ?
> >
> > with 3 entries (100000 runs)
> > AVDictionary    0.040sec
> > AVSet           0.027sec
> >
> > with 5 entries (100000 runs)
> > AVDictionary    0.065sec
> > AVSet           0.042sec
> >
> > with 10 entries (100000 runs)
> > AVDictionary    0.193sec
> > AVSet           0.087sec
> >
> > with 100 entries (100000 runs)
> > AVDictionary    8.7  sec
> > AVSet           1.4  sec
> >
> > with 1000 entries (1000 runs)
> > AVDictionary    8.0   sec
> > AVSet           0.240 sec
> >
> > with 10000 entries (10 runs)
> > AVDictionary    7.2   sec
> > AVSet           0.042 sec
> >
> >
> > I was a bit surprised for the 3 and 5 entry case, maybe my benchmark
> > is buggy or
> > AVSet is, but then AVDictionary is pretty bad with memory
> allocations
> >
> > AVDictionary needs to strdup every key and value, needs to allocate
> > the AVDictionary itself and reallocs the entry array each time
> > thats 10 memory allocation related calls for adding 3 entries
> >
> > while AVSet allocates the AVSet and then uses av_fast_realloc() for
> > the array
> > and theres nothing else, the key/value goes in that array too
> >
> >
> > bechmark code used is below:
> >
> >
> > #if 0
> >     for (int runs = 0; runs < 100000; runs++) {
> >         AVSet *set = av_set_new(strcmp, NULL, NULL);
> >         for(int pass = 0; pass < 2; pass++) {
> >             unsigned r = 5;
> >             for(int i=0; i<100; i++) {
> >                 r = r*123 + 7;
> >                 char str[2*7] = "TESTXXTESTXX";
> >                 str[4] = r;
> >                 str[5] = r>>8;
> >                 if(pass == 0) {
> >                     av_set_add(set, str, 2*7, 0);
> >                 } else {
> >                     av_set_get(set, NULL, str, NULL);
> >                 }
> >             }
> >         }
> >         av_set_free(&set);
> >     }
> > #else
> >     for (int runs = 0; runs < 100000; runs++) {
> >         AVDictionary *dict = NULL;
> >         for(int pass = 0; pass < 2; pass++) {
> >             unsigned r = 5;
> >             for(int i=0; i<100; i++) {
> >                 r = r*123 + 7;
> >                 char str[7] = "TEST";
> >                 str[4] = r;
> >                 str[5] = r>>8;
> >                 if(pass == 0) {
> >                     av_dict_set(&dict, str, str, 0);
> >                 } else {
> >                     av_dict_get(dict, str, NULL, 0);
> >                 }
> >             }
> >         }
> >         av_dict_free(&dict);
> >     }
> > #endif
> >
> >
> > --
> 
> Hi Michael,
> 
> 
> what's not quite realistic is that all keys are starting with the same
> 4 characters. This affects the lookups of course - and probably
> (maybe) not equally for both sides.
> 
> Doesn't the code create duplicate keys (at least when it gets > 65536
> it will for sure) ?
> 
> So, I think, the keys should be completely random (all chars).
> 
> I would also check whether the lookups are successful (just to be
> sure).

Sorry, I forgot the most important one: 

Timing for population and lookup should be measured separately..

sw