Pyrsistent leaking memory on PMap discard

[jonathanslenders]

When adding and then removing many items from a PMap we are leaking memory somewhere.

Take the following script to reproduce:

import gc
from collections import Counter

from pyrsistent import pmap

# Create pmap, add 1M tems, then delete them.
m = pmap()
for i in range(1_000_000):
    m = m.set(i, i)
for i in range(1_000_000):
    m = m.discard(i)

# Now we have an empty map.
print(m)

# Print object counts.
gc.collect()
ct = Counter([type(o) for o in gc.get_objects()])
for k, v in sorted(ct.items(), key=lambda kv: kv[1])[-20:]:
    print([k, v])

This produces:

pmap({})
[<class 'types.GenericAlias'>, 76]
[<class 're._constants._NamedIntConstant'>, 76]
[<class 'staticmethod'>, 86]
[<class '_frozen_importlib.ModuleSpec'>, 90]
[<class 'module'>, 92]
[<class 'classmethod'>, 93]
[<class 'frozenset'>, 105]
[<class 'set'>, 117]
[<class 'cell'>, 214]
[<class 'member_descriptor'>, 378]
[<class 'type'>, 403]
[<class 'getset_descriptor'>, 433]
[<class 'builtin_function_or_method'>, 793]
[<class 'method_descriptor'>, 806]
[<class 'weakref.ReferenceType'>, 836]
[<class 'wrapper_descriptor'>, 1124]
[<class 'dict'>, 1258]
[<class 'tuple'>, 1316]
[<class 'function'>, 2313]
[<class 'list'>, 34080]

For comparison, after removing the set/discard lines from the Python snippet, we have the following that remains:

pmap({})
[<class 'types.GenericAlias'>, 76]
[<class 're._constants._NamedIntConstant'>, 76]
[<class 'staticmethod'>, 86]
[<class '_frozen_importlib.ModuleSpec'>, 90]
[<class 'module'>, 92]
[<class 'classmethod'>, 93]
[<class 'frozenset'>, 105]
[<class 'set'>, 117]
[<class 'cell'>, 214]
[<class 'list'>, 254]
[<class 'member_descriptor'>, 378]
[<class 'type'>, 403]
[<class 'getset_descriptor'>, 433]
[<class 'builtin_function_or_method'>, 794]
[<class 'method_descriptor'>, 806]
[<class 'weakref.ReferenceType'>, 838]
[<class 'wrapper_descriptor'>, 1124]
[<class 'dict'>, 1258]
[<class 'tuple'>, 1342]
[<class 'function'>, 2313]

Looks like len(m._buckets) is still 1048576 after discarding all entries.

[jonathanslenders]

Update: it turns out the outcome depends a lot on the specific Python version. (edit: and OS/cpu architecture)

For the above snippet, the number of leaked list instances:

• Python 3.14.2: 247
• Python 3.13.6: 34063 (huge leak)
• Python 3.12.3: 240

Execution time of the above snippet (after adding time.time() calls for measuring):

• Python 3.14.2: 1.9s
• Python 3.13.6: 5.9s
• Python 3.12.3: 26.4s

edit: this was on arm-linux. Looks like Python 3.14 also leaks on Mac OS and amd64-linux.
edit: probably we are leaking if the C extension was not compiled, but please read on.

[jonathanslenders]

The above was tested using pyrsistent==0.20.0.

When using latest HEAD from master, on both Python 3.13 and 3.14, the above script crashes with a segmentation fault during the 12th PMap.set iteration. I'm running on arm linux.

[jonathanslenders]

Disclaimer: AI-usage over here for troubleshooting:

About the segfault I was experiencing on arm-linux on the latest master commit, I asked GPT-5.1-Codex to troubleshoot my test script and look for a fix for the C code. Here's what it said:

• Root cause: PMap._Evolver._reallocate created an empty C-backed pvector evolver and immediately called extend. The C extension’s PVectorEvolver.extend never supported general iterables; calling it with a Python list (even empty) dereferenced invalid memory, so every map reallocation segfaulted.
• Fixed the underlying pvectorc implementation: rewrote PVectorEvolver_extend to iterate over the supplied iterable via PyObject_GetIter, appending items one-by-one (with proper ref management and error propagation). No change to Python-level pmap code was needed.

Codex produced the following patch:

--- a/pvectorcmodule.c
+++ b/pvectorcmodule.c
@@ -1312,8 +1312,25 @@ static PyObject *PVectorEvolver_append(PVectorEvolver *self, PyObject *args) {
   return NULL;
 }

-static PyObject *PVectorEvolver_extend(PVectorEvolver *self, PyObject *args) {
-  if (PyList_SetSlice(self->appendList, PY_SSIZE_T_MAX, PY_SSIZE_T_MAX, args) < 0) {
+static PyObject *PVectorEvolver_extend(PVectorEvolver *self, PyObject *iterable) {
+  PyObject *iterator = PyObject_GetIter(iterable);
+  if (iterator == NULL) {
+    return NULL;
+  }
+
+  PyObject *item;
+  while ((item = PyIter_Next(iterator))) {
+    if (PyList_Append(self->appendList, item) < 0) {
+      Py_DECREF(item);
+      Py_DECREF(iterator);
+      return NULL;
+    }
+    Py_DECREF(item);
+  }
+
+  Py_DECREF(iterator);
+
+  if (PyErr_Occurred()) {
     return NULL;
   }

I'm not familiar with the code, so not sure if this makes sense. It can be very wrong. But the test script works and all the tests are passing.

edit: This is not the solution. I had some freezes in my application, likely due to the while-loop in this patch. (I hope to get some time to actually read through the whole code base.)