Counter Intuitive Results: Optimising an FFT routine for Speed

From: Paul Brown (postmaster_at_pwi.mailshell.com)
Date: 10/07/03 

Date: 7 Oct 2003 04:09:05 -0700

Thanks for the replies Tristan, Eric, Steven & Kurt. They have given
me some good leads.

I present justification for a lot of the comments that drew
(constructive) criticism below. Firstly, let me summarise the feedback
that has pointed me in the right direction :-

>> Steven
> 20.13: What's the best way of making my program efficient?
> A: By picking good algorithms and implementing them carefully.

<hand up> Count me in for that, there was no intention or suggestion
of micro-optimisation or use of inline assembler in my post. What I am
trying to find out is what algorithm is effective and what C syntax is
more efficient, albeit only on the small Turbo-C development system
that I have.
</hand up>

> http://www.eskimo.com/~scs/C-faq/top.html
Thanks, I am busy downloading the whole list by sequentially stepping
through all the URLs at this site.

> The biggest speed gains in an FFT (and most algorithms) come from much higher-
> level transformations. For example, our FFTW (www.fftw.org) ...

I see that I previously downloaded
   FFTW 3.0.1 is the latest official version of FFTW

a while back, I am overwhelmed with volume :
458 *.c files (2.9MB)
42 *.h files

Could take me a while to assimilate all of this.

> you should use a different routine than clock()
I thought I did quite well on the Athlon /Win98, synchronising on the
20ms ticks and counting in between I could improve resolution to
600ns. Still dependent on the system time sharing on the CPU though.

> The best resolution comes from reading the CPU cycle counter directly (see
> www.fftw.org/download.html for code to do this on many CPUs).
Yes, I knew there was something called the "software stopwatch",
hopefully I will come right with CYCLE.H.
I can't go and peep at this URL at the mo' as my C-FAQ download is
still stepping through each answer page. CYCLE.H has quite a bit of
code to it, I suppose I just chuck out most of the CPU specific code
and keep

_( Pentium cycle counter)
typedef unsigned long long ticks;
static __inline__ ticks getticks(void) {
 ticks ret;
 __asm__ __volatile__("rdtsc": "=A" (ret));
return ret; }

>> Tristan
I followed my usual method of
   QUERY GOOGLE -> READ -> FILTER -> POST

and using this I selected the four newsgroups that had hits on
   C Speed Optimisation FFT

> comp.lang.oberon
Subject: Re: Optimizing array bounds checking
Newsgroups: comp.lang.oberon

> comp.lang.functional
Subject: Re: Academia isn't interested...
Newsgroups: comp.lang.functional
....
But what you *can* do is generate low-level code from high-level
specifications. This has already been well-demonstrated in e.g. the
FFTW
(written in OCaml), which generates extremely efficient C-algorithms
for the FFT from specifications and specialises them for the given
architecture. This, however, is high-level programming again, not
low-level programming. There is no escape from imperativeness if you
work with von-Neumann architectures on a low level.

>> Eric

> You'd have to examine the actual generated code to have a hope
> of figuring out what's really happening in any particular case.
Don't want to do that, anyway my solution has to be fairly portable,
from me (design engineer) it goes to software engineer, rebuilt under
Visual C++, and then targetted to TMS320 (or equiv) DSP.

>> Steven

> You realize, of course, that your first mistake was starting with the
> radix-2 Numerical Recipes in C code and spending your time attempting
> micro-optimizations. The biggest speed gains in an FFT (and most
> algorithms) come from much higher-level transformations.
Actually I started with someone else's Fortran->C implementation of an
algorithm that looks like it came from the Cooley-Tukey paper. Then I
stepped to the Numerical Recipes (C) algorithm (Danielson - Lanczos?)
(which by the way still carries the legacy of Fortran array indexing)
   This took -72% off the time.

I have refined this in about five major steps, so that at the point of
posting I was
   -23% off the time of the NumRep routine as published (only high
level tweaks).

I will perform my last trial of converting the original code to double
without changing the indexing, just to see what I would have got,
before ...

Now, however, I will trawl through all the source in FFTW and see what
I can find.

> If you just want a fast FFT and are not doing this as a learning experience, you'll
> be much better off downloading an existing optimized code.
Even though I will probably do better with an FFTW routine, the
lessons learned will be valuable for other pieces of time critical
code.

> A decent compiler should transform array references a[j] in a loop
> into separate incremented pointers for you, if it's advantageous to do
> so. By being clever you can easily just confuse the compiler's
> optimizer unless you know what you're doing.
The two sets of indices do not change sequentially, which is why I
hoped that me forcing the use of pointers would be faster.

>> Kurt

> I've done the above many a time. The only way I've been able to cope is
> by learning the instruction set and reading the (equivalent) assembly code.
> It's pretty easy to tell when you've confused the optimizer.
This would be interesting given unlimited time, I do know that the DSP
code was definitely hand tweaked in the past as portability and
maintainability were far lower priority than performance.

Regards,
Paul

Relevant Pages

  • Re: Fast String Case Insensitive IndexOf
    ... IndexOf on a ToUpper performs at 380-400 ticks ... Forward Search (my algorithm going forward through the string) at 100-130 ticks ... Backward Search at 10-20 ticks ... Blog: http://weblogs.asp.net/justin_rogers "Justin Rogers" wrote in message ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Self Joins and optimization
    ... anything an optimizer can generate. ... compute the above with anything faster than a Oalgorithm. ... I'd argue that windowing functions allow for declarative ... challenge anyone to post any data definition and hypothetical query ...
    (comp.databases.theory)
  • Re: No knowledge of the database?
    ... Not if the optimizer does its job. ... > magnitude slower than a dedicated optimization algorithm except in a few ... Any software that collaborates with the Database Management System to ... BTW if you have a middle tier and the clients can only access to the ...
    (comp.object)
  • Re: No knowledge of the database?
    ... > Although it is very probable that you have to improve the DBMS ... > optimizer to achieve decent performance with more than a few cities. ... > appropiate algorithm behind the scenes. ... query AND it should have oodles of memory at its disposal on the server ...
    (comp.object)
  • Re: Ruby vs Java vs c++
    ... Interesting enough, I was a very experienced C++ programmer, and learning Java in 2000. ... I got an very heavy algorithm job. ... Java was more than twice faster than C++. ... Theoretically, with a good optimizer, this should be impossible...so I suspect the C optimizer. ...
    (comp.lang.ruby)
Loading