Skip to main content
added 144 characters in body
Source Link
G. Sliepen
  • 61.7k
  • 3
  • 61
  • 152

Missing const

I see you sprinkled const almost everywhere. However, you actually missed the one spot where it actually matters most: input should be a const pointer:

_Bool fft(const complex_t* input, complex_t* output, const unsigned int size) {
    ...
}

Use the restrict keyword if possible

Since input and output are of the same type, they can alias. This might prevent the compiler from generating optimal code, as it now must assume that any write to a value of output might change a value in input. Annotate these pointers with the restrict keyword if supported by your compiler.

Note that making input a const pointer doesn't prevent aliasing.

Avoid divisions

Divisions are one of the slowest operations on any CPU, but especially on low end CPUs they might take tens of times more cycles than a multiply. You can avoid the division when calculating angle by writing:

double angle = -M_PI;
for (unsigned int even_to_odd = 2; even_to_odd < size; even_to_odd *= 2) {
    angle *= 0.5;
    ...
}

However, note that the compiler can easily optimize divisions by constants, so there is no need to worry about expressions like skip /= 2.

But perhaps even better:

Consider using sin/cos look-up tables

cos() and sin() are transcedental functions that can take a long time to evaluate, especially on weak microcontrollers. On the other hand, microcontrollers usually have very low memory access latencies. So it might make sense to pre-calculate all the possible values of sin(angle) and cos(angle) that you might encounter, and store them in a look-up table.

Missing const

I see you sprinkled const almost everywhere. However, you actually missed the one spot where it actually matters most: input should be a const pointer:

_Bool fft(const complex_t* input, complex_t* output, const unsigned int size) {
    ...
}

Use the restrict keyword if possible

Since input and output are of the same type, they can alias. This might prevent the compiler from generating optimal code, as it now must assume that any write to a value of output might change a value in input. Annotate these pointers with the restrict keyword if supported by your compiler.

Note that making input a const pointer doesn't prevent aliasing.

Avoid divisions

Divisions are one of the slowest operations on any CPU, but especially on low end CPUs they might take tens of times more cycles than a multiply. You can avoid the division when calculating angle by writing:

double angle = -M_PI;
for (unsigned int even_to_odd = 2; even_to_odd < size; even_to_odd *= 2) {
    angle *= 0.5;
    ...
}

But perhaps even better:

Consider using sin/cos look-up tables

cos() and sin() are transcedental functions that can take a long time to evaluate, especially on weak microcontrollers. On the other hand, microcontrollers usually have very low memory access latencies. So it might make sense to pre-calculate all the possible values of sin(angle) and cos(angle) that you might encounter, and store them in a look-up table.

Missing const

I see you sprinkled const almost everywhere. However, you actually missed the one spot where it actually matters most: input should be a const pointer:

_Bool fft(const complex_t* input, complex_t* output, const unsigned int size) {
    ...
}

Use the restrict keyword if possible

Since input and output are of the same type, they can alias. This might prevent the compiler from generating optimal code, as it now must assume that any write to a value of output might change a value in input. Annotate these pointers with the restrict keyword if supported by your compiler.

Note that making input a const pointer doesn't prevent aliasing.

Avoid divisions

Divisions are one of the slowest operations on any CPU, but especially on low end CPUs they might take tens of times more cycles than a multiply. You can avoid the division when calculating angle by writing:

double angle = -M_PI;
for (unsigned int even_to_odd = 2; even_to_odd < size; even_to_odd *= 2) {
    angle *= 0.5;
    ...
}

However, note that the compiler can easily optimize divisions by constants, so there is no need to worry about expressions like skip /= 2.

But perhaps even better:

Consider using sin/cos look-up tables

cos() and sin() are transcedental functions that can take a long time to evaluate, especially on weak microcontrollers. On the other hand, microcontrollers usually have very low memory access latencies. So it might make sense to pre-calculate all the possible values of sin(angle) and cos(angle) that you might encounter, and store them in a look-up table.

Source Link
G. Sliepen
  • 61.7k
  • 3
  • 61
  • 152

Missing const

I see you sprinkled const almost everywhere. However, you actually missed the one spot where it actually matters most: input should be a const pointer:

_Bool fft(const complex_t* input, complex_t* output, const unsigned int size) {
    ...
}

Use the restrict keyword if possible

Since input and output are of the same type, they can alias. This might prevent the compiler from generating optimal code, as it now must assume that any write to a value of output might change a value in input. Annotate these pointers with the restrict keyword if supported by your compiler.

Note that making input a const pointer doesn't prevent aliasing.

Avoid divisions

Divisions are one of the slowest operations on any CPU, but especially on low end CPUs they might take tens of times more cycles than a multiply. You can avoid the division when calculating angle by writing:

double angle = -M_PI;
for (unsigned int even_to_odd = 2; even_to_odd < size; even_to_odd *= 2) {
    angle *= 0.5;
    ...
}

But perhaps even better:

Consider using sin/cos look-up tables

cos() and sin() are transcedental functions that can take a long time to evaluate, especially on weak microcontrollers. On the other hand, microcontrollers usually have very low memory access latencies. So it might make sense to pre-calculate all the possible values of sin(angle) and cos(angle) that you might encounter, and store them in a look-up table.