Welcome, guest | Sign In | My Account | Store | Cart

This recipe uses the multiprocessing module to kill functions that have run longer than intended. Unlike other recipes that use threading, this code is designed to actually kill execution that has continued for too long. This implementation does not rely on signals or anything that is OS specific, so it should work on any system on which you might need generic timeouts.

Python, 78 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import multiprocessing as MP
from sys import exc_info
from time import clock

DEFAULT_TIMEOUT = 60

################################################################################

def timeout(limit=None):
    if limit is None:
        limit = DEFAULT_TIMEOUT
    if limit <= 0:
        raise ValueError()
    def wrapper(function):
        return _Timeout(function, limit)
    return wrapper

class TimeoutError(Exception): pass

################################################################################

def _target(queue, function, *args, **kwargs):
    try:
        queue.put((True, function(*args, **kwargs)))
    except:
        queue.put((False, exc_info()[1]))

class _Timeout:

    def __init__(self, function, limit):
        self.__limit = limit
        self.__function = function
        self.__timeout = clock()
        self.__process = MP.Process()
        self.__queue = MP.Queue()

    def __call__(self, *args, **kwargs):
        self.cancel()
        self.__queue = MP.Queue(1)
        args = (self.__queue, self.__function) + args
        self.__process = MP.Process(target=_target, args=args, kwargs=kwargs)
        self.__process.daemon = True
        self.__process.start()
        self.__timeout = self.__limit + clock()

    def cancel(self):
        if self.__process.is_alive():
            self.__process.terminate()

    @property
    def ready(self):
        if self.__queue.full():
            return True
        elif not self.__queue.empty():
            return True
        elif self.__timeout < clock():
            self.cancel()
        else:
            return False

    @property
    def value(self):
        if self.ready is True:
            flag, load = self.__queue.get()
            if flag:
                return load
            raise load
        raise TimeoutError()

    def __get_limit(self):
        return self.__limit

    def __set_limit(self, value):
        if value <= 0:
            raise ValueError()
        self.__limit = value

    limit = property(__get_limit, __set_limit)

10 comments

Gabriel Genellina 14 years, 1 month ago  # | flag

Could you provide an example? If the intended way is to use the @timeout decorator, I could not make it work.

Stephen Chappell (author) 14 years, 1 month ago  # | flag

This is your test.py program to see how the library works. Support libraries for this test follow.

import os
import diff
import compare
import timeout
import operator

################################################################################

def poll(function):
    import time
    while True:
        ready = function.ready
        if ready is True:
            print('Function is ready.')
            show(function)
            return
        elif ready is False:
            print('Function is running.')
        else:
            assert ready is None
            print('Function timed out.')
            return
        time.sleep(1)

def show(function):
    try:
        string = repr(function.value)
    except:
        print('Function raised exception.')
        import traceback
        traceback.print_exc()
    else:
        print('Function returned:', string)
Stephen Chappell (author) 14 years, 1 month ago  # | flag

More test.py here:

if __name__ == '__main__':
    # TEST 1
    print('--------\n TEST 1\n--------')
    check = timeout.timeout()(compare.check)
    master = '''Consider, friend, as you pass by,
                as you are now, so once was I.
                As I am now, you too shall be.
                Prepare, therefore, to follow me.'''
    slave = '''you by, was therefore, now, pass as shall I.
               me. Consider, friend, now, am Prepare,
               as once you are As you be. I so too to follow'''
    check(master, slave)
    poll(check)
    # TEST 2
    print('--------\n TEST 2\n--------')
    search = timeout.timeout(10)(diff.search)
    a = os.urandom(256)
    b = os.urandom(256)
    search(a, b)
    poll(search)
    # TEST 3
    print('--------\n TEST 3\n--------')
    div = timeout.timeout()(operator.truediv)
    div(1, 0)
    poll(div)
    # TEST 4
    print('--------\n TEST 4\n--------')
    a = os.urandom(10)
    b = os.urandom(10)
    search(a, b)
    poll(search)
    # TEST 5
    print('--------\n TEST 5\n--------')
    master = '''Be skeptical of things on the Internet. Don't assume that
                e-mail "From:" a particular person is actually from that
                person until you have further reason to believe it's that
                person. Don't assume that an attachment is what it says it
                is. Don't give out your password to anyone, even if that
                person claims to be from "support."
                Be skeptical of things on the Internet. Don't assume that'''
    slave = '''is from attachment is things particular to have "From:"
               further person Don't to is. Internet. to that person Be
               Don't "support." password says you it that out even it
               believe a it's if person that an assume anyone, actually
               person. the e-mail assume reason your give on Don't of
               until be that claims from skeptical that what
               is from attachment is things particular to have "From:"'''
    check.limit = 1
    check(master, slave)
    poll(check)
    # TEST 6
    print('--------\n TEST 6\n--------')
    check.limit = 5
    check(master, slave)
    poll(check)
    ########
    input()
Stephen Chappell (author) 14 years, 1 month ago  # | flag

Part 1 of compare.py

import diff

# Matching Sensitivity - OFF
CASE_AND_PUNCTUATION = False

################################################################################

def connect_tree(tree):
    match = tree.nodes[tree.index.index(tree.value)]
    node = match.a
    if match.prefix.value:
        node.prefix = connect_tree(match.prefix)
    if match.suffix.value:
        node.suffix = connect_tree(match.suffix)
    return node

