Practical Testing: 25 - Nothing is free

I’m in the process of implementing a timer wheel that matches the interface to the timer queue that I previously developed in this series of articles. The idea being that for certain specific usage scenarios the timer wheel will perform better than the timer queues. Last time I refactored the tests that I was using for the timer queues to remove duplication and I now have a set of failing tests for the new timer wheel.

As soon as I started to look at making some of the failing tests pass I realised that having a heap of failing tests wasn’t such a good idea, at least with my home brew test framework. I had stubbed out the timer wheel’s interface and had decided to throw exceptions from the functions that weren’t implemented yet. Those exceptions caused the tests that used that functionality to fail, so far so good. Unfortunately there was no differentiation between tests that I knew would fail and tests that just happened to be failing; I discovered this when I realised that some of the failing tests were for the timer queues and not the wheel… Switching the exception thrown to one of my testing exceptions, a “test skipped” exception means that I now have a load of timer wheel tests that are skipped due to lack of implementation code and the test failures are clearly failures. Once the real failures were fixed I could move on with the new code.

The great thing about a timer wheel is that it has O(1) performance for setting a timer, simply index into the array and push the new timer onto the head of the list of other timers at this time. It also has O(1) timer cancellation; each timer knows where it is in the wheel and can unset itself directly. For many uses timeout handling can be O(1) as well, if your timer handling code runs from a hardware timer tick then each tick moves the wheel forward by one slot and expires the timers that are present there. My usage is a little more complicated in that I need to be able to query the wheel for the time when the next timer is due. This means that I need to look up when the next timer is due and to do that I need to scan the wheel from ’now’ forward until I find a timer… Our worst case is O(n slots) where the number of slots is determined by the maximum supported timeout and the timer granularity.

In the diagram above, if the timer wheel’s current time is 0 then we would need to scan forward sequentially from ‘start’ to the first timer that is set at position 30 to determine that the first timer is set at 30…

It’s possible to optimise this. We could manage a ‘hint’ which points to the earliest timer that has been set, discovering the next timeout could then be O(1) if the hint is set. The hint could be managed by our calls to SetTimer(), if the timer we’re setting is earlier than the hint, or if it’s the first timer set then we set the hint to point at it. Unfortunately this scheme falls down in the presence of timer cancellation. If you cancel the earliest timer then you need to scan forward to update the hint, this forward scan is potentially O(n); so now your cancellation has gone from O(1) to O(n) to keep your timeout processing at O(1)… In some usage scenarios this might be acceptable except that, of course, expiring a timer or setting a timer that is already set are also forms of cancellation…

For now we’ll avoid all of this complexity and settle for O(n) next timeout calculation. We will, however, mitigate the worst case and add a counter that counts how many timers are currently set, if the counter is zero then there’s no need to scan the whole array to discover that no timer is set; our worst case is now that only one timer is set and it’s set to the maximum timeout value. Likewise we can keep a hint that can be passed from one call to GetNextTimeout() to the next as long as the hint is zeroed upon any timer changes.

Milliseconds CCallbackTimerWheel::GetNextTimeout()
{
   Milliseconds nextTimeout = INFINITE;
  
   // We need to work out the time difference between now and the first timer that is set. 
  
   if (!m_pFirstTimerSetHint)
   {
      m_pFirstTimerSetHint = GetFirstTimerSet(); 
   }
  
   if (m_pFirstTimerSetHint)
   {
      // A timer is set! Calculate the timeout in ms
  
      nextTimeout = static_cast<milliseconds>((
         (m_pFirstTimerSetHint > m_pNow ? 
            (m_pFirstTimerSetHint - m_pNow) : 
            (m_pNow - m_pFirstTimerSetHint)) + 1) * m_timerGranularity);
  
      const Milliseconds now = m_tickCountProvider.GetTickCount();
  
      if (now != m_currentTime)
      {
         // Time has moved on, adjust the next timeout to take into account the difference between now and 
         // the timer wheel's view of the current time...
  
         const Milliseconds timeDiff = (now > m_currentTime ? now - m_currentTime : m_currentTime - now);
  
         if (timeDiff > nextTimeout)
         {
            nextTimeout = 0;
         }
         else
         {
            nextTimeout -= timeDiff;
         }
      }
   }
  
   return nextTimeout;
}
  
