Mailing-List: contact lucy-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: lucy-dev@incubator.apache.org
Received-SPF: pass (athena.apache.org: local policy)
Date: Tue, 8 Mar 2011 21:41:36 -0800
From: Marvin Humphrey <marvin@rectangular.com>
To: lucy-dev@incubator.apache.org
Message-ID: <20110309054136.GA23459@rectangular.com>
References: <20110303030834.GB5339@rectangular.com>
 <AANLkTikZv8FqYnnjx797GWFmhOcfVxRCr4vxONAhjztF@mail.gmail.com>
 <20110303063001.GA5707@rectangular.com>
 <AANLkTi=7-7F3bTiQw_oFEYN1Yx3ZDYwVbii21sydH-0f@mail.gmail.com>
 <20110307050300.GB23513@rectangular.com>
 <AANLkTinXf4fDe=Lw8VMM_-CfRgRcD8B7TRbE1=osGhh8@mail.gmail.com>
 <AANLkTinw4jXNVotDWjWSro_F__Q3AXh8DWViM9MDJ0sG@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <AANLkTinw4jXNVotDWjWSro_F__Q3AXh8DWViM9MDJ0sG@mail.gmail.com>
User-Agent: Mutt/1.5.18 (2008-05-17)
Subject: Re: [lucy-dev] Host overriding of all non-final methods

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