[FFmpeg-devel] [PATCH 5/5] lavu/dict: add hashtable index.

Clément Bœsch ubitux at gmail.com
Mon Apr 15 21:03:17 CEST 2013

On Mon, Apr 15, 2013 at 08:17:29PM +0200, Michael Niedermayer wrote:
> On Sun, Apr 14, 2013 at 03:01:41PM +0200, Clément Bœsch wrote:
> > On Sun, Apr 14, 2013 at 02:10:28PM +0200, Nicolas George wrote:
> > > Le quintidi 25 germinal, an CCXXI, Clement Boesch a écrit :
> > > > From a4b09dd6703b1f73bff3fcce15f8ef55946ecee4 Mon Sep 17 00:00:00 2001
> > > > From: =?UTF-8?q?Cl=C3=A9ment=20B=C5=93sch?= <ubitux at gmail.com>
> > > > Date: Sun, 14 Apr 2013 03:05:00 +0200
> > > > Subject: [PATCH 5/5] lavu/dict: add hashtable index.
> > > > 
> > > > ---
> > > >  libavutil/dict.c | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++------
> > > 
> > > Is there a specific performance problem you are trying to fix?
> > > 
> > 
> > Not really, but I thought a simple ordered dict API with fast fetching
> > would be a good idea.
> iam not sure the complexity and maintaince burden are a good idea if
> its not solving any actual meassureable speed problem

I thought it was a good idea for applications outside FFmpeg to be able to
have relatively decent strings mapping utils if already linking with our
libraries. In FFmpeg indeed, we don't have that much direct accesses, but
I was planning to add some as my previous mail pointed out. The idea of
that string interpolation patch is to be used for example in filters like

Random use case: a user wants to drawtext "frame:%(n)
pict_type:%(pict_type) format:%(format)" on each frame. Interpolating such
string by looping over a relatively large AVDictionary containing all kind
of meta data for each key 25x times per frame may eventually be

The code I'm adding shouldn't change anything in the public behaviour
except making fetching faster. So if at some point the fork is going to
change the whole AVDictionary implementation, we can just revert it and
take their changes without breaking anything in the API/ABI.

Also, I can volunteer on maintaining lavu/dict.c if you want.

> Also what effect does it have on speed & memory requirements?
> I mean with actual use cases in ffmpeg

512*ptr_size bytes per dictionary and 4+ptr_size bytes per entry. 512
being the hash table size, thus configurable.

About speed I could do some benchmarks, but the scenarios I'll use may not
be relevant in practice.

> > 
> > BTW, that code might get relevant with code like attached for instance...
> For a large number of multiple lockups, alternative to a hashtable
> would be to sort both lists and do a single linear pass through them

Sorting the keys is not that easy (the implementation is designed in a way
that entries are randomly swapped); I'm not sure it will be a better
solution (and it will likely require more changes to the code). The code
I'm adding is just adding an hashtable maintaining indexes in the array,
the overall design is kept.

Clément B.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 490 bytes
Desc: not available
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20130415/583bcbbc/attachment.asc>

More information about the ffmpeg-devel mailing list