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

[Michael Niedermayer]

On Mon, Apr 15, 2013 at 09:03:17PM +0200, Clément Bœsch wrote:
> 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
> drawtext.
>

> 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
> problematic.

Theres no need to do the lookup of the fields per frame, its more
efficient to do it just once


> 
> 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.

if its fixed its not asymptotically faster than now and iam not
sure 4kb per Dictionary extra space is a good idea.
An application using a million dictionaries would be killed by that
change. Thats a constructed example of course but so is the case where
theres a measureable speed effect.


> 
> 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.

I had not meant that the table be kept sorted but rather that it is
sorted when that speed relevant multi lookup series is done
But its very hard to talk about optimizing code that is not speed
relevant in any existing use case.

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Breaking DRM is a little like attempting to break through a door even
though the window is wide open and the only thing in the house is a bunch
of things you dont want and which you would get tomorrow for free anyway
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20130415/3557de82/attachment.asc>