new C3 MRO patch

Front page | perl.perl5.porters | Postings from April 2007

Thread Next

From:

Brandon Black

Date:

April 3, 2007 15:54

Subject:

new C3 MRO patch

Message ID:

84621a60704031554i6298e8fey43d97121957ddb5@mail.gmail.com

On 1/5/07, Rafael Garcia-Suarez <rgarciasuarez@gmail.com> wrote:
> I'm trying to make a list of what needs to be sorted out before a new
> development release: (5.9.5, which should be feature-equal to 5.10.0)
> [...]
> - C3 MRO ? (Brandon Black)

I'm still alive and kicking over here, I just stepped away for a month or two :)

I'm back to working on this now, and I've just re-integrated it with
perl-current in my local svk repo as of today.  I'll recap here with a
summary of the state of things / FAQ...

1) What is C3 MRO?

MRO = Method Resolution Order (as in, how do you walk the inheritance
tree when looking up inherited methods).  The perl default, which I've
taken to calling the DFS MRO, is depth-first search, which has serious
design issues when you do multiple inheritance (that whole "diamond
problem" thing).  C3 is an alternate algorithm that doesn't suffer
from those problems.  Take a look at Class::C3 / Algorithm::C3 on CPAN
(and the reference links there for more information, including the
original Dylan paper where it was invented).  Stevan Little wrote
these modules based on the Dylan and Python C3 MRO support, and I did
some maintenance and performance tweaking.

2) What does this patch do?

It digs into the guts of perl-current, adding C3 MRO alongside the
existing default DFS MRO.  This touches on a lot of deep things like
S_isa_lookup and gv_fetchmeth in very substantial ways, and can't
really be done outside the core effectively (although Class::C3 tries
really hard).

Along the way, it also adds a new interpreter variable
"PL_isa_generation", which is like the existing "PL_sub_generation",
but is incremented only on @ISA changes anywhere, as opposed to the
other cases (like symbol table manipulation) that affect
"PL_sub_generation".  It also caches packages' MRO linearizations
based on this variable.  It also adds an ext/mro module to core for
utility functions (like changing which MRO is in effect for a package,
and querying the linearized MRO of a package).

3) Why on earth do we want this thing?

For starters, the C3 MRO is simply better.  Python has switched to it
as their default MRO already.  Perl6 and Parrot are both defaulting to
C3 MRO as well.  This implies that any serious 6-on-5 effort will need
C3 support as well.  (That's the main reason I'm not bothering to
advocate changing our default - that's already planned for Perl 6
anyways, no need to cause compat issues in Perl5).  DBIx::Class has
been a C3-user for a long time now, and Catalyst wants to go that way
if it can, both of which are big new-school modules getting a lot of
attention lately.

4) Why not do it as a CPAN module?

We did, that's Class::C3.  Unfortunately, this isn't the kind of thing
that can easily be plugged in from userland.  Class::C3 has a number
of issues, including the need to call an "initialize()" method after
you've loaded all your classes (and after any C3-related @ISA changes
to clear out its caches), and that its doing a sort of manual
method-caching of its own in order to prevent being defeated by perl's
own method-caching (which is hackish and breaks down in unavoidable
ways in corner cases).

It's also a little bit slow, and while that's not a huge reason for
doing this, it is faster to put it in the core.  There are plans for
Class::C3::XS that will speed it up both in the existing 5.8.x case
and in any future version that has C3 support in the core (as things
like Class::C3's "next::method" are not in the core patch, and can be
sped up with XS and stay outside the core on CPAN).

5) How's the patch coming along?  Does it break things?  Is it ready?

The patch has been stable for a while now, and I've spent significant
time turning it over in my head (and in my home directory) trying to
root out any design issues that might break things.  It adds several
MRO-related tests to the perl test suite, and it passes the whole
suite successfully.  It's definitely at the stage that I'd really like
more random people to test it widely and find out if it affects
anything weird they're doing.

I've been flying solo on this effort for some time now, and I'm
relatively new to the perl core.  If anyone out there has any
suggestions on how the code or the interfaces could be better designed
or laid out to make the patch more acceptable, please feel free to
chime in and help me out, I promise not to be defensive about my code
:)

6) What about performance impact on non-C3 normal perl code?

In addition to the patch itself, I've attached c3bench.pl and
c3bench_results.txt.  These are highly artificial benchmarks that
highlight the performance impact.  The results text is annotated with
much greater detail than this text.

Basically, the only noticeable performance impact in any way is on
method cache misses (which misses the first time you call an inherited
method, and misses after any change to a method or @ISA anywhere in
the interpreter (those statements are true with or without my patch)).
 In the case of cache misses after a symbol table manipulation
(add/remove a method, etc), the patched perl is actually faster.  In
the case of @ISA changes, the patched perl is dramatically slower on
that first cache miss.  In practice with real applications, I don't
suspect anyone will see a substantial difference in runtimes in either
direction.

7) And performance for C3 code?

There's an unpublished variant of Class::C3 that takes (minimal so
far) advantage of this core C3 support.  I've benchmarked DBIx::Class
loading a 1000-table schema, as this heavily exercises C3, and seen
about a 33% performance improvement.  More improvements will certainly
come with later changes to Class::C3(::XS).

-- Brandon

Thread Next