Convoy effect with I/O bound threads and New GIL

@gvanrossum

BPO	7946
Nosy	@gvanrossum, @loewis, @arigo, @gpshead, @jcea, @mdickinson, @ncoghlan, @pitrou, @scoder, @larryhastings, @ericvsmith, @tarekziade, @carljm, @coderanger, @phsilva, @merwok, @alex, @jab, @briancurtin, @florentx, @cool-RR, @dimaqq, @thedrow, @corona10, @Sophist-UK
Files	udp-ioclient.py udp-iotest.py gilprio2.patch prioritygil.tar.gz: Priority GIL implementation from PyCON linux-7946.patch: Linux (libc) patch for py32 gilinter2.patch writes.py schedtest.py: Scheduling test dabeaz_gil.patch: Dave's GIL patch nir-ccbench-xp32.log nir-ccbench-linux.log ccbench-osx.log bfs.patch: Updated implementation of the BFS scheduler.

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2021-01-02.02:43:00.577>
created_at = <Date 2010-02-16.20:48:43.897>
labels = ['interpreter-core', '3.10', 'performance']
title = 'Convoy effect with I/O bound threads and New GIL'
updated_at = <Date 2022-03-21.22:05:04.974>
user = 'https://bugs.python.org/dabeaz'

bugs.python.org fields:

activity = <Date 2022-03-21.22:05:04.974>
actor = 'Sophist'
assignee = 'none'
closed = True
closed_date = <Date 2021-01-02.02:43:00.577>
closer = 'dabeaz'
components = ['Interpreter Core']
creation = <Date 2010-02-16.20:48:43.897>
creator = 'dabeaz'
dependencies = []
files = ['16315', '16316', '16323', '16324', '16570', '16676', '16968', '17095', '17106', '17194', '17370', '17393', '17504']
hgrepos = []
issue_num = 7946
keywords = ['patch']
message_count = 100.0
messages = ['99438', '99439', '99459', '99461', '99477', '99814', '99815', '99838', '99840', '99846', '99875', '100094', '101116', '101118', '101120', '101125', '101127', '101141', '101142', '101144', '101146', '101148', '101192', '101197', '101612', '101613', '101697', '101700', '101707', '101711', '101714', '101715', '101724', '101737', '101772', '101773', '101821', '101825', '101854', '102043', '102649', '102890', '103154', '103186', '103320', '103414', '103460', '104194', '104195', '104197', '104198', '104203', '104219', '104233', '104234', '104288', '104293', '104303', '104309', '104312', '104317', '104319', '104320', '104324', '104325', '104330', '104335', '104369', '104452', '104453', '104473', '104478', '104613', '104899', '105687', '105835', '105874', '106030', '106780', '106782', '156883', '223109', '223110', '346399', '346495', '347621', '347640', '347641', '377825', '377865', '378187', '378200', '378236', '385088', '385109', '415693', '415698', '415703', '415708', '415715']
nosy_count = 49.0
nosy_names = ['gvanrossum', 'loewis', 'jhylton', 'arigo', 'gregory.p.smith', 'jcea', 'mark.dickinson', 'ncoghlan', 'pitrou', 'scoder', 'movement', 'larry', 'eric.smith', 'kevinwatters', 'tarek', 'karld', 'carljm', 'coderanger', 'phsilva', 'durin42', 'eric.araujo', 'nirai', 'alex', 'stuaxo', 'andrix', 'konryd', 'jab', 'brian.curtin', 'hozn', 'victorpoluceno', 'flox', 'DazWorrall', 'cool-RR', 'rh0dium', 'rcohen', 'dabeaz', 'mahmoudimus', 'portante', 'aconrad', 'ysj.ray', 'thouis', 'donaldjeo', 'Michele', 'jmehnle', 'Dima.Tisnek', 'Omer.Katz', 'corona10', 'Sophist', 'maartenbreddels']
pr_nums = []
priority = 'normal'
resolution = 'wont fix'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue7946'
versions = ['Python 3.10']

Background
-----------
In order to multitask with threads, a critical part of the Python
interpreter implementation concerns the behavior of I/O operations
such as read, write, send, and receive. Specifically, whenever an I/O
operation is carried out, the interpreter releases the GIL so that
other threads can run while the program waits for the I/O operation to
complete.

Observed Behavior of I/O Operations
------------------------------------
The release of the GIL for I/O is a critical aspect of making sure the
interpreter doesn't make all threads hang while waiting. However, the
release of the GIL also assumes a worst-case scenario. In practice,
a large number of I/O requests actually complete immediately with no
actual blocking. For example, if a program is sending on a socket,
send() operations will typically complete immediately if buffer space
is available to accept the data. Likewise, read() and recv()
operations may return immediately if data is already available in the
operating system.

For system calls that complete immediately, a thread quickly releases
and then almost immediately reacquires the GIL to continue running.
However, given that the I/O operation didn't block, the release of the
GIL was technically unnecessary in this case.

Behavior of the new GIL
-----------------------
A feature of the new Python GIL implementation is that the interpreter
no longer periodically signals waiting threads (e.g., the check
interval). Instead, thread switching is based on a timed wait on a
condition variable. Should a timeout occur, a thread will indicate
that it wants the GIL and the currently running thread will be forced
to give it up.

Although this scheme solves the problem of CPU-bound threads
thrashing, it introduces a highly pronounced "convoy effect" when
CPU-bound threads and I/O bound threads get mixed together. A major
part of the problem is caused by the bahvior of I/O as described
above. Specifically, when an I/O bound thread executes an I/O call,
it always releases the GIL. Since the GIL is released, a CPU bound
thread is now free to acquire the GIL and run. However, if the I/O
call completes immediately (which is common), the I/O bound thread
immediately stalls upon return from the system call. To get the GIL
back, it now has to go through the timeout process to force the
CPU-bound thread to release the GIL again.

It should be noted that the behavior described also occurs in Python
2, but due to the small check interval, an I/O bound thread that wants
the GIL back will tend to get it without having to wait very long.

Example
-------
Here is a very simple example that illustrates the problem. In this
example, there is one CPU-bound thread that hammers the CPU and there
is an I/O bound thread that handles some network communication (an
echo server):

# iotest.py
import time
import threading
from socket import *

# CPU-bound thread (just hammers the CPU)
def spin():
    while True:
        pass

# I/O-bound thread (an echo TCP server)
def echo_server():
    s = socket(AF_INET, SOCK_STREAM)
    s.setsockopt(SOL_SOCKET, SO_REUSEADDR,1)
    s.bind(("",15000))
    s.listen(1)
    while True:
        c,a = s.accept()
        while True:
            data = c.recv(8192)
            if not data:
                break
            c.sendall(data)
        c.close()
    s.close()

# Launch the CPU-bound thread
t1 = threading.Thread(target=spin)
t1.daemon=True
t1.start()

# Run the I/O server
echo_server()

Here is a benchmark program that runs as a client for the echo_server()
thread defined above. It sends a sequence of messages and reads the
response back. It then reports some timings at the end.

# echoclient.py
from socket import *
import time

CHUNKSIZE = 16384
NUMMESSAGES = 640     # Total of 10MB

# Dummy message
msg = b"x"*CHUNKSIZE

# Connect and send messages
s = socket(AF_INET,SOCK_STREAM)
s.connect(("",15000))
start = time.time()
for n in range(NUMMESSAGES):
    s.sendall(msg)
    bytes_recv = len(msg)
    # Get the response back
    while bytes_recv > 0:
        data = s.recv(bytes_recv)
        bytes_recv -= len(data)
s.close()
end = time.time()
print("%0.3f seconds (%0.3f bytes/sec)" % (end-start, (CHUNKSIZE*NUMMESSAGES)/(end-start)))

Performance Results
-------------------
These results are from running the above programs on a dual-core
MacBook running OS-X Snow Leopard. I also get similar behavior on a
quad-core desktop machine.

If you run the iotest.py program using Python 2.6.4 and execute
the client, you get this result:

bash % python echoclient.py
1.064 seconds (9854148.739 bytes/sec)

If you switch the iotest.py to Python 3.2 and rerun, you get this
result:

bash % python echoclient.py
12.340 seconds (849726.150 bytes/sec)

Notice that there is a factor 12 performance difference.

Modify the iotest.py program so that there are 2 CPU-bound
threads spinning. Just add this extra code:

    t2 = threading.Thread(target=spin)
    t2.daemon
    t2.start()

Now, repeat the above tests. For Python 2.6.4, you get this:

bash-3.2$ python echoclient.py
0.358 seconds (29319821.410 bytes/sec)

(Yes the performance actually improves! That's left as an exercise
for the reader to figure out why)

Now, switch the iotest.py server to Python 3.2 and retry:

base-3 $ python echoclient.py
59.545 seconds (176098.609 bytes/sec)

Notice how the addition of one CPU-bound thread made the time go up by
more than a factor 4!

Now, disable all but one of the CPU cores and try the test again in
Python 3.2:

bash-3.2$ python echoclient.py
0.120 seconds (87246036.201 bytes/sec)

Here, you see that it runs about 500 times faster than with two cores
(yikes!)

What's causing this behavior?
-----------------------------
In the iotest.py program, there is an inner loop that
looks like this:

        while True:
            data = c.recv(8192)
            if not data:
                break
            c.sendall(data)

The I/O operations recv() and sendall() always release the GIL when
they execute. However, when this happens, CPU bound threads jump in
and start running again. The problem gets worse as the number of
CPU-bound threads increases--CPU bound threads might cycle round-robin
before the I/O bound thread runs again. The problem is more
pronounced on multiple CPU cores because when the GIL is released, one
of the cores will typically go handle the system call while the other
core wakes up the waiting CPU-bound thread (which then almost
immediately steals the GIL).

Is it worth fixing?
-------------------
I claim yes. There are many applications, such as those carried
out with the multiprocessing library, that will operate by trying
to overlap computation and I/O in some manner (for example, receiving
the next chunk of data to work on while carrying out calculations
on the currently received data).

In heavily loaded I/O bound applications such as servers with
hundreds of simultaneously connected clients, the release of the GIL
on short I/O operations may cause a lot of unintended thrashing
as threads cycle amongst themselves. This would most likely
manifest itself as an increased turnaround time for requests.

How to fix?
-----------
Modify all I/O operations in the interpreter to not release the
GIL if they won't block. Either that or maybe there's some sort of
really sneaky easy solution (unknown).

The effect can be minimized by setting the switch interval to a really
small value using sys.setswitchinterval(). However, doing this
greatly increases the amount of thread context-switching--something
that's also undesirable.

Would the idea of priority-GIL requests that Antoine had in his original patch solve this issue?

Just a quick test under Linux (on a dual quad core machine):

with iotest.py and echo_client.py both running Python 2.7: 25.562 seconds (410212.450 bytes/sec)
with iotest.py and echo_client.py both running Python 3.2: 28.160 seconds (372362.459 bytes/sec)

As already said, the "spinning endlessly" loop is a best case for thread switching latency in 2.x, because the opcodes are very short. If each opcode in the loop has an average duration of 20 ns, and with the default check interval of 100, the GIL gets speculatively released every 2 us (yes, microseconds). That's why I suggested trying more "realistic" workloads, as in ccbench.

Also, as I told you, there might also be interactions with the various timing heuristics the TCP stack of the kernel applies. It would be nice to test with UDP.

That said, the observations are interesting.

The comment on the CPU-bound workload is valid--it is definitely true that Python 2.6 results will degrade as the workload of each tick is increased. Maybe a better way to interpreter those results is as a baseline of what kind of I/O performance is possible if there is a quick I/O response time.

However, ignoring that and the comparison between Python 2.6 and 3.2, there is still a serious performance issue with I/O in 3.2. For example, the dramatic decrease in I/O performance as there are more CPU bound threads competing and the fact that there is a huge performance gain when all but one CPU core is disabled.

I tried the test using UDP packets and get virtually the exact same behavior described. For instance, echoing 10MB (sent in 8k UDP packets) takes about 0.6s in Python 2.6 and 12.0s in Python-3.2. The time shoots up to more than 40s if there are two CPU-bound threads.

The problem being described really doesn't have anything to do with TCP vs. UDP or any part of the network stack. It has everything to do with how the operating system buffers I/O requests and how I/O operations such as sends and receives complete immediately without blocking depending on system buffer characteristics (e.g., if there is space in the send buffer, a send will return immediately without blocking). The fact that the GIL is released when it's not necessary in these cases is really the source of the problem.

We could try not to release the GIL when socket methods are called on a non-blocking socket.

Regardless, I've re-run the tests under the Linux machine, with two spinning threads:

python 2.7:
25.580 seconds (409914.612 bytes/sec)
python 3.2:
32.216 seconds (325485.029 bytes/sec)

(and as someone mentioned, the "priority requests" mechanism which was in the original new GIL patch might improve things. It's not an ideal time for me to test, right now :-))

I'm attaching Dave's new UDP-based benchmarks, which eliminate the dependency on the TCP stack's behaviour.

And here is an experimental patch which enables the "priority requests" mechanism which was in the original new GIL patch. "Experimental" because it only enables them on a couple of socket methods (enough to affect the benchmarks).

Here are the UDP benchmark results (with 2 background threads):

2.x trunk (old GIL):
11.379 seconds (921515.168 bytes/sec)
vanilla py3k (new GIL):
27.400 seconds (382689.529 bytes/sec)
patched py3k (new GIL + priority requests):
1.828 seconds (5737130.676 bytes/sec)

And here's patched py3k with 8 background threads:
3.058 seconds (3429136.193 bytes/sec)

(benchmarks run on a 8-core Linux machine)

See also bpo-7993 for a patch adding a similar bandwidth benchmark to ccbench.

Here is an improved version of the priority requests patch.
With this patch I get the following result (2 background threads):
0.255 seconds (41109347.194 bytes/sec)

I posted some details about the priority GIL modifications I showed during my PyCON open-space session here:

http://www.dabeaz.com/blog/2010/02/revisiting-thread-priorities-and-new.html

I am attaching the .tar.gz file with modifications if anyone wants to look at them. Note: I would not consider this to be solid enough to be any kind of official patch. People should only look at it for the purposes of experimentation and for coming up with something better.

About nine years ago, I stood in front of a room of Python developers, including many core developers, and gave a talk about the problem described in this issue. It included some live demos and discussion of a possible fix.

https://www.youtube.com/watch?v=fwzPF2JLoeU

Based on subsequent interest, I think it's safe to say that this issue will never be fixed. Probably best to close this issue.

It's a known issue and has been outlined very well and still comes up from time to time in real world applications, which tend to see this issue and Dave's presentation and just work around it in any way possible for their system and move on with life.

Keeping it open even if nobody is actively working on it makes sense to me as it is still a known issue that could be resolved should someone have the motivation to complete the work.

My 2c as Python user:

Back in 2010, I've used multithreading extensively, both for concurrency and performance. Others used multiprocessing or just shelled out. People talked about using **the other** core, or sometimes the other socket on a server.

Now in 2020, I'm using asyncio exclusively. Some colleagues occasionally still shell out 🙈. None talking about using all cores on a single machine, rather, we'd spin up dozens of identical containers, which are randomly distributed across N machines, and the synchronisation is offloaded to some database (e.g. atomic ops in redis; transactions in sql).

In my imagination, I see future Python as single-threaded (from user's point of view, that is without multithreading api), that features speculative out-of-order async task execution (using hardware threads, maybe pinned) that's invisible to the user.

If someone wants to close this issue, I suggest to write a short section in the Python documentation to give some highlights on the available options and stategies to maximize performances and list drawbacks of each method. Examples:

Multiple threads (threading): limited by the GIL
Multiple processes (concurrent.futures, multiprocessing, distributed application): limited by shared data
Concurrent programming (asyncio): limited to 1 thread

These architectures are not exclusive. asyncio can use multiple threads and be distributed in multiple processes.

I would be bad to go too deep into the technical details, but I think that we can describe some advantages and drawbacks which are common on all platforms.

Catching up on the comments on this, it seems like nobody has enough certainty to say it will work well enough.

In Linux, the scheduler is pluggable, which lets other non-default schedulers be shipped and tried in the real world.

See schedutil, introduced in Linux 4.7 in 2016 default for some architectures in 2020, in 2021 still not default everywhere.

Similarly I think this needs more testing than it will get living here as a bug. If, like Linux the scheduler was pluggable, it could be shipped and enabled by real users that were brave enough and data could be collected.

In case someone finds it useful, I've written a blog post on how to visualize the GIL:
https://www.maartenbreddels.com/perf/jupyter/python/tracing/gil/2021/01/14/Tracing-the-Python-GIL.html

In the comments (or at maartenbreddels/fastblog#3 (comment) )
I looked specifically at the iotest.py example (no solutions though).

Please see also faster-cpython/ideas#328 for a proposal for a simple (much simpler than BFS) GIL scheduler only allocating the GIL between runable O/S threads waiting to have ownership of the GIL, and using the O/S scheduler for scheduling the threads.

I think that we should focus our efforts on removing the GIL, now that we
have a feasible solution for doing so without breaking anything (hopefully)
however the removal of the GIL is still far from being complete and will
need to be rebased upon the latest Python version to be merged.

This issue would probably hurt Celery since some users use it with a thread
pool and it uses a few threads itself but it seems like fixing it is too
much effort so if we were to invest a lot of effort, I'd focus on removing
the problem entirely.

Instead, I suggest we document this with a warning in the relevant place so
that people would know to avoid or workaround the problem entirely.

On Mon, Mar 21, 2022, 20:32 Guido van Rossum <[email protected]> wrote:

Change by Guido van Rossum <[email protected]>:

----------
nosy: +gvanrossum

Python tracker <[email protected]>
<https://bugs.python.org/issue7946\>

I think that we should focus our efforts on removing the GIL, now that we have a feasible solution for doing so without breaking anything

Is this really a thing? Something that is definitely happening in a reasonable timescale?

Or are there some big compatibility issues likely to rear up and at best create delays, and at worse derail it completely?

Can someone give me some links about this please?

Start here: https://docs.google.com/document/d/18CXhDb1ygxg-YXNBJNzfzZsDFosB5e6BfnXLlejd9l0/edit

AFAICT the SC hasn't made up their minds about this.

https://docs.google.com/document/d/18CXhDb1ygxg-YXNBJNzfzZsDFosB5e6BfnXLlejd9l0/edit

The steering committee hasn't given the go ahead for this yet, and we have no idea when such a decision will be made nor whether the decision with be yes or no.
Even after the decision is made "Removing the GIL will be a large, multi-year undertaking with increased risk for introducing bugs and regressions."
The promised performance gains are actually small by comparison to the existing project that Guido is running is hoping to achieve. It is unclear whether the no-gil implementation would impact those gains, and if so whether a small reduction in the large planned performance gains would actually more than wipe out the modest performance gains promised by the no-gil project.
Given that this "Removing the GIL will require making trade-offs and taking on substantial risk", it is easy to see that this project could come across an unacceptable risk or insurmountable technical problem at any point and thus fall by the wayside.

Taking all of the above points together, I think that there is still merit in considering the pros and cons of a GIL scheduler.

Navigation Menu

Repository navigation

Convoy effect with I/O bound threads and New GIL #52194

83 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Convoy effect with I/O bound threads and New GIL #52194

Description

Activity

dabeaz commented on Feb 16, 2010

alex commented on Feb 16, 2010

pitrou commented on Feb 17, 2010

dabeaz commented on Feb 17, 2010

pitrou commented on Feb 17, 2010

pitrou commented on Feb 22, 2010

pitrou commented on Feb 22, 2010

pitrou commented on Feb 22, 2010

pitrou commented on Feb 22, 2010

dabeaz commented on Feb 22, 2010

83 remaining items

dabeaz commented on Oct 3, 2020

gpshead commented on Oct 7, 2020

dimaqq commented on Oct 8, 2020

vstinner commented on Oct 8, 2020

stuaxo commented on Jan 14, 2021

maartenbreddels commented on Jan 15, 2021

Sophist-UK commented on Mar 21, 2022

thedrow commented on Mar 21, 2022

Sophist-UK commented on Mar 21, 2022

gvanrossum commented on Mar 21, 2022

Sophist-UK commented on Mar 21, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions