[FFmpeg-devel] [PATCH 0/3] avutil/dict2: Add AVDictionary2 with hash-based lookup

[ffmpegagent]

This is probably a PREMIERE.

This whole patchset has been antirely authored by AI, wich means that I
haven't written a single line of code. Still it had required a lot of strong
guidance, so it wouldn't have been able to do it alone. Even though it was
an experiment, it is still meant to be a serious submission - otherwisse it
would be a pointless endeavour.

The instructions were actuall given by Michael through his recent RFC
message and I hat assembled them from two of the e-mails to this:
https://gist.github.com/softworkz/c7a60c49e9e2b087bdf276ddf5dcf843

The initial direction was closely along the proposed text and atttempting to
use avtree for the search, but it struggled hard on that (one issue was
about translating/adapting the callback-based tree-enumeration to an
iterator-based API without doing allocations (which I forbid). It ended up
genereating a hash-based dictionary and after rejecting it for 2h, I let it
go with it - also due to the great performacne profile that it provides.

The original approach had implemented the single-memory strategy as proposed
by Michael but it hasn't been done for the final implementation (in this
PR). From the figures it just doesn't appear to be worth the effort. When
you have achieved an improvement by like factor 100 - which is HUGE - then
there's not much point in spending effort on something which woiuld bring an
improvement by a single percent at best. Anyway, it can still be improved.
This PR provides a solid hash-based dictionary without over-complication and
decent performance - at least when comparing to the old dictionary,

The only cases where AVDictionary is preferable over AVDictionary2 is when
there's a small number iof itemss in the dictionary or parameters like
NO_STRDUP are used.

softworkz (3):
  avutil/dict2: Add AVDictionary2  with hash-based lookup
  doc/dict2: Add doc and api change  for AVDictionary2
  tests/dict2: Add tests and benchmark for AVDictionary2

 doc/APIchanges             |   3 +
 doc/dict2.md               |  44 +++++
 libavutil/Makefile         |   3 +
 libavutil/dict2.c          | 335 +++++++++++++++++++++++++++++++++++++
 libavutil/dict2.h          | 167 ++++++++++++++++++
 libavutil/tests/dict2.c    | 185 ++++++++++++++++++++
 libavutil/version.h        |   2 +-
 tests/api/Makefile         |   1 +
 tests/api/api-dict2-test.c | 122 ++++++++++++++
 tests/fate/api.mak         |  15 ++
 tools/Makefile             |   2 +-
 tools/dict2_benchmark.c    | 237 ++++++++++++++++++++++++++
 12 files changed, 1114 insertions(+), 2 deletions(-)
 create mode 100644 doc/dict2.md
 create mode 100644 libavutil/dict2.c
 create mode 100644 libavutil/dict2.h
 create mode 100644 libavutil/tests/dict2.c
 create mode 100644 tests/api/api-dict2-test.c
 create mode 100644 tools/dict2_benchmark.c


base-commit: b02985b12c30fe44ca5abf5f90c39f2542b10ad7
Published-As: https://github.com/ffstaging/FFmpeg/releases/tag/pr-ffstaging-64%2Fsoftworkz%2Favdict2_test-v1
Fetch-It-Via: git fetch https://github.com/ffstaging/FFmpeg pr-ffstaging-64/softworkz/avdict2_test-v1
Pull-Request: https://github.com/ffstaging/FFmpeg/pull/64
-- 
ffmpeg-codebot