René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Use freelist for range object, iterator objects and other often used objects","articleBody":"# Feature or enhancement\r\n\r\n### Proposal:\r\n\r\nWe can add freelists for the `range` object and various iter objects to improve performance. Using the new methods from https://github.com/python/cpython/pull/121934 the amount of code needed for adding a freelist is quite small. A prototype implementation is here:\r\n\r\nhttps://github.com/python/cpython/compare/main...eendebakpt:cpython:iter_freelists\r\nhttps://github.com/python/cpython/compare/main...eendebakpt:cpython:range_freelist\r\n\r\n@markshannon In https://github.com/faster-cpython/ideas/discussions/132#discussioncomment-4766337 you noted that freelists should be used for all types. Is adding freelists in a similar style to the already existing freelists a good approach? We could also try to make a more generic construction (for example inside `PyObject_New`/`PyObject_Free`), but that would have a much larger impact and I cannot oversee all consequences.\r\n\r\nThe freelists from the prototype improve performance of `range` in microbenchmarks:\r\n```\r\nrange(1): Mean +- std dev: [rp_main] 50.0 ns +- 0.4 ns -\u003e [rp_pr] 40.6 ns +- 0.5 ns: 1.23x faster\r\niter(range(1)): Mean +- std dev: [rp_main] 91.7 ns +- 2.4 ns -\u003e [rp_pr] 68.5 ns +- 0.7 ns: 1.34x faster\r\nlist(range(1)): Mean +- std dev: [rp_main] 165 ns +- 1 ns -\u003e [rp_pr] 144 ns +- 1 ns: 1.15x faster\r\nlist(iter(range(1))): Mean +- std dev: [rp_main] 240 ns +- 17 ns -\u003e [rp_pr] 229 ns +- 13 ns: 1.05x faster\r\nrange(2, 1): Mean +- std dev: [rp_main] 61.6 ns +- 0.6 ns -\u003e [rp_pr] 46.7 ns +- 0.4 ns: 1.32x faster\r\niter(range(2, 1)): Mean +- std dev: [rp_main] 100 ns +- 4 ns -\u003e [rp_pr] 79.6 ns +- 4.0 ns: 1.26x faster\r\nlist(iter(range(2, 1))): Mean +- std dev: [rp_main] 227 ns +- 3 ns -\u003e [rp_pr] 209 ns +- 4 ns: 1.08x faster\r\nfor loop length 1: Mean +- std dev: [rp_main] 146 ns +- 4 ns -\u003e [rp_pr] 126 ns +- 6 ns: 1.16x faster\r\nrange(10): Mean +- std dev: [rp_main] 51.7 ns +- 2.4 ns -\u003e [rp_pr] 41.0 ns +- 0.9 ns: 1.26x faster\r\niter(range(10)): Mean +- std dev: [rp_main] 92.7 ns +- 3.5 ns -\u003e [rp_pr] 68.3 ns +- 2.2 ns: 1.36x faster\r\nlist(range(10)): Mean +- std dev: [rp_main] 205 ns +- 4 ns -\u003e [rp_pr] 184 ns +- 9 ns: 1.11x faster\r\nlist(iter(range(10))): Mean +- std dev: [rp_main] 279 ns +- 7 ns -\u003e [rp_pr] 261 ns +- 5 ns: 1.07x faster\r\nrange(2, 10): Mean +- std dev: [rp_main] 57.7 ns +- 1.5 ns -\u003e [rp_pr] 48.5 ns +- 2.2 ns: 1.19x faster\r\niter(range(2, 10)): Mean +- std dev: [rp_main] 101 ns +- 3 ns -\u003e [rp_pr] 78.1 ns +- 1.1 ns: 1.29x faster\r\nlist(iter(range(2, 10))): Mean +- std dev: [rp_main] 284 ns +- 17 ns -\u003e [rp_pr] 262 ns +- 10 ns: 1.08x faster\r\nfor loop length 10: Mean +- std dev: [rp_main] 329 ns +- 7 ns -\u003e [rp_pr] 295 ns +- 5 ns: 1.12x faster\r\nrange(100): Mean +- std dev: [rp_main] 52.3 ns +- 2.2 ns -\u003e [rp_pr] 41.1 ns +- 1.3 ns: 1.27x faster\r\niter(range(100)): Mean +- std dev: [rp_main] 91.7 ns +- 3.5 ns -\u003e [rp_pr] 69.6 ns +- 2.1 ns: 1.32x faster\r\nlist(range(100)): Mean +- std dev: [rp_main] 653 ns +- 27 ns -\u003e [rp_pr] 603 ns +- 29 ns: 1.08x faster\r\nlist(iter(range(100))): Mean +- std dev: [rp_main] 701 ns +- 17 ns -\u003e [rp_pr] 671 ns +- 17 ns: 1.04x faster\r\nrange(2, 100): Mean +- std dev: [rp_main] 58.5 ns +- 2.8 ns -\u003e [rp_pr] 48.1 ns +- 2.3 ns: 1.22x faster\r\niter(range(2, 100)): Mean +- std dev: [rp_main] 99.6 ns +- 1.5 ns -\u003e [rp_pr] 78.4 ns +- 0.8 ns: 1.27x faster\r\nlist(iter(range(2, 100))): Mean +- std dev: [rp_main] 710 ns +- 28 ns -\u003e [rp_pr] 674 ns +- 16 ns: 1.05x faster\r\nfor loop length 100: Mean +- std dev: [rp_main] 2.06 us +- 0.07 us -\u003e [rp_pr] 1.98 us +- 0.11 us: 1.04x faster\r\nrange(400): Mean +- std dev: [rp_main] 71.3 ns +- 2.2 ns -\u003e [rp_pr] 61.7 ns +- 5.1 ns: 1.16x faster\r\niter(range(400)): Mean +- std dev: [rp_main] 112 ns +- 5 ns -\u003e [rp_pr] 89.5 ns +- 2.8 ns: 1.25x faster\r\nlist(iter(range(400))): Mean +- std dev: [rp_main] 3.88 us +- 0.18 us -\u003e [rp_pr] 3.77 us +- 0.08 us: 1.03x faster\r\nrange(2, 400): Mean +- std dev: [rp_main] 79.3 ns +- 1.7 ns -\u003e [rp_pr] 66.0 ns +- 3.7 ns: 1.20x faster\r\niter(range(2, 400)): Mean +- std dev: [rp_main] 119 ns +- 2 ns -\u003e [rp_pr] 99.5 ns +- 3.1 ns: 1.19x faster\r\nfor loop length 400: Mean +- std dev: [rp_main] 12.1 us +- 0.7 us -\u003e [rp_pr] 10.9 us +- 0.4 us: 1.11x faster\r\n\r\nBenchmark hidden because not significant (2): list(range(400)), list(iter(range(2, 400)))\r\n\r\nGeometric mean: 1.16x faster\r\n```\r\n\u003cdetails\u003e\u003csummary\u003eBenchmark script\u003c/summary\u003e\r\n\r\n```\r\nimport pyperf\r\nrunner = pyperf.Runner()\r\n\r\nloop = \"\"\"\r\ndef g(n):\r\n    x=0\r\n    for ii in range(n):\r\n        x += 1\r\n\"\"\"\r\n        \r\nfor s in [1, 10, 100, 400]:\r\n\ttime = runner.timeit(name=f'range({s})', stmt=f\"range({s})\")\r\n\ttime = runner.timeit(name=f'iter(range({s}))', stmt=f\"iter(range({s}))\")\r\n\ttime = runner.timeit(name=f'list(range({s}))', stmt=f\"list(range({s}))\")\r\n\ttime = runner.timeit(name=f'list(iter(range({s})))', stmt=f\"list(iter(range({s})))\")\r\n\r\n\ttime = runner.timeit(name=f'range(2, {s})', stmt=f\"range(2, {s})\")\r\n\ttime = runner.timeit(name=f'iter(range(2, {s}))', stmt=f\"iter(range(2, {s}))\")\r\n\ttime = runner.timeit(name=f'list(iter(range(2, {s})))', stmt=f\"list(iter(range(2, {s})))\")\r\n\r\n\ttime = runner.timeit(name=f'for loop length {s}', stmt=f\"g({s})\", setup=loop)\r\n\r\n``\r\n\u003c/details\u003e\r\n\r\nOn the pyperformance test suite (actually, a subset of the suite, not all benchmarks run on my system) shows the percentage of successfull freelist allocations increases about 1%.\r\n\r\nMain:\r\n```\r\nAllocations from freelist \t2,004,971,371 \t39.8%\r\nFrees to freelist \t2,005,350,418 \t\r\nAllocations \t3,034,877,938 \t60.2%\r\nAllocations to 512 bytes \t3,008,791,812 \t59.7%\r\nAllocations to 4 kbytes \t18,648,072 \t0.4%\r\nAllocations over 4 kbytes \t7,438,054 \t0.1%\r\nFrees \t3,142,033,922 \t\r\n```\r\nPR\r\n```\r\nAllocations from freelist \t2,064,126,652 \t40.8%\r\nFrees to freelist \t2,064,499,538 \t\r\nAllocations \t2,989,239,063 \t59.2%\r\nAllocations to 512 bytes \t2,963,207,194 \t58.6%\r\nAllocations to 4 kbytes \t18,596,157 \t0.4%\r\nAllocations over 4 kbytes \t7,435,712 \t0.1%\r\nFrees \t3,096,349,170 \t\r\n```\r\n(Some quick testing shows that most of the allocations not via freelists are due to python int objects, so that is another candidate to use freelists for)\r\n\r\n\r\n\r\n### Has this already been discussed elsewhere?\r\n\r\nNo response given\r\n\r\n### Links to previous discussion of this feature:\r\n\r\nSome references to discussions on freelists:\r\n\r\n* https://github.com/python/cpython/pull/121934\r\n* https://github.com/faster-cpython/ideas/discussions/132\r\n* https://github.com/python/cpython/issues/91912\r\n* https://github.com/python/cpython/pull/101453\r\n\r\n\u003c!-- gh-linked-prs --\u003e\r\n### Linked PRs\r\n* gh-128368\r\n* gh-128592\r\n* gh-128594\r\n* gh-128619\r\n* gh-128692\r\n* gh-129638\n* gh-129921\n* gh-132319\n* gh-135233\n\u003c!-- /gh-linked-prs --\u003e\r\n","author":{"url":"https://github.com/eendebakpt","@type":"Person","name":"eendebakpt"},"datePublished":"2024-11-11T21:33:21.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":5},"url":"https://github.com/126703/cpython/issues/126703"}