Postcards from the Bleeding Edge
Saturday, September 25, 2010

  Interesting Failure #4 - Not speeding up Libsamplerate in 2008

My initial motivation for fooling with libsamplerate was that I was working on mixing down a HUGE, 12 hour, 12 track, 96khz audio recording, to a portable machine that only supported 44.1khz output, so I was constantly using libsamplerate to mix down and convert dozens of songs to something I could actually hear, and spending 40 minutes per iteration fiddling with my thumbs waiting for that to happen.

I also had a hardware audio server project coming up that looked like it might use the then-new Arm VFP instructions for samplerate conversion and I wanted to learn how to vectorize code on that processor. Not having an Arm 926 yet to play with I started playing with the Intel/Arm SSE2 and SSE3 extensions and various compilers (gcc, icc) and their options - to see what I could do on that chip series to improve matters.

It also bugged me that the default samplerate converter for pulseaudio - now a defacto standard - is speex-float1, which has a S/N ratio that I haven't been able to find.

You CAN hear the difference between speex-float1 and libsamplerate's medium to high modes, but unless you are a passionate listener to high quality (24 bit) music and video at non-44.1khz sample rates, it's difficult. The first thing I do upon getting a new Linux box is switch it to libsamplerate medium from speex-float1... I listen to a lot of music. The added computational overhead puts an atom on the moon, but bigger processors do ok.

So there I was, with too much time on my hands between mixdowns... With full source code to my problem children...

When I oprofiled the code, bells went off in my head - something like 99% of the mix was being spent in a pair of fairly small routines that looked very optimizable at first glance. In particular, they weren't using SSE at all! Even though the hardware could process two doubles at the same time through the pipe, the C code didn't compile down to anything even close to that...

So I rewrote those core routines using the SSE intrinsics and got them to work on both x86 and x86_64 mode. The generated code got really dense, but the instruction length got larger.

The initial results were encouraging, especially on x86_64. By taking better advantage of all the registers available, AND pushing two doubles through the pipeline, and eliminating/parallelizing several float->double conversions, I got anywhere from a 14% to 50% speed enhancement on my hardware. The x86_64 scaled up to more channels far better than the x86 did, too, showing that one of the big problems in the code was register pressure.

I also cut the C code size by a considerable amount with some pre-processor magic. I was HAPPY, and announced my initial results on the mailing list... and started work on making something more generic and general purpose than my initial (two channel only) hacks. Doing a CUDA version even looked plausible and I was dying to try working in that...

In digging into the generated assembly I found that the gcc compilers would arbitrarily reschedule software prefetching from where I thought it should be to where it did little good.

So I went to work on making the code better, reading instruction tables, clock counts, and generally having a merry time researching the darkest details of the x86_64 implementations of both Intel and AMD. I remember that instruction decoding was fascinating - I learnt one hell of a lot about how the various levels of SSE actually worked, and about the schism in instruction set extensions that occurred between AMD and Intel after SSE3, and about how difficult the C intrinsics were to actually use in a language that didn't have a native 128bit type, or conception of vector arithmetic. In frustration, I found myself reminiscing about APL one day...

Ultimately I produced a pure x86_64 assembly version which did up to 8 channels of samplerate conversion, and met most of my requirements, among many other things the average instruction length was shorter to fit into the decoding windows better... but it was difficult to maintain, debug, and link to, especially as it worked best as inline assembly, not as a function call, and it didn't outperform my initial attempts by very much.

So, as my final shot at the problem, I rewrote the pure assembly into something that could be inlined using gcc's inline assembly extensions. It used up the entire x86_64 register set (this always makes an assembly language programmer feel warm and fuzzy - and most people would be shocked at how few registers most subroutines actually use), BUT: it wouldn't compile due to not having enough virtual registers defined in the gcc compiler.

I made one small patch to the compiler to fix that, and filed a bug on it. (Which the gcc developers decided to ignore)

Then I started testing with more processors than I'd had on hand at the beginning.

A lot of oprofiling later...

On the then-new Atom processor, in 64 bit mode, the optimized SSE code was actually SLOWER than the unoptimized code. I puzzled over this for a while but it wasn't until I noticed that on an old Opteron, the code also lost performance when doubles were used in the highest quality samplerate conversion setting that I realized the source of the problem.

The size of the lookup table basically wiped out the L2 and L3 cache on any but the largest Intel processors available a the time. The large stride did terrible things to hardware prefetching, too. My hand placed software prefetches worked well on only a few processors.

