[9] RFR(M): 7194669: CodeCache::mark_for_deoptimization should avoid verifying dependencies multiple times

[Albert Noll]

Hi all,

could I get reviews for this patch?

bug: https://bugs.openjdk.java.net/browse/JDK-7194669
webrev: http://cr.openjdk.java.net/~anoll/7194669/webrev.00/

Problem:
The dependency verification code in CodeCache::mark_for_deoptimization 
walks over all live nmethods in the code cache and checks all 
dependencies for each nmethod. This leads to checking the same 
dependency multiple times which can take a huge amount of time.

Solution:
To avoid checking dependencies more than once, dependencies are 
abstracted by dependency signatures, which consider (i) the type of a 
dependency and (ii) the identity hashes of the arguments
of a dependency. For each dependency that will be checked, a dependency 
signature is generated
and that dependency signature is compared against a set of already 
checked dependency signatures.
If a dependency has already been checked, the check is skipped.
Dependency signatures of a specific type are stored in a binary tree to 
provide a fast lookup. I.e., each
dependency type has its own binary tree. The key to the tree is the 
identity hash of one argument. More
details about the data structure are described as comments in the code.

Results:
An evaluation of the performance gain shows a 4.3x speedup of dependency 
checking. More concretely,
I used nashorn + octane on a 64-bit Linux Hotspot version. The 
dependency checking time of the
original version is 3888 seconds. The dependency checking time of the 
optimized version is 902 seconds.

Passed jprt.


Many thanks in advance,
Albert