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
___
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
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
Changes by Antoine Pitrou pit...@free.fr:
--
status: pending - closed
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue17936
___
___
Python-bugs-list
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
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
Antoine Pitrou added the comment:
For the record, an updated patch.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue17936
___
___
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
___
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
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
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
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.
--
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
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
___
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
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
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
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
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
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
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
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
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
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
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_
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
___
___
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,
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?
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
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'
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.
--
Changes by STINNER Victor victor.stin...@gmail.com:
--
nosy: +haypo
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue17936
___
___
Python-bugs-list
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
33 matches
Mail list logo
