> -----Original Message----- > From: ffmpeg-devel <ffmpeg-devel-boun...@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 _______________________________________________ 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".
