[lucy-dev] Host overriding of all non-final methods

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

[lucy-dev] Host overriding of all non-final methods

Marvin Humphrey
Greets,

There's no good reason for it, but right now only methods which are tagged as
either "public" or "abstract" within Clownfish can be overridden from the host
language.

This caused a problem in an application I was working on because we wanted to
override IndexSearcher's Top_Docs() method.  Since Top_Docs() is not yet
public in Lucy, the attempt to override it from Perl fails silently: no
callback is installed.  Thus, when Searcher_Hits() invokes Top_Docs() from
C-space on our subclassed IndexSearcher, it gets the C function
IxSearcher_top_docs() rather than the Perl subroutine top_docs() from our
subclass.

The fix is to allow any non-final method to be overridden, regardless of its
exposure.  Patch below.

For "final" methods, we have two options.  We can fail silently, as we do now.
In this case, there will be different behavior when a method is invoked from
the host (the illegal host override method fires) vs. when it is invoked from
within the Lucy core (the "final" method definition fires).

The other option is to throw an exception at runtime when an attempt to
override a final method is detected.  Dynamic VTable objects are built lazily,
so the error would occur the first time the constructor for the problematic
class gets invoked.

The rationale for this change is that method overrides should work the same way
for both C-based classes and host-based classes: non-final methods should be
overridable from both C and the host.  There are no public API changes because
every public non-final method was already overridable; only non-public methods
will get a behavior change.  

Right this moment I'm feeling lazy, so inertia is favoring the first option for
final methods, "fail silently." :)  Failing at runtime when illegal method
overriding from the host is detected isn't as friendly as failing at compile
time when an illegal override is found in a .cfh Clownfish header file, though.

Marvin Humphrey


Index: ../clownfish/lib/Clownfish/Binding/Core/Class.pm
===================================================================
--- ../clownfish/lib/Clownfish/Binding/Core/Class.pm    (revision 1075667)
+++ ../clownfish/lib/Clownfish/Binding/Core/Class.pm    (working copy)
@@ -326,7 +326,7 @@
 
         # Define callbacks for methods that can be overridden via the
         # host.
