Avoid scanning huge freelists for large enough free blocks.

Avoid scanning huge freelists for large enough free blocks.

The current old-space allocation implementation performs a
linear search in a single (potentially *very long*) free list for
allocations > 2k.

This CL will change this behavior to limit the number of free list
entries traversed, falling back to allocate a new page if the maximum
number of steps was reached. The new page will be pushed onto the
front of the free list, therefore making new allocations go there
immediately.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

Closes #29588

R=kustermann@google.com

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

[kustermann, 2017-05-10 20:55:01]

Description was changed from

==========
Avoid scanning huge freelists for large enough free blocks.

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

Closes #29588
R=kustermann@google.com
BUG=#29588
==========

to

==========
Avoid scanning huge freelists for large enough free blocks.

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

Closes #29588
R=kustermann@google.com
BUG=#29588
==========

[kustermann, 2017-05-10 20:59:58]

Description was changed from

==========
Avoid scanning huge freelists for large enough free blocks.

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

Closes #29588
R=kustermann@google.com
BUG=#29588
==========

to

==========
Avoid scanning huge freelists for large enough free blocks.

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

Closes #29588
R=kustermann@google.com
==========

[kustermann, 2017-05-10 21:08:32]

Description was changed from

==========
Avoid scanning huge freelists for large enough free blocks.

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

Closes #29588
R=kustermann@google.com
==========

to

==========
Avoid scanning huge freelists for large enough free blocks.

The current old-space allocation implementation performs a
linear search in a single (potentially *very long*) free list for
allocations > 2k.

This CL will change this behavior to limit the number of free list
entries traversed, falling back to allocate a new page if the maximum
number of steps was reached.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)


I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.


Closes #29588
R=kustermann@google.com
==========

[kustermann, 2017-05-10 21:11:48]

Description was changed from

==========
Avoid scanning huge freelists for large enough free blocks.

The current old-space allocation implementation performs a
linear search in a single (potentially *very long*) free list for
allocations > 2k.

This CL will change this behavior to limit the number of free list
entries traversed, falling back to allocate a new page if the maximum
number of steps was reached.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)


I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.


Closes #29588
R=kustermann@google.com
==========

to

==========
Avoid scanning huge freelists for large enough free blocks.

The current old-space allocation implementation performs a
linear search in a single (potentially *very long*) free list for
allocations > 2k.

This CL will change this behavior to limit the number of free list
entries traversed, falling back to allocate a new page if the maximum
number of steps was reached. The new page will be pushed onto the
front of the free list, therefore making new allocations go there
immediately.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

Closes #29588
R=kustermann@google.com
==========

[kustermann, 2017-05-10 21:39:41]

LGTM - Though I still think a rotation might be worth a try -- to ensure we
don't limit ourselves to the first X free list entries!


I've updated the CL description to give a little more context.


Also I've run before/after with/without sweepers, to see the effect on the new
test (out of curiosity):

Before:

Measured via "out/ReleaseX64/dart tests/standalone/fragmentation_test.dart"

        Memory: 2295644 kB  -   0:25.82 real,   26.56 user,     1.90 sys
        Memory: 2286576 kB  -   0:53.08 real,   51.55 user,     5.44 sys
        Memory: 2301664 kB  -   0:35.05 real,   35.22 user,     2.69 sys
        Memory: 2289980 kB  -   0:48.70 real,   48.04 user,     4.16 sys

Measured via "out/ReleaseX64/dart tests/standalone/fragmentation_test.dart"

        Memory: 2286520 kB  -   3:30.48 real,   206.73 user,    7.12 sys
        Memory: 2284608 kB  -   3:11.74 real,   190.00 user,    4.95 sys
        Memory: 2283788 kB  -   3:15.00 real,   193.60 user,    4.69 sys
        Memory: 2282700 kB  -   3:43.65 real,   221.77 user,    5.51 sys

After:

Measured via "out/ReleaseX64/dart tests/standalone/fragmentation_test.dart"
        Memory: 2535516 kB  -   0:07.50 real,   7.82 user,      3.09 sys
        Memory: 2543656 kB  -   0:06.19 real,   6.88 user,      1.93 sys
        Memory: 2540580 kB  -   0:06.72 real,   7.38 user,      2.20 sys
        Memory: 2544640 kB  -   0:06.26 real,   7.10 user,      1.82 sys

