From what I've heard, the performance problem with KDE4 is that QT4 uses an unusual pixel format that the current graphics drivers don't accelerate (and, according to at least one developer, isn't natively supported by most GPUs in the first place).
Depends on what graphics card you've got.
It's unusably slow on my desktop machine with an nVidia card, unless I run the absolute latest video drivers. In that case, it's just slow. And crashes whenever a menu appears anywhere on the screen. The performance problems on nVidia hardware were basically because KDE 4 relies on the XRender extension to do most of it's drawing, and nVidia's implementation of that API was extremely slow. It's a lot better with the latest drivers, but still not good enough.
On my Macbook, which has an Intel GMA something-or-other (crap, basically), it works great. Easily as fast as anything else (Mac OS X included).
The pixel format thing is actually a different problem. KDE uses ARGB windows for certain features, such as Plasma, so the Plasma windows can have per-pixel transparency, and arbitrary shapes. Some drivers perform very poorly with ARGB windows, and some have (or had) all kinds of bugs, or graphics corruption...