-        if ( $method->public or $method->abstract ) {
+        if ( !$method->final ) {
             my $callback_sym = $method->full_callback_sym;
             if ( $novel{ $method->micro_sym } ) {
                 $callback_funcs


Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Nathan Kurz
On Wed, Mar 2, 2011 at 7:08 PM, Marvin Humphrey <[hidden email]> wrote:
> For "final" methods, we have two options.  We can fail silently, as we do now.
> In this case, there will be different behavior when a method is invoked from
> the host (the illegal host override method fires) vs. when it is invoked from
> within the Lucy core (the "final" method definition fires).
>
> The other option is to throw an exception at runtime when an attempt to
> override a final method is detected.  Dynamic VTable objects are built lazily,
> so the error would occur the first time the constructor for the problematic
> class gets invoked.

Orient me for a moment:  this would have to be caught in the host
language, and would need to be written this way for every language
that there are bindings?  Or is there somewhere that this could be
caught by Lucy core?  And there aren't many final methods are there?
Only on extremely performance sensitive paths?

> The rationale for this change is that method overrides should work the same way
> for both C-based classes and host-based classes: non-final methods should be
> overridable from both C and the host.  There are no public API changes because
> every public non-final method was already overridable; only non-public methods
> will get a behavior change.

Yes.

> Right this moment I'm feeling lazy, so inertia is favoring the first option for
> final methods, "fail silently." :)  Failing at runtime when illegal method
> overriding from the host is detected isn't as friendly as failing at compile
> time when an illegal override is found in a .cfh Clownfish header file, though.

That seems like the wrong kind of lazy. :)  I think the right kind of
lazy is to solve it once by brute force:  ASSERT(! $method->final).
But since true macros are hard in Perl, I'd be happy with adding an
'if DEBUG' to that so that it can get optimized away at compile if one
wants it to be.  But you never really got on the ASSERT train, did
you?

Nathan Kurz
[hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Marvin Humphrey
On Wed, Mar 02, 2011 at 09:28:07PM -0800, Nathan Kurz wrote:

> On Wed, Mar 2, 2011 at 7:08 PM, Marvin Humphrey <[hidden email]> wrote:
> > For "final" methods, we have two options.  We can fail silently, as we do now.
> > In this case, there will be different behavior when a method is invoked from
> > the host (the illegal host override method fires) vs. when it is invoked from
> > within the Lucy core (the "final" method definition fires).
> >
> > The other option is to throw an exception at runtime when an attempt to
> > override a final method is detected.  Dynamic VTable objects are built lazily,
> > so the error would occur the first time the constructor for the problematic
> > class gets invoked.
>
> Orient me for a moment:  this would have to be caught in the host
> language, and would need to be written this way for every language
> that there are bindings?  

The code that walks the host language OO structure needs to be custom-coded
for each binding.  The function VTable_novel_host_methods() fills that role.
Here's the implementing code for our Perl bindings, taken from from
perl/lib/Lucy.pm:

    sub novel_host_methods {
        my ( undef, $package ) = @_;
        no strict 'refs';
        my $stash   = \%{"$package\::"};
        my $methods = Lucy::Object::VArray->new(
            capacity => scalar keys %$stash );
        while ( my ( $symbol, $glob ) = each %$stash ) {
            next if ref $glob;
            next unless *$glob{CODE};
            $methods->push( Lucy::Object::CharBuf->new($symbol) );
        }
        return $methods;
    }

> Or is there somewhere that this could be caught by Lucy core?  

Checking to see whether a method is final can be done in the Lucy core, in
core/Lucy/Object/VTable.c -- so it doesn't need to be reimplemented for each
host.  There's some crude introspection metadata hanging off of each VTable;
we can store booleans in that metadata indicating which methods are final and
check the method names returned by novel_host_methods() to see whether an
illegal override has happened.  If we really want to.

> And there aren't many final methods are there?

Correct.  There are presently only three classes that have final methods.

Most methods on InStream and OutStream are final, because InStream and
OutStream are very performance sensitive -- they always show up in profiling
data.  The classes aren't final, so you can subclass them and add *more*
methods, e.g. to integrate additional decoders -- but you can't redefine
existing methods.

Then there's an internal class called InverterEntry.  It's a final class, so
all its methods are final.

> Only on extremely performance sensitive paths?

Right.  But even then, I don't recall that we got a lot of juice out of making
those methods final.  Our compiler isn't smart enough to extract the method
body from the source C file and inline it into another C file, like a HotSpot
compiler might do with a final method in Java.  The Clownfish compiler just
aliases the method to the implementing function, avoiding the double-deref of
retrieving the method pointer from the vtable.  There's not a lot to be saved
there.

Arguably, we don't even need the "final" keyword.  We'd should benchmark to
confirm my recollection about the performance implications, but I'll bet we
could remove it with no immediate impact on Lucy.  If we were doing fancier
stuff in our compiler we might, but as it stands, I think we're going to need
to declare code "inline" and put it into header files if we want the C
compiler to do perform aggressive inlining optimizations.

The file core/Lucy/Util/NumberUtils.cfh contains many such inline functions.  I
anticipate using those within posting decoders to operate directly on mmap'd
buffers.  Perhaps that's a better way forward given that we're always going to
be working within the constraints of a C compiler that operates file-by-file.

> > Right this moment I'm feeling lazy, so inertia is favoring the first option for
> > final methods, "fail silently." :)  Failing at runtime when illegal method
> > overriding from the host is detected isn't as friendly as failing at compile
> > time when an illegal override is found in a .cfh Clownfish header file, though.
>
> That seems like the wrong kind of lazy. :)  I think the right kind of
> lazy is to solve it once by brute force:  ASSERT(! $method->final).
> But since true macros are hard in Perl, I'd be happy with adding an
> 'if DEBUG' to that so that it can get optimized away at compile if one
> wants it to be.  But you never really got on the ASSERT train, did
> you?

Haha, that's true.  When code can be verified via unit tests, I prefer that,
since it stores the noise out of band in a unit test file.  I'm not a fan of
the way asserts pollute the main code base.

Marvin Humphrey

Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Andrew S. Townley
In reply to this post by Marvin Humphrey
Hi Marvin

On 3 Mar 2011, at 03:08 a.m., Marvin Humphrey <[hidden email]> wrote:

