[FFmpeg-devel] [PATCH 2/3] doc/dict2: Add doc and api change for AVDictionary2

[softworkz <ffmpegagent@gmail.com>]

From: softworkz <softworkz@hotmail.com>

Signed-off-by: softworkz <softworkz@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-request@ffmpeg.org with subject "unsubscribe".