René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Use a principled, and consistent, implementation of freelists.","articleBody":"We currently implement freelists for the following object and internal structs\r\n\r\n* str\r\n* float \r\n* tuple (about 20 freelists, which is really wasteful)\r\n* list\r\n* async generator\r\n* contexts\r\n* small dicts\r\n* small dict keys\r\n* slice (a freelist of one)\r\n\r\nAll of these are implemented independently and rather inefficiently.\r\nThey take up 3672 bytes of space, instead of the ~200 bytes they should take.\r\nThis is not a lot in terms of memory, but it is a lot in terms of L1 cache.\r\n\r\nA freelist should look like this:\r\n```C\r\ntypedef struct {\r\n    void *head;\r\n    uint32_t space;\r\n    uint16_t current_capacity;\r\n    uint16_t limit_capacity;\r\n} _PyFreelist;\r\n```\r\n\r\nOnly one test is needed for allocation and deallocation (on the fast path).\r\nAllocation needs to test `freelist.head != NULL`. Deallocation needs to test `freelist.space != 0`.\r\n\r\nThe actual list is threaded through the objects on the list, terminated by `NULL`.\r\n\r\nCache locality is good. The `head` and `space` are adjacent, and 4 freelists fit in a single cache line.\r\nWhen freeing, the object is hot (and thus in cache).\r\nWhen allocating, the object is about to be used, so needs to be moved to cache anyway.\r\n\r\nThe `capacity` fields are there to allow the capacity of a freelist to be temporarily set to 0, ensuring that all allocations go through the main allocator, for use cases like `tracemalloc`. Currently `tracemalloc` doesn't see a lot of allocations, due to freelists.\r\n\r\nUnifying the code for freelists reduces code duplication, and simplifies things for further improvements.\r\n\r\n### Original discussion\r\n\r\nhttps://github.com/faster-cpython/ideas/discussions/132\n\n\u003c!-- gh-linked-prs --\u003e\n### Linked PRs\n* gh-101453\n* gh-121934\n\u003c!-- /gh-linked-prs --\u003e\n","author":{"url":"https://github.com/markshannon","@type":"Person","name":"markshannon"},"datePublished":"2022-12-14T12:29:39.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":2},"url":"https://github.com/100240/cpython/issues/100240"}