想像していた通りですが、UnicodeをUTF-8に変換するのは、SJISやEUCに変換するよりもちょっと速いことがわかった。
>>> import timeit
>>> def unicode_henkan(c):
... t = timeit.Timer("a.encode('%s')" % c, "a=u'\u3042'*10000")
... print t.timeit(number=1000)
...
>>> unicode_henkan("utf-8")
0.075012922287
>>> unicode_henkan("sjis")
0.19597196579
>>> unicode_henkan("eucjp")
0.146716833115
>>> unicode_henkan("cp932")
0.21554517746
>>>
ちなみに、timeitは与えられた計測対象のプログラムを内部でpythonのプログラムとして解釈する際に、文字コードのことをあまり考えてくれないようなので、
t = timeit.Timer("a.encode('%s')" % c, "a=u'あ'*10000")
のように書くとUnicodeErrorになります。