CCallbackTimerWheel::TimerData **CCallbackTimerWheel::GetFirstTimerSet() const
{
   TimerData **pFirstTimer = 0;
  
   if (m_numTimersSet != 0)
   {
      // Scan forwards from now to the end of the array...
  
      for (TimerData **p = m_pNow; !pFirstTimer && p < m_pTimersEnd; ++p)
      {
         if (*p)
         {
            pFirstTimer = p;
         }
      }
  
      if (!pFirstTimer)
      {
         // We havent yet found our first timer, now scan from the start of the array to 
         // now...
  
         for (TimerData **p = m_pTimersStart; !pFirstTimer && p < m_pNow; ++p)
         {
            if (*p)
            {
               pFirstTimer = p;
            }
         }
      }
  
      if (!pFirstTimer)
      {
         throw CException(_T("CCallbackTimerWheel::GetFirstTimerSet()"),
            _T("Unexpected, no timer set but count = ") +
            ToString(m_numTimersSet));
      }
   }
  
   return pFirstTimer;
}

Now that we can work out when the next timeout is due we can start to think about handling the timers when they expire. Given the diagram below, if the timer wheel believes that the current time is as indicated and the timers are then expired when the time is at ’now’ we will need to process all of the the timers that are set in the order shown by their index numbers.

Again, if we were driving the wheel from a timer tick then things are simplified as we would only ever ‘rotate’ the wheel by one slot at a time. In the world of general purpose, multi-threaded, non-real time systems though (is that a big enough proviso?) all manner of reasons might mean that we don’t actually get to process the timers until after they’re due.

If all we need to worry about is processing the timers in sequence then we could step along the wheel and then walk each chain of timers and handle them as we go. It could be a little more complex than that if we want to use the BeginTimeoutHandling(), HandleTimeouts(), EndTimeoutHandling() methods to allow us to process timers without holding our lock onto the timer system whilst the timers are dispatched (I talk about why this is a desirable design here, and why needing to go through the begin, handle, end sequence multiple times to process timers is less than ideal here). Ideally, for the later situation we’d want our ‘begin’ to accumulate all 6 timers into a correctly ordered list and remove them from the wheel. We would then unlock the wheel and process the 6 timers in order before locking the wheel again to update the processed timers inside of EndTimeoutHandling(). Doing it this way would mean traversing each slot’s list of timers to get to the last one so that we can link the next list onto the end of the previous lists…

If we ignore the more complex scenario and implement the easy one we end up with code like this to deal with the ‘holding a lock whilst dispatching’ case.

void CCallbackTimerWheel::HandleTimeouts()
{
   const Milliseconds now = m_tickCountProvider.GetTickCount();
  
   while (TimerData *pTimers = GetTimersToProcess(now))
   {
      while (pTimers)
      {
         pTimers = pTimers->OnTimer();
  
         --m_numTimersSet;
      }
   }
}
  
CCallbackTimerWheel::TimerData *CCallbackTimerWheel::GetTimersToProcess(
   const Milliseconds now)
{
   TimerData *pTimers = 0;
  
   // Round 'now' down to the timer granularity
  
   const Milliseconds thisTime = ((now / m_timerGranularity) * m_timerGranularity);
  
   while (!pTimers && m_currentTime != thisTime)
   {
      TimerData **ppTimers = GetTimerAtOffset(0);
  
      pTimers = *ppTimers;
  
      // Step along the wheel...
  
      m_pNow++;
  
      if (m_pNow >= m_pTimersEnd)
      {
         m_pNow = m_pTimersStart + (m_pNow - m_pTimersEnd);
      }
  
      m_currentTime += m_timerGranularity;
   }
  
   if (pTimers)
   {
      m_pFirstTimerSetHint = 0;
   }
  
   return pTimers;
}

With this in place we’re left with 20 tests that fail due to lack of implementation and 4 functions that we need to deal with properly. Three form the begin, handle, end API for unlocked timer dispatch and the fourth is for the the SetTimer() overload that doesn’t require a handle. There’s an interesting amount of functionality required to implement the remaining functions as you can see from here and here. We’ll look at this next time.

The code can be found here and the previous rules apply.