[Mono-dev] Single thread scheduler for Threading.Timers patch

[Jonathan Gilbert]

At 09:37 AM 14/06/2006 -0700, Rafael Ferreira wrote:
>Hey there, let me start by saying thanks for the feedback.. my commments
>below:

No problem :-) By the way, it may have appeared to be off of the list (I
mention this because I didn't see your reply on the list), but actually my
post was to mono-devel-list and CCed to you. I've done the same with this
reply; I hope that's okay with you :-)

>> At 11:04 PM 13/06/2006 -0700, Rafael Ferreira wrote:
>>>Howdy,
>>>
>>>The attached patch changes the current Threading.Timer class to use a
>>>single thread scheduler instead of the current 1 thread per timer logic.
>>>I also spent a lot of time working on the Timer unit tests so they more
>>>consistently pass as well as fixing the "NotWorking" tests.
>>>
>>>Some key features include:
>>>
>>>* A single thread handles firing all timer jobs thus allowing a much
>>>greater number of Timers to be defined - Fixing bug #65734
>>>* Timer scheduler is only started after the first System.Threading.Timer
>>>is created (lazy init)
>>>* Timer scheduler thread dies if there are no more timer jobs in its Job
>>>queue (early termination)
>>>* Scheduler can spit out debug info by exporting the MONO_TIMER_DEBUG
>>>environment variable
>>
>> One thing that gets me about the design is the way that timer events are
>> marshalled to a different thread (in the thread pool) in order to be
>> fired.
>> Obviously, you don't want synchronous callbacks from a single thread for
>> all timers, but perhaps a timer thread pool, each of which handling a
>> subset of the timers, would be a viable alternate design. With a limit of,
>> say, 100 scheduler threads, up to 100 timers could be created without any
>> chance of interference, and after that point, the threads would be reused
>> instead of overloading the system with thousands of threads. The threads
>> could even switch from synchronous callbacks when they are handling only a
>> single timer to asynchronous thread pool callbacks when their
>> responsibilities increase.
>
>I'm not sure what do you mean by "marshalled to a different thread",
>there's no serialization taking place here and this implementation is not
>any different than what is currently being done by the timer class. The
>only difference is that I chose to call ThreadPool.QueueUserWorkItem
>explicitly instead of using .BeingInvoke(). Also, having n scheduler
>therads would not help you much, actually I the whole point of the
>single-thread scheduler is to minimize idle threads.

The call to ThreadPool.QueueUserWorkItem *is* the marshalling I was
referring to. It isn't data that's being marshalled, but rather the
function call itself. The only concern I had was with the responsiveness of
thread pool threads being awakened when they have possibly been asleep for
a long time; if pages have to be brought into memory when the thread pool
threads unblock, then the timer will have possibly several additional
seconds of delay added to the callback. Obviously, making the callback from
the thread that is driving the timer wouldn't have this problem, but it
would have the different problem that if the callback takes too long the
timer's activity (and that of any other timers on the same thread) will be
negatively affected.

I'm not actually sure how Microsoft's implementation works. I could write a
couple of tests and run them. Specifically, what I'm interested to know is,
if you have only one timer running, and that timer's callback takes longer
than the interval, will the next timer tick cause another, re-entrant call
into the callback on another thread, or does that next tick get delayed
until the callback returns? The MSDN documentation makes it clear that
thread pool threads are involved, but it doesn't indicate whether the
thread pool threads themselves drive the timer, or whether the timer(s) are
driven by a separate thread and only the callbacks are done through the
thread pool.

>> If we accept the single-thread thread-pool-callback design, though, I have
>> the following comments on the implementation:
>>
>> 1. A heap structure is very easy to maintain, and would be a significantly
>> more efficient way to find the next event to be fired. You have comments
>> that acknowledge the deficiency of looping over the entire set every time,
>> and I think this would be the logical next step in this.
>
>I agree that a sorted data structure would speed things up the problem
>there is that SortedList will just not cut it and writing a new data
>structure (or a wrapper class) just didn't sense just to speed up a very
>edge case (how many users are going create 10k timers?)

Sure, but heaps are especially easy to write :-) They fit into an array,
and they require only three helper methods to update the structure: swap,
heapify-up and heapify-down.