> Greets,
>
> There's no good reason for it, but right now only methods which are tagged as
> either "public" or "abstract" within Clownfish can be overridden from the host
> language.
>
> This caused a problem in an application I was working on because we wanted to
> override IndexSearcher's Top_Docs() method.  Since Top_Docs() is not yet
> public in Lucy, the attempt to override it from Perl fails silently: no
> callback is installed.  Thus, when Searcher_Hits() invokes Top_Docs() from
> C-space on our subclassed IndexSearcher, it gets the C function
> IxSearcher_top_docs() rather than the Perl subroutine top_docs() from our
> subclass.
>
> The fix is to allow any non-final method to be overridden, regardless of its
> exposure.  Patch below.
>
> For "final" methods, we have two options.  We can fail silently, as we do now.
> In this case, there will be different behavior when a method is invoked from
> the host (the illegal host override method fires) vs. when it is invoked from
> within the Lucy core (the "final" method definition fires).
>
> The other option is to throw an exception at runtime when an attempt to
> override a final method is detected.  Dynamic VTable objects are built lazily,
> so the error would occur the first time the constructor for the problematic
> class gets invoked.
>
> The rationale for this change is that method overrides should work the same way
> for both C-based classes and host-based classes: non-final methods should be
> overridable from both C and the host.  There are no public API changes because
> every public non-final method was already overridable; only non-public methods
> will get a behavior change.  
>
> Right this moment I'm feeling lazy, so inertia is favoring the first option for
> final methods, "fail silently." :)  Failing at runtime when illegal method
> overriding from the host is detected isn't as friendly as failing at compile
> time when an illegal override is found in a .cfh Clownfish header file, though.

Lazy or not, I think it's better to fail silently now and then try and build better checks into the clownfish compiler or some kind of clownlint tool later than imposing exception handling overhead on potentially every method call (unless I'm misunderstanding the impact of option B).

:)