Measured via "out/ReleaseX64/dart tests/standalone/fragmentation_test.dart"
        Memory: 2577892 kB  -   0:07.19 real,   7.65 user,      2.53 sys
        Memory: 2574664 kB  -   0:06.92 real,   7.53 user,      2.28 sys
        Memory: 2577984 kB  -   0:06.55 real,   7.27 user,      1.90 sys
        Memory: 2578216 kB  -   0:07.17 real,   7.92 user,      2.42 sys

For this particular fragmentation_test we
  - pay around 11-12% increase in memory
  - gain 6x reduction in CPU (125x reduction in CPU with sweepers disabled)

https://codereview.chromium.org/2872883003/diff/60001/runtime/vm/freelist.cc
File runtime/vm/freelist.cc (right):

https://codereview.chromium.org/2872883003/diff/60001/runtime/vm/freelist.cc#...
runtime/vm/freelist.cc:116: intptr_t tries_left = freelist_health_ + (size >>
kWordSizeLog2);
Maybe add a more elaborate comment explaining what this does, something like:

"""
For each successful free-list search we:
  * increase the search budget by #allocated-words
  * decrease the search budget by #free-list-entries-traversed
which guarantees us to not waste more than around 1 search step per word of
allocation

Furthermore, to guarantee reasonable allocation latency we limit the number of
searches to be at most kMaxFreelistHealth.

After falling back to allocating a new page, we reset the search budget.
"""

https://codereview.chromium.org/2872883003/diff/60001/runtime/vm/freelist.cc#...
runtime/vm/freelist.cc:165: freelist_health_ = Utils::Minimum(tries_left,
kMaxFreelistHealth);
The Utils::Minimum is only for reducing allocation latency, right?

We would still get the guarantee to not waste more than 1 free list search per
allocated word if we just set:

freelist_health_ = tries_left;

https://codereview.chromium.org/2872883003/diff/60001/runtime/vm/freelist.h
File runtime/vm/freelist.h (right):

https://codereview.chromium.org/2872883003/diff/60001/runtime/vm/freelist.h#n...
runtime/vm/freelist.h:101: static const intptr_t kMaxFreelistHealth = 1000;
Consider renaming this to "kInitialFreeListSearchBudget"

https://codereview.chromium.org/2872883003/diff/60001/runtime/vm/freelist.h#n...
runtime/vm/freelist.h:124: intptr_t freelist_health_;
Consider renaming this to "freelist_search_budget_"

https://codereview.chromium.org/2872883003/diff/60001/tests/standalone/fragme...
File tests/standalone/fragmentation_test.dart (right):

https://codereview.chromium.org/2872883003/diff/60001/tests/standalone/fragme...
tests/standalone/fragmentation_test.dart:7: // Normally runs in about 6-7
seconds on an x64 machine, using about 2.5Gbytes
That might be a bit too much memory for arm devices. We might need to skip the
test on arm.

https://codereview.chromium.org/2872883003/diff/60001/tests/standalone/fragme...
tests/standalone/fragmentation_test.dart:16: List<String> arrays = [];
List<String>   ->    final List<List>  ?

[erikcorry, 2017-05-11 07:41:56]

Description was changed from

==========
Avoid scanning huge freelists for large enough free blocks.

The current old-space allocation implementation performs a
linear search in a single (potentially *very long*) free list for
allocations > 2k.

This CL will change this behavior to limit the number of free list
entries traversed, falling back to allocate a new page if the maximum
number of steps was reached. The new page will be pushed onto the
front of the free list, therefore making new allocations go there
immediately.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

Closes #29588
R=kustermann@google.com
==========

to

==========
Avoid scanning huge freelists for large enough free blocks.

The current old-space allocation implementation performs a
linear search in a single (potentially *very long*) free list for
allocations > 2k.

This CL will change this behavior to limit the number of free list
entries traversed, falling back to allocate a new page if the maximum
number of steps was reached. The new page will be pushed onto the
front of the free list, therefore making new allocations go there
immediately.

For the new tests/standalone/fragmentation_test.dart we
      - pay around 11-12% increase in memory
      - to gain a 6x speedup (125x speedup with sweepers disabled)

I tried a much more complicated version that had power-of-two
buckets for freelist items > 2k.  This turned out to regress
dart2js and splay for reasons that I could not determine. This
version is much simpler and fixes the issue as observed in the
bug.

Closes #29588

R=kustermann@google.com

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

[erikcorry, 2017-05-11 07:41:57]

Committed patchset #5 (id:80001) manually as
37b320d38133344a69555377155e0e390b434d9c (presubmit successful).