[vorbis-dev] optimization patches

[Segher Boessenkool]

> Is dithering really useful for samples when the current dynamic range is is 
> using a good portion of the total range?  I'd expect it to just add [white if 
> not colored] noise and adding noise is generally frowned upon.  Of course, for 
> very low amplitude, the value of dithering is understood.

I am told that most soundcards don't have D/A convertors which do
oversampling/dithering stuff. There was a thread at mp3encoder recently.
You are right with dithering on, it sounds more noisy, but in a way, it
sounds better as well. Anyway, it was just a quick hack. This kind of
functionality should most likely go in an output plugin or something,
if anywhere. Well, try it out.

> 
> > codebook.[ch]
> > bitwise.[ch]
> > bookinternal.h
> > sharedbook.c
> > 	decode the first N bits of a huffman word in one step via table
> > 	look up.
> 
> Long ago I did Huffman this way, but found the additional lookup to be large 
> and negate the benefits if the tree was oddly proportioned.  I'd assume you'd 
> not do this unless it worked, so I'll look and see if I learn something ;-)

The biggest lookup is 8 or 9 bits, currently. Very much unbalanced huffman
trees do indeed suffer, but in the current code, the majority of huffman
time is taken by the residu, and that tree is reasonably balanced.

> 
> > 	The huffman decoding could be much more efficient (i.e., no
> > 	decode tree necessary -> saves a lot of cache, and decoding
> > 	time O(log log N) instead of O(log N), where N is alphabet
> > 	size), if the huffman tree would be left (or right; I prefer
> > 	left) aligned.
> 
> Please describe in more detail what you mean by left/right aligned.  I assume 
> you mean something about the hufftree structure rather than the bitsex of the 

Yep. It means all longer huffman codewords are more to the left of the
tree than the shorter huffman codewords. Btw, in this algorithm you
do _not_ have to construct a huffman tree; you only need to know the
lengths of the codewords.

> bitpacker (bitwise.c)?  There is generally method to my madness, but I'm 

It would be nice to have the 1st bit for huffman decoding come out of the
bitpacker msb, but it's not really necessary.

> mostly good at theoretical complexity optimization, not so much optimizing for 
> raw practicalities (lack of experience).

This is theoretical :-), only works well in practice as well.

> 
> > 	The code I submit now could be more clean, I know. Seems to
> > 	work though. Weird.
> 
> ...however *that* statement does not instill confidence.  Are you concerned 
> about the code clenliness or some other problem?  I worry about committing 
> things titled 'seems to work.  weird.' ;-)
> 

I added the _huff routines to bitwise.c, though I don't use them. These
routines are not very clean. And maybe someone else should check if I do
the right thing in out-of-bits conditions. There are some other places in
Vorbis which don't handle this ok as well, I think.

If you drop this _huff routines, the only problems remaining are
cosmetical. The 'seems to work, weird' only applied to my old version
of the code (which you don't have, fortunately |-)

> > 	unrolled && rerolled the decodevs loops.
> 
> Yeah, *that* little bit of ugliness I actually somewhat regret.

???

> 
> > envelope.c
> > 	if (fabs(...) < min) creates horrible assembler (gcc 2.95, x86),
> > 	so changed to  if (... < min && ... > -min). muchos faster.
> 
> Intersting.  I'll keep it in mind.

I added -mno-ieee-fp to the compile flags; I _think_ fabs() is ok in
this case. I'll test; no ieee is a huge speedup on x86 anyway.

> 
> > lsp.c
> > 	put the fromdB() before linearmap
> 
> Good.  I'll be squashing this even further.
> 

Great :-)

> > scales.h
> > 	todB_nn() for non-negative values. fabs() is horror.
> 
> OK, but in most cases I'm using todB not knowing if I'm >= 0 or just real.

Well, todB(a * a) has a * a >= 0. This is a lot of the todB's.

Dagdag,

Segher

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'vorbis-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.