Re: NSRunLoop Tidying

[David Chisnall]

On 8 Oct 2010, at 17:14, Richard Frith-Macdonald wrote:

> Actually the current implementation uses an unsorted list as depending on the 
> ordering introduced a subtle bug ... a timer can be present in more than one 
> run loop, and/or in the same loop in more than one mode.  

From the NSTimer documentation (CFRunLoopTimerRef contains a similar line):

'A timer object can be registered in only one run loop at a time, although it 
can be added to multiple run loop modes within that run loop.'

Therefore, the second case is the only one that should apply.  

> If it fires in one loop and changes its next fire date (ie is a repeating 
> timer), that automatically breaks the ordering for the other loops/modes that 
> it exists in.  Of course, what we really want is probably something more 
> complex to keep track of all the loops/modes the timer is in, and tell them 
> that they need to re-order their list of timers ... if we did that we could 
> depend on the order in the list.
> The API demands that we keep track of the timers some way (so we can return 
> the correct value from the -limitDateForMode: method), but it doesn't have to 
> be an ordered list if a better alternative is available (though I can't 
> really think of one).

I was thinking that it would be simpler to just keep an unsorted list and scan 
it when one of these methods is called.  It's O(n) in terms of the number of 
timers, but hopefully these methods are not called very often (and n is 
relatively small - I doubt many runloops have hundreds of timers associated 
with them).

>> This is required with traditional select() and poll(), but Win32 has 
>> SetTimer, Linux has timerfd(), and *BSD has kevent(), all of which allow you 
>> to schedule timer events and wait on them just like fd events.
> 
> I don't really see how that can help since the API explicitly separates timer 
> firing (done in -limitDateForMode:) and I/O event handling ... so having 
> timers and I/O events use the same mechanism in the operating system does not 
> mean that they can be done at the same place in the code or with a single 
> system call.  So using things like SetTimer() and timerfd() may just add 
> complexity.

No.  Timers and timeouts are different in the high-level API.  
-limitDateForMode: is an exception.  It is possible to implement the entire API 
on top of this, but that requires doing something in userspace that the kernel 
already has code for.  It is significantly simpler to just schedule the timers 
and sleep.  

The most common way of using a runloop is either -run (no timeout), or 
-runUntilDate: / -runMode:beforeDate:, which have an explicit timeout that is 
orthogonal to the timers.  As these are currently implemented, we:

1) Look through the timers list to find the next timer.
2) Find whether the timer will fire before the timeout.
3) Set the minimum as the timeout.
4) Call down into the kernel.
5) If the timeout occurred, determine whether it was due to a timer firing or 
due to the user-specified timeout elapsing.

In contrast, with kqueue timers, win32 timers, or timerfd, we need to:

1) Call down to the kernel with the user-specified timeout.

This is vastly simpler.  This is especially true when you consider multiple run 
loop iterations.  If timers change during the loop, then we need to recalculate 
the timer / timeout minimum with the first approach, while with the second we 
just need to modify a single timer in the kernel.

On vaguely modern platforms, this means that entering a run loop is much 
simpler, meaning that we spend a lot more time sleeping in userspace waiting 
for the kernel to wake us up, which helps preserve battery life as it means 
more time the CPU can spend in low-power mode.

> I agree with "Dr. H. Nikolaus Schaller" <address@hidden> ... that it would 
> make most sense to start by implementing the CFRunLoop API, and then 
> re-implement NSRunLoop on top of it (it's quite hard to do the other way 
> round).

CFRunLoop is quite a messy API and is actually not sufficiently expressive for 
NSRunLoop.  For example, you can add Mach ports as sources to a CFRunLoop, but 
the API does not provide a mechanism for specifying whether you want read or 
write events (presumably it only generates data-available?), and it does not 
provide an API for adding file descriptors, rather than Mach ports, so you'd 
have to modify it slightly for all non-Darwin platforms.

> Also, you need to put together *LOTS* to testcases in the testsuite to ensure 
> that the implementation behaves exactly like OSX does ... this is because 
> NSRunLoop is a really key part of so much of the system and very subtle/minor 
> changes in behavior can have really nasty effects on applications.  It's 
> really not good enough to have an implementation which does what the 
> documentation says, we have to mimic actual OSX behavior pretty closely.

Agreed.

> My guess is that your idea of re-implementing timer handling in a platform 
> specific way is actually a  recipe for a less maintainable and more complex 
> codebase, since the timeout behavior is largely mandated by the API and I 
> can't currently see how platform specific APIs will help... 

Timers are not timeouts.  They are completely orthogonal in the API, it's only 
an accident of implementation that we treat them as being the same.

> but maybe you have some ideas you didn't mention here.  In general it's a 
> good idea (for maintainability) to keep platform specific code to a minimum, 
> so for instance I wouldn't use PostThreadMessage()  as it's probably no more 
> efficient than the current code using SetEvent(), and would demand changes to 
> NSThread to hold additional thread data and a message queue.

Why would it need NSThread to be modified?  

> On the other hand, the kqueue API is supposed to be significantly more 
> efficient than poll/select ... so using that on BSD and the similar epoll API 
> on Linux would be good.

Using kqueue() to emulate poll() does not provide much of a performance 
advantage.  The advantage comes from actually using the features available with 
the new APIs, not simply making the existing kludge use a tiny subset of the 
new APIs.

> So, what would be great is to:
> 1. Implement the CFRunLoop
> 2. Keep platform specific code to a minimum (though make use of it where it 
> really helps performance) for maintainability
> 3. Have testcases to check that it behaves like OSX on all platforms
> 4. Finally, re-implement NSRunLoop on top of CFRunLoop

It is not possible to implement NSRunLoop on top of CFRunLoop using only the 
public APIs.  It should, however, be possible to create a thin 
platform-specific layer which permits implementation of both NSRunLoop and 
CFRunLoop.  On OS X 10.6, libdispatch is used to implement both.  

David