[FFmpeg-devel] [RFC] An hash table container in libavutil?

Michael Niedermayer michaelni
Fri May 23 02:41:30 CEST 2008


On Fri, May 23, 2008 at 01:27:41AM +0200, Stefano Sabatini wrote:
> Hi all,
> 
> This is the long story, skip to the last paragraph if you when you get
> bored ;-).
> 
> Yesterday I discovered another in av_set_string(), for example when we
> have:
> ffmpeg -bt 101-1
> it fails with an out of range error message (this is because the
> string +101-1 is tokenized, the bt value is set to 101 then to -1,
> that is the string 101-1 isn't evaluated globally but only the last
> "token" is set).
> 
> I thought a good solution could be to implement a separate switch
> case for FF_OPT_FLAGS strings and for numbers, in the latter case would
> be fine to just evaluate the string with ff_eval2(), the only problem
> is that we have to put in the list of constants and their values the
> named values and the custom default/min/max values for the option.
> 
> So I thought an hash table dynamically extensible with those elements
> (name + value) instead of the different arrays const_values and
> const_names would be nice.
> 

> An hash table also could also improve the performance of the av_*_opt
> operations, 

Is the current speed a problem? How fast is it? Have you done any
benchmarks which show that av_*_opt is currently causing a significant
speed problem or is this just a random brainfart about improving code which
you have zero clue if its worth doing?
I honestly cant imagine how the dozen function calls once at init are
causing any meassureable speed effect. And if they do iam pretty sure
ISO C bsearch() will solve this much simpler.


> for example the static array could be loaded in an hash
> table, the every look-up operation would have an execution time of O(1)
> rather than the current O(n).

I like O(1) lookups, especially when we initialize the table do a single
lookup and destroy the table afterwards. The init is O(n) of course so
the whole will not be any faster.


> 
> Such use of an hash table also would improve the interface of eval
> (think for example at ratecontrol.c:get_qscale since names and values
> would be connected in a immediate fashion), for example an hypotetical
> ff_eval3 could then look like this:
> 
> double ff_eval3(const char *s, AVHash *constants, AVHash* funcs1,
>                       AVHash *funcs2, void *opaque, const char **error); 

And where is the improvment? With that one has to spend extra time and space
building hashtables ...


> 
> I'm attaching an interface I wrote some time ago, let me know if you
> think it could result useful in ffmpeg 

Hash tables could certainly be usefull in libav*. When we do find a case
where we do want hashtables we can think about the interface and
implementation.


> (for what regards the
> av_set_string() problem, I'll try to look meaningwhile for a simpler
> solution).

Dont bother, ive fixed the bug already.

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

I have never wished to cater to the crowd; for what I know they do not
approve, and what they approve I do not know. -- Epicurus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20080523/eb387c44/attachment.pgp>



More information about the ffmpeg-devel mailing list