So I'd goofed (at least for older/cheaper hardware) by optimizing for floating point pipelining performance where memory bandwidth was more key to the performance of the algorithm. I easily forgive myself for this - it was impossible to "know" this without doing all the work I did delving into the algorithm.

While a CUDA version would still be interesting to try, most CUDA hardware available then (and most now!) doesn't have a lot of support for floating point math using doubles... And I think memory bandwidth would still be a problem.

And... building a version that had sufficient abstractions internally to take advantage of the dozens of different CPU types - much less CUDA! - the core loops would have to be optimized for proved to be hard too. It required far more object oriented coding in C than I cared to do (icc has a built in method making the support of different instruction set extensions easier, and I would like it if gcc had the same capability), and some tricky and hard to maintain cpu recognition routines.

Finally I found that when I compiled the original algorithm for the normal x86 register set, not SSE2, on x86_64, that it performed almost identically to my extensively hand optimized code.

This was discouraging in the utmost. I gave up.

The memory bandwidth limitation would be even worse on the Arm. Although using the VFP floating point unit made using libsamplerate feasible in the first place, I felt that it would perform badly on that chip at almost any sample rate conversion setting. So in the end I dropped that portion of the project, too.

As I write that hardware project is still x86 based, and we ended up using a DAC that was capable of sample rates all the way up to 192Khz, natively.

I bought a 3x faster Intel box, finished the massive recording project, and switched to recording most of my source material at 44.1khz, 32 bit. It would be interesting to play with the code and compilers again, once things like the VFX extension become more common, and Arms get more cache... Maybe the compilers have improved some...

But I'm also considerably more deaf than I was when I started caring about audio quality and find it harder and harder to care as overall cpu performance has doubled again since I started working on this. If anyone cares, I'll dig up the bzr tree.

Labels: ,

 
David Täht writes about politics, space, copyright, the internet, audio software, operating systems and surfing.


Resume,Songs,
My new blog, NeX-6, My facebook page
Orgs I like
The EFF - keeping free speech in the world
Musical stuff I like
Jeff, Rick, Ardour, Jack
Prior Rants - 49... and trying to find my navel Wheels down on mars! Tracking the landing of Curiosity, from Seattle spotting NEOs from around venus's orbit Asteroids as lunar orbit resources SOPA is bad news Departing France for England, then 'home'. An incredible stream of co-incidences passing me b... 12 suggestions for startups Steve Jobs, RIP.
Best of the blog:
Uncle Bill's Helicopter - A speech I gave to ITT Tech - Chicken soup for engineers
Beating the Brand - A pathological exploration of how branding makes it hard to think straight
Inside the Internet Mind - trying to map the weather within the global supercomputer that consists of humans and google
Sex In Politics - If politicians spent more time pounding the flesh rather than pressing it, it would be a better world
Getting resources from space - An alternative to blowing money on mars using NEAs.
On the Columbia - Why I care about space
Authors I like:
Doc Searls
Where's Cherie?
UrbanAgora
Jerry Pournelle
The Cubic Dog
Evan Hunt
The Bay Area is talking
Brizzled
Zimnoiac Emanations
Eric Raymond
Unlocking The Air
Bob Mage
BroadBand & Me
SpaceCraft
Selenian Boondocks
My Pencil
Transterrestial Musings
Bear Waller Hollar
Callahans
Pajamas Media BlogRoll Member

If you really want to, you can poke through the below links as well.

