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

[SourceForge.net]

Patches item #1153056, was opened at 2005-02-27 21:14
Message generated for change (Comment added) made by arigo
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: 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