I tend to expect performance to be a problem with FP, but I don't tend find it to be the case in practice. Immutable data structures are slower than mutable data structures, but typically only by a fixed order of magnitude. FP also tends to make use of more functions and closures, but those are usually quite performant.

I'm a little curious as to why you find FP performance problematic. I guess you must be trying to solve some pretty CPU-intensive problems?