On a decent GPU (let's say Nvidia GTX 570) you can do a 512x512 inverse FFT in a fraction of a millisecond. So for that sort of hardware, it's definitely very practical.
Yah, this for a coarse approximation and then perlin noise or something for normal mapped details plus a big one to remove visible patterns. Here's what Nvidia did: https://developer.nvidia.com/sites/default/files/akamai/gamedev/files/sdk/11/OceanCS_Slides.pdf
Though frankly the perlin noise blending at large scales kind of dampens the nice FFT effect out to something that doesn't look as good (in my opinion). But heck, it looks a lot better than the tiling does.