How to do per-line profiling?

[Roy Smith]

Are there any tools to do profiling on a line-by-line basis?

I've got a program that does a lot of low-level string manipulation, 
including building up strings character by character using "s1 += s2" 
constructs.  I knew this was evil, but it was quick-and-dirty and worked.  
Run time is just slow enough to be really annoying, but not slow enough to 
have ever convinced me to rewrite it :-)

All this recent talk about the quadratic complexity of string addition has 
made me finally go back and fix it.  I tore out all the string additions 
and replaced them with appending to a list, an join()ing the list at the 
end.  To my astonishment, this made it run about 10% slower!

The Python library profiler shows that, all my time is still spent 
groveling in string creation, and most of that is due to one routine 
(reformatted to fit the screen):

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.010    0.010   21.550   21.550 profile:0(app.main())
     1    0.000    0.000   21.540   21.540 <string>:1(?)
     1    0.000    0.000   21.540   21.540 ...(main)
     2    0.640    0.320   21.070   10.535 ...(parse)
 10382   14.270    0.001   17.210    0.002 ...(getNextStatement)
 10374    2.100    0.000    3.210    0.000 ...(processInsert)
 84882    2.120    0.000    2.120    0.000 ...(getLine)

The problem is that getNextStatement() is 165 lines of messy state machine 
code and it's not at all clear where the bad spots are.  At this point, 
what I really need is a profiler that can show me how much time is spent in 
each line of code, not just in each function.  Does such a thing exist?