Multimap replacement

Multimap replacement
Committed: https://code.google.com/p/dart/source/detail?r=4217

[danrubel, 2012-02-13 01:54:33]

ElementMap saves about 15% per compile/analyze cycle

MultiMap
 18 Analyze : Average 1919 ms 
 19 Compile : Average 1103 ms
ElementMap
 18 Analyze : Average 1703 ms
 19 Compile : Average  941 ms

[ahe, 2012-02-13 13:25:56]

LGTM!

http://codereview.chromium.org/9373059/diff/7001/compiler/java/com/google/dar...
File compiler/java/com/google/dart/compiler/resolver/ElementMap.java (right):

http://codereview.chromium.org/9373059/diff/7001/compiler/java/com/google/dar...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:39: throw new
RuntimeException();
Nit, in my opinion, it is better to use:

new AssertionError("ElementHolder should not be accessed outside this class");

http://codereview.chromium.org/9373059/diff/7001/compiler/java/com/google/dar...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:206: //
System.err.println("Growing to " + elements.length);
Remove debug code.

http://codereview.chromium.org/9373059/diff/7001/compiler/javatests/com/googl...
File compiler/javatests/com/google/dart/compiler/resolver/ElementMapTest.java
(right):

http://codereview.chromium.org/9373059/diff/7001/compiler/javatests/com/googl...
compiler/javatests/com/google/dart/compiler/resolver/ElementMapTest.java:4: *
Licensed under the Eclipse Public License v1.0 (the "License"); you may not use
this file except
Wrong license.

[mmendez, 2012-02-13 15:08:56]

lgtm

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
File compiler/java/com/google/dart/compiler/resolver/ElementMap.java (right):

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:45: throw new
RuntimeException();
Nit: I have to agree with Peter on the conversion to an AssertionError on the
following elements as well.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:111: if
((elements.length >> 2) * 3 <= size()) {
Nit: not sure how the  lhs of the size comp was arrived at.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:146: elements =
new Element[16];
Nit: why 16?

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:241: int mask =
elements.length - 1;
Nit: does it matter if elements.length is not a power of two?

[ahe, 2012-02-13 16:47:51]

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
File compiler/java/com/google/dart/compiler/resolver/ElementMap.java (right):

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:111: if
((elements.length >> 2) * 3 <= size()) {
On 2012/02/13 15:08:56, mmendez wrote:
> Nit: not sure how the  lhs of the size comp was arrived at.

This is 75% fill rate which anecdotal evidence claims is a good threshold for
growing.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:146: elements =
new Element[16];
On 2012/02/13 15:08:56, mmendez wrote:
> Nit: why 16?

If you compile Total and uncomment the println on line 206, it looks reasonable.
If it is 8, grow is called a lot more.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:241: int mask =
elements.length - 1;
On 2012/02/13 15:08:56, mmendez wrote:
> Nit: does it matter if elements.length is not a power of two?

I don't think this code would work well if elements.length is not a power of
two.

[danrubel, 2012-02-14 13:18:25]

Comments addresseda.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
File compiler/java/com/google/dart/compiler/resolver/ElementMap.java (right):

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:39: throw new
RuntimeException();
On 2012/02/13 13:25:56, ahe wrote:
> Nit, in my opinion, it is better to use:
> 
> new AssertionError("ElementHolder should not be accessed outside this class");

Done.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:45: throw new
RuntimeException();
On 2012/02/13 15:08:56, mmendez wrote:
> Nit: I have to agree with Peter on the conversion to an AssertionError on the
> following elements as well.

Done.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:111: if
((elements.length >> 2) * 3 <= size()) {
On 2012/02/13 16:47:51, ahe wrote:
> On 2012/02/13 15:08:56, mmendez wrote:
> > Nit: not sure how the  lhs of the size comp was arrived at.
> 
> This is 75% fill rate which anecdotal evidence claims is a good threshold for
> growing.

Added as comment for clarity.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:206: //
System.err.println("Growing to " + elements.length);
On 2012/02/13 13:25:56, ahe wrote:
> Remove debug code.

Done.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/java/com/go...
compiler/java/com/google/dart/compiler/resolver/ElementMap.java:241: int mask =
elements.length - 1;
On 2012/02/13 16:47:51, ahe wrote:
> On 2012/02/13 15:08:56, mmendez wrote:
> > Nit: does it matter if elements.length is not a power of two?
> 
> I don't think this code would work well if elements.length is not a power of
> two.

Added comment to this effect for clarity.

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/javatests/c...
File compiler/javatests/com/google/dart/compiler/resolver/ElementMapTest.java
(right):

https://chromiumcodereview.appspot.com/9373059/diff/7001/compiler/javatests/c...
compiler/javatests/com/google/dart/compiler/resolver/ElementMapTest.java:4: *
Licensed under the Eclipse Public License v1.0 (the "License"); you may not use
this file except
On 2012/02/13 13:25:56, ahe wrote:
> Wrong license.

Good catch. Fixed.