Python 3.13.0 No-GIL Resulting In Incorrect Reduced Results Occasionally.

[leimao]

Bug report

Bug description:

Occasionally, running the following two scripts with PYTHON_GIL=0 using Python 3.13.0 would result in incorrect reduced results on my machine. I also used a Docker container for building and reproducing results, please refer to my article for more details if necessary.

import math
import queue
import threading
import time


def compute_partial_factorial(start, end):

    partial_factorial = 1
    for i in range(start, end):
        partial_factorial *= i
    return partial_factorial


def compute_factorial_multithread(num, num_threads):

    threads = []
    results = queue.Queue()
    chunk_size = num // num_threads
    for i in range(num_threads):
        start = i * chunk_size + 1
        end = num + 1 if i == num_threads - 1 else (i + 1) * chunk_size + 1
        thread = threading.Thread(
            target=lambda: results.put(compute_partial_factorial(start, end)))
        thread.start()
        threads.append(thread)
    for thread in threads:
        thread.join()
    total_factorial = 1
    while not results.empty():
        total_factorial *= results.get()
    return total_factorial


def main():

    num_repeats = 20
    num = 100000
    factorial_ground_truth = math.factorial(num)
    num_threads = 4
    factorial_multithread = compute_factorial_multithread(num, num_threads)
    assert factorial_ground_truth == factorial_multithread
    # Time the factorial computation
    start_time = time.time()
    for _ in range(num_repeats):
        factorial_multithread = compute_factorial_multithread(num, num_threads)
    end_time = time.time()
    print(
        f"Average Time Elapsed: {(end_time - start_time) / num_repeats:.2f}s")


if __name__ == "__main__":

    main()

PYTHON_GIL=0 python factorial.py

import queue
import threading
import time


def compute_sum(arr, start, end):

    sum = 0
    for i in range(start, end):
        sum += arr[i]
    return sum


def compute_sum_multithread(arr, num_threads):

    n = len(arr)
    chunk_size = n // num_threads
    threads = []
    results = queue.Queue()
    for i in range(num_threads):
        start = i * chunk_size
        end = n if i == num_threads - 1 else (i + 1) * chunk_size
        thread = threading.Thread(
            target=lambda: results.put(compute_sum(arr, start, end)))
        thread.start()
        threads.append(thread)
    for thread in threads:
        thread.join()
    sum = 0
    while not results.empty():
        sum += results.get()
    return sum


def main():

    num_repeats = 20
    num_elements = 10000000
    arr = list(range(1, num_elements + 1))
    sum_ground_truth = num_elements * (num_elements + 1) // 2
    num_threads = 4
    sum_multithread = compute_sum_multithread(arr, num_threads)
    assert sum_ground_truth == sum_multithread
    # Time the sum computation
    start_time = time.time()
    for _ in range(num_repeats):
        sum_multithread = compute_sum_multithread(arr, num_threads)
    end_time = time.time()
    print(
        f"Average Time Elapsed: {(end_time - start_time) / num_repeats:.2f}s")


if __name__ == "__main__":

    main()

PYTHON_GIL=0 python reduce_sum.py

CPython versions tested on:

3.13

Operating systems tested on:

Linux

[colesbury]

You have a bug in your code. The lambda captures the variables start and end (not their values), and those variables get mutated by the loop. The result now depends on how quickly the thread actually starts executing its target function vs. the loop iteration.

Use instead:

        thread = threading.Thread(
            target=lambda s, e: results.put(compute_partial_factorial(s, e)), args=(start, end))

[leimao]

Thank you @colesbury! Now I see this subtle difference. I thought it does not matter whether it's capturing the value or variable since range(start, end) is not going to modify the start and end. But in the for i in range(num_threads) loop, the values can be modified before the for i in range(start, end) get executed in the last thread spawned.

What's funny was with GIL these programs (with bugs) always run fine on my machine and I thought they were bug-free.