Thanks for the write up. Very interesting idea! I've never seen this kind of optimization before, but I definitely see that the motivation is to avoid global optimizations from hampering local ones. Traditionally, to do to the kind of thing your proposing here, compilers would try to track the values within the block, but this seems to be a lot simpler. I think traditional intra-block optimizations may be able to help too, since with copy propagation, n = b.size() would be inlined and the value of 0 would be propagated as long as no statements with side-effects to b are executed between the definition of b and the valuation of n. I agree that when you combine this with object-inlining/destructuring (we all need to agree on terminology :) ) it could be very powerful in eliminating JRE collection overhead.
-Ray On Wed, Jun 17, 2009 at 3:07 PM, Bruce Johnson <[email protected]> wrote: > On Wed, Jun 17, 2009 at 3:01 PM, Ray Cromwell <[email protected]>wrote: > >> Bruce, By type cloning, do you mean using typeflow information to >> compute a set of types for a given reference, and then speculatively type >> tightening? >> > > I'm talking about something else, but you're right about the Will explain > more in the bottom section. > > >> >> We can compute the set of potential concrete types for 'list' as >> {LinkedList, ArrayList}. Therefore, we can inline the call to list.get(n), >> as: >> > > This is what Scott and Lex have been calling something like, "set-base type > tightening". > > If someNonInlineableMethod() is only ever reached from blocks where the >> parameter is ArrayList, then the 'l' parameter can be tightened to >> ArrayList. You need CFG/flow analysis because methodA(List l) might call >> methodB(List l) where the chain is only ever invoked with ArrayList. >> > > We do a CFG-independent version of what you're talking about. We do tighten > parameter types, but only based on the (tightened) types of all the call > sites, without regard to control flow. > > === Type Cloning === > What I mean by type cloning is this: for every unique (lexical) occurrence > of an allocation of type T, clone T into T' as if it were an independent > type, but arrange that T' is indistinguishable from T w.r.t. casts, > instanceof, and getClass(). In other words, you could never determine at > runtime that the object wasn't actually a genuine T. Now, optimize as > normal. To see how this could play out: > > class BasicList<E> { > > private E[] elems; > > > @SuppressWarnings("unchecked") > > public void add(E elem) { > > if (elems == null) { > > elems = (E[]) new Object[] {elem}; > > } else { > > E[] newElems = (E[]) new Object[elems.length + 1]; > > System.arraycopy(elems, 0, newElems, 0, elems.length); > > newElems[newElems.length - 1] = elem; > > elems = newElems; > > } > > } > > > public int size() { > > return elems == null ? 0 : elems.length; > > } > > > > public Iterator<E> iterator() { > > final int n = size(); > > > return new Iterator<E>() { > > private final int i = 0; > > > public boolean hasNext() { > > return i < n; > > } > > > public E next() { > > return elems[i]; > > } > > > public void remove() { > > // nothing > > } > > }; > > } > > } > > // Then in some other code, you could write... > void foo() { > BasicList<String> b = new BasicList<String>(); > for (int i = 0, n = b.size(); i < n; ++i) { > // Removed by dead code elim. > } > > for (String s: b) { > // Also removed by dead code elim. > } > } > > In the above, b is of type BasicList' (a clone of BasicList that can be > independently optimized). Thus, you can see that BasicList' does not have > the add() method called, which means that, for this particular use of the > type, the 'elems' field will always be null. Consequently, size() can be > statically known to return 0. Similarly, the iterator's hasNext() method can > be statically shown to always return false in the for/each loop. > > The key point is that the usage of a type in one context would not affect > how the type itself could be optimized in other contexts. As it stands > today, we can't do the above optimization if anywhere in the program someone > calls BasicList#add(). A great practical example is Widgets firing events. > You want widgets to be *able* to fire events *if* someone actually wants to > listen to them. In the cases where you can see that there are no listeners > to a widget, you'd really like the entirely of the even-firing infrastructur > to completely disappear. So, I think it can be a big win. > > > > > > > --~--~---------~--~----~------------~-------~--~----~ http://groups.google.com/group/Google-Web-Toolkit-Contributors -~----------~----~----~----~------~----~------~--~---
