Mailing-List: contact lucy-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: lucy-dev@incubator.apache.org
Received-SPF: pass (nike.apache.org: local policy)
Date: Thu, 10 Mar 2011 18:02:04 -0800
From: Marvin Humphrey <marvin@rectangular.com>
To: lucy-dev@incubator.apache.org
Message-ID: <20110311020204.GA23460@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>
 <20110309054136.GA23459@rectangular.com>
 <AANLkTimpoQD_YahgErPkbj4J-Tvdy8gvFjhCu6rUeAkt@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <AANLkTimpoQD_YahgErPkbj4J-Tvdy8gvFjhCu6rUeAkt@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 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