Bug 161581 - Make MarkedBlock state tracking support overlapped allocation and marking state
Summary: Make MarkedBlock state tracking support overlapped allocation and marking state
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on: 160125 161847 161869 161933
Blocks: 162121 162122 162296 149432
  Show dependency treegraph
 
Reported: 2016-09-04 18:59 PDT by Filip Pizlo
Modified: 2016-09-28 17:09 PDT (History)
14 users (show)

See Also:


Attachments
it begins (20.64 KB, patch)
2016-09-10 20:53 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it begins for real (14.24 KB, patch)
2016-09-12 09:59 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
a bit more (18.87 KB, patch)
2016-09-12 10:26 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
I think that I know how to allocate (20.40 KB, patch)
2016-09-12 11:48 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
sweeping is starting to make sense! (29.58 KB, patch)
2016-09-12 12:34 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
I think that MarkedBlock looks good (46.94 KB, patch)
2016-09-13 09:30 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
close to done (58.78 KB, patch)
2016-09-13 10:57 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
holy cow it might be done (60.76 KB, patch)
2016-09-13 11:12 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more things (66.46 KB, patch)
2016-09-13 12:22 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
starting to compile (78.49 KB, patch)
2016-09-13 12:36 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more compiling (91.97 KB, patch)
2016-09-13 17:07 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it compiles! (94.39 KB, patch)
2016-09-13 18:10 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
fixing it (117.40 KB, patch)
2016-09-14 14:06 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it just ran a program (120.15 KB, patch)
2016-09-14 14:50 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it ran splay (120.71 KB, patch)
2016-09-15 11:19 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it passed testapi in debug mode (123.36 KB, patch)
2016-09-16 10:13 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more (136.00 KB, patch)
2016-09-16 11:09 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
fixed the earley regression, got what might be a splay progression! (139.26 KB, patch)
2016-09-17 11:26 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
looking quite nice indeed (140.55 KB, patch)
2016-09-17 12:47 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it should build (157.05 KB, patch)
2016-09-17 15:41 PDT, Filip Pizlo
buildbot: commit-queue-
Details | Formatted Diff | Diff
performance (84.12 KB, text/plain)
2016-09-17 15:43 PDT, Filip Pizlo
no flags Details
Archive of layout-test-results from ews101 for mac-yosemite (388.44 KB, application/zip)
2016-09-17 16:35 PDT, Build Bot
no flags Details
Archive of layout-test-results from ews107 for mac-yosemite-wk2 (420.84 KB, application/zip)
2016-09-17 16:39 PDT, Build Bot
no flags Details
Archive of layout-test-results from ews121 for ios-simulator-elcapitan-wk2 (517.52 KB, application/zip)
2016-09-17 16:47 PDT, Build Bot
no flags Details
fixed the crashes (157.30 KB, patch)
2016-09-18 14:21 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more fixes (157.70 KB, patch)
2016-09-18 14:49 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
fixed looking for empty blocks (159.32 KB, patch)
2016-09-19 08:56 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (168.92 KB, patch)
2016-09-19 10:48 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
performance (83.86 KB, text/plain)
2016-09-19 10:49 PDT, Filip Pizlo
no flags Details
more (169.43 KB, patch)
2016-09-19 17:32 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
performance (83.56 KB, text/plain)
2016-09-19 20:45 PDT, Filip Pizlo
no flags Details
more (170.03 KB, patch)
2016-09-19 20:51 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (170.48 KB, patch)
2016-09-20 09:55 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (170.84 KB, patch)
2016-09-20 10:03 PDT, Filip Pizlo
ggaren: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2016-09-04 18:59:12 PDT
For example, each MarkedAllocator could have a Vector<std::unique_ptr<MarkedBlock::Handle>> m_blocks.  Then it could have the following sets represented by bitvectors indexed by the handle's index in m_blocks:
- m_canAllocate, which contains all non-empty non-retired blocks.
- m_snapshot, which contains all blocks in the block snapshot.
- m_empty, which contains all empty blocks.
- m_eden, which contains all blocks that have new objects.
- m_allocated, which contains all blocks that have been completely filled up.

If we do this, then we can get rid of block state, the m_blocksWithNewObjects vector, and the block snapshot vector.  The following operations become cheap operations over bitvectors:

- All of the flips:
    - Full GC flip: m_empty = 0, m_canAllocate = 0, m_allocated = 0.
    - Eden GC flip: m_canAllocate |= m_eden, m_allocated = 0.
    - Full GC snapshot: m_snapshot = 1.
    - Eden GC snapshot: m_snapshot |= m_eden.