ast
Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Marvin Humphrey
On Thu, Mar 03, 2011 at 09:03:39AM +0000, Andrew S. Townley wrote:
> Lazy or not, I think it's better to fail silently now and then try and build
> better checks into the clownfish compiler or some kind of clownlint tool
> later than imposing exception handling overhead on potentially every method
> call (unless I'm misunderstanding the impact of option B).

The host language's OO hierarchy is only walked once per subclass.  Once Lucy
creates a VTable singleton and stores it away, that VTable will not be
modified.  Thus, there is no extra overhead imposed on every method call
within the Lucy core -- but we don't support all the features of dynamic
languages.

Generally speaking, the VTable singleton for a host-defined subclass is
created the first time a constructor for that subclass is called[1].  It is at
this moment that we would attempt to detect illegal overriding of "final"
methods.  Here's the code from from VTable_singleton() in
core/Lucy/Object/VTable.c which enables host method overrides, modified to
enforce "final" methods:

     // Allow host methods to override.
     novel_host_methods = VTable_novel_host_methods(subclass_name);
     num_novel = VA_Get_Size(novel_host_methods);
     if (num_novel) {
         Hash *meths = Hash_new(num_novel);
         uint32_t i;
         CharBuf *scrunched = CB_new(0);
         ZombieCharBuf *callback_name = ZCB_BLANK();
         for (i = 0; i < num_novel; i++) {
             CharBuf *meth = (CharBuf*)VA_fetch(novel_host_methods, i);
             S_scrunch_charbuf(meth, scrunched);
             Hash_Store(meths, (Obj*)scrunched, INCREF(&EMPTY));
         }
         cfish_Callback **callbacks
             = (cfish_Callback**)singleton->callbacks;
         for (i = 0; callbacks[i] != NULL; i++) {
             cfish_Callback *const callback = callbacks[i];
             ZCB_Assign_Str(callback_name, callback->name,
                 callback->name_len);
             S_scrunch_charbuf((CharBuf*)callback_name, scrunched);
             if (Hash_Fetch(meths, (Obj*)scrunched)) {
+                if (callback->method_is_final) {
+                    THROW(ERR,
+                        "Can't override final method '%o' in class '%o'",
+                        meth, class_name);
+                }
                 VTable_Override(singleton, callback->func,
                     callback->offset);
             }
         }
         DECREF(scrunched);
         DECREF(meths);
     }
     DECREF(novel_host_methods);

Once a VTable is created, if you subsequently attempt to modify behavior using
dynamic features such as Ruby's singleton methods, you will get inconsistent
results.  The behavior will be visible from the host language, but it might
not be visible from inside the Lucy core.  You only get one shot to tell Lucy
that it needs to call back into the host.  If a method was not overridden at
the moment the VTable was created, Lucy won't notice if it gets overridden
later.
   
    class MyQueryParser < Lucy::Search::QueryParser
    end

    query_parser = MyQueryParser.new(schema)
    def query_parser.expand_leaf
        puts "This code will not be called from within the Lucy core."
    end

Clownfish's design is a compromise which lets us support a simple class-based
single-inheritance OO model without sacrificing speed.  Method dispatch in
Clownfish uses a vtable-based double dereference mechanism[2] -- typical for
C++ or Java.  It's less flexible than the dispatch techniques used by dynamic
languages like Ruby, Python and Perl, but until the host callback mechanism
gets invoked, it's much, much faster.

Marvin Humphrey

[1] All parent VTables must be created first, so if the VTable for a host
    subclass two generations removed from its Lucy ancestor is needed before
    its parent, the parent VTable will be initialized first as a side effect.

[2] http://en.wikipedia.org/wiki/Virtual_method_table
Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Andrew S. Townley

On 3 Mar 2011, at 1:35 PM, Marvin Humphrey wrote:

> On Thu, Mar 03, 2011 at 09:03:39AM +0000, Andrew S. Townley wrote:
>> Lazy or not, I think it's better to fail silently now and then try and build
>> better checks into the clownfish compiler or some kind of clownlint tool
>> later than imposing exception handling overhead on potentially every method
>> call (unless I'm misunderstanding the impact of option B).
>
> The host language's OO hierarchy is only walked once per subclass.  Once Lucy
> creates a VTable singleton and stores it away, that VTable will not be
> modified.  Thus, there is no extra overhead imposed on every method call
> within the Lucy core -- but we don't support all the features of dynamic
> languages.
>
> Generally speaking, the VTable singleton for a host-defined subclass is
> created the first time a constructor for that subclass is called[1].  It is at
> this moment that we would attempt to detect illegal overriding of "final"
> methods.  Here's the code from from VTable_singleton() in
> core/Lucy/Object/VTable.c which enables host method overrides, modified to
> enforce "final" methods:
>
>     // Allow host methods to override.
>     novel_host_methods = VTable_novel_host_methods(subclass_name);
>     num_novel = VA_Get_Size(novel_host_methods);
>     if (num_novel) {
>         Hash *meths = Hash_new(num_novel);
>         uint32_t i;
>         CharBuf *scrunched = CB_new(0);
>         ZombieCharBuf *callback_name = ZCB_BLANK();
>         for (i = 0; i < num_novel; i++) {
>             CharBuf *meth = (CharBuf*)VA_fetch(novel_host_methods, i);
>             S_scrunch_charbuf(meth, scrunched);
>             Hash_Store(meths, (Obj*)scrunched, INCREF(&EMPTY));
>         }
>         cfish_Callback **callbacks
>             = (cfish_Callback**)singleton->callbacks;
>         for (i = 0; callbacks[i] != NULL; i++) {
>             cfish_Callback *const callback = callbacks[i];
>             ZCB_Assign_Str(callback_name, callback->name,
>                 callback->name_len);
>             S_scrunch_charbuf((CharBuf*)callback_name, scrunched);
>             if (Hash_Fetch(meths, (Obj*)scrunched)) {
> +                if (callback->method_is_final) {
> +                    THROW(ERR,
> +                        "Can't override final method '%o' in class '%o'",
> +                        meth, class_name);
> +                }
>                 VTable_Override(singleton, callback->func,
>                     callback->offset);
>             }
>         }
>         DECREF(scrunched);
>         DECREF(meths);
>     }
>     DECREF(novel_host_methods);
>
> Once a VTable is created, if you subsequently attempt to modify behavior using
> dynamic features such as Ruby's singleton methods, you will get inconsistent
> results.  The behavior will be visible from the host language, but it might
> not be visible from inside the Lucy core.  You only get one shot to tell Lucy
> that it needs to call back into the host.  If a method was not overridden at
> the moment the VTable was created, Lucy won't notice if it gets overridden
> later.
>
>    class MyQueryParser < Lucy::Search::QueryParser
>    end
>
>    query_parser = MyQueryParser.new(schema)
>    def query_parser.expand_leaf
>        puts "This code will not be called from within the Lucy core."
>    end
>
> Clownfish's design is a compromise which lets us support a simple class-based
> single-inheritance OO model without sacrificing speed.  Method dispatch in
> Clownfish uses a vtable-based double dereference mechanism[2] -- typical for
> C++ or Java.  It's less flexible than the dispatch techniques used by dynamic
> languages like Ruby, Python and Perl, but until the host callback mechanism
> gets invoked, it's much, much faster.
>
> Marvin Humphrey
>
> [1] All parent VTables must be created first, so if the VTable for a host
>    subclass two generations removed from its Lucy ancestor is needed before
>    its parent, the parent VTable will be initialized first as a side effect.
>
> [2] http://en.wikipedia.org/wiki/Virtual_method_table


That all makes sense, but I guess I was coming from the perspective of you never know when those objects are going to be instantiated.  I was trying to have the least possible unexpected disruptions (e.g. fail safe) vs. potentially random uncaught exceptions in potentially complex systems that may or may not use plugins to configure things like search behavior.

Couldn't throwing the exception this way make it possible for bad code loaded dynamically at runtime to bring down an entire system?  If you never know when this exception can potentially be thrown, you'll never be able to reliably catch it (except perhaps in a top-level run loop) and avoid potential chaos.

Barring this, I think Nathan's suggestion of some kind of runtime behavior configuration via environment variables or initialization parameters would be preferable to "random" exceptions because of programmer error.  However, maybe I'm being a bit paranoid as well... ;)
--
Andrew S. Townley <[hidden email]>
http://atownley.org

Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Nathan Kurz
In reply to this post by Marvin Humphrey
On Wed, Mar 2, 2011 at 10:30 PM, Marvin Humphrey <[hidden email]> wrote:
> Arguably, we don't even need the "final" keyword.  We'd should benchmark to
> confirm my recollection about the performance implications, but I'll bet we
> could remove it with no immediate impact on Lucy.

I'd suggest this as the cleanest solution.  Intuitively, I'd think
that the benefit of 'final' would be very small, such that if one
really cares about performance one should inline the function call
completely and not worry about saving a single dereference.

>> That seems like the wrong kind of lazy. :)  I think the right kind of
>> lazy is to solve it once by brute force:  ASSERT(! $method->final).
>> But since true macros are hard in Perl, I'd be happy with adding an
>> 'if DEBUG' to that so that it can get optimized away at compile if one
>> wants it to be.  But you never really got on the ASSERT train, did
>> you?
>
> Haha, that's true.  When code can be verified via unit tests, I prefer that,
> since it stores the noise out of band in a unit test file.  I'm not a fan of
> the way asserts pollute the main code base.

