Skip to content

gh-137103: A faster check_circular #137286

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 6 commits into
base: main
Choose a base branch
from
Open

gh-137103: A faster check_circular #137286

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
0595ee7
Faster happy path, skips contains
aivarsk Jul 28, 2025
4e7465a
Reuse hash
aivarsk Jul 29, 2025
9bfa132
Remove extra lines, fix review issues
aivarsk Aug 4, 2025
4b92eb0
Add {}
aivarsk Aug 4, 2025
ba09a5b
Merge remote-tracking branch 'origin/main' into no_contains
aivarsk Aug 4, 2025
35f48cf
add news
aivarsk Aug 4, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions Misc/NEWS.d/next/Library/2025-08-04-22-37-02.gh-issue-137103.k6UCKy.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,3 @@
Make ``check_circular`` faster by skipping ``PyDict_Contains`` and comparing
dict size before and after adding an item and using ``_KnownHash`` functions
to calculate the hash only once.
58 changes: 37 additions & 21 deletions Modules/_json.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,6 +10,7 @@

#include "Python.h"
#include "pycore_ceval.h" // _Py_EnterRecursiveCall()
#include "pycore_dict.h" // _PyDict_SetItem_KnownHash()
#include "pycore_global_strings.h" // _Py_ID()
#include "pycore_pyerrors.h" // _PyErr_FormatNote
#include "pycore_runtime.h" // _PyRuntime
Expand Down Expand Up @@ -1523,19 +1524,24 @@ encoder_listencode_obj(PyEncoderObject *s, PyUnicodeWriter *writer,
}
else {
PyObject *ident = NULL;
Py_hash_t ident_hash = -1;
if (s->markers != Py_None) {
int has_key;
Py_ssize_t len;
ident = PyLong_FromVoidPtr(obj);
if (ident == NULL)
return -1;
has_key = PyDict_Contains(s->markers, ident);
if (has_key) {
if (has_key != -1)
PyErr_SetString(PyExc_ValueError, "Circular reference detected");
ident_hash = PyObject_Hash(ident);
if (ident_hash == -1) {
Py_DECREF(ident);
return -1;
}
if (PyDict_SetItem(s->markers, ident, obj)) {
len = PyDict_GET_SIZE(s->markers);
if (_PyDict_SetItem_KnownHash(s->markers, ident, obj, ident_hash)) {
Py_DECREF(ident);
return -1;
}
if (PyDict_GET_SIZE(s->markers) == len) {
PyErr_SetString(PyExc_ValueError, "Circular reference detected");
Py_DECREF(ident);
return -1;
}
Expand All @@ -1561,7 +1567,7 @@ encoder_listencode_obj(PyEncoderObject *s, PyUnicodeWriter *writer,
return -1;
}
if (ident != NULL) {
if (PyDict_DelItem(s->markers, ident)) {
if (_PyDict_DelItem_KnownHash(s->markers, ident, ident_hash)) {
Py_XDECREF(ident);
return -1;
}
Expand Down Expand Up @@ -1652,6 +1658,7 @@ encoder_listencode_dict(PyEncoderObject *s, PyUnicodeWriter *writer,
PyObject *ident = NULL;
PyObject *items = NULL;
PyObject *key, *value;
Py_hash_t ident_hash = -1;
bool first = true;

if (PyDict_GET_SIZE(dct) == 0) {
Expand All @@ -1660,17 +1667,20 @@ encoder_listencode_dict(PyEncoderObject *s, PyUnicodeWriter *writer,
}

if (s->markers != Py_None) {
int has_key;
Py_ssize_t len;
ident = PyLong_FromVoidPtr(dct);
if (ident == NULL)
goto bail;
has_key = PyDict_Contains(s->markers, ident);
if (has_key) {
if (has_key != -1)
PyErr_SetString(PyExc_ValueError, "Circular reference detected");
ident_hash = PyObject_Hash(ident);
if (ident_hash == -1) {
goto bail;
}
len = PyDict_GET_SIZE(s->markers);
if (_PyDict_SetItem_KnownHash(s->markers, ident, dct, ident_hash)) {
goto bail;
}
if (PyDict_SetItem(s->markers, ident, dct)) {
if (PyDict_GET_SIZE(s->markers) == len) {
PyErr_SetString(PyExc_ValueError, "Circular reference detected");
goto bail;
}
}
Expand Down Expand Up @@ -1720,8 +1730,9 @@ encoder_listencode_dict(PyEncoderObject *s, PyUnicodeWriter *writer,
}

if (ident != NULL) {
if (PyDict_DelItem(s->markers, ident))
if (_PyDict_DelItem_KnownHash(s->markers, ident, ident_hash)) {
goto bail;
}
Py_CLEAR(ident);
}
if (s->indent != Py_None && !first) {
Expand Down Expand Up @@ -1750,6 +1761,7 @@ encoder_listencode_list(PyEncoderObject *s, PyUnicodeWriter *writer,
PyObject *ident = NULL;
PyObject *s_fast = NULL;
Py_ssize_t i;
Py_hash_t ident_hash = -1;

ident = NULL;
s_fast = PySequence_Fast(seq, "_iterencode_list needs a sequence");
Expand All @@ -1761,17 +1773,20 @@ encoder_listencode_list(PyEncoderObject *s, PyUnicodeWriter *writer,
}

if (s->markers != Py_None) {
int has_key;
Py_ssize_t len;
ident = PyLong_FromVoidPtr(seq);
if (ident == NULL)
goto bail;
has_key = PyDict_Contains(s->markers, ident);
if (has_key) {
if (has_key != -1)
PyErr_SetString(PyExc_ValueError, "Circular reference detected");
ident_hash = PyObject_Hash(ident);
if (ident_hash == -1) {
goto bail;
}
if (PyDict_SetItem(s->markers, ident, seq)) {
len = PyDict_GET_SIZE(s->markers);
if (_PyDict_SetItem_KnownHash(s->markers, ident, seq, ident_hash)) {
goto bail;
}
if (PyDict_GET_SIZE(s->markers) == len) {
PyErr_SetString(PyExc_ValueError, "Circular reference detected");
goto bail;
}
}
Expand Down Expand Up @@ -1802,8 +1817,9 @@ encoder_listencode_list(PyEncoderObject *s, PyUnicodeWriter *writer,
}
}
if (ident != NULL) {
if (PyDict_DelItem(s->markers, ident))
if (_PyDict_DelItem_KnownHash(s->markers, ident, ident_hash)) {
goto bail;
}
Py_CLEAR(ident);
}

Expand Down
Loading