I’m still haunted by the slow VP3/Theora decoder in FFmpeg. While profiling reveals that most of the decoding time is spent in a function named unpack_vlcs(), I have been informed that finer-grained profiling indicates that the vast majority of that time is spent evaluating the following if statement:

  if (coeff_counts[fragment_num] > coeff_index)
    continue;

I put counters before and after that statement and ran the good old Big Buck Bunny 1080p movie through it. These numbers indicate, per frame, the number of times the if statement is evaluated and the number of times it evaluates to true:

[theora @ 0x1004000]3133440, 50643
[theora @ 0x1004000]15360, 722
[theora @ 0x1004000]15360, 720
[theora @ 0x1004000]0, 0
[theora @ 0x1004000]13888, 434
[theora @ 0x1004000]631424, 10711
[theora @ 0x1004000]2001344, 36922
[theora @ 0x1004000]1298752, 22897
[...]

Thus, while decoding the first frame, the if statement is evaluated over 3 million times but further action (i.e., decoding a coefficient) is only performed 50,000 times. Based on the above sample, each frame sees about 2 orders of magnitude more evaluations than are necessary.

Clearly, that if statement needs to go.

A frame of VP3/Theora video is comprised of a series of 8×8-sample fragments spread across the Y, U, and V frames. As the VLCs are decoded, the fragments are filled in with 64 coefficients. Most of the coefficients are supposed to be zero (this assumption is a big part of the compression). The algorithm decodes all of the 0th (DC) coefficients for all fragments first, then all the 1st (AC) coefficients, then 2nd, and so on down to all 63rd coefficients. However, since many fragments encode well fewer than 64 non-zero coefficients, many fragments are marked as end-of-block (EOB) after decoding the last non-zero coefficient for the fragment. Whether a fragment has been completely decoded yet is the condition that the gluttonous if statement is evaluating.

The decoder essentially maintains an array indicating — true or false — whether a fragment’s coefficients have yet to be fully decoded (not exactly true, but close enough). Here’s a crazy idea drawing from concepts presented in any introductory computer science course: use a list instead of an array. In doing so, the decoder can drop fragments from the list once they have reached EOB and then only traverse the fragments that still have coefficients in the bitstream.

I feel a little silly for not having thought of this sooner. But to be fair, no one else did, either. Though it’s not unreasonable to think that someone did, but was justifiably daunted by the cascading data structures in place for the decoding process.

So I implemented the list. I’ll spare you the fine details except to mention that I can’t eliminate the if statement entirely. But I did reduce its iterations drastically. As a first level performance measurement, I checked how many iterations are now performed vs. before. Compare these numbers with those from the beginning of the post:

[theora @ 0x1004000]57841, 50643
[theora @ 0x1004000]5280, 722
[theora @ 0x1004000]5280, 720
[theora @ 0x1004000]0, 0
[theora @ 0x1004000]868, 434
[theora @ 0x1004000]17679, 10711
[theora @ 0x1004000]37659, 36922
[theora @ 0x1004000]25435, 22897

Tens of thousands of iterations rather than several million? Doing well so far. Let’s evaluate the performance on more of a macro level by measuring wall clock execution time while decoding the entire Big Buck Bunny 1080p short, best run out of 2, between FFmpeg (before and after optimization) as well as libtheora 1.1. Command lines:

time ffmpeg -an -i big_buck_bunny_1080p_stereo.ogg -f null -y /dev/null
time dump_video big_buck_bunny_1080p_stereo.ogg > /dev/null

The results on my Core 2 Duo 2.0 GHz Mac Mini (Mac OS X 10.5) were thus:

6:36 - FFmpeg, before list optimization
5:06 - FFmpeg, after list optimization
4:22 - libtheora 1.1

So, substantial speedup, if I do say so myself.

A curious item about the data is the user vs. sys times. Here is the raw ‘time’ output for each of the best runs:

FFmpeg, before VP3 list optimization:
real    6m36.337s
user    6m18.659s
sys     0m16.217s

FFmpeg, after VP3 list optimations:
real    5m6.914s
user    4m50.535s
sys     0m15.838s

libtheora:
real    4m22.110s
user    4m19.744s
sys     0m1.756s

Evaluating performance based on user time instead of real time further narrows the gap between FFmpeg and libtheora. I’m open to theories (and hard data) explaining the wide discrepancy between the sys times for each program. I also need to note that this round of testing took into account dconrad’s advice from the last post on this matter which is why I tested FFmpeg using ‘-f null’ instead of ‘-f yuv4mpegpipe’ while modifying libtheora’s dump_video.c program to comment out this fwrite() call:

fwrite(ycbcr[pli].data+ycbcr[pli].stride*i, 1,
  ycbcr[pli].width, outfile);

I hope to get this patch approved and into FFmpeg SVN soon. It will be interesting to profile the VP3/Theora decoder afterwards since, ideally, unpack_vlcs() will not dominate the statistics as before. We might find some other notable hotspots.