Re: new C3 MRO patch

On 4/3/07, Brandon Black <blblackgmail.com> wrote:
> On 1/5/07, Rafael Garcia-Suarez <rgarciasuarezgmail.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...
>

Also, I had an effort going to make an even better variant
of this
patch, which I had given up on because of some seemingly
insurmountable issues.  I've now surmounted them, so here's
"c3-isarev.patch" (it applies directly to
perl-current, not on top of
c3.patch).

This changes a few things from c3.patch:
  1) No more PL_isa_generation, no longer neccesary.
  2) Cached ISA linearizations are no longer globally cleared
when
any ISA anywhere is modified.  Instead, Perl maintains a
dependecy
list which is the opposite of ISA ("who ISA's
me?") for each package,
and only destroys the cached linearizations for classes
actually
affected by a given ISA change.

The result is that in place of c3.patch's dramatic slowdown
in the
final artificial benchmark, we now have a mild slowdown in
simple
cases and a speedup in more complex ones.  This performs
much better
than c3.patch on the artificial benchmark, and I suspect its
a big win
for real-world code with complex class hierarchies over
c3.patch and
unpatched Perl.

It is however a little more behaviorally invasive than
c3.patch...

For one, when you do Foo::ISA = qw/ DoesNotExistYet /;, it
will
instantiate the DoesNotExistYet package at the time of the
ISA
assignment.  This creates problems for things like showing
the "Can't
locate package DoesNotExistYet for Foo::ISA" warning.  I
fixed that
with a new mro_meta flag "fake", which
magic_setisa sets on packages
it created in these situations, and the "package"
op resets to zero.
gv_fetchmeth uses this (and HvFILL(stash)) to figure out
what's going
on and still issue the correct warning in the same
situations that it
always did, so this should be a non-issue, but I wanted to
point it
out.

The other thing is that recursive inheritance heirarchies
will be
detected earlier.  I consider this a bonus, but it is a
change.
Before you could do "Foo::ISA = qw/ Foo
/;", and you wouldn't get a
complaint until you actually tried to resolve a method via
that
inheritance.  Now, the complaint happens at ISA
assignment time
(since we have to linearize the ISA at that point to keep
track of
the reverse dependencies, etc).

Attached is the c3-isarev.patch, as well as updated
benchmark script/results.

-- Brandon

> so here's "c3-isarev.patch"

Questions:

1. Why isn't this implemented as a feature?    use feature
'mro_c3';
That way it could be turned on at the application level for
all classes, no?

2. Does each class need to do 'use mro qw/c3/;', or do
derived classes
inherit from the parent class?

My interest is that this might be usable with
Object::InsideOut, but I
wouldn't what to have to have everyone's classes include a
'use mro
qw/c3/;'.

On 4/4/07, Brandon Black <blblackgmail.com> wrote:
> On 4/3/07, Brandon Black <blblackgmail.com> wrote:
> > On 1/5/07, Rafael Garcia-Suarez
<rgarciasuarezgmail.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...
> >
>
> Also, I had an effort going to make an even better
variant of this
> patch, which I had given up on because of some
seemingly
> insurmountable issues.  I've now surmounted them, so
here's
> "c3-isarev.patch" (it applies directly to
perl-current, not on top of
> c3.patch).
>
> This changes a few things from c3.patch:
>   1) No more PL_isa_generation, no longer neccesary.
>   2) Cached ISA linearizations are no longer globally
cleared when
> any ISA anywhere is modified.  Instead, Perl maintains a
dependecy
> list which is the opposite of ISA ("who ISA's
me?") for each package,
> and only destroys the cached linearizations for classes
actually
> affected by a given ISA change.
>
> The result is that in place of c3.patch's dramatic
slowdown in the
> final artificial benchmark, we now have a mild slowdown
in simple
> cases and a speedup in more complex ones.  This
performs much better
> than c3.patch on the artificial benchmark, and I
suspect its a big win
> for real-world code with complex class hierarchies over
c3.patch and
> unpatched Perl.
>
> It is however a little more behaviorally invasive than
c3.patch...
>
> For one, when you do Foo::ISA = qw/
DoesNotExistYet /;, it will
> instantiate the DoesNotExistYet package at the time of
the ISA
> assignment.  This creates problems for things like
showing the "Can't
> locate package DoesNotExistYet for Foo::ISA" warning.  I fixed that
> with a new mro_meta flag "fake", which
magic_setisa sets on packages
> it created in these situations, and the
"package" op resets to zero.
> gv_fetchmeth uses this (and HvFILL(stash)) to figure
out what's going
> on and still issue the correct warning in the same
situations that it
> always did, so this should be a non-issue, but I wanted
to point it
> out.
>
> The other thing is that recursive inheritance
heirarchies will be
> detected earlier.  I consider this a bonus, but it is a
change.
> Before you could do "Foo::ISA = qw/ Foo
/;", and you wouldn't get a
> complaint until you actually tried to resolve a method
via that
> inheritance.  Now, the complaint happens at ISA
assignment time
> (since we have to linearize the ISA at that point to keep
track of
> the reverse dependencies, etc).
>
> Attached is the c3-isarev.patch, as well as updated
benchmark script/results.

Just wanted to say that I for one think this is a can of
whoop ass.
Nice job. ++ to you.

Im not in the position to offer technical comments, but i
have to give
you massive cred for tackling such material. And if your
patch means
that installing subs at run time is now more efficient
(which i assume
is what you mean when you say that PL_sub_generation is
gone) then IMO
this could be a very very good thing.

Please gods of perl dont leave this thread warnocked!

cheers,
Yves

-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

"Brandon Black" <blblackgmail.com> wrote:
:This changes a few things from c3.patch:
:  1) No more PL_isa_generation, no longer neccesary.
:  2) Cached ISA linearizations are no longer globally
cleared when
:any ISA anywhere is modified.  Instead, Perl maintains a
dependecy
:list which is the opposite of ISA ("who ISA's
me?") for each package,
:and only destroys the cached linearizations for classes
actually
:affected by a given ISA change.

One thing I do regularly in my work application is to create
a new method
(or group of methods) by adding a new intermediate class,
and splicing it
into the ISA hierarchy.

When I do this, I know that the only methods for which any
caching is hereby
invalidated are the new ones (and usually, I also know these
methods have
never been called).

I wonder if it is possible to avoid invalidating the entire
cache in that
instance, possibly as a result of me supplying some hint.

The typical scenario is something like:
  Inter::Class::ISA = Leaf::Class::ISA;
  Leaf::Class::ISA = qw/ Inter::Class /;
  eval q{
    package Inter::Class;
    sub newmethod {
      ....
    }
  };
.. except that the classnames are variables. (And so I'm
doing the string
eval primarily to get the desired SUPER:: semantics for a
method being
defined in a dynamically generated class.)

HUgo

On 4/10/07, hvcrypt.org <hvcrypt.org> wrote:
> "Brandon Black" <blblackgmail.com> wrote:
> :This changes a few things from c3.patch:
> :  1) No more PL_isa_generation, no longer neccesary.
> :  2) Cached ISA linearizations are no longer globally
cleared when
> :any ISA anywhere is modified.  Instead, Perl maintains a
dependecy
> :list which is the opposite of ISA ("who ISA's
me?") for each package,
> :and only destroys the cached linearizations for
classes actually
> :affected by a given ISA change.
>
> One thing I do regularly in my work application is to
create a new method
> (or group of methods) by adding a new intermediate
class, and splicing it
> into the ISA hierarchy.
>
> When I do this, I know that the only methods for which
any caching is hereby
> invalidated are the new ones (and usually, I also know
these methods have
> never been called).
>
> I wonder if it is possible to avoid invalidating the
entire cache in that
> instance, possibly as a result of me supplying some
hint.
>

I'd rather not add special ways to make hints about it, but
instead
have it DTRT always.  So far, the ISA linearization caches
are doing
that (a change in Foo::ISA only invalidates the Foo
linearization and
the linearizations of anyone who (directly or indirectly)
has Foo in
their ISA).  Because under c3.patch half the work of full
method
lookups is cached by these linearization caches, the cost of
method
cache misses is already reduced by this.

The next step I'm working on (partially complete now) is to
take
advantage of the same reverse ISA dependencies to
localize method
cache invalidation, so that only the packages that could
possibly be
affected have their caches cleared.  In this scenario,
defining
methods or making ISA changes won't globally invalidate
method
caching, just locally as above with linearization caching. 
I think
I'll be done with this relatively soon, and the cost vs
benefit will
be a definite win.

The next stage one could take it to beyond that is to not
even
invalidate that set of packages' whole method caches in most
cases,
but instead only invalidate the necessary method name(s). 
It won't be
possible to do this efficiently in all cases (think method
changes in
a member of UNIVERSAL::ISA, or putting a new class with 40
methods
into Foo::ISA at runtime, when 40 other packages inherit
from Foo).

-- Brandon

On 4/10/07, Brandon Black <blblackgmail.com> wrote:
> The next step I'm working on (partially complete now)
is to take
> advantage of the same reverse ISA dependencies to
localize method
> cache invalidation [...]

Attached is a new patch "c3-subgen.patch", which
works against
perl-current (at least up through my rsync a few minutes
ago).  I
would term this one the "mro / c3 kitchen sink
patch", as it is very
maximal in its abilities (and its intrusiveness).  Some of
the new
parts aren't as well tested as the previous c3 patch, but
the gains
are nice, and I feel I can dispatch any regressions fairly
quickly if
and when someone finds them.  The kinds of regressions it is
likely to
generate (if any) are ones where a method cache entry should
have been
invalidated, but wasn't.  It passes the perl test suite for
me
locally, as well as the test suites of DBI, DBIx::Class, and
a few
other heavy modules I tried.

This patch makes method cache invalidation local (to a
subtree of the
ISA
hierarchy) in most of the hot places that used to do
PL_sub_generation++, including when changes happen to ISA and
most of
the common ways new subroutines are redefined.

It also moves what was the XS routines mro: in ext/mro
in previous
c3 patches straight into mro.c (like the XS subs in
universal.c,
xsutils.c, etc).  This was neccesary for miniperl to be able
to use
"mro" things in overload/constant for tests.

It also refactors the interfaces in mro: to be a
little more
natural, and a little easier to extend for future MRO types
down the
line.  Adds some new ones too, for querying the global and
package-level "sub_generation", and for
invalidating method caches
(again, globally, or for a given package's descendants). 
These make
good replacements for things like B::sub_generation and
Internals::inc_sub_generation (but I left those in, they
don't hurt
anything and no point in breaking them).

It also adds XS versions of next::method, next::can, and
maybe::next::method from Class::C3 as XSUBs booted via mro.c
as well.
These amount to the C3-equivalent of
"SUPER"/"NEXT"/etc.  With this
change, Class::C3 will no longer be necessary at all for
someone who
does "require 5.9.x" (for whatever version might
have this patch).
Class::C3 will still be available for backwards
compatibility (code
that does "use Class::C3" will work with older
perls as well as
patched perls, taking advantage of what it can)*.

Test/Benchmark it with real code and please tell me if
anything in it
is unacceptable for the perl core.  Only a small handful of
people are
testing these as patches anyways, so I suspect the
"real" testing
won't happen until/if it makes it into -current.

-- Brandon

* I should note that the version of Class::C3 that does
forward/backward-compatibility isn't on CPAN yet, pending
this patch
or something like it making it into -current.

On 4/12/07, Brandon Black <blblackgmail.com> wrote:
> On 4/10/07, Brandon Black <blblackgmail.com> wrote:
> > The next step I'm working on (partially complete
now) is to take
> > advantage of the same reverse ISA
dependencies to localize method
> > cache invalidation [...]
>
> Attached is a new patch "c3-subgen.patch"

Another new iteration.  Nothing has really changed
(especially for
non-c3 perl code), its mostly just doc improvements, another
few
interface renames for consistency, and several more tests
imported
from Class::C3.

Again, if you can find something it breaks, let me know and
I'll fix
it.  If there's anything else that needs to be
fixed/done/changed/etc
for this to be more palatable for inclusion, let me know
about that
too.

-- Brandon

I've generated a new version of the mro patch again.  In
addition to
integrating up with the most recent perl-current changes,
this patch
also adds ithreads support (was broken under ithreads
earlier) and
fixes up some memory management issues that ithreads made
apparent.
This patch is a standalone patch against perl-current.

-- Brandon

On 4/17/07, Brandon Black <blblackgmail.com> wrote:
> I've generated a new version of the mro patch again. 
In addition to
> integrating up with the most recent perl-current
changes, this patch
> also adds ithreads support (was broken under ithreads
earlier) and
> fixes up some memory management issues that ithreads
made apparent.
> This patch is a standalone patch against perl-current.
>

And of course, I forgot to wrap some of the new ithreads
stuff in
"#ifdef USE_ITHREADS".  I'll start linking instead
of attaching, since
this patch is getting kinda large to be sending to the ML
over and
over now.

http://www.dtmf.c
om/c3-subgen.patch

-- Brandon

Patch: http://www.dtmf.c
om/c3-subgen.patch

The patch at this url has seen some more small changes today
from me
doing some manual smoke testing and double-checking the
memory
management, and a number of new users trying it out and
reporting
things.  (I've also pushed a dev release of Class::C3 to
CPAN that
supports it, which has allowed some DBIx::Class users to
give it a
spin with full-blown applications - one guy reports more
than an order
of magnitude reduction in application startup overhead).

I'd say now this new (+method cache enhancements, etc)
version of the patch is
probably more stable than the old (just barely support c3)
version
ever was.  I'm hoping for no more changes to the patch from
my end,
other than the occasional re-sync to perl-current.

The most recent version of the patch will continue to be
available at
that url (and I'll post any significant changes here) until
its either
officially included or officially killed off, one way or the
other 

As always, more feedback/testing/suggestions/etc welcome,

-- Brandon