Oilpan: Implement marking time estimation

Source/platform/heap/Heap.cpp

Index: Source/platform/heap/Heap.cpp
diff --git a/Source/platform/heap/Heap.cpp b/Source/platform/heap/Heap.cpp
index 3edbf6206b5b97b0e67515ccb9091c33a404a035..ee8cba62c16afb24efc624eeba0df06821877cf6 100644
--- a/Source/platform/heap/Heap.cpp
+++ b/Source/platform/heap/Heap.cpp
@@ -2201,6 +2201,7 @@ void Heap::init()
     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();
 }
@@ -2508,8 +2509,11 @@ void Heap::collectGarbage(ThreadState::StackState stackState, ThreadState::GCTyp
     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);
     }
@@ -2619,8 +2623,20 @@ void Heap::collectAllGarbage()
 
 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()
@@ -2883,5 +2899,6 @@ 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