Add a much simplified set implementation designed to waste little memory for small sets.

Add a much simplified set implementation designed to waste little memory for small sets.

Use the new set (called setlet) in the type inferrer. I'd be happy to get rid of this
specialized implementation if we ever get a core library implementation that is equally
small and fast, but for now this CL reduces the working set with 15% when compiling
dart2js.

R=ahe@google.com, lrn@google.com, lry@google.com
BUG=

Committed: https://code.google.com/p/dart/source/detail?r=28784

[ahe, 2013-10-16 13:57:07]

LGTM

https://codereview.chromium.org/27510002/diff/1/sdk/lib/_internal/compiler/im...
File sdk/lib/_internal/compiler/implementation/inferrer/container_tracer.dart
(right):

https://codereview.chromium.org/27510002/diff/1/sdk/lib/_internal/compiler/im...
sdk/lib/_internal/compiler/implementation/inferrer/container_tracer.dart:152:
container.elementType.assignments.forEach((each) {
Perhaps you want a "addTo" method on Setlet?

https://codereview.chromium.org/27510002/diff/1/sdk/lib/_internal/compiler/im...
File sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart
(right):

https://codereview.chromium.org/27510002/diff/1/sdk/lib/_internal/compiler/im...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:756:
set.forEach((each) { result.add(each); });
Insert newline after {.

[Lasse Reichstein Nielsen, 2013-10-16 14:53:54]

just comments.

https://codereview.chromium.org/27510002/diff/6001/sdk/lib/_internal/compiler...
File sdk/lib/_internal/compiler/implementation/util/setlet.dart (right):

https://codereview.chromium.org/27510002/diff/6001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/util/setlet.dart:35: return (_MARKER
== _contents) ? 0 : 1;
Maybe use identical (unless you know the compiler always inlines the equality).

https://codereview.chromium.org/27510002/diff/6001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/util/setlet.dart:119: // after that
will preserve the insertion order.
Is this complexity warranted?
Maybe just keep holes in the list when you remove, and when the list reaches
capacity, go to a set, no matter how may holes are in there. Or just collapse
the list once when that happens, instead of doing it on every add.

Alternatively, always compact immediately on a remove. That would make add
always fast, and remove slower, but any intermixing of them would probably be
about the same.

https://codereview.chromium.org/27510002/diff/6001/sdk/lib/_internal/compiler...
sdk/lib/_internal/compiler/implementation/util/setlet.dart:203: while
(_remaining > 0) {
You may want concurrent modification guards here, and elsewhere too.

[kasperl, 2013-10-17 06:31:22]

Committed patchset #2 manually as r28784 (presubmit successful).