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

[Rafael Ferreira]

sorry for the late response to this email but work has kept me quite
busy lately. 

- raf 

On Wed, 2006-06-14 at 15:19 -0500, Jonathan Gilbert wrote:
> 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.

According to my tests and the documentation I found here

http://msdn.microsoft.com/msdnmag/issues/04/02/TimersinNET/default.aspx

which describes the re-entrance problem you described above, I believe
that the behavior of my implementation is consistent... but I'm not
claiming to be an expert on Timers. 
It might help you to look over the current Timer implementation so you
can get a sense for how we're currently utilizing the threadpool to
handle timers.

> 
> >> 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);
> }

I do like the Monitor Wait/Pulse logic so I'll play with it for a bit
and see how I could use it in the scheduler.

> 
> >> 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
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>