This patch implements type.__instancecheck__ and type.__subclasscheck__,
which speeds up isinstance and issubclass calls quite a bit.

See also issue #2303.

Here are the performance figures for the current trunk version:

Current SNV trunk:

Using 2.6a1+ (trunk:62102, Apr  2 2008, 11:30:16) [MSC v.1500 32 bit
(Intel)]
isinstance(42, int)	   1000000 loops, best of 3: 0.28 usec per loop
isinstance(42, type)	   1000000 loops, best of 3: 0.974 usec per loop
issubclass(object, type)   1000000 loops, best of 3: 1.1 usec per loop
issubclass(object, int)    1000000 loops, best of 3: 1.1 usec per loop
issubclass(float, int)     1000000 loops, best of 3: 1.15 usec per loop

Current trunk, patch applied:

Using 2.6a1+ (trunk:62102M, Apr  2 2008, 11:21:32) [MSC v.1500 32 bit
(Intel)]
isinstance(42, int)	   1000000 loops, best of 3: 0.274 usec per loop
isinstance(42, type)	   1000000 loops, best of 3: 0.524 usec per loop
issubclass(object, type)   1000000 loops, best of 3: 0.661 usec per loop
issubclass(object, int)    1000000 loops, best of 3: 0.662 usec per loop
issubclass(float, int)     1000000 loops, best of 3: 0.731 usec per loop

Python 2.5.2, for comparison:

Using 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)]
isinstance(42, int)	   1000000 loops, best of 3: 0.292 usec per loop
isinstance(42, type)	   1000000 loops, best of 3: 0.417 usec per loop
issubclass(object, type)   1000000 loops, best of 3: 0.626 usec per loop
issubclass(object, int)    1000000 loops, best of 3: 0.648 usec per loop
issubclass(float, int)     1000000 loops, best of 3: 0.752 usec per loop

I find similar speedups:

isinstance(42, int)       -2%
isinstance(42, type)      45%
isinstance(object, type)  -1%
isinstance(object, int)   42%
isinstance(float, int)    44%

(both negative ones are actually lower than original, but so low that it
could be considered timing glitches)

However, also I have an error in the test_exceptions.py suite:
facundo@pomcat:~/devel/reps/python/trunk$ ./python
Lib/test/test_exceptions.py
testAttributes (__main__.ExceptionTests) ... ok
testInfiniteRecursion (__main__.ExceptionTests) ... FAIL
testKeywordArgs (__main__.ExceptionTests) ... ok
testRaising (__main__.ExceptionTests) ... ok
testReload (__main__.ExceptionTests) ... ok
testSettingException (__main__.ExceptionTests) ... ok
testSlicing (__main__.ExceptionTests) ... ok
testSyntaxErrorMessage (__main__.ExceptionTests) ... ok
testUnicodeStrUsage (__main__.ExceptionTests) ... ok
test_WindowsError (__main__.ExceptionTests) ... ok

======================================================================
FAIL: testInfiniteRecursion (__main__.ExceptionTests)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "Lib/test/test_exceptions.py", line 336, in testInfiniteRecursion
    self.assertRaises(RuntimeError, g)
AssertionError: RuntimeError not raised

----------------------------------------------------------------------
Ran 10 tests in 0.031s

FAILED (failures=1)
Traceback (most recent call last):
  File "Lib/test/test_exceptions.py", line 351, in <module>
    test_main()
  File "Lib/test/test_exceptions.py", line 348, in test_main
    run_unittest(ExceptionTests)
  File "/home/facundo/devel/reps/python/trunk/Lib/test/test_support.py",
line 577, in run_unittest
    _run_suite(suite)
  File "/home/facundo/devel/reps/python/trunk/Lib/test/test_support.py",
line 560, in _run_suite
    raise TestFailed(err)
test.test_support.TestFailed: Traceback (most recent call last):
  File "Lib/test/test_exceptions.py", line 336, in testInfiniteRecursion
    self.assertRaises(RuntimeError, g)
AssertionError: RuntimeError not raised

The test fails on this:

def g():
    try:
        return g()
    except ValueError:
        return -1
self.assertRaises(RuntimeError, g)


Changing that "return -1" to "return sys.exc_info()" shows that a
RuntimeError was raised indeed. Also, using TypeError or TabError
instead of ValueError gives the same result.

Shallow testing of the new methods seem to show normal results,

[Runtime,Value]Error.__[subclass,instance]check__([Runtime,Value]Error)

is False for cross-checks and True otherwise.

Running Daniels code interactively, with a debug build on Windows,
additionally prints 'XXX undetected error' before the Runtime error is
raised.

I cannot see anything that is wrong with my code.  Maybe this, and the
test failure, has to do with the fact that the new
'type___subclasscheck__' function is sometimes called with the error
indicator already set?  Maybe some PyErr_Fetch() and PyErr_Restore()
calls are needed inside this function, similar to what
PyObject_IsSubclass() does?  I must admit that I do not really
understand the purpose of these calls...

Anyway, I attach a new, cleaner patch although this one still behaves in
the same, buggy, way: type_instancecheck-2.diff.

Thomas: I confirm your patch triggers this behavior.  I can reliably get
a __subclasscheck__ error by trying to "import sys" after the bogus
catching happens:

>>> def g():
...   try:
...     return g()
...   except ValueError:
...     return sys.exc_info()
...
>>> g()
(<type 'exceptions.RuntimeError'>, 'maximum recursion depth exceeded
while calling a Python object', <traceback object at 0xb7d9ba04>)
>>> import sys
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded in __subclasscheck__

I hope this helps...

Problem found.  See issue #2542, which contains a patch that fixes the
failure in test_exceptions; this test now additionally prints

  Exception RuntimeError: 'maximum recursion depth exceeded in
    __subclasscheck__' in <type 'exceptions.RuntimeError'> ignored
  Exception RuntimeError: 'maximum recursion depth exceeded while
    calling a Python object' in <type 'exceptions.RuntimeError'> ignored

speedup of this patch confirmed.  Also, it triggers the bugs mentioned
that have their own issues open.  Once #2542 is fixed this should be
looked at again.

Its a big performance regression in 2.6 over 2.5 if we don't get this
in, marking it critical.

Can this patch go in?

By the way, py3k suffers from this problem too, so a similar patch
should be applied if possible.

I'm currently doing the port to py3k. It makes me find interesting flaws
in the current isinstance/issubclass implementation :-))

Ok, here is the patch for py3k. As I said it fixes some interesting bugs
(when the second argument was a tuple, isinstance() and issubclass()
were trying to get __instancecheck__ / __subclasscheck__ on the tuple
rather than on each of the tuple items). I also had to disable
__subclasscheck__ for exception matching, otherwise there are some nasty
issues with recursion checking.

The patch for trunk should probably be reworked or regenerated from the
py3k patch.

Performance numbers:

timeit -s "val=ValueError(); cls=EOFError" "isinstance(val, cls)"
- before patch: 1.63 usec per loop
- after patch: 0.683 usec per loop

timeit -s "val=ValueError(); cls=EOFError" "isinstance(val, (cls,))"
- before patch: 1.86 usec per loop
- after patch: 0.773 usec per loop

timeit -s "val=ValueError; cls=EOFError" "issubclass(val, cls)"
- before patch: 1.95 usec per loop
- after patch: 0.624 usec per loop

timeit -s "val=ValueError; cls=EOFError" "issubclass(val, (cls,))"
- before patch: 2.35 usec per loop
- after patch: 0.721 usec per loop


pybench
-------

("this" is with patch, "other" is without)

Test                             minimum run-time        average  run-time
                                 this    other   diff    this    other 
 diff
-------------------------------------------------------------------------------
                TryRaiseExcept:    77ms   136ms  -43.5%    77ms   137ms
 -43.5%
               WithRaiseExcept:   189ms   280ms  -32.6%   190ms   282ms
 -32.6%
-------------------------------------------------------------------------------
Totals:                           266ms   416ms  -36.1%   267ms   419ms
 -36.2%

New patch with a couple of tiny fixes.

Here is the same patch, but backported to 2.6.

+1 on applying this patch right away.

For 2.6 and 3.0 to be successful, we need people to prefer to upgrade 
rather than stay with 2.5.  A systemic slowdown in not in the best 
interests of the language moving forward.

Both patches look correct to me, and I think they can be applied.

Committed in r66042 and r66043.