Hiya. I'm answering my own question. Being disappointed with how slowly TinyURL ran, I asked HN about the performance of others:
http://news.ycombinator.com/item?id=421552
I just spent a few minutes timing alternatives:
TinyURL: 0.44s/req
bit.ly: 0.19s/req
is.gd: 0.07s/req
That's a pretty big spread!