I'm using lxml with a bit of C for the scrapper behind Printful. My algorithm is way more complex than Readability and I can still parse web pages really fast. For example, parsing a long article from NYTimes on a really old machine:

fiam@raichu:~/printful$ cat /proc/cpuinfo

processor : 0

vendor_id : AuthenticAMD

cpu family : 6

model : 8

model name : AMD Athlon(tm) XP 2600+

fiam@raichu:~/printful$ python readable.py http://www.nytimes.com/2011/01/25/world/europe/25moscow.html > /dev/null

Took 0.193097171783 seconds for http://www.nytimes.com/2011/01/25/world/europe/25moscow.html

I'd say that hosting something like this on App Engine, which prevents you from using C extensions, is not a very good idea.

Edit: formatting