- All of the iterations:
    - Allocate: scan m_canAllocate, then scan m_empty, then scan m_empty of other size classes (so we can rebalance the heap cheaply!).
    - Incremental sweep: scan (m_snapshot & ~m_allocated).

We could allocate WeakSets outside MarkedBlocks, and have them also be tracked in their own Vector<std::unique_ptr<WeakSet>>, owned by MarkedSpace, and also track various sets of them using bitvectors.

This ought to reduce any per-block overheads by so much that they should appear invisible.  We did lose some perf by going from 64KB to 16KB even with many optimizations, so this may be enough to bring us back to where we were before.  For example, consider what happens when we are using 200MB.  That means having to sometimes consider about 13000 blocks, which the current code does by looping over that many things, and those things are unlikely to reside on the same cache line.  But with bitvectors, the typical flipping operation would only have to touch 13000 / 8 = 1625 bytes of contiguous bits.  Using 64-bit operations, that means only having to loop over about 200 words.  That means that the previous flipping operations that would take about 13000 iterations just to touch each block will now only require 200 iterations - as in we actually have a chance of speeding up those operations by 65x.
Comment 1 Filip Pizlo 2016-09-04 23:27:16 PDT
Another benefit of this approach is that on-the-fly retirement during marking will now be a CAS to clear the can-allocate bit rather than some crazy locking.

Maybe we can even make the clearing of the can-allocate bit racy.  In the worst case, we would forget that we had retired some blocks.  That's not the end of the world.
Comment 2 Filip Pizlo 2016-09-04 23:29:10 PDT
(In reply to comment #0)
> require 200 iterations - as in we actually have a chance of speeding up
> those operations by 65x.

It's actually speeding up by exactly 64x.
Comment 3 Filip Pizlo 2016-09-10 20:53:08 PDT
Created attachment 288519 [details]
it begins

I'm starting out by creating a super-flexible bitvector framework.  What I have now will make FastBitVector capable of the following amazing stuff:

FastBitVector a;
FastBitVector b;
FastBitVector c;
... // do things to populate a, b, c
auto intersection = a.bitAnd(b); // Returns a view of a & b that is computed on the fly.
intersection.forEachSetBit([&] (size_t i) { print(i); }); // Super efficiently walks the words of a & b.
a.bitAnd(b.bitOr(c).bitNot()).forEachClearBit([&] (size_t i) { print (i); });
Comment 4 Filip Pizlo 2016-09-12 09:59:10 PDT
Created attachment 288574 [details]
it begins for real

Starting to turn the MarkedAllocator into a thingy that does bitvectors
Comment 5 Filip Pizlo 2016-09-12 10:26:29 PDT
Created attachment 288578 [details]
a bit more
Comment 6 Filip Pizlo 2016-09-12 11:48:57 PDT
Created attachment 288595 [details]
I think that I know how to allocate
Comment 7 Filip Pizlo 2016-09-12 12:34:52 PDT
Created attachment 288602 [details]
sweeping is starting to make sense!
Comment 8 Filip Pizlo 2016-09-13 09:30:59 PDT
Created attachment 288690 [details]
I think that MarkedBlock looks good
Comment 9 Filip Pizlo 2016-09-13 10:57:36 PDT
Created attachment 288699 [details]
close to done
Comment 10 Filip Pizlo 2016-09-13 11:12:10 PDT
Created attachment 288702 [details]
holy cow it might be done

This patch turned out so wonderful.  I think I've axed all of the block scans in the GC!

And look what we're left with.  For example, setting up the block states after marking:

    m_empty = m_live & ~m_markingNotEmpty;
    m_canAllocate = m_live & m_markingNotEmpty & ~m_markingRetired;

Or snapshotting in an eden collection:

    m_snapshot |= m_eden;

It's like garbage poetry.
Comment 11 Filip Pizlo 2016-09-13 12:22:51 PDT
Created attachment 288714 [details]
more things

I made a few changes after I thought through how a collection cycle really works.

I added a big comment that illustrates how the various bits work.
Comment 12 Filip Pizlo 2016-09-13 12:36:30 PDT
Created attachment 288716 [details]
starting to compile
Comment 13 Filip Pizlo 2016-09-13 12:41:22 PDT
I changed the title of the bug to reflect the most significant end goal that this change achieves.

Even if it was perf-neutral, we'd still take it since unlike trunk, this would take us a big step closer to allowing allocation to happen during marking.
Comment 14 Filip Pizlo 2016-09-13 17:07:03 PDT
Created attachment 288750 [details]
more compiling
Comment 15 Filip Pizlo 2016-09-13 18:10:08 PDT
Created attachment 288757 [details]
it compiles!
Comment 16 Filip Pizlo 2016-09-14 14:06:11 PDT
Created attachment 288855 [details]
fixing it
Comment 17 Filip Pizlo 2016-09-14 14:50:20 PDT
Created attachment 288866 [details]
it just ran a program
Comment 18 Filip Pizlo 2016-09-15 11:19:20 PDT
Created attachment 288976 [details]
it ran splay
Comment 19 Filip Pizlo 2016-09-16 10:13:47 PDT
Created attachment 289068 [details]
it passed testapi in debug mode
Comment 20 Filip Pizlo 2016-09-16 11:09:44 PDT
Created attachment 289080 [details]
more

It now has ChangeLogs.
Comment 21 Filip Pizlo 2016-09-16 11:34:00 PDT
Wow, it passes JSC tests!  Let's see what EWS has to say.
Comment 22 WebKit Commit Bot 2016-09-16 11:35:10 PDT
Attachment 289080 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:244:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:254:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:141:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Total errors found: 5 in 37 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 23 Filip Pizlo 2016-09-16 19:08:37 PDT
Something is wrong:

   earley                                            0.23629+-0.00409    !     0.28332+-0.00153       ! definitely 1.1990x slower

I'm investigating.
Comment 24 Filip Pizlo 2016-09-17 11:22:47 PDT
(In reply to comment #23)
> Something is wrong:
> 
>    earley                                            0.23629+-0.00409    !  
> 0.28332+-0.00153       ! definitely 1.1990x slower
> 
> I'm investigating.

Ha!  Found two issues:

1) When we moved a MarkedBlock from one allocator to another, we weren't fixing up its cellSize and attributes.  I have no idea why this didn't cause a ton of test failures.  I fixed it but now I'm going to have to write some kind of test for it.  Though this wasn't the reason for the perf regression - I just found it while investigating.

2) The reason for the regression was that we were first allocating out of non-empty blocks and then allocating out of empty blocks. In practice this meant that we would spend more time overall allocating out of non-empty blocks, which meant doing more popping and less bumping.  It also seemed to create more fragmentation overall.  This was so easy to fix.  I just switched:

        m_allocationCursor = m_canAllocate.findBit(m_allocationCursor, true);

