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

[Uoti Urpala]

On Mon, 2008-03-24 at 00:41 +0100, Michael Niedermayer wrote:
> On Sun, Mar 23, 2008 at 03:31:15AM +0200, Uoti Urpala wrote:
> > > > 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

1 second is a huge exaggeration in practical uses. On a setup where
printing a message would take that long FFmpeg startup would take ages.

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

That's the asymptotic behavior as you get beyond billions of translated
messages, but in practice the number of disk seeks needed during the
binary search is significantly less than log2(N) because several last
steps are read with a single seek.


Anyway this isn't too important if even gettext doesn't use binary
search in practice.