[FFmpeg-devel] [RFC] AVDictionary2

[softworkz .]

> -----Original Message-----
> From: ffmpeg-devel <ffmpeg-devel-bounces at ffmpeg.org> On Behalf Of
> Michael Niedermayer
> Sent: Freitag, 11. April 2025 21:06
> To: FFmpeg development discussions and patches <ffmpeg-devel at 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 at 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 at 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 at 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 at 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 at 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