to this:

        m_allocationCursor = (m_canAllocate | m_empty).findBit(m_allocationCursor, true);

and voila, no regression on earley.

Still running other tests.
Comment 25 Filip Pizlo 2016-09-17 11:26:04 PDT
Created attachment 289175 [details]
fixed the earley regression, got what might be a splay progression!

Replaced the best-fit search (canAllocate first, empty second) with a first-fit search (scan both canAllocate and empty in tandem).  This seems to work a lot better.

Also fixed a bug where we weren't properly reassigning blocks between allocators.

Also made lookForEmptyBlocksInOtherAllocators into an Option.  It's great for debugging, since this feature is 100% optional for correctness and it's a super likely source of bugs.
Comment 26 Filip Pizlo 2016-09-17 12:47:36 PDT
Created attachment 289177 [details]
looking quite nice indeed
Comment 27 Filip Pizlo 2016-09-17 12:48:54 PDT
I messed with how WeakInlines.h gets included because it was causing a nasty header cycle, so this is going to require more header rewiring in the DOM.  I'm going to do that next.
Comment 28 Filip Pizlo 2016-09-17 15:41:01 PDT
Created attachment 289178 [details]
it should build
Comment 29 WebKit Commit Bot 2016-09-17 15:43:17 PDT
Attachment 289178 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:244:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:254:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 45 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 30 Filip Pizlo 2016-09-17 15:43:43 PDT
Created attachment 289179 [details]
performance

Looks to be neutral on things that matter.

I'll run in-browser benchmarks next.
Comment 31 Build Bot 2016-09-17 16:35:16 PDT
Comment on attachment 289178 [details]
it should build

Attachment 289178 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.webkit.org/results/2096606

Number of test failures exceeded the failure limit.
Comment 32 Build Bot 2016-09-17 16:35:22 PDT
Created attachment 289180 [details]
Archive of layout-test-results from ews101 for mac-yosemite

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews101  Port: mac-yosemite  Platform: Mac OS X 10.10.5
Comment 33 Build Bot 2016-09-17 16:39:53 PDT
Comment on attachment 289178 [details]
it should build

Attachment 289178 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.webkit.org/results/2096616

