Modules/_functoolsmodule.c (part 6)

Source:

cpython 3.14 @ ab2d84fe1023/Modules/_functoolsmodule.c ↗

This annotation covers the C-level lru_cache implementation. See lib_functools5_detail for the Python-level lru_cache algorithm description.

Map

Lines	Symbol	Role
1-80	_lru_cache_wrapper type	C struct holding the cache state
81-180	lru_cache_call	Cache lookup and call dispatch
181-280	make_key in C	Hash args into a cache key
281-360	LRU list manipulation	Move-to-front and eviction in C
361-500	cache_info / cache_clear C	Statistics and reset

Reading

lru_cache_call

// CPython: Modules/_functoolsmodule.c:820 lru_cache_call
static PyObject *
lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
{
    PyObject *key = make_key(self, args, kwds);
    /* Lookup in the cache dict */
    lru_list_elem *link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
    if (link != NULL) {
        /* Cache hit: move to front of LRU list */
        lru_cache_move_link_to_front(self, link);
        self->hits++;
        PyObject *result = Py_NewRef(link->result);
        Py_DECREF(key);
        return result;
    }
    /* Cache miss: call the wrapped function */
    PyObject *result = PyObject_Call(self->func, args, kwds);
    if (self->maxsize > 0 && PyDict_GET_SIZE(self->cache) >= self->maxsize) {
        /* Evict LRU entry */
        lru_cache_evict(self);
    }
    lru_cache_append(self, key, result);
    self->misses++;
    return result;
}

The C implementation avoids Python interpreter overhead for the cache lookup. The LRU list is a circular doubly linked list of lru_list_elem structs. Cache hits are the fast path: one dict lookup + pointer manipulation.

make_key in C

// CPython: Modules/_functoolsmodule.c:680 make_key
static PyObject *
make_key(lru_cache_object *self, PyObject *args, PyObject *kwds)
{
    /* Build a hashable key from args and kwds */
    Py_ssize_t nargs = PyTuple_GET_SIZE(args);
    Py_ssize_t nkwds = kwds ? PyDict_GET_SIZE(kwds) : 0;
    if (nkwds == 0 && !self->typed) {
        /* Fast path: single arg or tuple key */
        if (nargs == 1) {
            PyObject *arg = PyTuple_GET_ITEM(args, 0);
            if (PyUnicode_CheckExact(arg) || PyLong_CheckExact(arg))
                return Py_NewRef(arg);
        }
        return Py_NewRef(args);
    }
    /* General case: build a combined tuple */
    ...
}

Single-int and single-string keys bypass tuple creation for maximum speed. Combined tuples for multi-arg calls are built by extending the args tuple with keyword pairs.

gopy notes

The C _lru_cache_wrapper is module/functools.CacheLRU in module/functools/module.go. The LRU list is a lruList struct with head and tail pointers. make_key uses objects.TupleNew for multi-arg keys and direct object references for single-primitive keys. Cache stats are atomic counters.