Backed out changeset d578993db396 (bug 590422) due to possible performance regressions (especially WinXP Tscroll).
authorBoris Zbarsky <bzbarsky@mit.edu>
Fri, 27 Aug 2010 14:00:41 -0400
changeset 51588 c8e75a4433d9b62eddcfb841c53af5815ae95948
parent 51587 cf4d7946e2e064b0e8cce517553d593814f9f09e
child 51589 647a515c509bbd80b77f1f8cee451c1a2913c83b
push idunknown
push userunknown
push dateunknown
bugs590422
milestone2.0b5pre
backs outd578993db3969fa6e89e2e487ac4bb1c660aa7c9
Backed out changeset d578993db396 (bug 590422) due to possible performance regressions (especially WinXP Tscroll).
dom/base/nsGlobalWindow.cpp
xpcom/threads/TimerThread.cpp
xpcom/threads/TimerThread.h
xpcom/threads/nsTimerImpl.cpp
--- a/dom/base/nsGlobalWindow.cpp
+++ b/dom/base/nsGlobalWindow.cpp
@@ -8412,21 +8412,22 @@ nsGlobalWindow::RunTimeout(nsTimeout *aT
   nsCOMPtr<nsIScriptGlobalObject> windowKungFuDeathGrip(this);
 
   // A native timer has gone off. See which of our timeouts need
   // servicing
   TimeStamp now = TimeStamp::Now();
   TimeStamp deadline;
 
   if (aTimeout && aTimeout->mWhen > now) {
-    // The OS timer fired early (which can happen due to the timers
-    // having lower precision than TimeStamp does).  Set |deadline| to
-    // be the time when the OS timer *should* have fired so that any
-    // timers that *should* have fired before aTimeout *will* be fired
-    // now.
+    // The OS timer fired early (yikes!), and possibly out of order
+    // too. Set |deadline| to be the time when the OS timer *should*
+    // have fired so that any timers that *should* have fired before
+    // aTimeout *will* be fired now. This happens most of the time on
+    // Win2k.
+
     deadline = aTimeout->mWhen;
   } else {
     deadline = now;
   }
 
   // The timeout list is kept in deadline order. Discover the latest
   // timeout whose deadline has expired. On some platforms, native
   // timeout events fire "early", so we need to test the timer as well
--- a/xpcom/threads/TimerThread.cpp
+++ b/xpcom/threads/TimerThread.cpp
@@ -56,17 +56,19 @@ NS_IMPL_THREADSAFE_ISUPPORTS2(TimerThrea
 
 TimerThread::TimerThread() :
   mInitInProgress(0),
   mInitialized(PR_FALSE),
   mLock(nsnull),
   mCondVar(nsnull),
   mShutdown(PR_FALSE),
   mWaiting(PR_FALSE),
-  mSleeping(PR_FALSE)
+  mSleeping(PR_FALSE),
+  mDelayLineCounter(0),
+  mMinTimerPeriod(0)
 {
 }
 
 TimerThread::~TimerThread()
 {
   if (mCondVar)
     PR_DestroyCondVar(mCondVar);
   if (mLock)
@@ -182,16 +184,70 @@ nsresult TimerThread::Shutdown()
   }
 
   mThread->Shutdown();    // wait for the thread to die
 
   PR_LOG(gTimerLog, PR_LOG_DEBUG, ("TimerThread::Shutdown end\n"));
   return NS_OK;
 }
 
+// Keep track of how early (positive slack) or late (negative slack) timers
+// are running, and use the filtered slack number to adaptively estimate how
+// early timers should fire to be "on time".
+void TimerThread::UpdateFilter(PRUint32 aDelay, TimeStamp aTimeout,
+                               TimeStamp aNow)
+{
+  TimeDuration slack = aTimeout - aNow;
+  double smoothSlack = 0;
+  PRUint32 i, filterLength;
+  static TimeDuration kFilterFeedbackMaxTicks =
+    TimeDuration::FromMilliseconds(FILTER_FEEDBACK_MAX);
+  static TimeDuration kFilterFeedbackMinTicks =
+    TimeDuration::FromMilliseconds(-FILTER_FEEDBACK_MAX);
+
+  if (slack > kFilterFeedbackMaxTicks)
+    slack = kFilterFeedbackMaxTicks;
+  else if (slack < kFilterFeedbackMinTicks)
+    slack = kFilterFeedbackMinTicks;
+
+  mDelayLine[mDelayLineCounter & DELAY_LINE_LENGTH_MASK] =
+    slack.ToMilliseconds();
+  if (++mDelayLineCounter < DELAY_LINE_LENGTH) {
+    // Startup mode: accumulate a full delay line before filtering.
+    PR_ASSERT(mTimeoutAdjustment.ToSeconds() == 0);
+    filterLength = 0;
+  } else {
+    // Past startup: compute number of filter taps based on mMinTimerPeriod.
+    if (mMinTimerPeriod == 0) {
+      mMinTimerPeriod = (aDelay != 0) ? aDelay : 1;
+    } else if (aDelay != 0 && aDelay < mMinTimerPeriod) {
+      mMinTimerPeriod = aDelay;
+    }
+
+    filterLength = (PRUint32) (FILTER_DURATION / mMinTimerPeriod);
+    if (filterLength > DELAY_LINE_LENGTH)
+      filterLength = DELAY_LINE_LENGTH;
+    else if (filterLength < 4)
+      filterLength = 4;
+
+    for (i = 1; i <= filterLength; i++)
+      smoothSlack += mDelayLine[(mDelayLineCounter-i) & DELAY_LINE_LENGTH_MASK];
+    smoothSlack /= filterLength;
+
+    // XXXbe do we need amplification?  hacking a fudge factor, need testing...
+    mTimeoutAdjustment = TimeDuration::FromMilliseconds(smoothSlack * 1.5);
+  }
+
+#ifdef DEBUG_TIMERS
+  PR_LOG(gTimerLog, PR_LOG_DEBUG,
+         ("UpdateFilter: smoothSlack = %g, filterLength = %u\n",
+          smoothSlack, filterLength));
+#endif
+}
+
 /* void Run(); */
 NS_IMETHODIMP TimerThread::Run()
 {
   nsAutoLock lock(mLock);
 
   while (!mShutdown) {
     // Have to use PRIntervalTime here, since PR_WaitCondVar takes it
     PRIntervalTime waitFor;
@@ -202,17 +258,17 @@ NS_IMETHODIMP TimerThread::Run()
     } else {
       waitFor = PR_INTERVAL_NO_TIMEOUT;
       TimeStamp now = TimeStamp::Now();
       nsTimerImpl *timer = nsnull;
 
       if (!mTimers.IsEmpty()) {
         timer = mTimers[0];
 
-        if (now >= timer->mTimeout) {
+        if (now >= timer->mTimeout + mTimeoutAdjustment) {
     next:
           // NB: AddRef before the Release under RemoveTimerInternal to avoid
           // mRefCnt passing through zero, in case all other refs than the one
           // from mTimers have gone away (the last non-mTimers[i]-ref's Release
           // must be racing with us, blocked in gThread->RemoveTimer waiting
           // for TimerThread::mLock, under nsTimerImpl::Release.
 
           NS_ADDREF(timer);
@@ -259,17 +315,17 @@ NS_IMETHODIMP TimerThread::Run()
           // tick or two, and we may goto next below.
           now = TimeStamp::Now();
         }
       }
 
       if (!mTimers.IsEmpty()) {
         timer = mTimers[0];
 
-        TimeStamp timeout = timer->mTimeout;
+        TimeStamp timeout = timer->mTimeout + mTimeoutAdjustment;
 
         // Don't wait at all (even for PR_INTERVAL_NO_WAIT) if the next timer
         // is due now or overdue.
         if (now >= timeout)
           goto next;
         waitFor = PR_MillisecondsToInterval((timeout - now).ToMilliseconds());
       }
 
@@ -357,17 +413,25 @@ PRInt32 TimerThread::AddTimerInternal(ns
 
   TimeStamp now = TimeStamp::Now();
   PRUint32 count = mTimers.Length();
   PRUint32 i = 0;
   for (; i < count; i++) {
     nsTimerImpl *timer = mTimers[i];
 
     // Don't break till we have skipped any overdue timers.
-    if (now < timer->mTimeout && aTimer->mTimeout < timer->mTimeout) {
+
+    // XXXbz why?  Given our definition of overdue in terms of
+    // mTimeoutAdjustment, aTimer might be overdue already!  Why not
+    // just fire timers in order?
+
+    // XXX does this hold for TYPE_REPEATING_PRECISE?  /be
+
+    if (now < timer->mTimeout + mTimeoutAdjustment &&
+        aTimer->mTimeout < timer->mTimeout) {
       break;
     }
   }
 
   if (!mTimers.InsertElementAt(i, aTimer))
     return -1;
 
   aTimer->mArmed = PR_TRUE;
@@ -402,16 +466,19 @@ void TimerThread::DoAfterSleep()
   for (PRUint32 i = 0; i < mTimers.Length(); i ++) {
     nsTimerImpl *timer = mTimers[i];
     // get and set the delay to cause its timeout to be recomputed
     PRUint32 delay;
     timer->GetDelay(&delay);
     timer->SetDelay(delay);
   }
 
+  // nuke the stored adjustments, so they get recalibrated
+  mTimeoutAdjustment = TimeDuration(0);
+  mDelayLineCounter = 0;
   mSleeping = PR_FALSE;
 }
 
 
 /* void observe (in nsISupports aSubject, in string aTopic, in wstring aData); */
 NS_IMETHODIMP
 TimerThread::Observe(nsISupports* /* aSubject */, const char *aTopic, const PRUnichar* /* aData */)
 {
--- a/xpcom/threads/TimerThread.h
+++ b/xpcom/threads/TimerThread.h
@@ -100,11 +100,20 @@ private:
   PRLock *mLock;
   PRCondVar *mCondVar;
 
   PRPackedBool mShutdown;
   PRPackedBool mWaiting;
   PRPackedBool mSleeping;
   
   nsTArray<nsTimerImpl*> mTimers;
+
+#define DELAY_LINE_LENGTH_LOG2  5
+#define DELAY_LINE_LENGTH_MASK  PR_BITMASK(DELAY_LINE_LENGTH_LOG2)
+#define DELAY_LINE_LENGTH       PR_BIT(DELAY_LINE_LENGTH_LOG2)
+
+  PRInt32  mDelayLine[DELAY_LINE_LENGTH]; // milliseconds
+  PRUint32 mDelayLineCounter;
+  PRUint32 mMinTimerPeriod;     // milliseconds
+  TimeDuration mTimeoutAdjustment;
 };
 
 #endif /* TimerThread_h___ */
--- a/xpcom/threads/nsTimerImpl.cpp
+++ b/xpcom/threads/nsTimerImpl.cpp
@@ -398,16 +398,18 @@ void nsTimerImpl::Fire()
 #endif
 
   TimeStamp timeout = mTimeout;
   if (mType == TYPE_REPEATING_PRECISE) {
     // Precise repeating timers advance mTimeout by mDelay without fail before
     // calling Fire().
     timeout -= TimeDuration::FromMilliseconds(mDelay);
   }
+  if (gThread)
+    gThread->UpdateFilter(mDelay, timeout, now);
 
   if (mCallbackType == CALLBACK_TYPE_INTERFACE)
     mTimerCallbackWhileFiring = mCallback.i;
   mFiring = PR_TRUE;
   
   // Handle callbacks that re-init the timer, but avoid leaking.
   // See bug 330128.
   CallbackUnion callback = mCallback;