Title: [142764] trunk/Source/WebCore
- Revision
- 142764
- Author
- [email protected]
- Date
- 2013-02-13 11:30:53 -0800 (Wed, 13 Feb 2013)
Log Message
Avoid updating timer heap when nothing changes
https://bugs.webkit.org/show_bug.cgi?id=109630
Reviewed by Andreas Kling.
When the fire time of a Timer is changed we remove it from the timer heap and reinsert it. This is pretty slow.
Turns out that in ~80% of cases we are already in the heap and the insertion position is the same as the
original position. We can check if anything is actually going to change before doing this work.
This makes starting a timer ~30% faster in average, ~0.1% progression in PLT3.
* platform/Timer.cpp:
(TimerHeapLessThanFunction):
(WebCore::TimerHeapLessThanFunction::operator()):
(WebCore::parentHeapPropertyHolds):
(WebCore):
(WebCore::childHeapPropertyHolds):
(WebCore::TimerBase::hasValidHeapPosition):
The code here assumes that STL heap is a normal binary heap. If there is a different implementation
somewhere the assertions will catch it.
(WebCore::TimerBase::updateHeapIfNeeded):
Skip updating the heap if it is already valid.
(WebCore::TimerBase::setNextFireTime):
* platform/Timer.h:
(TimerBase):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (142763 => 142764)
--- trunk/Source/WebCore/ChangeLog 2013-02-13 19:18:43 UTC (rev 142763)
+++ trunk/Source/WebCore/ChangeLog 2013-02-13 19:30:53 UTC (rev 142764)
@@ -1,3 +1,35 @@
+2013-02-12 Antti Koivisto <[email protected]>
+
+ Avoid updating timer heap when nothing changes
+ https://bugs.webkit.org/show_bug.cgi?id=109630
+
+ Reviewed by Andreas Kling.
+
+ When the fire time of a Timer is changed we remove it from the timer heap and reinsert it. This is pretty slow.
+ Turns out that in ~80% of cases we are already in the heap and the insertion position is the same as the
+ original position. We can check if anything is actually going to change before doing this work.
+
+ This makes starting a timer ~30% faster in average, ~0.1% progression in PLT3.
+
+ * platform/Timer.cpp:
+ (TimerHeapLessThanFunction):
+ (WebCore::TimerHeapLessThanFunction::operator()):
+ (WebCore::parentHeapPropertyHolds):
+ (WebCore):
+ (WebCore::childHeapPropertyHolds):
+ (WebCore::TimerBase::hasValidHeapPosition):
+
+ The code here assumes that STL heap is a normal binary heap. If there is a different implementation
+ somewhere the assertions will catch it.
+
+ (WebCore::TimerBase::updateHeapIfNeeded):
+
+ Skip updating the heap if it is already valid.
+
+ (WebCore::TimerBase::setNextFireTime):
+ * platform/Timer.h:
+ (TimerBase):
+
2013-02-13 Martin Robinson <[email protected]>
[GTK] Remove remaining dead code from the GLib unicode backend
Modified: trunk/Source/WebCore/platform/Timer.cpp (142763 => 142764)
--- trunk/Source/WebCore/platform/Timer.cpp 2013-02-13 19:18:43 UTC (rev 142763)
+++ trunk/Source/WebCore/platform/Timer.cpp 2013-02-13 19:30:53 UTC (rev 142764)
@@ -167,10 +167,10 @@
class TimerHeapLessThanFunction {
public:
- bool operator()(TimerBase*, TimerBase*) const;
+ bool operator()(const TimerBase*, const TimerBase*) const;
};
-inline bool TimerHeapLessThanFunction::operator()(TimerBase* a, TimerBase* b) const
+inline bool TimerHeapLessThanFunction::operator()(const TimerBase* a, const TimerBase* b) const
{
// The comparisons below are "backwards" because the heap puts the largest
// element first and we want the lowest time to be the first one in the heap.
@@ -312,6 +312,58 @@
ASSERT(this == timerHeap().last());
}
+static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex)
+{
+ if (!currentIndex)
+ return true;
+ unsigned parentIndex = (currentIndex - 1) / 2;
+ TimerHeapLessThanFunction compareHeapPosition;
+ return compareHeapPosition(current, heap[parentIndex]);
+}
+
+static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex)
+{
+ if (childIndex >= heap.size())
+ return true;
+ TimerHeapLessThanFunction compareHeapPosition;
+ return compareHeapPosition(heap[childIndex], current);
+}
+
+bool TimerBase::hasValidHeapPosition() const
+{
+ ASSERT(m_nextFireTime);
+ if (!inHeap())
+ return false;
+ // Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
+ // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
+ // in updateHeapIfNeeded() will get hit.
+ const Vector<TimerBase*>& heap = timerHeap();
+ if (!parentHeapPropertyHolds(this, heap, m_heapIndex))
+ return false;
+ unsigned childIndex1 = 2 * m_heapIndex + 1;
+ unsigned childIndex2 = childIndex1 + 1;
+ return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
+}
+
+void TimerBase::updateHeapIfNeeded(double oldTime)
+{
+ if (m_nextFireTime && hasValidHeapPosition())
+ return;
+#ifndef NDEBUG
+ int oldHeapIndex = m_heapIndex;
+#endif
+ if (!oldTime)
+ heapInsert();
+ else if (!m_nextFireTime)
+ heapDelete();
+ else if (m_nextFireTime < oldTime)
+ heapDecreaseKey();
+ else
+ heapIncreaseKey();
+ ASSERT(m_heapIndex != oldHeapIndex);
+ ASSERT(!inHeap() || hasValidHeapPosition());
+}
+
void TimerBase::setNextFireTime(double newUnalignedTime)
{
ASSERT(m_thread == currentThread());
@@ -333,14 +385,7 @@
bool wasFirstTimerInHeap = m_heapIndex == 0;
- if (oldTime == 0)
- heapInsert();
- else if (newTime == 0)
- heapDelete();
- else if (newTime < oldTime)
- heapDecreaseKey();
- else
- heapIncreaseKey();
+ updateHeapIfNeeded(oldTime);
bool isFirstTimerInHeap = m_heapIndex == 0;
Modified: trunk/Source/WebCore/platform/Timer.h (142763 => 142764)
--- trunk/Source/WebCore/platform/Timer.h 2013-02-13 19:18:43 UTC (rev 142763)
+++ trunk/Source/WebCore/platform/Timer.h 2013-02-13 19:30:53 UTC (rev 142764)
@@ -73,6 +73,9 @@
bool inHeap() const { return m_heapIndex != -1; }
+ bool hasValidHeapPosition() const;
+ void updateHeapIfNeeded(double oldTime);
+
void heapDecreaseKey();
void heapDelete();
void heapDeleteMin();
@@ -81,8 +84,7 @@
void heapPop();
void heapPopMin();
- const Vector<TimerBase*>& timerHeap() const { ASSERT(m_cachedThreadGlobalTimerHeap); return *m_cachedThreadGlobalTimerHeap; }
- Vector<TimerBase*>& timerHeap() { ASSERT(m_cachedThreadGlobalTimerHeap); return *m_cachedThreadGlobalTimerHeap; }
+ Vector<TimerBase*>& timerHeap() const { ASSERT(m_cachedThreadGlobalTimerHeap); return *m_cachedThreadGlobalTimerHeap; }
double m_nextFireTime; // 0 if inactive
double m_unalignedNextFireTime; // m_nextFireTime not considering alignment interval
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
