[MPlayer-dev-eng] NUT backptr proposal

[Rich Felker]

oded and i have been working on implementing seeking in nut and run
into some problems with performance. to recall:

seeking to a timestamp t is the process of finding the /latest/ point
x in the file such that each /active/ stream has a keyframe after
point x but before timestamp t.

key words:

- latest: if we're free to choose any earlier point x, not just the
  latest, seeking guarantees nothing useful. we might as well just
  decode from beginning_of_file... and in pathological cases we might
  have to.

- active: if we just wanted the latest point such that all frames ...,
  we could just use the single backptr in the current spec for
  syncpoints and the index. this has 2 major drawbacks:
   a) prevents hi-res audio seeking in a+v files, e.g. music vid
   b) causes seek behavior to change when new irrelevant streams are
      added to a file. if these streams have infrequent keyframs it
      could severely harm seeking precision.
  thus we demand ability to seek based on just a collection of
  'active' interesting streams.

now the problem:

the current method of seeking is as follows:

1. identify the previous syncpoint before the desired timestamp t
   using either the index or binary search.
2. follow is back_ptr which tells how far you have to go back to
   ensure that you will find a keyframe for each stream.
3. linear search this span to find the latest possible point x such
   that ...

now the problem is that for a file with 1600kbit video and 250-frame
keyint, the linear search in step 3 spans around 2 megs. this is way
too slow for acceptable performance even on local media (cdrom, dvd,
even hdd..) not to mention network streams.

step 2 can be skipped if you want imprecise seeking, but in nasty
special cases this could make seeking get 'stuck' and make it
impossible to seek were you want. what's worse, it's totally
unacceptable for media editor apps since it will skip the actual
frames the user wanted!!

step 3 can be skipped too, but then you'll end up at a position much
earlier in the file than you wanted. moreover, where you end up
depends partly on the syncpoint structure and other possibly
irrelevant streams. syncpoints are non-semantic objects so this is bad
on a conceptual level too. they should only be aids to make
implementation of the correct behavior (which can be defined without
syncpoints) efficient. the behavior should not depend on them; only
its efficiency should.

solution:

oded and i have worked on the problem a lot and the only solution we
can find is bringing back an old proposal that has slightly high
overhead associated with it: per-stream back_ptr. this means, at every
syncpoint, we store a back_ptr for each stream, pointing to the latest
syncpoint at which you can start demuxing if you want to get a
keyframe before or at the current syncpoint.

possible seeking algorithm:

1. identify the previous syncpoint before the desired timestamp t
   using either the index or binary search.
2. among all active streams, choose the one with earliest back_ptr and
   seek to that point.
3. linear search for latest point x, but only up to next syncpoint.
   note that this is a very quick bounded operation due to
   max_distance restriction on syncpoints.

due to max_distance it's also possible for an implementation which
does not care about perfect exactness to just skip step 3, without
fear that it will seek too far from the desired position.

conclusions:

per-stream back_ptr values do add some overhead to nut, but i believe
we can keep it under control and keep it down to acceptable levels.
they allow us to meet our goals for correct and very efficient seeking
in the presence of multiple streams and ensure that there is a
reasonable way to seek that is bounded in time and memory usage and
where the results depend only on the semantic content of the nut file
(packet timestamps and keyframe flags), not the non-semantic
structures (syncpoints).

beyond: the index..

naturally an index that simply points to each syncpoint can be used;
however that increases the required media-seek operations to 2 per
seek instead of just 1. storing back_ptr values in the index seems
desirable if it can be done without severe overhead costs. oded will
hopefully be sending a proposal based on some of our ideas for the
index to go with per-stream back_ptr.

rich