ARCHIVES
06/09/2002 - 06/16/2002 / 07/28/2002 - 08/04/2002 / 08/11/2002 - 08/18/2002 / 08/18/2002 - 08/25/2002 / 08/25/2002 - 09/01/2002 / 09/22/2002 - 09/29/2002 / 11/10/2002 - 11/17/2002 / 12/15/2002 - 12/22/2002 / 12/22/2002 - 12/29/2002 / 12/29/2002 - 01/05/2003 / 01/05/2003 - 01/12/2003 / 01/19/2003 - 01/26/2003 / 01/26/2003 - 02/02/2003 / 02/09/2003 - 02/16/2003 / 02/16/2003 - 02/23/2003 / 03/02/2003 - 03/09/2003 / 03/16/2003 - 03/23/2003 / 04/06/2003 - 04/13/2003 / 04/13/2003 - 04/20/2003 / 04/20/2003 - 04/27/2003 / 05/04/2003 - 05/11/2003 / 05/18/2003 - 05/25/2003 / 05/25/2003 - 06/01/2003 / 06/01/2003 - 06/08/2003 / 06/08/2003 - 06/15/2003 / 06/15/2003 - 06/22/2003 / 06/22/2003 - 06/29/2003 / 06/29/2003 - 07/06/2003 / 07/20/2003 - 07/27/2003 / 07/27/2003 - 08/03/2003 / 08/03/2003 - 08/10/2003 / 08/10/2003 - 08/17/2003 / 08/17/2003 - 08/24/2003 / 08/24/2003 - 08/31/2003 / 08/31/2003 - 09/07/2003 / 09/07/2003 - 09/14/2003 / 09/14/2003 - 09/21/2003 / 09/21/2003 - 09/28/2003 / 09/28/2003 - 10/05/2003 / 10/05/2003 - 10/12/2003 / 10/12/2003 - 10/19/2003 / 10/19/2003 - 10/26/2003 / 10/26/2003 - 11/02/2003 / 11/02/2003 - 11/09/2003 / 11/09/2003 - 11/16/2003 / 11/30/2003 - 12/07/2003 / 12/07/2003 - 12/14/2003 / 12/14/2003 - 12/21/2003 / 12/28/2003 - 01/04/2004 / 01/11/2004 - 01/18/2004 / 01/18/2004 - 01/25/2004 / 01/25/2004 - 02/01/2004 / 02/01/2004 - 02/08/2004 / 02/08/2004 - 02/15/2004 / 02/15/2004 - 02/22/2004 / 02/22/2004 - 02/29/2004 / 02/29/2004 - 03/07/2004 / 03/14/2004 - 03/21/2004 / 03/21/2004 - 03/28/2004 / 03/28/2004 - 04/04/2004 / 04/04/2004 - 04/11/2004 / 04/11/2004 - 04/18/2004 / 04/18/2004 - 04/25/2004 / 04/25/2004 - 05/02/2004 / 05/02/2004 - 05/09/2004 / 05/09/2004 - 05/16/2004 / 05/16/2004 - 05/23/2004 / 05/30/2004 - 06/06/2004 / 06/06/2004 - 06/13/2004 / 06/13/2004 - 06/20/2004 / 06/20/2004 - 06/27/2004 / 06/27/2004 - 07/04/2004 / 07/04/2004 - 07/11/2004 / 07/11/2004 - 07/18/2004 / 07/18/2004 - 07/25/2004 / 08/08/2004 - 08/15/2004 / 08/22/2004 - 08/29/2004 / 08/29/2004 - 09/05/2004 / 09/05/2004 - 09/12/2004 / 09/19/2004 - 09/26/2004 / 09/26/2004 - 10/03/2004 / 10/03/2004 - 10/10/2004 / 10/10/2004 - 10/17/2004 / 10/17/2004 - 10/24/2004 / 10/24/2004 - 10/31/2004 / 10/31/2004 - 11/07/2004 / 11/07/2004 - 11/14/2004 / 11/14/2004 - 11/21/2004 / 11/21/2004 - 11/28/2004 / 11/28/2004 - 12/05/2004 / 12/05/2004 - 12/12/2004 / 12/12/2004 - 12/19/2004 / 12/19/2004 - 12/26/2004 / 12/26/2004 - 01/02/2005 / 01/02/2005 - 01/09/2005 / 01/16/2005 - 01/23/2005 / 01/23/2005 - 01/30/2005 / 01/30/2005 - 02/06/2005 / 02/06/2005 - 02/13/2005 / 02/13/2005 - 02/20/2005 / 02/20/2005 - 02/27/2005 / 02/27/2005 - 03/06/2005 / 03/06/2005 - 03/13/2005 / 03/27/2005 - 04/03/2005 / 04/03/2005 - 04/10/2005 / 04/10/2005 - 04/17/2005 / 05/29/2005 - 06/05/2005 / 06/05/2005 - 06/12/2005 / 06/12/2005 - 06/19/2005 / 06/19/2005 - 06/26/2005 / 06/26/2005 - 07/03/2005 / 07/03/2005 - 07/10/2005 / 07/10/2005 - 07/17/2005 / 07/24/2005 - 07/31/2005 / 07/31/2005 - 08/07/2005 / 08/07/2005 - 08/14/2005 / 08/14/2005 - 08/21/2005 / 08/21/2005 - 08/28/2005 / 08/28/2005 - 09/04/2005 / 09/04/2005 - 09/11/2005 / 09/11/2005 - 09/18/2005 / 09/18/2005 - 09/25/2005 / 09/25/2005 - 10/02/2005 / 10/02/2005 - 10/09/2005 / 10/09/2005 - 10/16/2005 / 10/16/2005 - 10/23/2005 / 10/23/2005 - 10/30/2005 / 10/30/2005 - 11/06/2005 / 11/06/2005 - 11/13/2005 / 11/13/2005 - 11/20/2005 / 11/20/2005 - 11/27/2005 / 11/27/2005 - 12/04/2005 / 12/04/2005 - 12/11/2005 / 12/11/2005 - 12/18/2005 / 12/18/2005 - 12/25/2005 / 01/01/2006 - 01/08/2006 / 01/08/2006 - 01/15/2006 / 01/15/2006 - 01/22/2006 / 01/22/2006 - 01/29/2006 / 01/29/2006 - 02/05/2006 / 02/19/2006 - 02/26/2006 / 03/05/2006 - 03/12/2006 / 03/19/2006 - 03/26/2006 / 03/26/2006 - 04/02/2006 / 04/02/2006 - 04/09/2006 / 04/09/2006 - 04/16/2006 / 04/23/2006 - 04/30/2006 / 05/07/2006 - 05/14/2006 / 05/14/2006 - 05/21/2006 / 05/21/2006 - 05/28/2006 / 06/04/2006 - 06/11/2006 / 06/11/2006 - 06/18/2006 / 06/18/2006 - 06/25/2006 / 06/25/2006 - 07/02/2006 / 07/02/2006 - 07/09/2006 / 07/09/2006 - 07/16/2006 / 07/23/2006 - 07/30/2006 / 08/06/2006 - 08/13/2006 / 08/13/2006 - 08/20/2006 / 09/03/2006 - 09/10/2006 / 09/17/2006 - 09/24/2006 / 09/24/2006 - 10/01/2006 / 10/01/2006 - 10/08/2006 / 10/22/2006 - 10/29/2006 / 11/19/2006 - 11/26/2006 / 11/26/2006 - 12/03/2006 / 12/03/2006 - 12/10/2006 / 12/10/2006 - 12/17/2006 / 12/17/2006 - 12/24/2006 / 12/24/2006 - 12/31/2006 / 01/07/2007 - 01/14/2007 / 01/14/2007 - 01/21/2007 / 01/28/2007 - 02/04/2007 / 02/11/2007 - 02/18/2007 / 02/18/2007 - 02/25/2007 / 02/25/2007 - 03/04/2007 / 03/04/2007 - 03/11/2007 / 03/18/2007 - 03/25/2007 / 04/01/2007 - 04/08/2007 / 04/08/2007 - 04/15/2007 / 04/15/2007 - 04/22/2007 / 04/22/2007 - 04/29/2007 / 04/29/2007 - 05/06/2007 / 05/06/2007 - 05/13/2007 / 05/20/2007 - 05/27/2007 / 05/27/2007 - 06/03/2007 / 06/03/2007 - 06/10/2007 / 06/10/2007 - 06/17/2007 / 06/17/2007 - 06/24/2007 / 07/01/2007 - 07/08/2007 / 07/08/2007 - 07/15/2007 / 07/22/2007 - 07/29/2007 / 07/29/2007 - 08/05/2007 / 08/05/2007 - 08/12/2007 / 08/26/2007 - 09/02/2007 / 09/09/2007 - 09/16/2007 / 09/23/2007 - 09/30/2007 / 09/30/2007 - 10/07/2007 / 10/07/2007 - 10/14/2007 / 10/14/2007 - 10/21/2007 / 10/21/2007 - 10/28/2007 / 10/28/2007 - 11/04/2007 / 11/04/2007 - 11/11/2007 / 11/11/2007 - 11/18/2007 / 11/18/2007 - 11/25/2007 / 11/25/2007 - 12/02/2007 / 12/02/2007 - 12/09/2007 / 12/09/2007 - 12/16/2007 / 12/16/2007 - 12/23/2007 / 12/23/2007 - 12/30/2007 / 01/06/2008 - 01/13/2008 / 02/03/2008 - 02/10/2008 / 02/17/2008 - 02/24/2008 / 02/24/2008 - 03/02/2008 / 03/02/2008 - 03/09/2008 / 03/09/2008 - 03/16/2008 / 03/16/2008 - 03/23/2008 / 03/23/2008 - 03/30/2008 / 03/30/2008 - 04/06/2008 / 04/20/2008 - 04/27/2008 / 04/27/2008 - 05/04/2008 / 05/04/2008 - 05/11/2008 / 05/11/2008 - 05/18/2008 / 05/18/2008 - 05/25/2008 / 05/25/2008 - 06/01/2008 / 06/01/2008 - 06/08/2008 / 06/08/2008 - 06/15/2008 / 06/15/2008 - 06/22/2008 / 06/22/2008 - 06/29/2008 / 07/06/2008 - 07/13/2008 / 07/13/2008 - 07/20/2008 / 07/20/2008 - 07/27/2008 / 07/27/2008 - 08/03/2008 / 08/03/2008 - 08/10/2008 / 08/10/2008 - 08/17/2008 / 08/17/2008 - 08/24/2008 / 08/31/2008 - 09/07/2008 / 09/07/2008 - 09/14/2008 / 09/14/2008 - 09/21/2008 / 09/21/2008 - 09/28/2008 / 09/28/2008 - 10/05/2008 / 10/05/2008 - 10/12/2008 / 10/12/2008 - 10/19/2008 / 10/19/2008 - 10/26/2008 / 10/26/2008 - 11/02/2008 / 11/02/2008 - 11/09/2008 / 11/09/2008 - 11/16/2008 / 11/16/2008 - 11/23/2008 / 12/07/2008 - 12/14/2008 / 12/21/2008 - 12/28/2008 / 12/28/2008 - 01/04/2009 / 01/18/2009 - 01/25/2009 / 01/25/2009 - 02/01/2009 / 03/22/2009 - 03/29/2009 / 05/10/2009 - 05/17/2009 / 05/17/2009 - 05/24/2009 / 05/31/2009 - 06/07/2009 / 06/14/2009 - 06/21/2009 / 06/21/2009 - 06/28/2009 / 06/28/2009 - 07/05/2009 / 07/05/2009 - 07/12/2009 / 07/12/2009 - 07/19/2009 / 07/26/2009 - 08/02/2009 / 08/09/2009 - 08/16/2009 / 08/23/2009 - 08/30/2009 / 09/06/2009 - 09/13/2009 / 09/20/2009 - 09/27/2009 / 09/27/2009 - 10/04/2009 / 10/04/2009 - 10/11/2009 / 10/11/2009 - 10/18/2009 / 10/18/2009 - 10/25/2009 / 10/25/2009 - 11/01/2009 / 11/29/2009 - 12/06/2009 / 12/27/2009 - 01/03/2010 / 01/31/2010 - 02/07/2010 / 02/07/2010 - 02/14/2010 / 02/28/2010 - 03/07/2010 / 03/07/2010 - 03/14/2010 / 03/28/2010 - 04/04/2010 / 04/18/2010 - 04/25/2010 / 05/16/2010 - 05/23/2010 / 05/30/2010 - 06/06/2010 / 06/13/2010 - 06/20/2010 / 06/20/2010 - 06/27/2010 / 07/04/2010 - 07/11/2010 / 07/11/2010 - 07/18/2010 / 07/18/2010 - 07/25/2010 / 08/08/2010 - 08/15/2010 / 08/29/2010 - 09/05/2010 / 09/05/2010 - 09/12/2010 / 09/19/2010 - 09/26/2010 / 09/26/2010 - 10/03/2010 / 10/10/2010 - 10/17/2010 / 10/17/2010 - 10/24/2010 / 10/31/2010 - 11/07/2010 / 11/28/2010 - 12/05/2010 / 12/05/2010 - 12/12/2010 / 12/12/2010 - 12/19/2010 / 12/26/2010 - 01/02/2011 / 03/06/2011 - 03/13/2011 / 03/13/2011 - 03/20/2011 / 05/22/2011 - 05/29/2011 / 08/07/2011 - 08/14/2011 / 08/14/2011 - 08/21/2011 / 09/18/2011 - 09/25/2011 / 10/02/2011 - 10/09/2011 / 10/09/2011 - 10/16/2011 / 11/06/2011 - 11/13/2011 / 01/15/2012 - 01/22/2012 / 04/22/2012 - 04/29/2012 / 06/24/2012 - 07/01/2012 / 08/05/2012 - 08/12/2012 / 08/11/2013 - 08/18/2013 /


Powered by Blogger