Your unit tests are great, but assert() let's you catch errors while
still programming defensively. Take the "!!foo == !!bar" example from
a couple days ago.   You fix the problem with "!!", and presumably
have unit tests that check that you fix it, but now you never get a
warning that something has gone awry.  With only unit tests, you have
to choose whether to report the error or try your best to handle it.
Assert (running only for the debug build) let's you do both of these
--- cry out loudly that an assumption has been broken when running
debug, and do what you can to carry on in production.   In some ways,
the key is not just assert(), but rather the existence of a debug
build with appropriate scaffolding.

If you choose to keep 'final', I think assert() is really the right
tool here, too.  You don't want the production system to fail because
a programmer is trying to override something non-overridable, but you
need to warn the user somehow.  Unit tests and asserts are not a "belt
and suspenders" sort of redundancy.  Rather it's more of "shirt and
pants" thing.  Both have their place socially, and there are
situations one, the other, or neither are needed.  But rarely do you
find yourself required to have at least one, but are allowed to choose
which one that is.   But it's your house/project, and you're welcome
to set your own dress code, even if it is a bit pedantic to test the
limits of "Shirt and Shoes Required" by not wearing any pants.  (long
day)

Nathan Kurz
[hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Marvin Humphrey
On Fri, Mar 04, 2011 at 11:27:59PM -0800, Nathan Kurz wrote:
> On Wed, Mar 2, 2011 at 10:30 PM, Marvin Humphrey <[hidden email]> wrote:
> > Arguably, we don't even need the "final" keyword.  We'd should benchmark to
> > confirm my recollection about the performance implications, but I'll bet we
> > could remove it with no immediate impact on Lucy.
>
> I'd suggest this as the cleanest solution.  Intuitively, I'd think
> that the benefit of 'final' would be very small, such that if one
> really cares about performance one should inline the function call
> completely and not worry about saving a single dereference.

Sounds good -- I'll work up a patch.  We'll leave the "inline" keyword in
Clownfish, but drop the "final" keyword.

Looking forward, we'll need to think about how to design our classes and
interfaces so that time-critical functionality can been inlined whenever
possible.  Java JIT compilers have the option of inlining even non-final
method bodies by branching for each known implementation at the site of the
method invocation (while providing a fallback branch for lazy-loaded classes).
That's an advantage we'll never have.  However, those kind of tricks are
notoriously unpredictable, and the Lucene folks have experienced a lot of
frustration trying to optimize around such optimizations.  Maybe we'll have a
little more luck with our manual inlining.

Our object structs are opaque, which limits our options since the inlined
functions have to go in header files.   However, we've had success with making
raw mmap'd buffers available via InStream_Buf() and Instream_Advance_Buf() so
that the inlined encoders/decoders in the NumUtils module can be deployed.
Perhaps we'll find other such opportunities.
 

> If you choose to keep 'final', I think assert() is really the right
> tool here, too.  You don't want the production system to fail because
> a programmer is trying to override something non-overridable, but you
> need to warn the user somehow.  Unit tests and asserts are not a "belt
> and suspenders" sort of redundancy.  Rather it's more of "shirt and
> pants" thing.  Both have their place socially, and there are
> situations one, the other, or neither are needed.  But rarely do you
> find yourself required to have at least one, but are allowed to choose
> which one that is.   But it's your house/project, and you're welcome
> to set your own dress code, even if it is a bit pedantic to test the
> limits of "Shirt and Shoes Required" by not wearing any pants.  (long
> day)

I don't work from home as much as I used to. ;)

Asserts are fine, of course -- they're SOP for lots of developers.  I'm not
arguing to exclude them from the Lucy codebase, just explaining why I haven't
made them a habit.  Who knows, maybe I'll amend my ways with time.

Marvin Humphrey

Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Nathan Kurz
On Sun, Mar 6, 2011 at 9:03 PM, Marvin Humphrey <[hidden email]> wrote:

> On Fri, Mar 04, 2011 at 11:27:59PM -0800, Nathan Kurz wrote:
>> On Wed, Mar 2, 2011 at 10:30 PM, Marvin Humphrey <[hidden email]> wrote:
>> > Arguably, we don't even need the "final" keyword.  We'd should benchmark to
>> > confirm my recollection about the performance implications, but I'll bet we
>> > could remove it with no immediate impact on Lucy.
>>
>> I'd suggest this as the cleanest solution.  Intuitively, I'd think
>> that the benefit of 'final' would be very small, such that if one
>> really cares about performance one should inline the function call
>> completely and not worry about saving a single dereference.
>
> Sounds good -- I'll work up a patch.  We'll leave the "inline" keyword in
> Clownfish, but drop the "final" keyword.

Great.  I think you could get away with dropping 'inline' as well.  My
point was not that Clownfish needs to inline things, but that if you
really want to squeeze out the last drop of performance by avoiding
function calls, you'll have to take control of the compilation
yourself, likely by rewriting the entire core class in some unreadable
and unmodifiable fashion.

It would be interesting, though, to someday benchmark the potential
advantage here.  Once you're generating code, it wouldn't be hard to
test generate a monolithic 'final' library as well, with inter-class
inlining.  But if one was to take this route for anything production,
I think it would make more sense as an overall compile time option
rather than a method-by-method keyword: -O lock-it-all-down.

> Looking forward, we'll need to think about how to design our classes and
> interfaces so that time-critical functionality can been inlined whenever
> possible.

While there is some small gain to be had here, I don't think it should
be a priority.  I can be as cycle-count-conscious as anyone, but once
you're memory bound there isn't that much advantage is optimizing
cycles much further.  I think we can get far by keeping the base
architecture fast (as it currently is) and concentrating on data
layout.   To the extent that one does worry about cycles, it's not the
function calls that need to be avoided, rather the mispredicted
branches.  So long as you take the same convoluted path every time,
modern processors are monstrously efficient.

Let's make the Northbridge scream for mercy.

Nathan Kurz
[hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Nathan Kurz
On Mon, Mar 7, 2011 at 12:17 AM, Nathan Kurz <[hidden email]> wrote:
> Great.  I think you could get away with dropping 'inline' as well.  My
> point was not that Clownfish needs to inline things, but that if you
> really want to squeeze out the last drop of performance by avoiding
> function calls, you'll have to take control of the compilation
> yourself, likely by rewriting the entire core class in some unreadable
> and unmodifiable fashion.

Responding to myself, I just learned that GCC now supports Link Time
Optimization, which might make this sort of inter-module inlining
practical: <http://gcc.gnu.org/onlinedocs/gccint/LTO.html>.  I'd known
that it was possible with LLVM:
<http://llvm.org/docs/LinkTimeOptimization.html>, but not that it had
landed in GCC.   This might make creating a benchmark easy enough that
one can see what (if anything) one is missing.

--nate
Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Marvin Humphrey
On Tue, Mar 08, 2011 at 01:10:32PM -0800, Nathan Kurz wrote:
> Responding to myself, I just learned that GCC now supports Link Time
> Optimization, which might make this sort of inter-module inlining
> practical: <http://gcc.gnu.org/onlinedocs/gccint/LTO.html>.  I'd known
> that it was possible with LLVM:
> <http://llvm.org/docs/LinkTimeOptimization.html>, but not that it had
> landed in GCC.  

Great stuff!  Thanks for passing it along.

Ironically, the availability of link-time optimization suggests that we should
preserve the "final" keyword in Clownfish.  

From what I gather, really fancy JIT inlining involves discovering all
possible paths in a class hierarchy when a non-final method is invoked, and
creating multiple inlined paths at the site of the invocation.  I would be
shocked if LLVM or GCC were able to figure out our virtual method invocation
scheme well enough to discover such possibilities.  The theory is similar,
but those compilers wouldn't know to look.

If I understand correctly, what LTO can do for us is associate a symbol with a
small body of compiled code and inline that compiled code at the site of an
invocation.  That's possible if we alias method symbols to real function
symbols, but not if the method symbols remain vtable lookup invocations as
they are now.

The Get() method on Lucy::Index::BitVecDelDocs returns true if the bit at
"tick" is set and false otherwise.  Here's what the Clownfish compiler
currently produces for it:

    extern size_t Lucy_BitVecDelDocs_Get_OFFSET;
    static CHY_INLINE chy_bool_t
    Lucy_BitVecDelDocs_Get(const lucy_BitVecDelDocs *self, uint32_t tick)
    {
        char *const method_address = *(char**)self + Lucy_BitVecDelDocs_Get_OFFSET;
        const lucy_BitVec_get_t method = *((lucy_BitVec_get_t*)method_address);
        return method((lucy_BitVector*)self, tick);
    }

If we change BitVecDelDocs to be a "final" class, the Clownfish compiler
instead aliases Lucy_BitVecDelDocs_Get() to the function lucy_BitVec_get():

    #define Lucy_BitVecDelDocs_Get(self, tick) \
        lucy_BitVec_get((lucy_BitVector*)self, tick)

The function body at lucy_BitVec_get() is small and would be an ideal candidate
for inlining.  It's a bottleneck while iterating over posting lists.

I think GCC or LLVM has a decent shot at figuring out that it should inline
the aliased function.  I don't think there's any hope that the virtual method
call will be optimized in the same manner.

> This might make creating a benchmark easy enough that one can see what (if
> anything) one is missing.

True, that!

Marvin Humphrey

Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Nathan Kurz
On Tue, Mar 8, 2011 at 9:41 PM, Marvin Humphrey <[hidden email]> wrote:
> On Tue, Mar 08, 2011 at 01:10:32PM -0800, Nathan Kurz wrote:
>>
>>  <http://gcc.gnu.org/onlinedocs/gccint/LTO.html>
>> <http://llvm.org/docs/LinkTimeOptimization.html>
>
> Ironically, the availability of link-time optimization suggests that we should
> preserve the "final" keyword in Clownfish.

Yes, presuming that a quick test shows that it actually has some real
world benefit.  :)

When I started thinking about it, I was wondered whether an "opt-out"
approach might be better.  Instead of marking things that are final,
have one compilation option for everything overridable, and a
performance option where everything is presumed final unless otherwise
marked in some way.  I'm guessing the majority of people won't be
overriding anything, and this will make their experience slightly
better.  The added mental overhead of having to mark individual
classes/methods that you are overriding seems acceptable as long as
the error messages are clear.  :)

