[Patches] [ python-Patches-1153056 ] PyXxx_Check() speed-up

Thu Apr 14 12:57:56 CEST 2005

Patches item #1153056, was opened at 2005-02-27 21:14
Message generated for change (Comment added) made by mwh
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1153056&group_id=5470

Category: Core (C code)
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Armin Rigo (arigo)
Assigned to: Nobody/Anonymous (nobody)
Summary: PyXxx_Check() speed-up

Initial Comment:
Once upon a time, the macros PyInt_Check(),
PyString_Check(), etc., used to be very fast: just a
pointer comparison.  But 2.2 came.  Suddenly, types
could inherit from each other.  Thus the macros became:

(ob->type == &PyXxx_Check ||
   PyType_IsSubType(ob->type, &PyXxx_Check)

Subtyping of built-in types still being rare, the
common cases here are: (1) ob is indeed exactly of type
Xxx, (2) ob is absolutely not an instance of Xxx.  The
macro is fast for case 1 but becomes a call to a slow
function in case 2.

It sounds minor -- but a program can make half a
million "case 2" calls in 5 seconds.

The following patch proposes to fix that, based on a few
measurements that show which are the more common
"case 2" calls in a few applications.  It adds a
family of type flags meaning "this type is not at all an
Xxx", for Xxx in [module, tuple, float, int, unicode,
long, complex, str].

I cannot measure the performance gain on this machine
(figures vary all the time) but it looks like some 0.2s
for the above-mentioned 5s program.

----------------------------------------------------------------------

>Comment By: Michael Hudson (mwh)
Date: 2005-04-14 11:57

Message:
Logged In: YES 
user_id=6656

I suppose I should read the patch then :)

It seems very odd that _PyType_FastTypeCheck mutates a->tp_flags.

In fact, shoudn't it be possible to not have _PyType_FastTypeCheck at 
all?

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2005-04-14 10:22

Message:
Logged In: YES 
user_id=4771

I am convinced now by #1153075 that PyCheck_Xxx should not be semantically changed, and really means walking the mro.  So the patch here remains valid.

Yes, I know that N is unbounded, that's why the next sentence was "let's only include the most common of them".

Where to stop?  Don't guess, measure.  That's what I did, and in a few applications there were systematically a set of types that were PyChecked quite more often than the others.  So my patch special-cases exactly these types.

----------------------------------------------------------------------

Comment By: Michael Hudson (mwh)
Date: 2005-04-14 09:05

Message:
Logged In: YES 
user_id=6656

(I haven't seen any mail about this patch!)

> array of N bits, where N is the number of C-level PyXxxObject
> structures

That's unbounded too, in the presence of extension modules.

(I still think my fix for #1153075 suffices, and is probably a good thing).

I can believe that special casing int and str subclasses is worth it -- but 
where to stop?

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2005-02-28 09:26

Message:
Logged In: YES 
user_id=4771

Ah, but that's not so different: M can still be arbitrarily
large...

However, see also bug #1153075.  I think that PyInt_Check()
using PyType_IsSubtype() is essentially buggy: the purpose of
PyInt_Check() is to check if the PyObject* is a
PyIntObject*, not if its type pretends to have 'int' in its
mro.  If we fix this, then making PyType_IsSubtype()
faster will become unrelated to making PyXxx_Check()
faster.

If we want to fix PyXxx_Check() for the bug described above
and make it fast too, then we probably only need an
array of N bits, where N is the number of C-level PyXxxObject
structures.  The idea of only including the most common such
structures instead of all of them was based on simplicity and
performance (it's faster and easier to check for a known bit
than for a bit which itself is computed at run-time).

If we want to make PyType_IsSubtype() fast, it might be worth
the effort or not; we should measure it.  But I think it's
unrelated.

----------------------------------------------------------------------

Comment By: Martin v. Löwis (loewis)
Date: 2005-02-28 06:20

Message:
Logged In: YES 
user_id=21627

No. Each type would have an array of M bits, where M is the
maximum number of a super class; each type would also store
the value of M. As types are created and deleted
dynamically, it might be necessary to keep track of assigned
type numbers, and recycle them as types are deleted.

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2005-02-27 23:56

Message:
Logged In: YES 
user_id=4771

I'm not sure I understand your suggestion.  Would each type
have an array of N bits, where N is the total number of types
that exist?  That looks quite unreasonable in any program
that builds a lot of types (I know some that build them
programatically in loops).  What I did is a limited
version of that: a bitfield with room for only some commonly
checked-for superclasses.

(With some care, my patch could be modified to build the
bitfield in PyType_Ready(); this would allow the
PyXxx_Check() macros to become a single bit check operation.)

Changing the base classes isn't an issue in my limited patch
because you cannot ever add or remove the core built-in types
I check for from the bases of an existing type.

----------------------------------------------------------------------

Comment By: Martin v. Löwis (loewis)
Date: 2005-02-27 23:44

Message:
Logged In: YES 
user_id=21627

I would rather see a constant-time subtype check implemented
in Python, using strategies that other interpreters have
been using for a long time.

Essentially, each type gets a unique number (e.g. in the
order of PyType_Ready calls), and a bit-field of all
supertypes, with a bit set for each type that is one of its
supertypes. Creation of the bitfield could be delayed until
a subtype check is actually needed.

The tricky part is to update the supertype bitmask when
__super__ is assigned.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1153056&group_id=5470