This is a half-port of the patches in #1685986 and #1700288 to Python
3.0. Speedups are about the same as in those patches applied to their
respective Python versions for minibenchmarks (included in the patch as
fastattr_test_py3k.py): 5%-30% or more depending on how deep the class
hierarchy is. Pybench takes 4% less time on my system, and pystone takes
6% less time.

(Pybench would do better, but SpecialClassAttribute runs long and spends
half its time setting class attributes.)

The main difference between this and the previous patches is that 3.0's
simplifications allow a smaller footprint and make it easier to analyze
its correctness. Specifically, the fact that every object in the MRO
must be a type allows us to assume that every attribute lookup is
cacheable, and allows integration into the update_subclasses mechanism
when attributes are set. The lack of compiled extension modules means
there is no flag to check to see whether a type object supports caching.

This patch adds the ability to invalidate all of a subclasses' cache
entries upon setattr rather than updating just one cache entry. It's not
clear which of these is the Right Thing To Do, so I've made it an #ifdef
for now. It defaults to updating.

Recommend holding-off on applying this one until I've reviewed and
applied the Py2.6 version.

#1700288's patch has been committed. Leaving this open as a guide to
whoever has to merge it to Py3k.

I tried patch python30-attrcache-1.diff (after reverting the changes
made to the 2.6 branch).

But test_descr fails. The cache update does not handle the case when an
attribute is unmasked, as shown in the following code:

class A: pass
class B(A): pass
b=B()
A.x = 1
assert b.x == A.x
B.x = 2
assert b.x == B.x
del B.x
b.x         # <== AttributeError: 'B' object has no attribute 'x'

(b.x should be A.x, of course)
In debug build, a C assert() stops the program
    assert(ep->value == _PyType_LookupInternal(type, name));
which suggest that the cache is out of sync.

Then I enabled 
    #define ATTRCACHE_SETATTR_INVALIDATES
to try the other possibility suggested by Neil. This version seems to
work correctly. 
I'm currently running the test suite...

Question: why is this patch different from the 2.6 version? Does it take
advantage of some 3.0 feature?

Well horse pucky. I plum forgot about deletes.

I've attached an update that properly clears the cache entry for the
deleted attribute for all non-shadowing subclasses. (It was a small
change.) Undef'ing ATTRCACHE_SETATTR_INVALIDATES should work now.

Re: different from 2.6: It takes advantage of the lack of "classic"
classes. That makes some things a lot easier. Also, I was looking into
updating cache entries to see if it would be faster than invalidating
all the entries for a type, among other improvements. FWIW, updating
cache entries is a little faster on my box.

Also: This may have the same problem with test_ctypes'
test_incomplete.py as #1700288 did, though I haven't seen any ctypes
tests fail.

Yes, now the test suite runs without problem.
The patch also contains a file "fastattr_test_py3k.py". It seems to
perform some benchmark, but I'm not sure to understand its output.

Is it meant to be added somewhere? Does it make sense to keep it as a
unit test?

There's nothing it tests that standard unit tests don't, so it shouldn't
stick around as a unit test. I used it to time different types of
attribute lookups and left it in as an optimization aid.

The main test groups are '.' access, successful hasattr (returns True),
and failing hasattr (returns False). For each group it prints a header
and then four test cases for each test class: metaclass attribute access
(class.__class__), class attribute access (class.__init__), class
attribute access via an instance (class().__class__), and instance
attribute access (class().__init__). The test classes include a few
built-ins and the classes of a made-up deep hierarchy.

The main thing to notice is that, when you run this using the patched
source, every number is no larger than when you run it using the trunk,
and most are smaller.

This has been merged to py3k a long time ago, hasn't it?

I'm not sure this should be closed. According to Neil (see above) the 
implementation could be simpler in 3.0

Ok, reopening and retargetting to 3.1 in case someone wants to work on it.

As the patch provides some performance increase which has already been proven to work in 2.6, could we get this into 3.2?  I say this because I understand that performance was degraded in py3k, could this be one of the reasons why?

Closing: Neil's algorithm is not different from what is already in 3.2, except for the additional type_attrcache_callback() which probably doesn't make a difference in normal workloads.