Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(87789)

Unified Diff: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Patch Set: Created 5 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
« Lib/test/test_functools.py ('K') | « Lib/test/test_functools.py ('k') | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
--- a/Modules/_functoolsmodule.c Thu Nov 21 11:07:45 2013 -0800
+++ b/Modules/_functoolsmodule.c Fri Nov 22 19:48:06 2013 +0200
@@ -2,6 +2,10 @@
#include "Python.h"
#include "structmember.h"
+#ifdef WITH_THREAD
+#include "pythread.h"
AntoinePitrou 2013/11/22 20:36:58 You don't seem to need it right now... (but see be
+#endif
+
/* _functools module written and maintained
by Hye-Shik Chang <perky@FreeBSD.org>
with adaptations by Raymond Hettinger <python@rcn.com>
@@ -540,6 +544,526 @@
of the sequence in the calculation, and serves as a default when the\n\
sequence is empty.");
+/* lru_cache object **********************************************************/
+
+/* this object is used delimit args and keywords in the cache keys */
+static PyObject *kwd_mark = NULL;
+
+struct lru_list_elem;
+struct lru_cache_object;
+
+typedef struct lru_list_elem {
+ PyObject_HEAD
+ struct lru_list_elem *prev, *next; /* borrowed links */
+ PyObject *key, *result;
+} lru_list_elem;
+
+static void
+lru_list_elem_dealloc(lru_list_elem *link)
+{
+ Py_DECREF(link->key);
AntoinePitrou 2013/11/22 20:36:58 Py_XDECREF, no? tp_clear could have been called be
storchaka 2013/11/22 21:54:56 Done.
+ Py_DECREF(link->result);
+ PyObject_FREE(link);
AntoinePitrou 2013/11/22 20:36:58 PyObject_GC_Del, no?
storchaka 2013/11/22 21:54:56 Done.
+}
+
+static int
+lru_list_elem_traverse(lru_list_elem *link, visitproc visit, void *arg)
+{
+ Py_VISIT(link->key);
+ Py_VISIT(link->result);
+ return 0;
+}
+
+static int
+lru_list_elem_clear(lru_list_elem *link)
+{
+ Py_CLEAR(link->key);
+ Py_CLEAR(link->result);
+ return 0;
+}
+
+static PyTypeObject lru_list_elem_type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "functools._lru_list_elem", /* tp_name */
+ sizeof(lru_list_elem), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)lru_list_elem_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_reserved */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT, /* tp_flags */
AntoinePitrou 2013/11/22 20:36:58 It seems you should add the GC flags here.
storchaka 2013/11/22 21:54:56 Done.
+ 0, /* tp_doc */
+ (traverseproc)lru_list_elem_traverse, /* tp_traverse */
+ (inquiry)lru_list_elem_clear, /* tp_clear */
+};
+
+
+typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject *, PyObject *);
+
+typedef struct lru_cache_object {
+ lru_list_elem root; /* includes PyObject_HEAD */
+ Py_ssize_t maxsize;
+ PyObject *maxsize_O;
+ PyObject *func;
+ lru_cache_ternaryfunc wrapper;
+ PyObject *cache;
+ PyObject *cache_info_type;
+ Py_ssize_t misses, hits;
+ int typed;
+ PyObject *dict;
+ int full;
+} lru_cache_object;
+
+static PyTypeObject lru_cache_type;
+
+static PyObject *
+lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
AntoinePitrou 2013/11/22 20:36:58 This seems to miss one optimization of functools.p
storchaka 2013/11/22 21:54:56 I will do it later (with other make_key optimizati
+{
+ PyObject *key, *sorted_items;
+ Py_ssize_t key_size, pos, key_pos;
+
+ /* short path, key will match args anyway, which is a tuple */
+ if (!typed && !kwds) {
+ Py_INCREF(args);
+ return args;
+ }
+
+ if (kwds && PyDict_Size(kwds) > 0) {
+ sorted_items = PyDict_Items(kwds);
+ if (!sorted_items)
+ return NULL;
+ if (PyList_Sort(sorted_items) < 0) {
+ Py_DECREF(sorted_items);
+ return NULL;
+ }
+ } else
+ sorted_items = NULL;
+
+ key_size = PyTuple_GET_SIZE(args);
+ if (sorted_items)
+ key_size += PyList_GET_SIZE(sorted_items);
+ if (typed)
+ key_size *= 2;
+ if (sorted_items)
+ key_size++;
+
+ key = PyTuple_New(key_size);
AntoinePitrou 2013/11/22 20:36:58 You should check for error here.
storchaka 2013/11/22 21:54:56 Done.
+ key_pos = 0;
+
+ for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
+ PyObject *item = PyTuple_GET_ITEM(args, pos);
+ Py_INCREF(item);
+ PyTuple_SET_ITEM(key, key_pos++, item);
+ }
+ if (sorted_items) {
+ Py_INCREF(kwd_mark);
+ PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
+ for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
+ PyObject *item = PyList_GET_ITEM(sorted_items, pos);
+ Py_INCREF(item);
+ PyTuple_SET_ITEM(key, key_pos++, item);
+ }
+ }
+ if (typed) {
+ for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
+ PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
+ Py_INCREF(item);
+ PyTuple_SET_ITEM(key, key_pos++, item);
+ }
+ if (sorted_items) {
+ for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
+ PyObject *tp_items = PyList_GET_ITEM(sorted_items, pos);
+ PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(tp_items, 1));
+ Py_INCREF(item);
+ PyTuple_SET_ITEM(key, key_pos++, item);
+ }
+ }
+ }
+ assert(key_pos == key_size);
+
+ if (sorted_items)
+ Py_DECREF(sorted_items);
+ return key;
+}
+
+static PyObject *
+uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
+{
+ PyObject *result = PyObject_Call(self->func, args, kwds);
+ if (!result)
+ return NULL;
+ self->misses++;
AntoinePitrou 2013/11/22 20:36:58 Should be moved before the error return, IMO. (it'
storchaka 2013/11/22 21:54:56 It doesn't match functools.py.
+ return result;
+}
+
+static PyObject *
+infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
+{
+ PyObject *result;
+ PyObject *key = lru_cache_make_key(args, kwds, self->typed);
+ if (!key)
+ return NULL;
+ result = PyDict_GetItemWithError(self->cache, key);
+ if (result) {
+ Py_INCREF(result);
+ self->hits++;
+ Py_DECREF(key);
+ return result;
+ }
+ if (PyErr_Occurred()) {
+ Py_DECREF(key);
+ return NULL;
+ }
+ result = PyObject_Call(self->func, args, kwds);
+ if (!result) {
+ Py_DECREF(key);
+ return NULL;
+ }
+ if (PyDict_SetItem(self->cache, key, result) < 0) {
+ Py_DECREF(result);
+ Py_DECREF(key);
+ return NULL;
+ }
+ Py_DECREF(key);
+ self->misses++;
AntoinePitrou 2013/11/22 20:36:58 Should be moved before "PyErr_Occurred()" above.
storchaka 2013/11/22 21:54:56 It doesn't match functools.py.
+ return result;
+}
+
+static void
+lru_cache_extricate_link(lru_list_elem *link)
+{
+ link->prev->next = link->next;
+ link->next->prev = link->prev;
+}
+
+static void
+lru_cache_append_link(lru_cache_object *self, lru_list_elem *link)
+{
+ lru_list_elem *root = &self->root;
+ lru_list_elem *last = root->prev;
+ last->next = root->prev = link;
+ link->prev = last;
+ link->next = root;
+}
+
+static PyObject *
+bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
+{
+ lru_list_elem *link;
+ PyObject *key, *result;
+
+ key = lru_cache_make_key(args, kwds, self->typed);
+ if (!key)
+ return NULL;
+ link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
+ if (link) {
+ lru_cache_extricate_link(link);
+ lru_cache_append_link(self, link);
+ self->hits++;
+ result = link->result;
+ Py_INCREF(result);
+ Py_DECREF(key);
+ return result;
+ }
+ if (PyErr_Occurred()) {
+ Py_DECREF(key);
+ return NULL;
+ }
+ result = PyObject_Call(self->func, args, kwds);
+ if (!result) {
+ Py_DECREF(key);
+ return NULL;
+ }
+ if (self->full && self->root.next != &self->root) {
+ /* Use the oldest item to store the new key and result. */
+ PyObject *oldkey, *oldresult;
+ /* Extricate the oldest item. */
+ link = self->root.next;
+ lru_cache_extricate_link(link);
+ /* Remove it from the cache. */
+ if (PyDict_DelItem(self->cache, link->key) < 0) {
AntoinePitrou 2013/11/22 20:36:58 This destroys link, no? How can link still be vali
storchaka 2013/11/22 21:54:56 Link in a dict has a refcount 2. One for a dict, a
AntoinePitrou 2013/11/22 22:09:29 I think you should explain that in a comment somew
storchaka 2013/11/22 22:44:58 Done.
+ lru_cache_append_link(self, link);
+ Py_DECREF(key);
+ Py_DECREF(result);
+ return NULL;
+ }
+ /* Keep a reference to the old key and old result to
+ prevent their ref counts from going to zero during the
+ update. That will prevent potentially arbitrary object
+ clean-up code (i.e. __del__) from running while we're
+ still adjusting the links. */
+ oldkey = link->key;
+ oldresult = link->result;
+
+ link->key = key;
+ link->result = result;
+ if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
+ Py_DECREF(link);
+ Py_DECREF(oldkey);
+ Py_DECREF(oldresult);
+ return NULL;
+ }
+ lru_cache_append_link(self, link);
+ Py_INCREF(result); /* for return */
+ Py_DECREF(oldkey);
+ Py_DECREF(oldresult);
+ } else {
+ /* Put result in a new link at the front of the queue. */
+ link = (lru_list_elem *)PyObject_New(lru_list_elem,
AntoinePitrou 2013/11/22 20:36:58 Hmm, PyObject_GenericNew() does a lot more than th
storchaka 2013/11/22 21:54:56 May be PyObject_GC_New()? Done. I haven't found P
AntoinePitrou 2013/11/22 22:09:29 I think you also need PyObject_GC_Track... (the so
storchaka 2013/11/22 22:44:58 Done.
+ &lru_list_elem_type);
+ if (link == NULL) {
+ Py_DECREF(key);
+ Py_DECREF(result);
+ return NULL;
+ }
+
+ link->key = key;
+ link->result = result;
+ if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
AntoinePitrou 2013/11/22 20:36:58 This can also release the GIL.
storchaka 2013/11/22 21:54:56 This is why lru_cache_append_link() is called afte
+ Py_DECREF(link);
+ return NULL;
+ }
+ lru_cache_append_link(self, link);
AntoinePitrou 2013/11/22 20:36:58 At this point, one reference to link is owned by t
storchaka 2013/11/22 21:54:56 One by all linked list. Memory will no leak when t
+ Py_INCREF(result); /* for return */
+ self->full = (PyDict_Size(self->cache) >= self->maxsize);
+ }
+ self->misses++;
AntoinePitrou 2013/11/22 20:36:58 Should be moved before "PyErr_Occurred()" above.
storchaka 2013/11/22 21:54:56 It doesn't match functools.py.
+ return result;
+}
+
+static PyObject *
+lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
+{
+ PyObject *func, *maxsize_O, *cache_info_type;
+ int typed;
+ lru_cache_object *obj;
+ Py_ssize_t maxsize;
+ PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
+ static char *keywords[] = {"user_function", "maxsize", "typed",
+ "cache_info_type", NULL};
+
+ if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
+ &func, &maxsize_O, &typed,
+ &cache_info_type)) {
+ return NULL;
+ }
+
+ if (!PyCallable_Check(func)) {
+ PyErr_SetString(PyExc_TypeError,
+ "the first argument must be callable");
+ return NULL;
+ }
+
+ /* select the caching function, and make/inc maxsize_O */
+ if (maxsize_O == Py_None) {
+ wrapper = infinite_lru_cache_wrapper;
+ /* use this only to initialize lru_cache_object attribute maxsize */
+ maxsize = -1;
+ } else if (PyNumber_Check(maxsize_O)) {
+ maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
+ if (maxsize == -1 && PyErr_Occurred())
+ return NULL;
+ if (maxsize == 0)
+ wrapper = uncached_lru_cache_wrapper;
+ else
+ wrapper = bounded_lru_cache_wrapper;
+ } else {
+ PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
+ return NULL;
+ }
+
+ obj = (lru_cache_object *)type->tp_alloc(type, 0);
+ if (obj == NULL)
+ return NULL;
+
+ if (!(obj->cache = PyDict_New())) {
+ Py_DECREF(obj);
+ return NULL;
+ }
+
+ obj->root.prev = &obj->root;
+ obj->root.next = &obj->root;
+ obj->maxsize = maxsize;
+ Py_INCREF(maxsize_O);
+ obj->maxsize_O = maxsize_O;
+ Py_INCREF(func);
+ obj->func = func;
+ obj->wrapper = wrapper;
+ obj->misses = obj->hits = 0;
+ obj->typed = typed;
+ Py_INCREF(cache_info_type);
+ obj->cache_info_type = cache_info_type;
+
+ return (PyObject *)obj;
+}
+
+static lru_list_elem *
+lru_cache_unlink_list(lru_cache_object *self)
+{
+ lru_list_elem *root = &self->root;
+ lru_list_elem *link = root->next;
+ if (link == root)
+ return NULL;
+ root->prev->next = NULL;
+ root->next = root->prev = root;
+ return link;
+}
+
+static void
+lru_cache_clear_list(lru_list_elem *link)
+{
+ while (link != NULL) {
+ lru_list_elem *next = link->next;
+ Py_DECREF(link);
+ link = next;
+ }
+}
+
+static void
+lru_cache_dealloc(lru_cache_object *obj)
+{
+ lru_list_elem *list = lru_cache_unlink_list(obj);
+ Py_XDECREF(obj->maxsize_O);
+ Py_XDECREF(obj->func);
+ Py_XDECREF(obj->cache);
+ Py_XDECREF(obj->dict);
+ Py_XDECREF(obj->cache_info_type);
+ lru_cache_clear_list(list);
+ Py_TYPE(obj)->tp_free(obj);
+}
+
+static PyObject *
+lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
+{
+ return self->wrapper(self, args, kwds);
+}
+
+static PyObject *
+lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
+{
+ return PyObject_CallFunction(self->cache_info_type, "nnOn",
+ self->hits, self->misses, self->maxsize_O,
+ PyDict_Size(self->cache));
+}
+
+static PyObject *
+lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
+{
+ lru_list_elem *list = lru_cache_unlink_list(self);
+ self->hits = self->misses = 0;
+ self->full = 0;
+ PyDict_Clear(self->cache);
+ lru_cache_clear_list(list);
+ Py_RETURN_NONE;
+}
+
+static int
+lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
+{
+ Py_VISIT(self->maxsize_O);
+ Py_VISIT(self->func);
+ Py_VISIT(self->cache);
+ Py_VISIT(self->cache_info_type);
+ Py_VISIT(self->dict);
+ return 0;
+}
+
+static int
+lru_cache_tp_clear(lru_cache_object *self)
+{
+ lru_list_elem *list = lru_cache_unlink_list(self);
+ Py_CLEAR(self->maxsize_O);
+ Py_CLEAR(self->func);
+ Py_CLEAR(self->cache);
+ Py_CLEAR(self->cache_info_type);
+ Py_CLEAR(self->dict);
+ lru_cache_clear_list(list);
+ return 0;
+}
+
+
+PyDoc_STRVAR(lru_cache_doc,
+"Create a cached callable that wraps another function.\n\
+\n\
+user_function: the function being cached\n\
+\n\
+maxsize: 0 for no caching\n\
+ None for unlimited cache size\n\
+ n for a bounded cache\n\
+\n\
+typed: False cache f(3) and f(3.0) as identical calls\n\
+ True cache f(3) and f(3.0) as distinct calls\n\
+\n\
+cache_info_type: namedtuple class with the fields:\n\
+ hits misses currsize maxsize\n"
+);
+
+static PyMethodDef lru_cache_methods[] = {
+ {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
+ {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
+ {NULL}
+};
+
+static PyGetSetDef lru_cache_getsetlist[] = {
+ {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
+ {NULL}
+};
+
+static PyTypeObject lru_cache_type = {
+ PyVarObject_HEAD_INIT(NULL, 0)
+ "functools._lru_cache_wrapper", /* tp_name */
+ sizeof(lru_cache_object), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)lru_cache_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_reserved */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ (ternaryfunc)lru_cache_call, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC,
+ /* tp_flags */
+ lru_cache_doc, /* tp_doc */
+ (traverseproc)lru_cache_tp_traverse,/* tp_traverse */
+ (inquiry)lru_cache_tp_clear, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ lru_cache_methods, /* tp_methods */
+ 0, /* tp_members */
+ lru_cache_getsetlist, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ offsetof(lru_cache_object, dict), /* tp_dictoffset */
+ 0, /* tp_init */
+ 0, /* tp_alloc */
+ lru_cache_new, /* tp_new */
+};
+
/* module level code ********************************************************/
PyDoc_STRVAR(module_doc,
@@ -552,6 +1076,11 @@
{NULL, NULL} /* sentinel */
};
+static void
+module_free(void *m)
+{
+ Py_XDECREF(kwd_mark);
AntoinePitrou 2013/11/22 20:36:58 Well, this should use Py_CLEAR.
storchaka 2013/11/22 21:54:56 Done.
+}
static struct PyModuleDef _functoolsmodule = {
PyModuleDef_HEAD_INIT,
@@ -562,7 +1091,7 @@
NULL,
NULL,
NULL,
- NULL
+ module_free,
};
PyMODINIT_FUNC
@@ -573,6 +1102,7 @@
char *name;
PyTypeObject *typelist[] = {
&partial_type,
+ &lru_cache_type,
NULL
};
@@ -580,6 +1110,12 @@
if (m == NULL)
return NULL;
+ kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL);
+ if (!kwd_mark) {
+ Py_DECREF(m);
+ return NULL;
+ }
+
for (i=0 ; typelist[i] != NULL ; i++) {
if (PyType_Ready(typelist[i]) < 0) {
Py_DECREF(m);
« Lib/test/test_functools.py ('K') | « Lib/test/test_functools.py ('k') | no next file » | no next file with comments »

RSS Feeds Recent Issues | This issue
This is Rietveld 894c83f36cb7+