Killing a thread

[Tim Peters]

[catlee at my-deja.com wrote:]
> - Is it conceivable that a user could make write some resource
> intensive code without using any kind of jump operations?

[Greg Ewing]
> Yes!
>
> def fib(n):
>     return {
>         0: lambda: 1,
>         1: lambda n=n: fib(n-1) + fib(n-2)
>     }[n>=3]()
>
> Although if you include function calls as well
> as jumps, you're probably safe (until Tim comes
> up with an even more perverted counterexample).

If the critical resource is time, measuring anything other than time is a
doomed strategy.  Consider this guy:

import re
from time import clock
for i in range(10):
    start = clock()
    re.search("x.*" * i + "y", "x" * 100)
    finish = clock()
    print i, round(finish - start)

This sets up some exponentially-expensive regexp searches.  Even as low as
i==4, the search

    re.search("x.*x.*x.*x.*y", "x" * 100)

consumes close to 40 seconds on my machine, and at i==5 well over 500.  I'm
not waiting for i==6 <wink>.

The first x matches at any of 100 places, the second at any from the first x
to the end, the third at any from the second to the end, and so on.  The "y"
at the end prevents any attempt from succeeding, and so forces all possible
choose(100, 4) combinations of "x" matches to be tried.  The search is
entirely in re's C code:  no bytecodes are interpreted-- nor function calls
made --for the duration.

To be really safe, I think you need to write some platform-specific C cruft
to spawn a distinct process, watch its progress, and kill it if it gets out
of hand.

Note too that it's no real trick to crash the Python interpreter (which is
why you need a separate process, not just a new thread):

a = []
b = []
a.append(a)
b.append(b)
print a == b

The number of ways you can fool Python similarly decreases every year; that
way in particular is widely known so I don't mind publicizing it even more
<wink>.

will-crash-python-for-big-bux-ly y'rs  - tim