Number of test failures exceeded the failure limit.
Comment 34 Build Bot 2016-09-17 16:39:58 PDT
Created attachment 289181 [details]
Archive of layout-test-results from ews107 for mac-yosemite-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews107  Port: mac-yosemite-wk2  Platform: Mac OS X 10.10.5
Comment 35 Filip Pizlo 2016-09-17 16:46:05 PDT
Wow. I bet I messed up the incremental sweeper. I'll investigate later.
Comment 36 Build Bot 2016-09-17 16:47:20 PDT
Comment on attachment 289178 [details]
it should build

Attachment 289178 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: http://webkit-queues.webkit.org/results/2096618

Number of test failures exceeded the failure limit.
Comment 37 Build Bot 2016-09-17 16:47:24 PDT
Created attachment 289182 [details]
Archive of layout-test-results from ews121 for ios-simulator-elcapitan-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews121  Port: ios-simulator-elcapitan-wk2  Platform: Mac OS X 10.11.6
Comment 38 Filip Pizlo 2016-09-18 14:21:06 PDT
Created attachment 289211 [details]
fixed the crashes

I was forgetting to set m_needsDestruction correctly.
Comment 39 WebKit Commit Bot 2016-09-18 14:23:48 PDT
Attachment 289211 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 45 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 40 Filip Pizlo 2016-09-18 14:49:25 PDT
Created attachment 289212 [details]
more fixes

It passes tests for me.  I think it just needs some #include love to build on all ports.
Comment 41 WebKit Commit Bot 2016-09-18 14:51:05 PDT
Attachment 289212 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 46 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 42 Filip Pizlo 2016-09-19 08:56:21 PDT
Created attachment 289232 [details]
fixed looking for empty blocks

The feature to look for empty blocks in other allocators didn't actually work, because MarkedSpace::m_allocatorForEmptyAllocation was stuck null.  Fixing that without doing anything else causes a splay regression and divergent memory usage (1GB after a couple seconds instead of steady at 200MB) because we didn't check for the need to collect until we failed in tryAllocateWithoutCollecting().  So, this also changes allocateSlowCaseImpl() to always check for the need to collect before doing tryAllocateWithoutCollecting().
Comment 43 WebKit Commit Bot 2016-09-19 08:58:20 PDT
Attachment 289232 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 47 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 44 Filip Pizlo 2016-09-19 10:48:28 PDT
Created attachment 289238 [details]
the patch

Still running experiments, but I think it's ready for review.

Note that some benchmarks regress when I enable searching for empty blocks, while others progress.  If I disable it, then this is perf-neutral.  That part of this patch is not on the critical path for concurrent GC.  I'll land with it either turned on or off depending on what all of the benchmarks say.
Comment 45 Filip Pizlo 2016-09-19 10:49:40 PDT
Created attachment 289239 [details]
performance

Short programs that allocate lots of strings seem not to like searching for empty blocks in other allocators or the change to trigger GC as soon as the eden size is consumed.  Larger programs don't seem to mind this.  I'm going to test in-browser next to get a definitive answer.
Comment 46 WebKit Commit Bot 2016-09-19 10:49:41 PDT
Attachment 289238 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 47 Filip Pizlo 2016-09-19 17:32:37 PDT
Created attachment 289291 [details]
more

I've made some changes to deal with a PLT regression.  I think I've got it under control now.  Now I'll test it.
Comment 48 WebKit Commit Bot 2016-09-19 17:34:17 PDT
Attachment 289291 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 49 Filip Pizlo 2016-09-19 20:45:17 PDT
Created attachment 289306 [details]
performance

neutral on everything except Microbenchmarks.
Comment 50 Filip Pizlo 2016-09-19 20:51:00 PDT
Created attachment 289307 [details]
more
Comment 51 WebKit Commit Bot 2016-09-19 20:54:02 PDT
Attachment 289307 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 52 Filip Pizlo 2016-09-20 09:55:46 PDT
Created attachment 289364 [details]
the patch
Comment 53 WebKit Commit Bot 2016-09-20 09:57:48 PDT
Attachment 289364 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 54 Filip Pizlo 2016-09-20 10:03:46 PDT
Created attachment 289367 [details]
the patch
Comment 55 WebKit Commit Bot 2016-09-20 10:05:52 PDT
Attachment 289367 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:241:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedSpace.cpp:251:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:83:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:85:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/runtime/WeakGCMap.h:96:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:192:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/SlotVisitor.cpp:297:  Should have a space between // and comment  [whitespace/comments] [4]
ERROR: Source/JavaScriptCore/heap/MarkedAllocator.h:156:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/JavaScriptCore/Scripts/builtins/builtins_generate_internals_wrapper_header.py:65:  whitespace before ']'  [pep8/E202] [5]
Total errors found: 9 in 50 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 56 Geoffrey Garen 2016-09-20 11:07:24 PDT
Comment on attachment 289367 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=289367&action=review

