Very slow Nios II performance for my c code

Are you doing the FFT using double, float or integer (fixed point) data types.

Unless you are using integers it will be slow, even more so if you are using soft-float.

The soft-float code will be even worse if the BSP (which contains the FP functions) hasn't been compiled with -O3.

You can do fast (integer) FFT on a DSP - by throwing dedicated hardware at it.

Your PC could be running a 3.5GHz, your nios probably at no more than 100MHz.

The PC can execute several instructions every clock, the nios at most one.

The PC will have enough instruction and data cache to hold all the code and data in cache, the nios migh have enough instruction cache, but is probably thrashing the data cache.

The PC can do an FP multiply of divide every clock (more if your code is using any of the SIMD instructions - which FFT could generate).

All in all, I wouldn't be surprised if the nios code is 1000 (or more) times slower.