[FFmpeg-devel] [PATCH] 'vorbis_residue_decode' optimizations

Siarhei Siamashka siarhei.siamashka
Tue Sep 2 05:03:15 CEST 2008

On Sunday 31 August 2008, Michael Niedermayer wrote:
> On Sun, Aug 31, 2008 at 01:18:14PM +0300, Siarhei Siamashka wrote:
> > Regarding 'vorbis_residue_decode' function, it probably makes sense to
> > optimize these loops:
> >
> > if(dim==2) {
> >     for(k=0;k<step;++k) {
> >         coffs=get_vlc2(gb, codebook.vlc.table, codebook.nb_bits, 3) * 2;
> >         vec[voffs+k     ]+=codebook.codevectors[coffs  ];  // FPMATH
> >         vec[voffs+k+vlen]+=codebook.codevectors[coffs+1];  // FPMATH
> >     }
> > } else if(dim==4) {
> >     for(k=0;k<step;++k, voffs+=2) {
> >         coffs=get_vlc2(gb, codebook.vlc.table, codebook.nb_bits, 3) * 4;
> >         vec[voffs       ]+=codebook.codevectors[coffs  ];  // FPMATH
> >         vec[voffs+1     ]+=codebook.codevectors[coffs+2];  // FPMATH
> >         vec[voffs+vlen  ]+=codebook.codevectors[coffs+1];  // FPMATH
> >         vec[voffs+vlen+1]+=codebook.codevectors[coffs+3];  // FPMATH
> >     }
> > } ...
> >
> > 'get_vlc2' call could be replaced with some GET_VLC/GET_RL_VLC variant
> > so that the number of intermediate excessive UPDATE_CACHE operations is
> > minimized.
> These are all nice ideas but they arent really related to the change here
> so patch welcome
> [...]

Thank you for applying the previous patch.

Now here is some preliminary version (not intended for applying yet) of a new
patch which tries to implement the ideas which were quoted above.

The first thing that is important for performance is that a vast majority
of 'get_vlc2' calls perform only a singe table lookup. Probability of single
table lookup is usually higher than 90% when V_NB_BITS is equal to 8 and more
than 95% if V_NB_BITS is increased to 9. And that results not only in a lower
number of instructions executed, but also is much better for branch predictor
reducing conditional jump overhead. I used a test code from 
'vorbis_vlcfreq.diff' (ugly hack) to measure these probabilities and 
get the statistics.

As sometimes 'codebook_setup->maxdepth' is lower than V_NB_BITS, there is no
point in creating larger VLC tables, it saves memory and reduces the number of
cache misses. That's why 'if(codebook_setup->maxdepth < V_NB_BITS)
codebook_setup->nb_bits=codebook_setup->maxdepth' line was added to code.

There is no point doing more than one UPDATE_CACHE operation per GET_VLC.
Moreover, as GET_VLC reads at most 11 bits (and typically just V_NB_BITS 
bits) per table lookup, it is possible to do UPDATE_CACHE once per two or
even three calls to GET_VLC. Generic SHOW_UBITS macro is also quite expensive.
As the first table lookup in GET_VLC always uses a constant number of bits 
as index, it is possible to pre-calculate bitmask and use it to speed up code.

Most performance critical parts of 'vorbis_residue_decode' function were
extracted into separate 'vorbis_residue_decode_inner_loop_dimN' functions
for benchmarking purposes. Log from oprofile typically looks like this (for
256 kbit vorbis file):

CPU: PIII, speed 1862.24 MHz (estimated)
Counted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit 
mask of 0x00 (No unit mask) count 99991
samples %        image name              symbol name
1062    12.9449  ffmpeg_g                ff_imdct_half_sse
976     11.8966  ffmpeg_g                vorbis_residue_decode_inner_loop_dim2
953     11.6163  ffmpeg_g                ff_vorbis_floor1_render_list
745      9.0809  ffmpeg_g                vorbis_residue_decode
671      8.1789  ffmpeg_g                pass_sse.loop
577      7.0332  ffmpeg_g                vorbis_floor1_decode
389      4.7416  ffmpeg_g                vorbis_parse_audio_packet
384      4.6806  ffmpeg_g                fft16_sse
378      4.6075  ffmpeg_g                vorbis_residue_decode_inner_loop_dim4
290      3.5349  libc-2.7.so             (no symbols)
266      3.2423  ffmpeg_g                vorbis_inverse_coupling_sse
224      2.7304  ffmpeg_g                vector_fmul_window_sse
161      1.9625  ffmpeg_g                fft8_sse
153      1.8649  ffmpeg_g                vector_fmul_sse