r=me

> Source/JavaScriptCore/ChangeLog:81
> +        Browser benchmarks:

Did the rebalancing feature produce a high watermark memory reduction in the end on v8-splay or v8-earley?

> Source/JavaScriptCore/heap/MarkedAllocator.cpp:349
> +        // FIXME: Make this work again.
> +        // https://bugs.webkit.org/show_bug.cgi?id=162296

Should probably RELEASE_ASSERT here so someone doesn't fall into a trap.

> Source/JavaScriptCore/heap/MarkedAllocator.h:84
> +// - by default we have clear markingNotEmpty/markingRetired bits.

cleared?

> Source/JavaScriptCore/heap/MarkedAllocator.h:134
> +// After this, we just need to answer the question: what does an object allocated during eden GC
> +// look like to the GC?
> +//
> +// I've come up with two compelling answers.

I think the paragraphs below belong better in a comment on a concurrent GC bugzilla or in the ChangeLog. For the time being, they don't describe the behavior of the code.

> Source/JavaScriptCore/heap/MarkedAllocator.h:145
> +// we'd make the object is eligible for freeing at the next eden GC. There's a bunch of things we

is eligible

> Source/JavaScriptCore/heap/MarkedSpace.cpp:241
> +        //dataLog("Allocated ", RawPointer(result), "\n");

Revert.

> Source/JavaScriptCore/heap/MarkedSpace.cpp:251
> +        //dataLog("Try-allocated ", RawPointer(result), "\n");

Revert.

> Source/JavaScriptCore/heap/SlotVisitor.cpp:297
> +    //dataLog("Visiting ", RawPointer(cell), "\n");

Revert.
Comment 57 Filip Pizlo 2016-09-20 11:11:51 PDT
(In reply to comment #56)
> Comment on attachment 289367 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=289367&action=review
> 
> r=me
> 
> > Source/JavaScriptCore/ChangeLog:81
> > +        Browser benchmarks:
> 
> Did the rebalancing feature produce a high watermark memory reduction in the
> end on v8-splay or v8-earley?

It did.  It reduces the heap capacity in splay from ~200KB to ~180KB.  I'll note it in the changelog.

> 
> > Source/JavaScriptCore/heap/MarkedAllocator.cpp:349
> > +        // FIXME: Make this work again.
> > +        // https://bugs.webkit.org/show_bug.cgi?id=162296
> 
> Should probably RELEASE_ASSERT here so someone doesn't fall into a trap.

Good idea.

> 
> > Source/JavaScriptCore/heap/MarkedAllocator.h:84
> > +// - by default we have clear markingNotEmpty/markingRetired bits.
> 
> cleared?

Yup.

> 
> > Source/JavaScriptCore/heap/MarkedAllocator.h:134
> > +// After this, we just need to answer the question: what does an object allocated during eden GC
> > +// look like to the GC?
> > +//
> > +// I've come up with two compelling answers.
> 
> I think the paragraphs below belong better in a comment on a concurrent GC
> bugzilla or in the ChangeLog. For the time being, they don't describe the
> behavior of the code.

Removed.

> 
> > Source/JavaScriptCore/heap/MarkedAllocator.h:145
> > +// we'd make the object is eligible for freeing at the next eden GC. There's a bunch of things we
> 
> is eligible
> 
> > Source/JavaScriptCore/heap/MarkedSpace.cpp:241
> > +        //dataLog("Allocated ", RawPointer(result), "\n");
> 
> Revert.
> 
> > Source/JavaScriptCore/heap/MarkedSpace.cpp:251
> > +        //dataLog("Try-allocated ", RawPointer(result), "\n");
> 
> Revert.
> 
> > Source/JavaScriptCore/heap/SlotVisitor.cpp:297
> > +    //dataLog("Visiting ", RawPointer(cell), "\n");
> 
> Revert.

I removed these.
Comment 58 Filip Pizlo 2016-09-20 11:14:53 PDT
Landed in http://trac.webkit.org/changeset/206154
Comment 59 Saam Barati 2016-09-28 17:07:40 PDT
Comment on attachment 289367 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=289367&action=review

> Source/JavaScriptCore/heap/Heap.cpp:1079
> +    if (false) {

Is it worth putting this under logGC?
Comment 60 Saam Barati 2016-09-28 17:08:25 PDT
This looks like a 3-4% octane progression on macs.
Comment 61 Saam Barati 2016-09-28 17:09:10 PDT
(In reply to comment #60)
> This looks like a 3-4% octane progression on macs.

And on some iOS devices as well.