Introduce per-isolate cache for compile time constants

Introduce per-isolate cache for compile time constants

Compile-time constant values are maintained in a cache, keyed
by script and token position. When the same code is compiled
again later, e.g. by the optimizing compiler, the value is
found in the cache and does not need to be computed again.

In this version, the key is a string concatenated from the
script url and the token position. That’s probably more overhead
than we want.

Added two compiler stat counters for number of cached constants
and number of cache hits. Running dart2js to compile a hello world
program results in about 1400 cached values and 85 cache hits.


BUG=
R=srdjan@google.com

Committed: https://github.com/dart-lang/sdk/commit/62e9d056681308fef71540300643db1a63639bc4

[hausner, 2015-08-25 18:02:49]

hausner@google.com changed reviewers:
+ iposva@google.com

[koda, 2015-08-25 18:27:12]

koda@google.com changed reviewers:
+ koda@google.com

[koda, 2015-08-25 18:27:12]

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11905: String& suffix =
String::Handle(String::NewFormatted("_%" Pd "", token_pos));
Add TODO: avoid allocations for lookup by introducing a (script, token_pos)
wrapper type and overloading IsMatch/Hash in the traits (like
Symbols::FromConcat does for string pairs).

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11905: String& suffix =
String::Handle(String::NewFormatted("_%" Pd "", token_pos));
Make private method and then: Handle(Z, ...)

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11911: String& key = String::Handle();
Handle(Z)

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11931: String& key = String::Handle();
Handle(Z)

[hausner, 2015-08-25 19:48:52]

Thanks for taking a look.

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11905: String& suffix =
String::Handle(String::NewFormatted("_%" Pd "", token_pos));
On 2015/08/25 18:27:12, koda wrote:
> Add TODO: avoid allocations for lookup by introducing a (script, token_pos)
> wrapper type and overloading IsMatch/Hash in the traits (like
> Symbols::FromConcat does for string pairs).

We discussed offline, but for those following along at home: it does not help
much to avoid the allocation because if no object is found for this position, it
will be inserted later. Creating the symbol here means we don't have to allocate
it when the constant gets inserted.

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11905: String& suffix =
String::Handle(String::NewFormatted("_%" Pd "", token_pos));
On 2015/08/25 18:27:12, koda wrote:
> Make private method and then: Handle(Z, ...)

Done.

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11911: String& key = String::Handle();
On 2015/08/25 18:27:12, koda wrote:
> Handle(Z)

Done.

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11931: String& key = String::Handle();
On 2015/08/25 18:27:12, koda wrote:
> Handle(Z)

Done.

[srdjan, 2015-08-25 22:16:18]

srdjan@google.com changed reviewers:
+ srdjan@google.com

[srdjan, 2015-08-25 22:16:19]

DBC

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11905: String& suffix =
String::Handle(String::NewFormatted("_%" Pd "", token_pos));
String::NewFormatted is allocating a string in new space. We need to avoid that
in order to run the optimizing compiler in a the parallel thread.

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:11916: Array::Handle(Z,
HashTables::New<ConstantsMap>(kInitialConstMapSize)));
It does not matter for optimizing compiler (since the table will be allocated
inside an unoptimized compilation), but does it make sense to store the HashMap
in old space as it is long lived and will anyhow land in old space?

[Florian Schneider, 2015-08-26 08:27:32]

fschneider@google.com changed reviewers:
+ fschneider@google.com

[Florian Schneider, 2015-08-26 08:27:32]

DBC:

As I suggested before my idea would be to try a different approach - not using a
global hash-map:

1. Number the computed constants (each LiteralNode gets a number 1..N) within
each function.

2. If not present (first unoptimizing compilation), store an index array with
each function where the Nth entry contains an index I to constant N the into the
object pool.

3. If the index array is present (e.g. re-compilation with the optimizing
compiler), lookup the Nth computed constant by loading
object_pool[index_array[N]].

I have not thought it through 100%... but does that make sense?

[Florian Schneider, 2015-08-26 08:58:09]

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:12936: CacheConstantValue(literal_pos, const_instance);
Are cached constants ever GCed? What if the code that refers to such a constant
gets GCed? Wouldn't you need to traverse the cache to evict the corresponding
constants?

[hausner, 2015-08-26 17:46:14]

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc
File runtime/vm/parser.cc (right):

https://codereview.chromium.org/1308073005/diff/1/runtime/vm/parser.cc#newcod...
runtime/vm/parser.cc:12936: CacheConstantValue(literal_pos, const_instance);
On 2015/08/26 08:58:09, Florian Schneider wrote:
> Are cached constants ever GCed? What if the code that refers to such a
constant
> gets GCed? Wouldn't you need to traverse the cache to evict the corresponding
> constants?

No, they are not GCed. But we hold on to these constants through the list of
canonical values (RawClass::constants_) already, so they don't get GCed even
now.

[hausner, 2015-08-26 21:22:57]

PTAL

I think I addressed the allocation issue.

[srdjan, 2015-08-26 21:39:41]

LGTM

[hausner, 2015-08-26 23:17:38]

Committed patchset #2 (id:20001) manually as
62e9d056681308fef71540300643db1a63639bc4 (presubmit successful).