Re: Single-threading servers and select()

[skaller <skaller@...>]

On Mon, 2005-01-24 at 02:38, David Given wrote:

> The advantage is that from a process' point of view, all I/O is O(1) 
> regardless of how many pending requests there are. Unfortunately, the 
> disadvantage is that all the work happens inside callbacks, so if you want 
> absolute top performance (i.e., your callback doesn't just kick another 
> process that's been blocked) you end up with state machines.

Your program logic has to reflect the application's needs.
The difficulty with callbacks is that the programmer is the
slave instead of the master.

So what you need is 'control inversion', which is what Felix does:
it takes code written using an algorithmic style with blocking
reads and inverts the control structure into a callback,
automatically.

In fact it makes a chain of finite state machines on the heap,
representing the stack -- unlike the machine stack context
switching involves just swapping a single pointer.

The problem doing that with the machine stack pointer
is linear addressing -- the very thing that makes stacks
fast also means you have to pre-allocate enough address
space for their maximum size -- CPU's just don't
have enough address space for lots of stacks.

> Emulating sync I/O on top of async is *easy*...

Yes, and emulating subroutines on top of coroutines
is easy too.

This suggests Lua coroutines should not be an 'add on'
interesting feature -- they should be considered fundamental,
and functions should be eliminated from the core.

> Doing it the other way round is not.

I know -- 5 years work to write Felix to automate this..

> In a way it's a shame that Unix took off so much. It's an amazingly flexible, 
> powerful system --- at least as originally planned; Plan9 is pretty much the 
> only Unix that followed the original design philosophy --- but it's terribly 
> suited for doing a lot of tasks that it's now being used for.

There is an interesting phenomena in the industrial programming
world -- programmers and managers are terrible bigots.

They'll happily pay the best people to use the best libraries
to design an application -- but insist it all be done in 
some particular programming system. That is, the non-expert
managers have the ultimate say in that for which the most expertise
is actually needed -- they rely on marketting hype instead,
refusing to accept the judgement of their own team.

> In an attempt to bring the discussion back on topic: you know what would be 
> really, really useful for Lua? A standard scheduler. Coroutines are superb 
> things, but if you actually want to use them for anything non-trivial you 
> start having to write a scheduler. 

Yes, that seems to be the case. I wonder how much coroutine
based code is out there?

> It would be really useful to have a simple, 
> extendable, standard scheduler that could be used as the core for servers and 
> the like. I know there are a number out there, but they're all tailored for a 
> particular application. Imagine how much code could be thrown away by having a 
> standard one.

Well I don't know how to design one -- either for Felix or Lua.
The standard Felix one emulates a single threaded program
that doesn't do any async I/O. I have written ones that
handle a couple of interesting cases, but I have no idea
how to make an extensible one.

Looking at Lua Socket event queue was very interesting,
I see in that the basis for such a design.

Event queue iterators are iterators -- and STL style
iterators do control inversion. (The queue is filled
from callbacks .. but it is emptied by calls, so the
buffering does control inversion).

The problem seems to be with 'metamethods'. To extend
a data structure (eg event queue) is easy -- to
extend a *control* structure is not.

Ordinary metamethods are not enough because they're callbacks.
What we need is 'metamethods' that are actually coroutines.
Some way to take dispatch loops and join them up...
probably using coroutine chain composition.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net