Skip to content

Instantly share code, notes, and snippets.

@shipilev
Last active January 3, 2016 13:39
Show Gist options
  • Save shipilev/8470787 to your computer and use it in GitHub Desktop.
Save shipilev/8470787 to your computer and use it in GitHub Desktop.
This is a class:
class C {
final int v;
C(int v) {
this.v = v;
}
int sqr() {
return v*v;
};
}
...there are lots and lots of instances floating around in the heap:
List<C> cs = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
cs.add(new C(i));
}
writeToHeap(cs);
...somewhere later somebody finally uses *some* instance of C:
C c = readFromHeap();
print(c.sqr());
Please go ahead, inline sqr and optimize it for given "c"?
But which one? Would you enumerate all possible instances of "c"?
This optimization requires *stable C identity* as the prerequisite.
"Think CHA on steroids"?!
Note that CHA for classes works plausibly well because:
a) *class* identity set is much smaller
b) *and* the changes to that set are easily detectable
c) *and* the changes to that set are infrequent
That actually matters for speculative optimizations like these.
Otherwise you are looking at the combinatorial explosion of
metadata to swallow, as well as runtime overhead.
Ok, assume you are lucky, and there is only a single instance of C
is floating around (*highly* unlikely for *generic* application,
not for the microbenchmark) What would you do if somebody else
instantiates another C? Deoptimize all sqr()-s? Or, you generate the
code for "sqr()" which proactively checks the "c"-ish identity before
applying the optimization? Do you sweep the optimized code when some
"c" is going out of heap and stops being reachable? Are you specializing
for multiple "c"-s? How many? Etc. etc. etc.
@giltene
Copy link

giltene commented Jan 17, 2014

I would only expect to see constant propagation for "effectively final" static fields, but there are plenty of good examples of those that could be automagically identified (through global code analysis) just like CHA identifies the single implementor situations in a given global class set. These can also be extended to identifying "effectively final" even when code that late-mutates the state exists, as long as it never actually executes (the analog here us an inline cache or a guarded inline).

Instance fields may also be worth analyzing for this. While trying to constant propagate instance fields would be silly, there are optimization benefits to knowing (or assuming) that an instance field is final. Ordering and instruction scheduling is one key example, as reads of final fields can be freely scheduled across ordering barriers in the memory model, allowing folding of reads. and caching of values that would otherwise need to be re-read after certain barriers (caused by things like a volatile load, or a monitor enter). So deducing or speculating on "effectively final" for an instance field can still be valuable in either a CHA-like (global analysis of current code base with expensive invalidation depots if class loading changes assumptions) or an inline-cache-like (optimistic assumption that mutating code never executes, with expensive depots if it ever does) ways.

@giltene
Copy link

giltene commented Jan 17, 2014

Think about it this way:

Just like there is no optimization value to explicitly declaring a method final (CHA can match that value every time by detecting effectively-final methods), we can also make it so that there is no optimization value to explicitly declaring a field final, whether it is static or not. Whatever optimization the compiler can derive from being explicitly told that a field is final can also be derived from proving that it s effectively final through analysis of the currently loaded code.

Similarly, just like final-method-like optimizations can be applied to call sites even when there are multiple loaded implementors for the method (with the slight cost of a guard for dynamic checking of the monomorphic site assumption), final-field-like optimizations can be applied to reads of fields that are "effectively final" even when code that modifies those fields exists. The cost of guarding these effectively-final assumptions is cheaper than that of monomorphic site verification, since the guard only needs to apply to the mutating-but-never-yet-run code, and will only trigger once (it can be ripped out after the first trigger).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment