Why we say dequeue in python is threadsafe when GIL already restricts running one thread at a time

From what I have been reading Python has GIL that ensures only one thread can run the python code. So I am slightly confused when we say collections.dequeue is thread-safe. If only one thread is run at a time wouldn't objects be in a consistent state already?

It would be great if someone can give an example of how a list in python is not thread safe and using a dequeue possible counters that?

The GIL doesn't prevent race conditions, it only protects python internals from corruption, you cannot have a dangling pointer or a use-after-free inside the python interpreter. the only way they were able to make a GIL-free interpreter in python3.13 is to put a lock (or more than one lock) in every object in python, including things you don't think about like stack variables, and the stack frame.

You can have race conditions with the GIL for the same reason you needed locks on a CPU with 1 core, the thread can be suspended at any moment in time, python threads automatically drop the GIL and suspend themselves every few milliseconds to allow other threads to run, if you have 2 atomic operations, each one of them is atomic, the two operations together are not atomic.

CPython deque is similar to C++ deque, it is a linked list of small arrays (lists), currently 64 items per block.

A single append operation involves 2 operations

1. put item at the head of the array
2. increment the head counter.

if the current head block is full it has to allocate a new empty block, and put it in the end of the linked list, to illustrate those 2 operations in python code

block = [None for i in range(64)]  # one block in the linked list
head = 5
def append(obj):
    block[head] = obj
    # thread could get suspended here
    head += 1

There is also a tail counter (called left and right in source code), so it can grow in 2 directions, the tail logic decrements instead of incrementing.

If you implemented that in python it won't be thread-safe without a lock, one thread will put its object at the current head, then get suspended before it increments the head counter, and another thread will end up overwriting this location before the first thread could increment the head count, then the first thread will increment it again, essentially the data of the first thread is lost, and there is now an empty slot in the middle of the deque.

In CPython without the GIL the entire deque is locked during this append operation, so the scenario above is not possible, and when the GIL is used, the GIL is not dropped until the append operation is done, as the deque is written in C, not in python. you can control the GIL in C extensions, but you cannot control it in python.

CPython list has atomic operations too, its append and pop, are both thread-safe. however implementing a deque using a simple list will be very slow, popleft done with pop(0) will be an O(n) operation, whereas python deque makes it O(1)

Every other operation in the list like index or remove or indexing it are not thread-safe, and can remove or access the wrong element, demo: concurrent append + remove removing the wrong element, you'll need an external lock on all operations if you use those operations concurrently on a list or deque.