[FFmpeg-devel] GSoC with FFMpeg waht a combination!

[Michael Niedermayer]

On Sun, Mar 23, 2008 at 03:31:15AM +0200, Uoti Urpala wrote:
> On Sun, 2008-03-23 at 00:19 +0100, Michael Niedermayer wrote:
[...]
> > > > * gettext uses strings as keys (very inefficient requireing O(log n) lookups)
> > > 
> > > O(log n) is NOT inefficient for text lookups!
> > 
> > If the area where the strings are has been paged out to disk then O(log n)
> > can be alot slower than O(1). And i would expect it to be paged out in
> > practice as ffmpeg doesnt print the overhelming amount of these strings
> > regularly. If it were in memory id immedeatly agree with you that O(log N)
> > is irrelevant.
> 
> If it's used rarely enough to need paging does the speed really matter?

Well, having 1 second extra delay before a error message comes up is giving
a bad impression. Things like that make a program look bloated and slow to
the user. Its not that this would noticeably affect the amount of time a
transcoding of something would take ...

Also it reminds me a little of firefox and how long it takes to become
useable again once its paged out (after not using it for 10min).
These things do add up. Once you start on the path of "1 second doesnt matter"
you quickly have accumulated a minute from 60 different functions where
in each 1 second didnt matter.


> Also it's not that obvious that there would be much of a speed
> difference. Even a directly hardcoded string without any lookup can be
> swapped out, and a lookup structure is unlikely to need a separate seek
> and read for every accessed page.

binary search needs O(log N) seeks.


> 
> Also note that this isn't an inherent difference between compile-time
> and runtime hash calculation, both have the same O() behavior.

no, its of course a hashtab vs binary search issue.


> 
> > > Also your claim that using
> > > strings as keys would necessarily require O(log n) lookups is not true.
> > > Hash tables require O(1) on average, and your own suggested method needs
> > > an equal lookup.
> > 
> > Yes, but if you do use a hash table why calculate the hash values at runtime?
> > Why store the english strings twice instead of corresponding hash values?
> > I dont belive you consider this good design. It is plain waste of space.
> 
> Having the strings in the binary means you don't need a separate
> translation file to use the program. If you use a translation but it
> doesn't contain all needed strings you always have at least the English
> version available. If you manage to find some use case where performance
> actually matters then it allows you to turn off translation to get
> optimal behavior (direct access to the string with no lookup step).

I dont have a strong oppinion on storing the default strings once in the
program if this is what people want, though i do not  think it is a good
idea.
Its rather the unneeded storeage of
them on disk and in memory once for every single language.

Storing the default once has some advanatges, storing them more than once
does not.

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

Many things microsoft did are stupid, but not doing something just because
microsoft did it is even more stupid. If everything ms did were stupid they
would be bankrupt already.
-------------- 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/20080324/733a19f5/attachment.pgp>