> If I understand correctly, what LTO can do for us is associate a symbol with a
> small body of compiled code and inline that compiled code at the site of an
> invocation.  That's possible if we alias method symbols to real function
> symbols, but not if the method symbols remain vtable lookup invocations as
> they are now.

Yes, I think that's what it can do --- essentially it allows inlines
across modules.

> I think GCC or LLVM has a decent shot at figuring out that it should inline
> the aliased function.  I don't think there's any hope that the virtual method
> call will be optimized in the same manner.

I'd have thought so to, but recently I saw a few references to things
like this: http://www.reddit.com/r/programming/comments/fzwlh/for_c_programmers_that_hate_c/c1jwuxo

Nathan Kurz
[hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: [lucy-dev] Host overriding of all non-final methods

Marvin Humphrey
On Tue, Mar 08, 2011 at 11:51:08PM -0800, Nathan Kurz wrote:
> > If I understand correctly, what LTO can do for us is associate a symbol with a
> > small body of compiled code and inline that compiled code at the site of an
> > invocation.  That's possible if we alias method symbols to real function
> > symbols, but not if the method symbols remain vtable lookup invocations as
> > they are now.
>
> Yes, I think that's what it can do --- essentially it allows inlines
> across modules.

Well, this is annoying:

  http://gcc.gnu.org/onlinedocs/gccint/LTO.html

  To make the situation even more difficult, many applications organize
  themselves as a set of shared libraries, and the default ELF visibility
  rules allow one to overwrite any externally visible symbol with a different
  symbol at runtime. This basically disables any optimizations across such
  functions and variables, because the compiler cannot be sure that the
  function body it is seeing is the same function body that will be used at
  runtime. Any function or variable not declared static in the sources
  degrades the quality of inter-procedural optimization.

There's hope here:

  http://software.intel.com/en-us/articles/software-convention-models-using-elf-visibility-attributes/

On a side note, thes articles solve something that baffled me when I was
looking at the assembler generated by our virtual method invocation mechanism.
Regardless of whether the _OFFSET variable was declared "extern const" or
"extern", the assembler didn't change: the symbol was always retrieved from
the GOT and the value fetched each time.  I wound up declaring the _OFFSET
variables as "extern" and leaving off the no-op "const":

  extern size_t Lucy_BitVecDelDocs_Get_OFFSET;

I now understand why those _OFFSET vars are always looked up in the GOT: the
symbol could be overwritten at any time.  The last loaded shared object wins.

The penalty for that lookup seems to be small, and keeping the offset as a
variable is essential for preserving binary compatibility with external
extensions when the Lucy core is updated and vtables are reorganized.
Ideally, Clownfish method invocations would be built at runtime using JIT
compilation, but that's not going to happen.  :)  FWIW, we do have the option
of hard-coding those offsets to constants within the Lucy core, so that only
extensions would pay the penalty.

> > I think GCC or LLVM has a decent shot at figuring out that it should inline
> > the aliased function.  I don't think there's any hope that the virtual method
> > call will be optimized in the same manner.
>
> I'd have thought so to, but recently I saw a few references to things
> like this: http://www.reddit.com/r/programming/comments/fzwlh/for_c_programmers_that_hate_c/c1jwuxo

Thinking this through, I'm certain that our virtual method invocation
mechanism would foil this optimization.  The compiler can't build the call
graphs because it can't limit the method pointers that would reside in the
vtable to a finite set.  In a Java JIT compiler, it can know all of the
possible paths, because the method invocation mechanism is private -- in a
worst case, all it has to know is how to deal with a lazy-loaded class.

Ours vtables are just ordinary structs, though -- anything at all could be in
there.  Such an optimization would only be theoretically possible under
whole-program compilation -- and even then it would be very impressive if the
compiler could discover it.

Marvin Humphrey