From: softworkz <softwo...@hotmail.com> Signed-off-by: softworkz <softwo...@hotmail.com> --- doc/APIchanges | 3 +++ doc/dict2.md | 44 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 47 insertions(+) create mode 100644 doc/dict2.md
diff --git a/doc/APIchanges b/doc/APIchanges index 65bf5a9419..1e0d47083b 100644 --- a/doc/APIchanges +++ b/doc/APIchanges @@ -2,6 +2,9 @@ The last version increases of all libraries were on 2025-03-28 API changes, most recent first: +2025-04-12 - xxxxxxxxxx - lavu 60.02.100 - dict2.h + Add AVDictionary2. + 2025-04-07 - 19e9a203b7 - lavu 60.01.100 - dict.h Add AV_DICT_DEDUP. diff --git a/doc/dict2.md b/doc/dict2.md new file mode 100644 index 0000000000..65147dd4ba --- /dev/null +++ b/doc/dict2.md @@ -0,0 +1,44 @@ +# AVDictionary2 - High Performance Dictionary Implementation + +AVDictionary2 is a hash table-based key-value dictionary implementation that provides significant performance improvements over the original AVDictionary implementation. + +## Overview + +The implementation uses: + +- Hash table with chaining for collision resolution +- Automatic table resizing when load factor exceeds 0.75 +- Optimized key/value storage management +- Efficient iteration through entries + +## Performance + +### Time Complexity +AVDictionary2 offers substantial time complexity improvements: + +| Operation | AVDictionary (Linked List) | AVDictionary2 (Hash Table) | +|-----------|----------------------------|----------------------------| +| Insert | O(n)* | O(1) avg, O(n) worst | +| Lookup | O(n) | O(1) avg, O(n) worst | +| Iteration | O(n) | O(n) | + +*Where n is current dictionary size due to duplicate checking + +### Memory Characteristics + +**Original AVDictionary (dict.c)** +- 2 allocations per entry (key + value string duplicates) +- Dynamic array with O(log n) reallocations +- Total: ~2n + log₂(n) allocations for n entries + +**AVDictionary2 (dict2.c)** +- 3 allocations per entry (struct + key + value duplicates) +- Hash table with O(log n) bucket table reallocations +- 2 initial allocations (dict struct + initial table) +- Total: ~3n + 2 + log₂(n) allocations for n entries + +**Key Differences:** +1. AVDictionary2 has faster O(1) average case operations despite 50% more allocations +2. Both handle growth with logarithmic reallocations but with different base structures +3. Real-world benchmarks show dramatic speed improvements outweigh allocation costs + -- ffmpeg-codebot _______________________________________________ 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".
