[Tremor] optimization thoughts on the codebook and other parts of the Tremor source

[Ethan Bordeaux]

Hi, I'm looking at speed optimization options for the Tremor lowmem version
of the Ogg Vorbis decoder.  One area I am looking at closely is the codebook
search.  Specifically, the Huffman tree traversal (the set of for loops
inside vorbis_book_decodevv_add commented with things like 8/8, 8/16, etc).
I thought I could potentially remove the for loop entirely and just check
for valid data at the leaf of the tree.  However, it seems that this doesn't
work because the encoder doesn't set the MSb to 1 when the leaf is at the
maximum tree depth, so it's using the termination condition from the for
loop rather than the test inside the loop to exit.  My thought was that I
could change the codebook initialization routine to add a 1 to the MSb of
all leaf locations, including those at the end of the tree.  That should
remove one additional test as I can just keep shifting lok by 1 until I find
my data.

My questions are:

1.  Is my understanding of the tree traversal correct?
2.  Is there a reason why this optimization wouldn't work?  It's a little
baffling to me why the encoder wouldn't indicate valid data at the maximum
depth by setting the MSb, but there might be something I'm missing.
3.  Is there an efficient way to identify all the leaf locations?  My first
thought was to replicate the codebook search code and feed in all valid
values for lok, see if I reach the maximum depth in the search, and if I do
set the MSb to 1.  However, this is a pretty dumb exhaustive search while
will add a fair bit of delay in the initialization of the codec.  Also, I'm
not sure if all trees are valid for all values of lok.  Would this work/is
there a better way?

If anyone has any thoughts on where else to focus optimization time I'd
appreciate it.  I've already done some work reordering the codebook search
code to optimize for mono/stereo files, and that was quite helpful.

Thanks!

Ethan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.xiph.org/pipermail/tremor/attachments/20090410/c14b14b2/attachment.htm