[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: Just updating for recent changes, right? LGTM. Shouldn't this just get committed? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: I see I haven't addressed your previous comment about PyErr_Clear(), I should probably address it before anything gets committed. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Updated patch replacing PyErr_Clear() with PyErr_WriteUnraisable(), and PyDict_Check() with PyDict_CheckExact(). -- Added file: http://bugs.python.org/file32411/subclasses_dict3.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Changes by Antoine Pitrou pit...@free.fr: -- status: pending - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Roundup Robot added the comment: New changeset a7f1ce6fe293 by Antoine Pitrou in branch 'default': Issue #17936: Fix O(n**2) behaviour when adding or removing many subclasses of a given type. http://hg.python.org/cpython/rev/a7f1ce6fe293 -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Actually, PyErr_Clear() was necessary in some cases. Now committed. -- resolution: - fixed stage: patch review - committed/rejected status: open - pending ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: For the record, an updated patch. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Changes by Antoine Pitrou pit...@free.fr: Added file: http://bugs.python.org/file32399/subclasses_dict2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Here is another approach to make tp_subclasses a dict, rather than a list. I'll let you benchmark and choose whichever you prefer :) -- nosy: +gvanrossum, rhettinger Added file: http://bugs.python.org/file30364/subclasses_dict.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: One question: I saw you clearing exceptions in the tp_clear() function, isn't it better to use PyErr_PrintUnraisable()? You're right, that would be better. I was just being lazy. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: Looks good, I'll give it a spin. This is probably smarter then trying to do tricks with lists. One question: I saw you clearing exceptions in the tp_clear() function, isn't it better to use PyErr_PrintUnraisable()? Is there a guideline to when to use that one in internal code? When is it safe to just shrug and ignore? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Note that making tp_subclasses a dict makes the __subclasses__ return order undefined. I don't think I've ever seen __subclasses__ actually used, so I'm not convinced it's a problem, but perhaps it's worth floating the idea on python-dev. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Guido van Rossum added the comment: I can't think of a use for the order of __subclasses__ so no objection here. — Sent from Mailbox for iPad On Sat, May 25, 2013 at 6:16 AM, Antoine Pitrou rep...@bugs.python.org wrote: Antoine Pitrou added the comment: Note that making tp_subclasses a dict makes the __subclasses__ return order undefined. I don't think I've ever seen __subclasses__ actually used, so I'm not convinced it's a problem, but perhaps it's worth floating the idea on python-dev. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: Yes, thanks for pointing that out, Antoine, I have made the change locally. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: I think the logic is slightly wrong in remove_subclass. When you encounter Py_None, you can't be sure it's the weakref for the current type; theoretically, it could be any other one (depending on oddities in cleanup order, cycle collection, etc.). So you have to continue walking the list. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Attaching an alternative implementation for remove_subclass(). -- Added file: http://bugs.python.org/file30247/subtype2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: Basically the logic is this: When the class goes away, it _always_ calls remove_subclass(). Now, this may be before or after the weakref has been clear so that it will either find itself in a weakref, or a clear weakref. In case this logic is flawed, we know that when remove_subclass() is called, exactly one child is removed. Whether it is us, or some previous class, is irrelevant. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: In case this logic is flawed, we know that when remove_subclass() is called, exactly one child is removed. Whether it is us, or some previous class, is irrelevant. remove_subclass() is called when __bases__ is assigned to, so it is not irrelevant: class A: pass ... class B(A): pass ... class C: pass ... A.__subclasses__() [class '__main__.B'] B.__bases__ = C, A.__subclasses__() [] C.__subclasses__() [class '__main__.B'] -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: There are two cases when remove_subclass is called: One when we are changing base classes(the original use of this function), and in this case we must find the correct one. The second one is when the class is being deleted, for housekeeping of the weakrefs. I worry that your alternative will cause us to walk the entire list in the second case because it will be called when the weakref has been cleared, so it will never find itself in the list, only None. I'll make some tests to verify. I think perhaps a small adjustment, an exact flag or something, can be added to differentiate between the two cases -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: The second one is when the class is being deleted, for housekeeping of the weakrefs. I worry that your alternative will cause us to walk the entire list in the second case because it will be called when the weakref has been cleared, so it will never find itself in the list, only None. I don't think that matters much. In both cases the expected complexity is O(n). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: Actually, in a program that dynamically creates a class, and then deletes it, you would expect a O(1) complexity. adding children at the end, and searching from the end, is a way to achieve this. While I admit that I oversaw the exact requirement for __bases__, I think that allowing for a None to be sufficient when the class is being deleted is an important improvement. I realize that the therotetical worst case is O(n), but the practical common case is still O(1) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: While I admit that I oversaw the exact requirement for __bases__, I think that allowing for a None to be sufficient when the class is being deleted is an important improvement. You can't be sure the None corresponds to the type being deleted and not another one. If you want guaranteed (almost :-)) O(1) behaviour, you must switch to a dict. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: Yes I am sure. Please see the previous reasoning. Igoring assigning to __bases__ for the moment... Every class deletion will try to remove itself from the list. Either it will a) find an existing reference in the weakref and remove it b) find a None in the weakref and remove it. b) is guaranteed to be the old weakref, because every previous class removal has also succeeded. At any time, there is at most a single stale weakref in the list. And _even_if_ there is a flaw in the argument, every call will remove _one_ stale (or just about to become stale) weakref from the list. Whether it is its own weakref or that of a previous deletion is immaterial. The removal of _one_ entry for each class deletion keeps the list at its optimal size. For the case of assigning to __bases__, of course, the weakrefs are not stale and we must find the correct class to remove for correctness. I don't want guaranteed O(1) behaviour, just O(1) for the common case of creating a class, or a few classes, and then removing them. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: I don't want guaranteed O(1) behaviour, just O(1) for the common case of creating a class, or a few classes, and then removing them. Then just make sure you call remove_subclass() before PyObject_ClearWeakRefs() in type_dealloc(). Really, this thing should be demonstrably correct. Performance of dynamic class creation is not critical enough to take shortcuts. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: That is not sufficient. The weakrefs may have been cleared already if the deletion comes as a result of garbage collection (which is currently the only way classes get deleted.) It is still easily demonstratably correct: The previous version _only_ removed subclasses on setting __bases__. Housekeeping of stale weakrefs was done when new classes were created. This proposed version still properly removes subclasses when setting __bases__, but housekeeping of dead weakrefs is now moved to the point when a class is deleted. To do housekeeping of stale weakrefs, it is sufficient to remove _one_ stale weakref for each class that is deleted. It is not important that this is the correct stale weakref, all stale weakrefs are the same. I've uploaded an updated patch with added in-line comments explaining the case. -- Added file: http://bugs.python.org/file30253/subtype.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: One thing: int i should be Py_ssize_t i. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: It turned out to be slightly more compilcated. Two additions make this complete: 1) check for the subtype OR the Py_None when removing subclass. This removes any dependency on the order in which weakrefs are cleared. 2) When the type is cleared, manually remove ourselves from all the base classes. It is because of the lack of 2) that the original version was always clearing out all stale weakrefs when new subclasses were added. -- Added file: http://bugs.python.org/file30218/subtype.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: So, any objections? It is pretty straighforward. Btw, the searching for Py_NONE seems to be a rudiment of some older version, there is no place where a Py_NONE is put in there. Also, what is the policy for 2.7? Are performance bugs proper bugs? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Py_None is what PyWeakref_GET_OBJECT() returns when the object is dead. (same as calling () on a weakref, really) The patch looks straightforward to me. 2.7 doesn't receive performance fixes, though, except for large regressions. Also, we've had enough regressions in the last 2.7 bugfix release, IMHO. (I had worked on a patch which replaced the list with a dict, but I had refcounting issues with it, and I'm not interested enough in the issue to push any further) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Kristján Valur Jónsson added the comment: Right, I misread the code. Since the remove_subclass() function is called when a subclass dies, I don't think it is necessary to clear out weak references in add_subclass(). They are there merely to break the reference cycle. Btw, the 'patch diff' stuff seems to be broken in the tracker -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Right, I misread the code. Since the remove_subclass() function is called when a subclass dies, I don't think it is necessary to clear out weak references in add_subclass(). They are there merely to break the reference cycle. Agreed. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Changes by STINNER Victor victor.stin...@gmail.com: -- nosy: +haypo ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17936] O(n**2) behaviour when adding/removing classes
Antoine Pitrou added the comment: Funny, I had once noticed this theoretical problem, but it didn't seem to matter concretely, so I hadn't posted about it :) -- nosy: +pitrou stage: - patch review title: O(2) behaviour when adding/removing classes - O(n**2) behaviour when adding/removing classes versions: -Python 2.7, Python 3.3 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17936 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com