Bug 165963

Created attachment 297409 [details] a little something like this Work in progress.

Comment on attachment 297409 [details] a little something like this View in context: https://bugs.webkit.org/attachment.cgi?id=297409&action=review > Source/JavaScriptCore/heap/SpaceTimeScheduler.cpp:22 > - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE > + * (INCLUDING NEGfLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE Oops. Reverted.

Created attachment 297442 [details] a bit more

Created attachment 297678 [details] so fun

Created attachment 297865 [details] more

Created attachment 297909 [details] the patch

Attachment 297909 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/heap/MarkingConstraint.cpp:38: Code inside a namespace should not be indented. [whitespace/indent] [4] ERROR: Source/JavaScriptCore/heap/MarkingConstraint.cpp:38: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4] ERROR: Source/JavaScriptCore/heap/MarkingConstraint.cpp:39: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4] ERROR: Source/JavaScriptCore/heap/MarkingConstraint.cpp:40: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4] Total errors found: 4 in 25 files If any of these errors are false positives, please file a bug against check-webkit-style.

Comment on attachment 297909 [details] the patch Ooops, did not mean to set r?

Created attachment 298173 [details] more

Created attachment 298202 [details] it compiles!

Created attachment 298216 [details] seems to work sorta

Created attachment 298232 [details] even more This is getting fun.

<rdar://problem/29909896>

The initial implementation boosted splay-latency but hurt on retreating wavefront worst-case pathologies like hash-map, because the only scheduler was a tad bit quicker to choose a longer pause. It looks like the old scheduler was getting luckier on hash-map, but was still having a bad time - lots of wasted iterations before finishing a GC cycle. I'm now adding some exponential backoff to the space-time scheduler. This appears to preserve the patch's advantage on splay-latency while also progressing hash-map. Ultimately, the goal of this patch is to create a framework that can be more easily extended, since it doesn't hide the cost of constraint evaluation from the scheduler.

Created attachment 298250 [details] giving up on the new scheduler Going to go back to the old scheduler. The new one is empirically worse.

(In reply to comment #15) > Created attachment 298250 [details] > giving up on the new scheduler > > Going to go back to the old scheduler. The new one is empirically worse. I should clarify: the same configuration that led to better splay-latency performance also killed Speedometer performance. We don't want that.

Created attachment 298280 [details] reverted to the old scheduling algorithm I think that what made the old scheduling algorithm so effective is that its decisions were so time-driven. It stayed in phase except when we "snapped" phase after a round of constraint solving. This meant that if we encountered jank while in some mode (resumed or suspended) and overran our budget then the scheduler would degrade to something like a coin flip. It turns out that having this kind of non-determinism is _good_ for the GC, since it protects us from many run-away scenarios. For example if a deterministic scheduler encounters a huge object, then we'd yield to mutator unless the scheduler had some mechanism to detect this case. Altogether it seems that the good things about the old scheduler are: - Eventually stop-the-world, which we arrive at somewhat elastically. - Periodic stop-the-world increments that have a chance of getting lucky and declaring termination. - Prioritize collector progress. In a retreating wavefront collector, the mutator has the speed advantage - so we need to give the collector some unfair advantage. - Allow constraint solving to take as long as it needs to take to generate work. - Degrade to coin flip when we encounter jank. I can't easily think of another scheduling algorithm that achieves these things while staying so simple. Every time I've tried to dramatically change this scheduler, I've gotten regressions all over the place. I think I'll stick to making only incremental improvements. Probably if I do come back to improving the scheduler, then I'll try to make the scheduler's period adapt to the time it took to run constraints. We should use a longer period when we took longer to run constraints so that the mutator has more time to itself.

(In reply to comment #17) > Created attachment 298280 [details] > reverted to the old scheduling algorithm > > I think that what made the old scheduling algorithm so effective is that its > decisions were so time-driven. It stayed in phase except when we "snapped" > phase after a round of constraint solving. This meant that if we encountered > jank while in some mode (resumed or suspended) and overran our budget then > the scheduler would degrade to something like a coin flip. It turns out that > having this kind of non-determinism is _good_ for the GC, since it protects > us from many run-away scenarios. For example if a deterministic scheduler > encounters a huge object, then we'd yield to mutator unless the scheduler > had some mechanism to detect this case. > > Altogether it seems that the good things about the old scheduler are: > - Eventually stop-the-world, which we arrive at somewhat elastically. > - Periodic stop-the-world increments that have a chance of getting lucky and > declaring termination. > - Prioritize collector progress. In a retreating wavefront collector, the > mutator has the speed advantage - so we need to give the collector some > unfair advantage. > - Allow constraint solving to take as long as it needs to take to generate > work. > - Degrade to coin flip when we encounter jank. > > I can't easily think of another scheduling algorithm that achieves these > things while staying so simple. Every time I've tried to dramatically change > this scheduler, I've gotten regressions all over the place. I think I'll > stick to making only incremental improvements. Probably if I do come back to > improving the scheduler, then I'll try to make the scheduler's period adapt > to the time it took to run constraints. We should use a longer period when > we took longer to run constraints so that the mutator has more time to > itself. Still testing this new scheduler... so far I just confirmed that it does the right things on splay and hash-map.

The patch is actually fixing this and its parent bug. *** This bug has been marked as a duplicate of bug 165910 ***