Thanks for your update :)

Thank you so much for reviewing and pointing out the weakness in the LRU cache :)

@pablogsal, @shihai1991, @methane: I've reverted the LRU cache optimisations as per @vstinner's request.

If you want to hide the functools._lru_list_elem type, the lru_cache_tp_traverse() function must not traverse its type. Otherwise, there is a risk that the type is discovered using gc.get_objects() or a similar function.

Right now, the functools._lru_list_elem type is hidden in the main branch and it doesn't implement the GC protocol. In this case, the current code for it in lru_cache_tp_traverse() in ok:

    lru_list_elem *link = self->root.next;
    while (link != &self->root) {
        lru_list_elem *next = link->next;
        Py_VISIT(link->key);
        Py_VISIT(link->result);
        link = next;
    }

And the current code for it in lru_cache_cache_clear() is also ok:

    lru_cache_clear_list(list);

But you still need to add Py_VISIT(Py_TYPE(self)); in lru_cache_tp_traverse().

Since the lru_cache is way more complicated, I suggest to restrict this PR to functools.KeyWrapper and partial type, and write a second PR just for the lru_cache type.

Since the lru_cache is way more complicated, I suggest to restrict this PR to functools.KeyWrapper and partial type, and write a second PR just for the lru_cache type.

Reverting fc39917 should be sufficient; no need to open a new PR.

UPDATE: The PR now adds GC support to the KeyWrapper and partial types, and modifies lru_cache_tp_traverse to visit the LRU cache type and the LRU cache element type.

If you want to hide the functools._lru_list_elem type, the lru_cache_tp_traverse() function must not traverse its type. Otherwise, there is a risk that the type is discovered using gc.get_objects() or a similar function.

Since _lru_list_elem is not GC-tracked type, gc.get_objects() don't leak _lru_list_elem regardless lru_cache_tp_traverse() visit _lru_list_elem or not.

Right now, the functools._lru_list_elem type is hidden in the main branch and it doesn't implement the GC protocol. In this case, the current code for it in lru_cache_tp_traverse() in ok:

Current PR breaks circular reference correctly. See #26363 (comment)

Since _lru_list_elem is hidden and immutable now, it is OK to remove Py_VISIT(Py_TYPE(link)); if we are sure about _lru_list_elem_type don't create circular reference.
But I am not sure about it. So I feel current PR is the best. It breaks circular reference correctly anyway.

Since _lru_list_elem is hidden and immutable now [...]

It's not immutable; only static types and heap types with the Py_TPFLAGS_IMMUTABLETYPE flag are immutable.

@methane: "Since _lru_list_elem is not GC-tracked type, gc.get_objects() don't leak _lru_list_elem regardless lru_cache_tp_traverse() visit _lru_list_elem or not."

It doesn't matter if the type implements the protocol or not. As soon as there is a Py_VISIT() call on it, it is exposed in gc.get_objects().

I tested the current PR (commit 6313247, Revert "Revert LRU cache element optimisation"):

static int
lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
{
    ...
    lru_list_elem *link = self->root.next;
    while (link != &self->root) {
        lru_list_elem *next = link->next;
        Py_VISIT(link->key);
        Py_VISIT(link->result);
        Py_VISIT(Py_TYPE(link));  // <==== HERE
        link = next;
    }
    ...
}

Example:

$ cat x.py 
import functools

class Value:
    pass
value = Value()

@functools.lru_cache
def func():
    return value

func()

$ ./python -i x.py 
>>> import gc
>>> isinstance(int, type)
True
>>> types=[obj for obj in gc.get_objects() if isinstance(obj, type)]
>>> lru=[type for type in types if 'lru' in type.__qualname__]
>>> lru
[<class 'functools._lru_cache_wrapper'>, <class 'functools._lru_list_elem'>]

Here is the hidden functools._lru_list_elem type.

@erlend-aasland: Can you please leave LRU unchanged in this PR and create a new PR just for LRU? The LRU problem sounds complicated and IMO it deserves its own change.

@erlend-aasland: Can you please leave LRU unchanged in this PR and create a new PR just for LRU? The LRU problem sounds complicated and IMO it deserves its own change.

Of course. Give me 2 minutes. UPDATE: Done.

@vstinner @methane, see GH-26423

Thanks for your insights and reviews, everyone!

Thanks @erlend-aasland for the PR, and @vstinner for merging it 🌮🎉.. I'm working now to backport this PR to: 3.10.
🐍🍒⛏🤖

GH-26424 is a backport of this pull request to the 3.10 branch.