Double linked list implementation for asyncio tasks

Currently asyncio tasks are stored in a Weakset, this is inefficient and in some cases causes bugs because of thread safety (#80788). In terms of memory usage it requires maintaining a full set and their corresponding weakref callback to cleanup objects when deallocated and finalized by the gc. In applications where tasks are created at fast pace this becomes a bottle neck, to mitigate this now asyncio tasks will now be stored in a global double linked of tasks for cases where Task is a subclass of _asyncio.Task in other cases we still rely on the weakset. This reduces the work done by the gc speedups the execution and reduces memory usage. In some of my own benchmarks I have seen 15- 20% improvement and pyperformance benchmarks reflect roughly the same.

https://github.com/faster-cpython/benchmarking-public/blob/main/results/bm-20230805-3.13.0a0-1d32835/bm-20230805-linux-x86_64-kumaraditya303-linked_list-3.13.0a0-1d32835-vs-base.md

Updated: https://github.com/faster-cpython/benchmarking-public/tree/main/results/bm-20240622-3.14.0a0-4717aaa#vs-base

Linked PRs

GH-107803: double linked list implementation for asyncio tasks (GH-10…

I think there are some thread-safety issues with the linked list implementation:

It's not going to be thread-safe in the free-threaded build. We can probably add a lock or a critical section.
Even with the GIL, the linked list of tasks may be modified while it's being looped over because the GIL can be released in add_one_task.

@colesbury

Thanks @colesbury for flagging this.

I am closing this, will track free threaded issues in #120974

@kumaraditya303

@kumaraditya303, can you fix the thread-safety/reentrancy issue that affects the default build (with the GIL)? head can be deallocated while it's being used. It needs to be protected by a Py_INCREF(). This is not specific to the free-threading build.

cpython/Modules/_asynciomodule.c

Lines 3711 to 3721 in 2d3187b

    
           TaskObj *tail = &state->asyncio_tasks.tail; 
        
           while (head != tail) 
        
           { 
        
               if (add_one_task(state, tasks, (PyObject *)head, loop) < 0) { 
        
                   Py_DECREF(tasks); 
        
                   Py_DECREF(loop); 
        
                   return NULL; 
        
               } 
        
               head = head->next; 
        
               assert(head != NULL); 
        
           }

gh-107803: fix thread safety issue in double linked list implementati…

gh-107803: add whatsnew for asyncio double linked list implementation (…

pythonGH-107803: double linked list implementation for asyncio tasks (p…

pythongh-107803: fix thread safety issue in double linked list implem…

pythongh-107803: add whatsnew for asyncio double linked list implemen…

Backport gh-107803: Double linked list implementation for asyncio tasks

pythonGH-107803: double linked list implementation for asyncio tasks (p…

pythongh-107803: fix thread safety issue in double linked list implem…

pythongh-107803: add whatsnew for asyncio double linked list implemen…

pythonGH-107803: double linked list implementation for asyncio tasks (p…

pythongh-107803: fix thread safety issue in double linked list implem…

pythongh-107803: add whatsnew for asyncio double linked list implemen…

GH-107803: use circular double linked list for tasks in `_asyncio` (#…

pythonGH-107803: use circular double linked list for tasks in `_async…

Navigation Menu

Repository navigation

Double linked list implementation for asyncio tasks #107803

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	TaskObj *tail = &state->asyncio_tasks.tail;
	while (head != tail)
	{
	if (add_one_task(state, tasks, (PyObject *)head, loop) < 0) {
	Py_DECREF(tasks);
	Py_DECREF(loop);
	return NULL;
	}
	head = head->next;
	assert(head != NULL);
	}

Double linked list implementation for asyncio tasks #107803

Description

Linked PRs

Activity

colesbury commented on Jun 24, 2024

willingc commented on Jun 24, 2024

kumaraditya303 commented on Jun 25, 2024

colesbury commented on Jun 25, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions