Why is muttithreading quicksort slower than normal quicksort in python?

Question

Performance of quicksort implemented with mutlithreading is lower than normal quicksort although my processor is dual core.

Please provide suggestion to improve performance of multithreading.

I am uploading both versions of quicksort and also sample testcase generator written in python3(3.5.2)

Multithread Quicksort

#quicksort in multithreading

from queue import Queue 
import threading
import time

n = int(input().strip())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
f = open('results.txt','w')

q = Queue()
q.put([0,n-1])

def aux(i,j):
    if i<j:
        pivot = j
        k = 0
        global arr 
        while k<pivot:
            if arr[k]>arr[pivot]:
                tmp = arr[k]
                itr = k+1
                while itr<=pivot:
                    arr[itr-1]=arr[itr]
                    itr+=1
                arr[pivot]=tmp

                k-=1
                pivot-=1
            else:
                pass
            k+=1
        q.put([i, pivot-1])
        q.put([pivot+1, j])
    else:
        pass



def qsort_threader():
    while  True:
        if q.empty():
            pass
        else:
            indices = q.get()
            aux(indices[0],indices[1])
            q.task_done()


start = time.time()

for i in range (0,15):
    t = threading.Thread(target = lambda: qsort_threader())
    t.daemon = True
    t.start()

q.join()
print(time.time()-start)
f.write(str(arr))

Here's also the normal version

Normal Quicksort

#normal quicksort

import threading
import time

n = int(input().strip())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
f = open('results.txt','w')

def xsort(i=0,j=n-1):
    #print(threading.currentThread().getName())
    if i<j:
        pivot = j
        k = 0
        global arr 
        while k<pivot:
            if arr[k]>arr[pivot]:
                tmp = arr[k]
                itr = k+1
                while itr<=pivot:
                    arr[itr-1]=arr[itr]
                    itr+=1
                arr[pivot]=tmp

                k-=1
                pivot-=1
            else:
                pass
            k+=1

        xsort(i,pivot-1)
        xsort(pivot+1,j)
    else:
        pass



start = time.time()
xsort()
print(time.time()-start)
f.write(str(arr))
f.close()

Below is the test code generator

testcase generator

f = open('testfile.txt','w')
n = int(input("no of integers to generate ? "))
f.write(str(n)+'\n')
from random import randint as r
for i in range(0,n):
    f.write(str(r(-100000,100000))+' ')
f.close()

I'm also uploading screenshots of CPU performance graphs during running the programs on a testcase of 10000 unsorted random numbers

CPU graph during normal quicksort

see the 100% usage of CPU-3

CPU graph during multithread quicksort

No CPU is utilized properly

Normal Quicksort finishes the task in 20.041423797607422 seconds. Multithread Quicksort finishes it in 27.749499320983887 seconds.

Answer 1

You see the famous GIL in action: "mutex that prevents multiple native threads from executing Python bytecodes at once".

Guido's recommendation was to use multiprocessing with IPC messaging instead of threads with shared state.

If there is no special requirements for stability, you can try PyPy-STM, it was the most complete attempt to remove GIL.

Answer 2

Python uses a Global Interpreter Lock, which means that at any time only one thread can be running. So you won't be able to fully utilize a multicore machine with threads in Python. The reason it runs slower is likely the added communication overhead in your multithreaded example.

I suggest writing a multithreaded solution in C or another language that allows real multithreading and forking it from your Python program.