Grow various arrays geometrically rather than linearly.

Grow various arrays geometrically rather than linearly.

This doesn't address any concrete issue and is expected to be
performance neutral except in extreme cases where it will be
better. It's merely a fix for some places where we would be
quadratic instead of amortized linear.
R=regis@google.com
BUG=

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

[regis, 2017-04-24 16:08:07]

I would be cautious with changing the linear growth if there are no issues. A
factor 3 or even 5 can waste memory quickly. We picked linear growth to save
memory.

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

https://codereview.chromium.org/2841533002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:4524: const intptr_t new_length = list_len + 4 + (list_len
>> 2);
Why a factor of 5? How many canonical numbers are you seeing inserted in this
array?

https://codereview.chromium.org/2841533002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:5091: // Grow the instantiations array by about 50%, but at
least by 1.
50%? Your change looks rather like a factor 2 to me, i.e. 100%. Also, do you
really need the division? Previous measurements showed a very limited number of
instantiations. Does this change with fasta?

https://codereview.chromium.org/2841533002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10875: capacity = capacity + kImportsCapacityIncrement +
(capacity >> 2);
Factor 3?

https://codereview.chromium.org/2841533002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:11435: const intptr_t new_length = length + kIncrementSize
+ (length >> 2);
ditto

[regis, 2017-04-24 17:18:14]

These are right shifts, not left shifts. So the risk of wasting memory is not
that bad.
This will teach me not to review code when starting the week half awake and
grumpy...

lgtm

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

https://codereview.chromium.org/2841533002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:4524: const intptr_t new_length = list_len + 4 + (list_len
>> 2);
On 2017/04/24 16:08:07, regis wrote:
> Why a factor of 5? How many canonical numbers are you seeing inserted in this
> array?

As Martin pointed out, this is a right shift, so %25 increase.

https://codereview.chromium.org/2841533002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:5091: // Grow the instantiations array by about 50%, but at
least by 1.
On 2017/04/24 16:08:07, regis wrote:
> 50%? Your change looks rather like a factor 2 to me, i.e. 100%. Also, do you
> really need the division? Previous measurements showed a very limited number
of
> instantiations. Does this change with fasta?

Never mind. Right shift again.

https://codereview.chromium.org/2841533002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:10875: capacity = capacity + kImportsCapacityIncrement +
(capacity >> 2);
On 2017/04/24 16:08:07, regis wrote:
> Factor 3?

No.

[Vyacheslav Egorov (Google), 2017-04-24 18:37:58]

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

[Vyacheslav Egorov (Google), 2017-04-24 18:37:58]

Before landing this it would be nice to check how it affects some big AOT
snapshot, e.g. Flutter Gallery, if only to satiate our curiosity on the
potential impact of these changes. 

Fields like RawClass::constants_ go into the snapshot - so any "air" there turns
into air in the snapshot.

[siva, 2017-04-24 23:45:55]

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

[siva, 2017-04-24 23:45:55]

when you say performance neutral do you mean runtime performance or both runtime
performance and Dart heap footprint size?

Also could you elaborate on the specific case you expect the behavior to be
better.

[erikcorry, 2017-04-25 15:23:01]

On 2017/04/24 18:37:58, Vyacheslav Egorov (Google) wrote:
> Before landing this it would be nice to check how it affects some big AOT
> snapshot, e.g. Flutter Gallery, if only to satiate our curiosity on the
> potential impact of these changes. 
> 
> Fields like RawClass::constants_ go into the snapshot - so any "air" there
turns
> into air in the snapshot.

I tried this and there was no change in the sizes.  Before and after:

erikcorry@bbc:~/flutter/examples/flutter_gallery$ ls -al aot-unpatched/
total 9208
drwxr-x---  2 erikcorry eng    4096 Apr 25 15:56 .
drwxr-x--- 10 erikcorry eng    4096 Apr 25 16:51 ..
-rw-r-----  1 erikcorry eng      99 Apr 25 16:49 gen_snapshot.d
-rw-r-----  1 erikcorry eng 4304432 Apr 25 16:49 isolate_snapshot_data
-rw-r-----  1 erikcorry eng 5019952 Apr 25 16:49 isolate_snapshot_instr
-rw-r-----  1 erikcorry eng   51579 Apr 25 16:49 snapshot.d
-rw-r-----  1 erikcorry eng   21824 Apr 25 16:49 vm_snapshot_data
-rw-r-----  1 erikcorry eng    9984 Apr 25 16:49 vm_snapshot_instr
erikcorry@bbc:~/flutter/examples/flutter_gallery$ ls -al build/aot
total 9208
drwxr-x--- 2 erikcorry eng    4096 Apr 25 16:51 .
drwxr-x--- 3 erikcorry eng    4096 Apr 25 16:51 ..
-rw-r----- 1 erikcorry eng      99 Apr 25 17:19 gen_snapshot.d
-rw-r----- 1 erikcorry eng 4304432 Apr 25 17:19 isolate_snapshot_data
-rw-r----- 1 erikcorry eng 5019952 Apr 25 17:19 isolate_snapshot_instr
-rw-r----- 1 erikcorry eng   51579 Apr 25 17:19 snapshot.d
-rw-r----- 1 erikcorry eng   21824 Apr 25 17:19 vm_snapshot_data
-rw-r----- 1 erikcorry eng    9984 Apr 25 17:19 vm_snapshot_instr

[erikcorry, 2017-04-25 15:34:33]

On 2017/04/24 23:45:55, siva wrote:
> when you say performance neutral do you mean runtime performance or both
runtime
> performance and Dart heap footprint size?

I meant runtime performance.

For the Dart heap I would expect mostly unchanged, but if any of these arrays
are large then I would expect an asymptotically smaller amount of allocation and
a larger amount of live data (by a constant factor).  This is the normal result
of growing by a factor which is the standard way to grow arrays, as I am sure
you know.

> Also could you elaborate on the specific case you expect the behavior to be
> better.

When the arrays are large.  I already said in the description that there is no
concrete scenario that I have seen.  It is my opinion that it is worthwhile to
replace quadratic algorithms with linear ones rather than wait for it to become
an issue.  My experience with V8 is that it always eventually becomes an issue.

[erikcorry, 2017-04-25 15:45:08]

Description was changed from

==========
Grow various arrays geometrically rather than linearly.

This doesn't address any concrete issue and is expected to be
performance neutral except in extreme cases where it will be
better. It's merely a fix for some places where we would be
quadratic instead of amortized linear.
R=regis@google.com
BUG=
==========

to

==========
Grow various arrays geometrically rather than linearly.

This doesn't address any concrete issue and is expected to be
performance neutral except in extreme cases where it will be
better. It's merely a fix for some places where we would be
quadratic instead of amortized linear.
R=regis@google.com
BUG=

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

[erikcorry, 2017-04-25 15:45:09]

Committed patchset #1 (id:1) manually as
f5c33bfc46ed1cb04869037a720a59779ce64107 (presubmit successful).