FFTs are snappy if done correctly
Bet you wouldn’t be able to tell the difference 
I wonder if that would work when targeting at least100 fps (including reading audio for each frame) and doing a bunch of other calculations for 256 leds on the same chip.
From the PJRC site: “Teensy 3.0 & 3.1 have the Cortex-M4 DSP instructions which provide plenty of computational power for real-time FFT (spectrum analysis), opening up the possibility of creating advanced sound-reactive projects.”
PJRC released the Teensy Audio Library 1.0 yesterday (you do need to download a release candidate version of Teensyduino 1.20 to get it though):
http://www.pjrc.com/teensy/td_libs_Audio.html
http://forum.pjrc.com/threads/26727-Teensyduino-1-20-Release-Candidate-5-Available
The library is designed to take advantage of the Cortex-M4 DSP instructions in the Teensy 3.1. There’s one note on FFT performance: “The 1024 point FFT consumes 52% CPU time on 1 of every 4 audio updates. On the other 3 of 4 updates, it merely stores the incoming audio, to be analyzed on the 4th update.”
I’m sure with a smaller point FFT there will be plenty of CPU cycles left over for updating LEDs.
Good timing, thank you for the link.