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

[Oded Shimon]

On Wed, Jan 18, 2006 at 09:11:39PM +0100, Michael Niedermayer wrote:
> Hi
> 
> On Wed, Jan 18, 2006 at 10:03:26PM +0200, Oded Shimon wrote:
> [...]
> > > > > 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 ...
> > 
> > Ohhh, yes, I forgot extra streams actually take more space in regards to 
> > actual data... Damn side-effects :)
> > 
> > 
> > Any thoughts on other thing I said (max(key_pts)) ?..
> 
> that several syncpoint would have the same pts? well that will always
> happen, think about a single stream in a file 300frame GOP and more then
> 1 syncpoint within a GOP

Re-read my mail:

-
I think using max(key_pts) for syncpoint ts is very false, it doesn't even                                                                                      
strictly interleave by MN rule, and it causes a very odd scenario of                                                                                            
several syncpoints with same ts but different back_ptr (scenario above).
-

all those syncpoints in your GOP will have same back_ptr (more correctly, 
all of them will back point to the same syncpoint). With this, you have 
several syncpoints, with the same pts, but each one has a more "correct" 
and different back_ptr. This isn't disasterous, but it is just blatently 
wrong. Also the syncpoints themselves don't comply to MN rule, which they 
should...

And again, you have to linear search O(max_b_frames + decode_delay) instead 
of max_distance. Rich's algo was based on syncpoints with ts P really 
pointing to the closest keyframe to P, using max(key_pts) destroys that and 
the algo completely.

- ods15