GeezerVison is showing github.com — A better JSON check_circular · Issue #137103 · python/cpython
A better JSON check_circular #137103DescriptionFeature or enhancement
Proposal:
json.dump(check_circular=True) uses a dictionary to track all objects already visited and creates keys with PyLong_FromVoidPtr. There is another solution for recursive container types in CPython already: Py_ReprEnter and Py_ReprLeave.
I have a patch to replace the dictionary and custom object tracking with the CPython functions and that removes some code and also avoids allocating Long objects for each recursive call.
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Linked PRs
Activitypicnixz commented on Jul 25, 2025 Could you benchmark those changes please? I don't know which one will be faster but it would be good to know (also, memory benchmarks could be good). Don't forget to check the performance impact against both circular and non-circular objects. TiA! Reacted by Aivars Kalvāns aivarsk commented on Jul 25, 2025 ContributorAuthor More actions Here's pyperformance to start with:
before_json_markers.json
========================
Performance version: 1.11.0
Python version: 3.15.0a0 (64-bit) revision d7db0ee7ee
Report on Linux-6.11.0-29-generic-x86_64-with-glibc2.40
Number of logical CPUs: 8
Start date: 2025-07-25 18:55:12.638581
End date: 2025-07-25 18:55:25.621784
after_json_markers.json
=======================
Performance version: 1.11.0
Python version: 3.15.0a0 (64-bit) revision f7171eb2f2
Report on Linux-6.11.0-29-generic-x86_64-with-glibc2.40
Number of logical CPUs: 8
Start date: 2025-07-25 18:57:40.864653
End date: 2025-07-25 18:57:53.336472
### json_dumps ###
Mean +- std dev: 15.2 ms +- 0.6 ms -> 14.4 ms +- 0.3 ms: 1.06x faster
Significant (t=9.82)
aivarsk commented on Jul 28, 2025 ContributorAuthor More actions I tested a couple implementations using https://gist.github.com/aivarsk/f8aea7864155c948e8fb2e3b72f8dd61 : it creates a dictionary with a single nested element to stress the circular object check. In real cases the difference will be smaller compared to the real work done by json.dump. The results from my machine are here:
Original is the current implementation of the check: it allocates a new Long object for each container object and stores that in a dict.
List is a copy of Py_ReprEnter/Py_ReprLeave that uses a List to check if the container object was visited before aivarsk@e290481
Dict is similar to the original but it skips allocation of a Long object by using (abusing?) _PyDict_SetItem_KnownHash / _PyDict_DelItem_KnownHash functions aivarsk@703c26d
The list approach seems to be the faster that the original dict until recursion depth of hundreds but it gets worse quickly after that serhiy-storchaka commented on Jul 28, 2025 Thank you for your benchmarks, @aivarsk. They were done for the optimized build, right?
The version that uses _PyDict_SetItem_KnownHash is clever, but it depends on too many implementation details -- details of the dict object implementation, details of Py_HashPointer implementation, the fact that Py_hash has the same number of bits as a pointer, etc. There is a tiny chance of hash collision -- for pointers 0x...FFFF and 0x...FFEF. It is too risky to use it, because it can be broken without noticing.
It needs a version of dict which behaves well even if there a hash collision (using identity comparison instead of value comparison). You can search for IdentityDict in past discussion.
The list version works fine for most common cases. I believe that most user data has depth less than 10. Although the benefit is also small. But we should also consider extreme cases, when the list version complexity became quadratic. Could you extend your benchmarks to 10000 or even 100000? This will require changing the recursion limit, and for very deep recursion you can get stack overflow.
Consider also using a hybrid approach -- a list for small depth and a dict for large depth. For some depth we will pay double price, for a list and for a dict, so we need to test different thresholds from 100 to 1500.
Any of these changes conflict with the current private API -- _json.make_encoder takes the markers dict, ant the result has the markers attribute. It needs to be changed -- remove attribute and pass the boolean check_circular instead of markers. I hope nobody relies on that private API. aivarsk commented on Jul 28, 2025 ContributorAuthor More actions
They were done for the optimized build, right?
yes, it's -O3
The version that uses _PyDict_SetItem_KnownHash is clever, but it depends on too many implementation details -- details of the dict object implementation, details of Py_HashPointer implementation, the fact that Py_hash has the same number of bits as a pointer, etc. There is a tiny chance of hash collision -- for pointers 0x...FFFF and 0x...FFEF. It is too risky to use it, because it can be broken without noticing.
It is a hacky solution but perhaps a bit less than you assume:
The original solution converts address to Long https://github.com/python/cpython/blob/main/Modules/_json.c#L1528
and hash for the long is the long (pointer) itself with that -1 becomes -2 case.
The number of bits in pointer vs hash do not matter, the collisions are ok when they happen - same as when using a Long.
What happens when there are collisions, the keys are compared using PyObject_RichCompareBool https://github.com/python/cpython/blob/main/Objects/dictobject.c#L1099 and that works both on dict and list. For the happy flow it will match the hash and then return on pointer comparison. For collision it will have to compare the whole container object until the first difference.
The only case it could break (except radical changes to dict implementation) is when a key mutates while encoding.
That being said, it's still hacky and I would add some tests to assert behavior of same hash and multiple keys.
The list version works fine for most common cases. I believe that most user data has depth less than 10. Although the benefit is also small. But we should also consider extreme cases, when the list version complexity became quadratic. Could you extend your benchmarks to 10000 or even 100000? This will require changing the recursion limit, and for very deep recursion you can get stack overflow.
The benefit is a bit bigger in the < 10 range when there are more entries in the dict, I will produce results where the number of elements varies. The depth exercise tested the dict O(1) vs list O(n) algorithms and they break even for n>100. When we have 100 elements in a shallow dict (n < 10), the difference should be bigger.
Any of these changes conflict with the current private API -- _json.make_encoder takes the markers dict, ant the result has the markers attribute. It needs to be changed -- remove attribute and pass the boolean check_circular instead of markers. I hope nobody relies on that private API.
Sorry, did not understand this point. The current code enables/disables the "check_circular" based on the presence of the markers attribute https://github.com/python/cpython/blob/main/Modules/_json.c#L1526 nineteendo commented on Jul 28, 2025
yes, it's -O3
He's talking about --enable-optimizations and --with-lto. serhiy-storchaka commented on Jul 28, 2025 The number of bits matters, because if Py_hash did have less bits, collisions would be much more probable. Currently collisions are virtually impossible, but this may be changed in future.
When you compare deep lists or dicts, you can get a RecursionError. Especially if you do this in deep recursion. You may even overflow the stack on platforms with little stack.
It can also be an arbitrary object (if you use default), so comparison can execute arbitrary code which can raise arbitrary exception. A big difference with comparing the ids.
The current code enables/disables the "check_circular" based on the presence of the markers attribute
The _json.Encoder object has public markers attribute. If you use a list internally, the tracked objects are no longer present in the markers dict, so any code that uses it will be fooled. It is better to remove it. This is a breaking change, but I doubt that much code depends on it. This is not a public API, and it was not easy to use it anyway. Also, to pass None or {} to the constructor only to check if it is None is not the most direct way. It is better to just pass a boolean. All this means that a larger change is needed, this is not a transparent optimization. aivarsk commented on Jul 28, 2025 ContributorAuthor More actions
The number of bits matters, because if Py_hash did have less bits, collisions would be much more probable. Currently collisions are virtually impossible, but this may be changed in future.
I get the idea, I just don't see how it's different from current approach using Longs which produce the same hash value and the same collisions. nineteendo commented on Jul 28, 2025 It does matter because in this case you can't fall back to equality. aivarsk commented on Jul 28, 2025 ContributorAuthor More actions
It does matter because in this case you can't fall back to equality.
Is this on the bits and hash topic? I know that _KnownHash functions are hacky, etc. Not arguing that, not pushing that solution. All I'm saying is that Py_HashPointer does the same thing as PyLong_FromVoidPtr, it has the same hash value, same bits and same collisions, same "maybe changed in the future". nineteendo commented on Jul 28, 2025 Don't get me wrong I also like that solution. I'm just saying that if two objects have the same hash and are equal they are treated the same:
class MyList(list):
def __hash__(self):
return 0
class MyInt(int):
def __hash__(self):
return 0
# storing the object itself with a hash collision
print(len({MyList(), MyList()})) # 1
# storing the id with a hash collision
print(len({MyInt(0), MyInt(1)})) # 2So you do have to be careful. aivarsk commented on Jul 28, 2025 ContributorAuthor More actions For hash collision of MyList the code should be
print(len({MyList([1]), MyList([2])}))
or MyInt as follows to compare apples vs apples
print(len({MyInt(), MyInt()}))
When hash is the same, first a cheap comparison of pointers is done (if the same hash is for pointers pointing to the same thing, they are equal). Otherwise it compares the objects usint comparison that int/list/dict all have: https://github.com/python/cpython/blob/main/Objects/dictobject.c#L1099
>>> MyList() == MyList()
True
>>> MyInt() == MyInt()
True
>>> MyList([1]) == MyList([2])
False
>>> MyInt(1) == MyInt(2)
False
So you got length of 1 for the MyList because both lists are equal and 2 for the MyInt because they are not serhiy-storchaka commented on Jul 28, 2025
I just don't see how it's different from current approach using Longs which produce the same hash value and the same collisions.
If you use object IDs as keys, there is no problem, because in case of a hash collision you simply compare the object IDs. You do not call recursive or user defined __eq__ methods. aivarsk commented on Jul 30, 2025 ContributorAuthor More actions I did some more tests on more shallow dicts with more elements (x axis) and a couple depths: (https://gist.github.com/aivarsk/302b1d3d1e093d5de4b5def7a0e23f59) :
- nocheck is
json.dump(check_circular=False) as the limit how fast it could be. It's 2x faster because all elements are quite small and contain just the nested elements and nothing else
- default is
json.dump(check_circular=True) as the upper limit
- list is the
Py_ReprEnter/Py_ReprLeave style implementation with a list (but that becomes much slower in depth of hundreds) I think it's unstable because of list resizes (list lives in encoder object not in thread locals)
- contains is an experiment without breaking API: check circular by comparing dicts sizes before and after insert, it's faster than calling Contains. And then it used
_KnownHash functions to avoid calculating hashes 2 times https://github.com/aivarsk/cpython/blob/no_contains/Modules/_json.c#L1535
And just for the record, other JSON libraries that are faster:
So if the goal is to keep the API then it might be better to just avoid the Contains and optimistically set dict items. If API changes are on the plate (not keeping markers) it might be better to add recursion_limit which will catch rare errors cheaper at the expense of not catching those ASAP and having large exception details. nineteendo commented on Jul 31, 2025 I don't see any problem with no_contains. nineteendo commented on Oct 15, 2026
MetadataMetadataStatusShow more project fields
DevelopmentNo branches or pull requestsIssue actions
|
