[MPlayer-dev-eng] NUT (informal) proposal, based on discussions

[Michael Niedermayer]

Hi

On Wed, Jan 18, 2006 at 09:30:56PM +0200, Oded Shimon wrote:
> On Wed, Jan 18, 2006 at 08:14:23PM +0100, Michael Niedermayer wrote:
> > Hi
> > 
> > On Wed, Jan 18, 2006 at 08:57:18PM +0200, Oded Shimon wrote:
> > > On Wed, Jan 18, 2006 at 07:47:43PM +0100, Michael Niedermayer wrote:
> > > > On Wed, Jan 18, 2006 at 07:41:40PM +0200, Oded Shimon wrote:
> > > > > writing a syncpoint will still point to last_target. Or did I completely 
> > > > > miss something. (Also don't forget, for your back_ptr method we need to 
> > > > > buffer several keyframes, not just the last one.)
> > > > 
> > > > hmm, my idea was to use the last keyframes (no buffering) and use their
> > > > max pts as timetsamp, this seems pretty easy but maybe iam missing some
> > > > issues associated with it?
> > > 
> > > Oh, I missed that - you never pointed that out.
> > > 
> > > > it wont give you the optimal keyframe in a single seek but there is no
> > > > way that could be possible with a single pts anyway you would always end
> > > > up with a syncpoint per keyframe and O(n^2*log n) overhead if there are many
> > > > streams
> > > 
> > > Yes we gave up single seek with syncpoints, we still want single seek with 
> > > index and that's a whole other and very easy story.
> > > 
> > > Now that you change the idea so you just use max pts of last keyframes for 
> > > syncpoint ts instead of the dts mess it was before, yes, implementation is 
> > > MUCH easier, no buffering, however...
> > > 
> > > A1  A2  A3  A4  A5  ...
> > >   I5  B3  B4  P6  ...
> > > 
> > > All syncpoints between I5 and A5 will have pts 5. When seeking to 4, 
> > > you'll end up at A2, and will have to linear search all the way till A4. 
> > > This linear search is bounded by O(max_b_frames+decode_delay), which is 
> > > quite worse than O(max_distance). :/
> > 
> > you need O(max_b_frames+decode_delay) anyway to display it dont you agree?
> > feeding I5 in the decoder gives you ... nothing, I5 wont come out before you
> > feed P6 into it ...
> 
> Actually I was reffering to audio being the only active stream, if I wanted 
> video I would've went to I0... (Do backwards only B frames really exist? 

i dunno, the standard mentions them ...


> NUT can't handle them right anyway, and I'm not sure if we should at all, 
> even though it is rather easy, use GOP boundries instead of keyframes..)

IMHO we should ignore such b frames ...


> 
> > so it seems we have
> > per stream ptr&pts  O(streams log streams) overhead, O(log filesize) seeks
> > per stream ptr&1pts O(streams log streams) overhead, O(log filesize) seeks
> > 1 ptr+pts O(log streams) overhead and O(log filesize) seeks but not "optimal"
> 
> O(s*log(s))  is a bit unoptimistic, I think even false.
> My syncpoint compression is worst case scenario O(s) and best case.. Well, 
> still O(s) but with a much smaller constant. :)
> 
> IMO single back pts/ptr is O(1) really, and if you measure it differently, 
> it is O(max keyint). It has little relavence to amount of streams...

well, no, your analysis is wrong :)
if we assume similar streams (similar bitrate, frame rate, keyint, ...) which
isnt really a unrealistic assumtation and more here for simplicity then 
anything else then as you add more streams the distance in bytes between
keyrames of one stream will increase proportionally to the number of streams
so a back pointer will point proportionally farther -> log n factor for
storing it unless you do something tricky ...

[...]

-- 
Michael