Or sometimes like this (for 64 kbit vorbis file):

CPU: PIII, speed 1862.24 MHz (estimated)
Counted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit 
mask of 0x00 (No unit mask) count 99991
samples %        image name              symbol name
1112    16.8536  ffmpeg_g                ff_imdct_half_sse
891     13.5041  ffmpeg_g                ff_vorbis_floor1_render_list
656      9.9424  ffmpeg_g                pass_sse.loop
408      6.1837  ffmpeg_g                vorbis_residue_decode
384      5.8199  ffmpeg_g                fft16_sse
372      5.6381  ffmpeg_g                vorbis_floor1_decode
349      5.2895  ffmpeg_g                vorbis_parse_audio_packet
285      4.3195  ffmpeg_g                vorbis_residue_decode_inner_loop_dim8
252      3.8193  ffmpeg_g                vector_fmul_window_sse
240      3.6375  ffmpeg_g                vorbis_inverse_coupling_sse
237      3.5920  libc-2.7.so             (no symbols)
219      3.3192  ffmpeg_g                vorbis_residue_decode_inner_loop_dim2
161      2.4401  ffmpeg_g                fft8_sse
142      2.1522  ffmpeg_g                float_to_int16_interleave_sse2
118      1.7884  ffmpeg_g                vector_fmul_sse
110      1.6672  ffmpeg_g                build_table
83       1.2580  ffmpeg_g                av_interleave_packet_per_dts
79       1.1973  ffmpeg_g                pcm_encode_frame
72       1.0912  ffmpeg_g                output_packet
>51      0.7730  ffmpeg_g                vorbis_residue_decode_inner_loop_dim4
35       0.5305  ffmpeg_g                av_encode
33       0.5002  ffmpeg_g                compute_pkt_fields2

In any case, 'vorbis_residue_decode_inner_loop_dimN' functions all together
usually take most of the time of 'vorbis_residue_decode' execution.

The attached patch already provides a visible performance improvement (up to 
5% for 256 kbit vorbis file, lower bitrate files gain less). But these
functions can be probably optimized using assembly (as gcc really does a poor 
job allocating registers here) and SIMD instructions. I wonder of it makes 
sense still inlining them, or moving them to dsputil would be also ok? 
Calling them via a pointer also makes it possible to create several versions 
with 'codebook_nb_bits' and 'codebook_nb_bits_mask' hardcoded as immediate 
operands in order to optimize registers allocation (values 8 and 11 
for 'codebook_nb_bits' might be used) and also in order to do UPDATE_CACHE
operations in an optimal way (once per 3 GET_VLC or once per 2 GET_VLC
operations). A pointer to the appropriate function could be set in each
instance of 'vorbis_codebook'

If assembly optimizations are going to be used for dealing with VLC tables,
this should be covered well by regressions tests in order to avoid potential
sudden breakages if changes may get introduced to the implementations of VLC
tables format in the future.

Other things to optimize later are 'vorbis_floor0_decode' as it is *very* slow 
when used (you have provided a link to an interesting file in one of the 
previous posts: http://www.gnu.org/fun/jokes/eternal-flame.ogg). And also
'render_line', which is a major contributor to 'ff_vorbis_floor1_render_list' 
time from the oprofile logs above. Both can be optimized quite trivially.
After implementation of a faster split-radix FFT was added, all these
performance bottlenecks are now much more visible ;)

Best regards,
Siarhei Siamashka
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vorbis_vlcfreq.diff
Type: text/x-diff
Size: 1741 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20080902/fd379821/attachment.diff>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vorbis_vlc_opt_preview.diff
Type: text/x-diff
Size: 7937 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20080902/fd379821/attachment-0001.diff>

More information about the ffmpeg-devel mailing list