I've implemented AES in my library with several variations: a straight C version, a version using x86 SSSE3, and a version using x86 AES-NI. The SSSE3 and AES-NI implementations are constant-time, whereas the C implementation uses lookup tables.
My SSSE3 implementation is a bit (~20%) slower than my C implementation. It doesn't use bit-slicing, so as to support CBC encryption. AES-NI, of course, is at least 15x faster than either of the other two.
How important is it that my implementation prevents timing attacks? I'm wondering whether I should ditch my SSSE3 implementation and stick with straight C.