def flatten_tree(node):
    array = [0]
    _flatten(node, array)
    return array

def _flatten(node, array):
    if isinstance(node.prefix, diff.Slice):
        _flatten(node.prefix, array)
    else:
        array.append(node.prefix)
    array[0] += 1
    array.append((array[0], node.root))
    if isinstance(node.suffix, diff.Slice):
        _flatten(node.suffix, array)
    else:
        array.append(node.suffix)

################################################################################

if CASE_AND_PUNCTUATION:

    def check(master, slave):
        key = tuple(master.split())
        data = tuple(slave.split())
        tree = diff.search(key, data)
        if tree.value:
            node = connect_tree(tree)
            array = flatten_tree(node)
            answer = build_answer(array)
        else:
            answer = ' '.join('_' * len(word) for word in key)
        return tree.value, len(key), answer

    def build_answer(array):
        cache = []
        for chunk in array:
            if chunk and isinstance(chunk, tuple):
                if isinstance(chunk[0], int):
                    for word in chunk[1]:
                        cache.append(word)
                else:
                    for word in chunk:
                        cache.append('_' * len(word))
        return ' '.join(cache)
Stephen Chappell (author) 14 years, 1 month ago  # | flag

Part 2 of compare.py

else:

    def check(master, slave):
        words = master.split()
        key = simplify(words)
        assert len(words) == len(key), 'Cannot Simplify Words'
        data = simplify(slave.split())
        tree = diff.search(key, data)
        if tree.value:
            node = connect_tree(tree)
            array = flatten_tree(node)
            pairs = flatten_list(array)
            answer = build_answer(words, pairs)
        else:
            answer = ' '.join('_' * len(word) for word in key)
        return tree.value, len(key), answer

    def simplify(words):
        letter = lambda s: ''.join(filter(lambda s: 'a' <= s <= 'z', s))
        return tuple(filter(bool, map(letter, map(str.lower, words))))

    def flatten_list(array):
        pairs = []
        for chunk in array:
            if chunk and isinstance(chunk, tuple):
                if isinstance(chunk[0], int):
                    for word in chunk[1]:
                        pairs.append((True, word))
                else:
                    for word in chunk:
                        pairs.append((False, word))
        return pairs

    def build_answer(words, pairs):
        cache = []
        for word, (flag, load) in zip(words, pairs):
            cache.append(word if flag else '_' * len(load))
        return ' '.join(cache)
Stephen Chappell (author) 14 years, 1 month ago  # | flag

This is the diff.py module used in the code:

class Slice:

    __slots__ = 'prefix', 'root', 'suffix'

    def __init__(self, prefix, root, suffix):
        self.prefix = prefix
        self.root = root
        self.suffix = suffix

################################################################################

class Match:

    __slots__ = 'a', 'b', 'prefix', 'suffix', 'value'

    def __init__(self, a, b, prefix, suffix, value):
        self.a = a
        self.b = b
        self.prefix = prefix
        self.suffix = suffix
        self.value = value

################################################################################

class Tree:

    __slots__ = 'nodes', 'index', 'value'

    def __init__(self, nodes, index, value):
        self.nodes = nodes
        self.index = index
        self.value = value

################################################################################

def search(a, b):
    # Initialize startup variables.
    nodes, index = [], []
    a_size, b_size = len(a), len(b)
    # Begin to slice the sequences.
    for size in range(min(a_size, b_size), 0, -1):
        for a_addr in range(a_size - size + 1):
            # Slice "a" at address and end.
            a_term = a_addr + size
            a_root = a[a_addr:a_term]
            for b_addr in range(b_size - size + 1):
                # Slice "b" at address and end.
                b_term = b_addr + size
                b_root = b[b_addr:b_term]
                # Find out if slices are equal.
                if a_root == b_root:
                    # Create prefix tree to search.
                    a_pref, b_pref = a[:a_addr], b[:b_addr]
                    p_tree = search(a_pref, b_pref)
                    # Create suffix tree to search.
                    a_suff, b_suff = a[a_term:], b[b_term:]
                    s_tree = search(a_suff, b_suff)
                    # Make completed slice objects.
                    a_slic = Slice(a_pref, a_root, a_suff)
                    b_slic = Slice(b_pref, b_root, b_suff)
                    # Finish the match calculation.
                    value = size + p_tree.value + s_tree.value
                    match = Match(a_slic, b_slic, p_tree, s_tree, value)
                    # Append results to tree lists.
                    nodes.append(match)
                    index.append(value)
        # Return largest matches found.
        if nodes:
            return Tree(nodes, index, max(index))
    # Give caller null tree object.
    return Tree(nodes, index, 0)
Stephen Chappell (author) 14 years, 1 month ago  # | flag

Do you want a practical application example? I can upload the program this code was developed for on YouSentIt.

David Twery 12 years, 6 months ago  # | flag

Steve -- this is an excellent recipe for teaching a number of useful programming techniques and CS concepts. Thanks for posting it!

Stephen Chappell (author) 12 years, 6 months ago  # | flag

It is great to hear that someone found it useful! May I suggest looking at a better example of practical application? If you go to Google Code, you can find the finished version of the code above. These three modules are part of a much larger verse-quizzing program:

Jing Lu 10 years, 8 months ago  # | flag

Could you provide a simple example using map_async() function in multiprocessing?

I am a new to python. From your code, your function timeout(limit=None) is a timeout wrapper?