-1
\$\begingroup\$

I have this assignment with the goal of improving the performance and execution time of a FFT C++ code without the use of external libraries. The code is as following:

void FftCalculator::ButterflyFFT(std::complex<double> *a,
                             std::complex<double> *b,
                             std::complex<double> w) {
 auto U = *b * w;
 *b = *a - U;
 *a = *a + U;
 }
 
uint32_t FftCalculator::bitReverseSingle(uint32_t x) {
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return ((x >> 16) | (x << 16));
}

void FftCalculator::FFT(std::complex<double> *a, const int m) {
for (int i = 0; i < (degree_ / 2); i++) {
int m_idx = i / m;
// base address
int t_idx = i % m;
std::complex<double> *a_x = a + 2 * m_idx * m + t_idx;
std::complex<double> *a_y = a_x + m;
std::complex<double> w = tw[m + t_idx];
ButterflyFFT(a_x, a_y, w);
} 
}

void FftCalculator::bitReverse(std::complex<double> *a) {
for (int i = 0; i < (degree_); i++) {
int logdegree_ = log2(degree_);
int degree_idx = i % degree_;
int revdegree_ = bitReverseSingle(degree_idx) >> (32 - logdegree_);
if (revdegree_ > degree_idx) {
  std::complex<double> temp = a[degree_idx];
  a[degree_idx] = a[revdegree_];
  a[revdegree_] = temp;
}
}
}
 // mode 1 for FFT and 2 for inverse
ComplexVec FftCalculator::GetTwiddle(int mode) {
ComplexVec twiddle(degree_);
twiddle[0] = {1.0, 0.0};
for (int i = 1; i < degree_; i *= 2) {
for (int j = 0; j < i; j++) {
  twiddle[i + j] = {cos(M_PI * (double)j / (double)i),
                    sin(powf(-1.0, mode) * M_PI * (double)j / (double)i)};
}
}
return twiddle;
}

 void FftCalculator::ExecFFT(std::complex<double> *a) {
 auto twiddle_factor = GetTwiddle(1);
 bitReverse(a);
 for (int i = 1; i < degree_; i *= 2) {
 FFT(a, i);
 } 
 }

The execution time is 30 ms Aprox, so I don't know how much can this code be improved. The thing is i'm not too good on C++ so I don't know what can I do to improve the performance. I know there is some libraries to optimize FFT in C++ but I was told I cannot use them. If someone can help me, I'd be really grateful.

Thanks

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Don't cross post your question. Pick one site, and delete the question on the other site. \$\endgroup\$ Nov 15, 2021 at 4:00
  • \$\begingroup\$ I think we need to see the class definition, and how it's being used to have enough context to review this properly. \$\endgroup\$
    – user673679
    Nov 15, 2021 at 6:50
  • 1
    \$\begingroup\$ There is some code missing to make this compile. If you add that, I'll probably give it a real look. In the meantime you can this review of a different FFT implementation, several of the points of interest are probably going to be similar. \$\endgroup\$
    – user555045
    Nov 15, 2021 at 7:46
  • \$\begingroup\$ Why couldn't you use one of the available libraries? Licence compatibility? \$\endgroup\$ Nov 15, 2021 at 12:39

1 Answer 1

1
\$\begingroup\$
  1. Use float instead of double.

  2. Don't use logdegree_ = log2(degree_), you can use std::bit_width (https://en.cppreference.com/w/cpp/numeric/bit_width)

  3. You can use std::swap to swap something

  4. Change mode to template parameter typed bool. Replace powf(-1.0, mode) to mode ? -1.0f : 1.0f

There are also lots of other room to improve your code style, but I think that things are irrelevant to performance.

\$\endgroup\$
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.