Double linked list implementation for asyncio tasks

[kumaraditya303]

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 #107804
• gh-107803: add whatsnew for asyncio double linked list implementation #120995
• gh-107803: fix thread safety issue in double linked list implementation  #121007
• GH-107803: use circular double linked list #126577

[colesbury]

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.

[willingc]

Thanks @colesbury for flagging this.

[kumaraditya303]

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

[colesbury]

@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);
	}