functools._make_key is slow due to creation of lots of temporary tuples - optimizable with list

[heikkitoivonen]

Feature or enhancement

Proposal:

First, I am not sure how important this is because even though _make_key could be optimized, AFAIK only _lru_cache_wrapper uses it, and that may be overwritten by this import:

try:
    from _functools import _lru_cache_wrapper
except ImportError:
    pass

If we do think it is worth optimizing, then this change (I can make a PR if needed):

@@ -537,18 +537,17 @@ def _make_key(args, kwds, typed,
     # Formerly, we sorted() the kwds before looping.  The new way is *much*
     # faster; however, it means that f(x=1, y=2) will now be treated as a
     # distinct call from f(y=2, x=1) which will be cached separately.
-    key = args
+    key = list(args) if kwds or typed else args
     if kwds:
-        key += kwd_mark
-        for item in kwds.items():
-            key += item
+        key.append(kwd_mark)
+        key.extend(kwds.items())
     if typed:
-        key += tuple(type(v) for v in args)
+        key.extend([type(v) for v in args])
         if kwds:
-            key += tuple(type(v) for v in kwds.values())
+            key.extend([type(v) for v in kwds.values()])
     elif len(key) == 1 and type(key[0]) in fasttypes:
         return key[0]
-    return key
+    return tuple(key)
 
 def lru_cache(maxsize=128, typed=False):
     """Least-recently-used cache decorator.

makes _make_key significantly faster:

from functools import _make_key as mk

timeit mk((), {}, False)
257 ns ± 0.645 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

timeit mk((1, 2, 3), {1:2, 2:3, 3:4}, False)
861 ns ± 0.597 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

timeit mk((1, 2, 3), {1:2, 2:3, 3:4}, True)
3.03 μs ± 6.85 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

to

timeit mk((), {}, False)
239 ns ± 0.429 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.08x faster

timeit mk((1, 2, 3), {1:2, 2:3, 3:4}, False)
700 ns ± 2.74 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.23x faster

timeit mk((1, 2, 3), {1:2, 2:3, 3:4}, True)
1.25 μs ± 2.24 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
2.42x faster

If we remove the import, then a benchmark for lru_cache, which is the public API of this code, shows 1.01x to 1.68x improvement depending on use case:

lru_cache_baseline.json
=======================

Python version: 3.15.0a3+ (64-bit) revision e0fb2780649
Report on macOS-14.6.1-arm64-arm-64bit-Mach-O
Number of logical CPUs: 8
Start date: 2026-01-13 20:58:56.174556
End date: 2026-01-13 21:02:28.432336

lru_cache_optimized.json
========================

Python version: 3.15.0a3+ (64-bit) revision e0fb2780649
Report on macOS-14.6.1-arm64-arm-64bit-Mach-O
Number of logical CPUs: 8
Start date: 2026-01-13 21:04:47.595674
End date: 2026-01-13 21:08:21.508782

### lru_cache_hit_args_and_kwargs ###
Mean +- std dev: 104 us +- 1 us -> 103 us +- 1 us: 1.01x faster
Not significant

### lru_cache_hit_args_and_multiple_kwargs ###
Mean +- std dev: 126 us +- 1 us -> 113 us +- 1 us: 1.12x faster
Significant (t=65.57)

### lru_cache_hit_multiple_args ###
Mean +- std dev: 68.5 us +- 0.9 us -> 66.1 us +- 0.6 us: 1.04x faster
Significant (t=17.21)

### lru_cache_hit_multiple_kwargs ###
Mean +- std dev: 121 us +- 1 us -> 106 us +- 1 us: 1.14x faster
Significant (t=91.32)

### lru_cache_hit_single_float ###
Mean +- std dev: 71.7 us +- 0.6 us -> 69.5 us +- 1.1 us: 1.03x faster
Significant (t=13.89)

### lru_cache_hit_single_int ###
Mean +- std dev: 69.0 us +- 0.7 us -> 65.4 us +- 0.7 us: 1.05x faster
Significant (t=27.70)

### lru_cache_hit_single_kwarg ###
Mean +- std dev: 98.3 us +- 2.7 us -> 95.1 us +- 0.9 us: 1.03x faster
Significant (t=8.68)

### lru_cache_hit_single_str ###
Mean +- std dev: 69.8 us +- 0.7 us -> 66.7 us +- 0.5 us: 1.05x faster
Significant (t=27.05)

### lru_cache_hit_typed_args_and_kwargs ###
Mean +- std dev: 247 us +- 2 us -> 147 us +- 1 us: 1.68x faster
Significant (t=367.54)

### lru_cache_hit_typed_multiple_args ###
Mean +- std dev: 143 us +- 2 us -> 103 us +- 1 us: 1.38x faster
Significant (t=158.01)

### lru_cache_hit_typed_single_arg ###
Mean +- std dev: 123 us +- 1 us -> 92 us +- 0 us: 1.34x faster
Significant (t=212.03)

### lru_cache_hit_typed_single_kwarg ###
Mean +- std dev: 213 us +- 2 us -> 128 us +- 2 us: 1.66x faster
Significant (t=233.02)

### lru_cache_miss_single_int ###
Mean +- std dev: 68.5 us +- 0.8 us -> 65.0 us +- 0.5 us: 1.05x faster
Significant (t=29.21)

### lru_cache_miss_single_kwarg ###
Mean +- std dev: 96.6 us +- 0.7 us -> 94.4 us +- 0.5 us: 1.02x faster
Significant (t=19.86)

### lru_cache_miss_typed_args_kwargs ###
Mean +- std dev: 237 us +- 3 us -> 143 us +- 1 us: 1.65x faster
Significant (t=260.03)

The benchmark was written by Claude Code, and since it is 233 lines long I am attaching it rather than inlining.

bm_lru_cache.py

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

Linked PRs

• gh-143825: Micro-optimizations to _make_key. #143844

[sergey-miryanov]

I believe it is related to #139951

cc @nascheme @markshannon

[sergey-miryanov]

@heikkitoivonen Thanks for the report. Could you please run your benchmarks on 3.14.0 and 3.14.1?

[serhiy-storchaka]

I am surprised by your result for _make_key((), {}, False). The current code should return an empty tuple which is already passed as argument, without creating temporary list and calling methods. The proposed code does more work, it cannot be 8% faster. Something is wrong with these benchmarks.

The current code is optimized for the case of few or no keyword arguments. Even if you have one keyword argument -- this is one tuple concatenation. It is expected to be cheaper than creating a temporary list and convert between tuples and lists. The proposed code will be substantially faster only if there are many keyword arguments (maybe many tens or hundreds) -- this is far from the common case. If this is your case, it may be more efficient to create a wrapper around the cached function which would pass kwargs as a single dict argument.

cc @rhettinger

[rhettinger]

The current code is optimized for the case of few or no keyword arguments. Even if you have one keyword argument -- this is one tuple concatenation. It is expected to be cheaper than creating a temporary list and convert between tuples and lists.

This analysis makes sense. I would add that the typed case is almost never used (by a factor of thousands).

Depending on the cost of the tuple/list/tuple conversion (generally very quick), it may be worthwhile to focus on the kwds section only:

diff --git a/Lib/functools.py b/Lib/functools.py
index 836eb680ccd..2293172c0c5 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -539,9 +539,11 @@ def _make_key(args, kwds, typed,
     # distinct call from f(y=2, x=1) which will be cached separately.
     key = args
     if kwds:
+        key = list(key)
         key += kwd_mark
         for item in kwds.items():
             key += item
+        key = tuple(key)
     if typed:
         key += tuple(type(v) for v in args)
         if kwds:

Our main concern is to not damage the common cases in an effort to improve uncommon cases. When keyword arguments are used, the number of them likely follows an inverse power distribution (i.e. for every 1 case of two kwargs for every 10 cases of one kwarg, 1 case of three args for every 10 cases of two kwargs, etc).

AFAIK only _lru_cache_wrapper uses it, and that may be overwritten by this import:

Right. So any edit to the pure python version will only be relevant to users of PyPy. CPython benchmarks won't tell us anything useful.

Something is wrong with these benchmarks.

Of course, this needs to be addressed as well.

[heikkitoivonen]

TL;DR: The original has generator expressions, which makes it slower.

I agree that the results for _make_key((), {}, False) look suspicious. I run the test several times yesterday, and today I brought just those two versions of the function into a new file to test things in isolation, and that is still what I am seeing.

I tried different things to see what might make it go faster, one isolated change at a time:

1. slower: key = list(args) if (kwds or typed) else args
2. slower: return tuple(key)
3. slower: 1 & 2
4. slower: 3 & key.append(kwd_mark)
5. slower: 4 & key.extend(kwds.items())
6. slower: 5 & key.extend([type(v) for v in args])
7. faster: 6 & key.extend([type(v) for v in kwds.values()]) (this is the complete patch)
8. slower: just key.extend([type(v) for v in kwds.values()])

Changes 4 through 8 should have no effect, because they are behind if-branches that are not executed. Only thing I can think of at this point is that the patch causes the whole thing to compile to something that executes faster.

I then saved the dis output and looked at both. Unfortunately I don't know enough of that format to understand it, so I had to ask Claude. This is what Claude said:

● Found it! Look at the very first instruction in each:                         
                                                                                
  Slow (original):                                                              
  Line 1:   MAKE_CELL                6 (type)                                   
                                                                                
  Fast:                                                                         
  Line 1:   RESUME                   0                                          
                                                                                
  The original has MAKE_CELL at the start because it uses a generator           
  expression:                                                                   
  key += tuple(type(v) for v in args)  # generator expression captures `type`   
                                                                                
  This requires creating a cell object for the type variable closure, even when 
  that code path is never executed.                                                                                                           

So the difference comes down to generator (original) vs not (optimized).

I then confirmed the finding by changing the original to this:

@@ -543,9 +543,9 @@ def _make_key(args, kwds, typed,
         for item in kwds.items():
             key += item
     if typed:
-        key += tuple(type(v) for v in args)
+        key += tuple([type(v) for v in args])
         if kwds:
-            key += tuple(type(v) for v in kwds.values())
+            key += tuple([type(v) for v in kwds.values()])
     elif len(key) == 1 and type(key[0]) in fasttypes:
         return key[0]
     return key

Now the numbers look like this:

timeit mk((), {}, False)
207 ns ± 0.63 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

to

timeit mk((), {}, False)
237 ns ± 0.678 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

So in summary, the patch, tests and test numbers look correct.

[serhiy-storchaka]

This all is just quirks of the current optimizer. Currently, tuple([x for x in it]) is faster than tuple(x for x in it). This can be reversed in future (there is an open issue for this), and then this microoptimization will be wasted.