Oilpan: Implement marking time estimation

Source/platform/heap/Heap.cpp

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 2183 matching lines @@
     s_postMarkingCallbackStack = new CallbackStack();
     s_weakCallbackStack = new CallbackStack();
     s_ephemeronStack = new CallbackStack();
     s_heapDoesNotContainCache = new HeapDoesNotContainCache();
     s_markingVisitor = new MarkingVisitor<GlobalMarking>();
     s_freePagePool = new FreePagePool();
     s_orphanedPagePool = new OrphanedPagePool();
     s_allocatedObjectSize = 0;
     s_allocatedSpace = 0;
     s_markedObjectSize = 0;
+    s_recentMarkingTime = 0.0;

[haraken, 2015/03/02 04:49:41]

s_recentMarkingTime => s_markingTimeInLastGC

[kouhei (in TOK), 2015/03/03 04:45:08]

Done.

 
     GCInfoTable::init();
 }
 
 void Heap::shutdown()
 {
     s_shutdownCalled = true;
     ThreadState::shutdownHeapIfNecessary();
 }
 
@@ skipping 287 matching lines @@
     // pointers to the orphaned pages.  (If we have such dangling pointers,
     // we should have crashed during marking before getting here.)
     orphanedPagePool()->decommitOrphanedPages();
 
     postGC(gcType);
 
 #if ENABLE(GC_PROFILING)
     static_cast<MarkingVisitor<GlobalMarking>*>(s_markingVisitor)->reportStats();
 #endif
 
+    double markingTimeInMilliseconds = WTF::currentTimeMS() - timeStamp;
+    s_recentMarkingTime = markingTimeInMilliseconds / 1000;
+
     if (Platform::current()) {
-        Platform::current()->histogramCustomCounts("BlinkGC.CollectGarbage", WTF::currentTimeMS() - timeStamp, 0, 10 * 1000, 50);
+        Platform::current()->histogramCustomCounts("BlinkGC.CollectGarbage", markingTimeInMilliseconds, 0, 10 * 1000, 50);
         Platform::current()->histogramCustomCounts("BlinkGC.TotalObjectSpace", Heap::allocatedObjectSize() / 1024, 0, 4 * 1024 * 1024, 50);
         Platform::current()->histogramCustomCounts("BlinkGC.TotalAllocatedSpace", Heap::allocatedSpace() / 1024, 0, 4 * 1024 * 1024, 50);
     }
 
     if (state->isMainThread())
         ScriptForbiddenScope::exit();
 }
 
 void Heap::collectGarbageForTerminatingThread(ThreadState* state)
 {
@@ skipping 89 matching lines @@
     // should die. Unfortunately it is not the case for all objects
     // because the hierarchy was not completely moved to the heap and
     // some heap allocated objects own objects that contain persistents
     // pointing to other heap allocated objects.
     for (int i = 0; i < 5; ++i)
         collectGarbage(ThreadState::NoHeapPointersOnStack);
 }
 
 double Heap::estimatedMarkingTime()
 {
-    // FIXME: Implement heuristics
-    return 0.0;
+    // Marking algorithm takes O(N_live_objs), so the next marking time can be estimated as:
+    //        ~             N_live_objs
+    // t_next = t_last * ------------------
+    //                    N_last_live_objs
+    // By estimating N_{,last}_live_objs ratio using object size ratio, we get:
+    //        ~           (Size_new_objs + Size_last_marked_objs) * Rate_alive
+    // t_next = t_last * ------------------------------------------------------
+    //                                     Size_last_marked_objs
+
+    double estimatedObjectCountIncreaseRatio = 1.0;
+    if (Heap::markedObjectSize() > 0)
+        estimatedObjectCountIncreaseRatio = (Heap::allocatedObjectSize() + Heap::markedObjectSize()) * ThreadState::mainThreadState()->collectionRate() / Heap::markedObjectSize();

[haraken, 2015/03/02 04:49:41]

Can you fprintf estimatedObjectCountIncreaseRatio and see if you're getting a
reasonable value in various benchmarks before landing this CL? I think your
heuristics make sense but want to confirm that it's actually working as
expected.

[haraken, 2015/03/02 04:49:41]

I'd prefer to add ASSERT(isMainThread()) at the top of the function and use
ThreadState::current() here, to indicate that we currently support only the main
thread but want to support other threads in the future.

[kouhei (in TOK), 2015/03/03 04:45:08]

Tested locally visiting some real world websites.
Estimate seems to work well while loading (max off by 25%-ish).
However, after page load (e.g. object created as response to user action), it
varies on the website and sometimes off by 200% (too conservative on the
estimate).

Imo the current one is good enough to start experiment with, and let me improve
the metric progressively.

[kouhei (in TOK), 2015/03/03 04:45:08]

Done.

+
+    return s_recentMarkingTime * estimatedObjectCountIncreaseRatio;
 }
 
 size_t Heap::objectPayloadSizeForTesting()
 {
     size_t objectPayloadSize = 0;
     for (ThreadState* state : ThreadState::attachedThreads()) {
         state->setGCState(ThreadState::GCRunning);
         state->makeConsistentForSweeping();
         objectPayloadSize += state->objectPayloadSizeForTesting();
         state->setGCState(ThreadState::EagerSweepScheduled);
@@ skipping 242 matching lines @@
 FreePagePool* Heap::s_freePagePool;
 OrphanedPagePool* Heap::s_orphanedPagePool;
 Heap::RegionTree* Heap::s_regionTree = nullptr;
 size_t Heap::s_allocatedObjectSize = 0;
 size_t Heap::s_allocatedSpace = 0;
 size_t Heap::s_markedObjectSize = 0;
 
 size_t Heap::s_externallyAllocatedBytes = 0;
 size_t Heap::s_externallyAllocatedBytesAlive = 0;
 unsigned Heap::s_requestedUrgentGC = false;
+double Heap::s_recentMarkingTime = 0.0;
 
 } // namespace blink