Avoiding creating strings for canonicalization

Avoiding creating strings for canonicalization

Do a hash table for tripples:
(list of bytes, start, end) --> canonicalized string

R=ahe@google.com

Committed: https://github.com/dart-lang/sdk/commit/58ca47d58ae846dfc9a71d59a03ecafb5cd31537

[Dmitry Olshansky, 2017-02-14 13:21:41]

dmitryolsh@google.com changed reviewers:
+ ahe@google.com

[ahe, 2017-02-14 13:52:46]

lgtm

Thank you!

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart (right):

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:1: // Copyright (c) 2012,
the Dart project authors.  Please see the AUTHORS file
That comment is so last last last last last year ;-)

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:9: class _Node {
No need for privacy on classes.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:10: var data; // String
or List<int>
When I can't give a precise type, I usually do this:

var /* String or List<int> */ data;

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:11: int start, end;
Could you split this declaration in two?

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:17: class
HashCanonicalizer {
I suggest you rename this to StringCanonicalizer.

A small amount of documentation would be nice, for example, what you put in the
CL description.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:18: // Mask away top bits
to keep hash calculation within 32-bit SMI range.
This is a documentation comment, it should have three slashes.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:21: int _size; // Linear
size of hash table.
This is also a documentation comment, so it should be formatted like this:

/// Linear size of hash table.
int _size;

Applies to two more below.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:21: int _size; // Linear
size of hash table.
No need for privacy.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:26: _count = 0;
Move the field initializers to the field declarations and remove the
constructor.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:36: s =
UTF8.decoder.convert(data, start, end);
You need to change this to:

new Utf8Decoder(allowMalformed: true).convert(data, start, end)

Otherwise this may cause compiler crashes on malformed input.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:57: _rehash() {
No need for privacy.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/scanner/token.dart (right):

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/token.dart:265: static String
canonicalizedString(String s, int start, int end, bool canonicalize) {
Long line.

[Dmitry Olshansky, 2017-02-14 14:31:09]

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart (right):

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:1: // Copyright (c) 2012,
the Dart project authors.  Please see the AUTHORS file
On 2017/02/14 13:52:46, ahe wrote:
> That comment is so last last last last last year ;-)

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:9: class _Node {
On 2017/02/14 13:52:46, ahe wrote:
> No need for privacy on classes.

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:10: var data; // String
or List<int>
On 2017/02/14 13:52:46, ahe wrote:
> When I can't give a precise type, I usually do this:
> 
> var /* String or List<int> */ data;

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:11: int start, end;
On 2017/02/14 13:52:45, ahe wrote:
> Could you split this declaration in two?

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:17: class
HashCanonicalizer {
On 2017/02/14 13:52:45, ahe wrote:
> I suggest you rename this to StringCanonicalizer.
> 
> A small amount of documentation would be nice, for example, what you put in
the
> CL description.

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:18: // Mask away top bits
to keep hash calculation within 32-bit SMI range.
On 2017/02/14 13:52:46, ahe wrote:
> This is a documentation comment, it should have three slashes.

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:21: int _size; // Linear
size of hash table.
On 2017/02/14 13:52:46, ahe wrote:
> No need for privacy.

On the contrary I believe that direct access to _size from the outside is
dangerous as it could easily destroy the fragile invariant that _nodes.length ==
size and size is power of 2. Also size is not informative to the outside, it
doesn't tell the actual count of items.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:26: _count = 0;
On 2017/02/14 13:52:46, ahe wrote:
> Move the field initializers to the field declarations and remove the
> constructor.

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:36: s =
UTF8.decoder.convert(data, start, end);
On 2017/02/14 13:52:46, ahe wrote:
> You need to change this to:
> 
> new Utf8Decoder(allowMalformed: true).convert(data, start, end)
> 
> Otherwise this may cause compiler crashes on malformed input.

Done.

https://codereview.chromium.org/2696803003/diff/40001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:57: _rehash() {
On 2017/02/14 13:52:46, ahe wrote:
> No need for privacy.

Done.

[ahe, 2017-02-14 14:35:04]

lgtm

https://codereview.chromium.org/2696803003/diff/80001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart (right):

https://codereview.chromium.org/2696803003/diff/80001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart:21: * Using tripples
avoids allocating string slices before checking if they
triples (one p).

https://codereview.chromium.org/2696803003/diff/80001/pkg/front_end/lib/src/f...
File pkg/front_end/lib/src/fasta/scanner/token.dart (right):

https://codereview.chromium.org/2696803003/diff/80001/pkg/front_end/lib/src/f...
pkg/front_end/lib/src/fasta/scanner/token.dart:265: static String
canonicalizedString(String s, int start, int end, bool canonicalize) {
Long line.

[Dmitry Olshansky, 2017-02-14 14:44:45]

Description was changed from

==========
Avoiding creating strings for canonicalization

Do a hash table for tripples:
(list of bytes, start, end) --> canonicalized string
==========

to

==========
Avoiding creating strings for canonicalization

Do a hash table for tripples:
(list of bytes, start, end) --> canonicalized string

R=ahe@google.com

Committed:
https://github.com/dart-lang/sdk/commit/58ca47d58ae846dfc9a71d59a03ecafb5cd31537
==========

[Dmitry Olshansky, 2017-02-14 14:44:46]

Committed patchset #6 (id:100001) manually as
58ca47d58ae846dfc9a71d59a03ecafb5cd31537 (presubmit successful).