When should a decoder seek forward?

[NicolasHug]

This is a technical note I posted internally. Posting it here to justify an incoming PR.

I propose a heuristic to decide whether a decoder should seek forward vs just decode all the frames until the target. The moral of the story is don’t throw away work you’ve already done, if you’ll need it - duh, but I promise there is more substance to the post.

TL;DR: the heuristic is seek iff dist(current frame, target keyframe) > frame_reorder_buffer_size + thread_count - 1.

~5 % of this post was written by an LLM.

The problem

We are at frame x. We now want to decode frame y with y > x. Do we seek? Or do we just decode all the frames from x to y?

.....x...................j...............y.......
     ^                                   ^
     |                                   |
 we are here                        we want to decode y

By definition, seeking means seeking to keyframe j, the last keyframe before y.

In TorchCodec, we always seek [1], but we’ll see that sometimes it’s worth just decoding all the frames.

Let's look at some plots

Each of the 5 plots shows the same experiment for different num_ffmpeg_threads values[2]: how long does it take to decode frame y from frame x. On each plot, we compare the seek vs no-seek strategies on two values of S = (j - x): one small (x and j are close, on the left), and one large (x and j are far apart, on the right).

When x and j are far apart (the right side of each plot), the results match our intuition that seeking wins: the cost of seeking and flushing is much lower than the cost of decoding so many frames, and this is true for all num_ffmpeg_threads values.

When x and j are close, the no-seek strategy tends to dominate more as num_ffmpeg_threads grows. There are 3 separate mechanisms at play here:

Flush direct cost: The flush itself (i.e. the avcodec_flush_buffers()), which is the red part on the plots, isn't that cheap. It becomes relatively more expensive as num_ffmpeg_threads grows, since everything else becomes faster. Also, and this is more visible on the x265 plots, the cost of avcodec_flush_buffers() seems to be O(num_ffmpeg_threads)!

Flush opportunity cost: B-frames. Flushing empties the B-frames buffer, which means some frames need to be decoded again. This is very visible on the first plot where num_ffmpeg_threads=1, look at the time it takes to receive the key frame. When we don’t seek, the keyframe is already there in the B-frames buffer, so it can be returned immediately. That’s because the codec will always buffer frame_reorder_buffer_size [3] frames before returning anything When we seek, that already-decoded keyframe is flushed from the buffer, and we have to decode it again. Not only that, but we also have to decode all the next frame_reorder_buffer_size frames before outputting that keyframe!

Flush opportunity cost: parallel decoding. A similar thing happens with the frame-threading pipeline. With frame multi-threading there are num_ffmpeg_threads - 1 frames in-flight, being decoded in parallel (they depend on each-other, so it’s not 100% parallel): the decoder deliberately won't output anything until all threads have been given work to do. By flushing, we throw away those num_ffmpeg_threads - 1 frames that were close to being decoded, and we have to wait for the buffers to primed again before the next frame comes out. The higher num_ffmpeg_threads, the bigger the opportunity cost we pay by flushing.

The heuristic

We now know that at any given point in time, when the decoder is reasonably warm, there are:

• frame_reorder_buffer_size frames already decoded, ready to be output
• num_ffmpeg_threads - 1 frames being decoded

These are additive buffers.

Clearly, if we’re going to need these frames, we shouldn’t discard them. Which means that if j is within those next frame_reorder_buffer_size + num_ffmpeg_threads - 1 frames, we shouldn’t seek. That’s it.

seek iff j - x > frame_reorder_buffer_size + thread_count - 1

The heuristic in practice

The plots above compare the seek vs no-seek strategy with different values of N = num_ffmpeg_threads. They’re the same plots as before, just with more values of S = (j - i). I’m observing similar plots on other resolutions and on h265.

Our heuristic is the purple vertical line, and it shows where it would put the threshold that decides between seek and no-seek (the green line is for another heuristic, more accurate, but impractical, so I won’t detail it).

Clearly our heuristic under-estimates the threshold. It will seek more often than it should, and that’s what we want: the cost of seeking when we shouldn't have is far lower than the cost of not seeking when we should have, because that last cost grows to infinity.

A pedantically formal way to prove that the heuristic undershoots (and is thus safe) is to derive it from a cost analysis:

    Cost(no-seek) < Cost(seek)
<=> Cost(decode x -> j) + Cost(decode j -> y) < Cost(seek to j) + Cost(flush) + Opportunity cost + Cost(decode j -> y)

# Dropping Cost(seek to j), reasonable when j is close to x
# Dropping Cost(decode j -> y) from both sides

<=> Cost(decode x -> j) < Cost(flush) + Opportunity cost

# Dropping Cost(flush) which we can't know in practice
# This why we undershoot: we can't account for all costs.
# Now with d = average decoding time of a frame:

Cost(decode x -> j) < Opportunity cost
=> (j - x).d < num_buffered_frames .d
=> (j - x) < num_buffered_frames
=> (j - x) < frame_reorder_buffer_size + thread_count - 1

---

[1] well, we always seek unless j happens to also be the keyframe of x (as in ...j...x...y...). If we were to seek in this scenario, we would seek backwards to j and then re-decode all frames up to x, which brings us back to where we already are.
[2] num_ffmpeg_threads is AVCodecContext.thread_count, and here we assume the FRAME type of FFmpeg parallelism, which is the default.
[3] frame_reorder_buffer_size is has_b_frame in ffmpeg, which I’m renaming to avoid confusion. It’s a quantity, not a bool.