When a new timer is added, you simply drop it onto the end of the array,
and then heapify-up. When a timer tick occurs, you move the item at the end
of the array overtop of the one at the front of the array, and then
heapify-down. Following these rules, the first entry in the array will
always be the next event to fire.

The heapifying functions are relatively simple to implement and take only a
dozen lines each.

>> 2. Using Thread.Abort to signal the thread is fundamentally flawed. A user
>> very quickly adding & removing timers would eventually cause a
>> ThreadAbortException to fire inside the 'catch' handler, killing off the
>> scheduler thread and disabling all timers. A better approach would be to
>> use Monitor.Wait on a synchronization object in the scheduler thread with
>> the correct time-out, and then Monitor.Pulse to awaken the thread for an
>> update. The scheduler can use DateTime.Now comparisons to determine, when
>> Monitor.Wait returns, how long it actually waited and whether it should
>> actually fire the event at top of the heap, and the return value of
>> Monitor.Wait will indicate whether it was interrupted and thus should
>> check
>> the queue of timer additions/deletions before proceeding.
>
>I agree that doing a Abort() on the thread is not the most elegant way to
>singal a thread but I do cover the edge cases in send_scheduler_signal so
>a thread is only signaled if it is in the right "state". I also "queue" up
>abort()'s so under heavy "timer" creation only 1 abort call is made. I'm
>not quite sure how your Monitor logic would work but I would be more than
>glad to entertain your solution.

I haven't had the opportunity to apply the patch; I have been reading it
directly from the timer.patch file, in which form it is rather difficult to
make heads or tails of :-) So, I'm not able to evaluate the
send_scheduler_signal code to see if there might be any holes in it.

The monitor approach looks roughly like this:

void send_signal(object signal_object)
{
  lock (sync)
  {
    signal_queue.Enqueue(signal_object);
    Monitor.Pulse(sync);
  }
}

Queue signal_queue = new Queue();
object sync = new object();

struct TickInfo
{
  public DateTime TimeOfNextTick, Interval;
  public WaitCallback CallbackMethod;
  public object CallbackData;
}

void thread_proc()
{
  TickInfo[] heap = new TickInfo[initial size];
  int num_heap_entries = 0;

  lock (sync)
    while (true)
    {
      TimeSpan delay = TimeSpan.FromMilliseconds(Timeout.Infinite);

      if (num_heap_entries > 0)
      {
        DateTime now = DateTime.Now;

        if (heap[0].TimeOfNextTick < now)
        {  
          fire_first_event_from_heap(heap, num_heap_entries);
          continue;
        }

        delay = heap[0].TimeOfNextTick - now;
      }

      Monitor.Wait(sync, delay);

      while (signal_queue.Count > 0)
        update_heap(ref heap,
(SchedulerUpdateSignalObject)signal_queue.Dequeue());
    }
}

void fire_first_event_from_heap(TickInfo[] heap, int num_heap_entries)
{
  ThreadPool.QueueUserWorkItem(heap[0].CallbackMethod, heap[0].CallbackData);

  TickInfo next_tick = heap[0];

  next_tick.TimeOfNextTick = DateTime.Now + next_tick.Interval;

  // remove the old tick
  heap[0] = heap[num_heap_entries - 1];
  heapify_down(heap, num_heap_entries - 1);

  // insert the new one
  heap[num_heap_entries - 1] = next_tick;
  heapify_up(heap, num_heap_entries);
}

>> If you'd like, I can try writing an alternate implementation along these
>> lines, but it will have to wait until after work for me today.
>
>Like I said, go right ahead. There's always more than 1 way to implement
>things

I guess the above counts as a rough pseudocode implementation of what I had
in mind :-) What are your thoughts?

Jonathan Gilbert