python multithread "maximum recursion depth exceed"

Question

I use Python multithread to realize Quicksort. Quicksort is implement in a function. It is a recursive function. Each thread calls Quicksort to sort the array it has. Each thread has its own array that stores the numbers needs to be sorted. If the array size is smaller (<10,000). It runs ok. However, if the array size is larger, it shows the "maximum recursion depth exceed". So, I use setrecursionlimit () function to reset the recursion depth to 1500. But the program crash directly... The following is quicksort code. It works well if not in multi-thread environment. It seems multiple threads is the cause of recursion depth problem.

def partition (array, p, r):
    x = array[r]
    i = (p-1)
    j = p
    while (1):
        if array[j] <= x:
            i = (i+1)
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
        j+=1
        if j == r:
            break
    temp = array[i+1]
    array[i+1] = array[r]
    array[r] = temp
    return i+1

def quicksort (array, p, r):
    if p < r:
        q = partition (array, p, r)
        quicksort (array, p, q-1)
        quicksort (array, q+1, r)

Answer 1

It sounds like your real question is "Why is the recursion depth shorter when using threads"? I will try to answer that question.

First, background. Each level of recursion is stored an area of memory known as the stack. Unfortunately, the system has to allocate the stack space in advance and it doesn't know in advance how much stack space your program might need. That's why too much recursion causes a "maximum recursion depth" error: your program has used up all of that stack space.

Each thread needs its own stack to store the list of functions that are currently executing in that thread. In a single threaded program, the system can afford to give a big chunk of memory to the stack for that one thread. In a multi-threaded program, the system has to be a bit more conservative and it gives only a small stack to each thread. Otherwise, a program with many threads could quickly use up all system memory just with stack space (most of which won't be used).

All of this is done by the operating system and/or by the C library, which Python (more precisely, CPython) runs on top of. Python tries hard to prevent you from using the entire C stack, because that would cause a hard crash rather than simply an exception. You can tell Python how to behave with the setrecursionlimit function, but that doesn't change the actual amount of stack space available.

On a unix-ish system with a bash shell, you may be able to change the stack size with the ulimit -s command. Type help ulimit at your bash shell prompt for more information.