Re: Interpreter vs hardware threads

[Xavier Leroy <Xavier.Leroy@inria.fr>]

> What is the source of the linearity of thread context switches in
> ocaml?

Well, the list of all threads is scanned at each context switch to
find runnable threads, determine whether we need to select(), etc.

> Are there ways to eliminate it? If so I'd be happy to have a
> look at doing so.

It's been on my "to do" list for a while, so feel free to give it a try...

The standard trick is to split the collection of threads into several
queues: a queue of runnable threads and a queue of threads waiting for
I/O or timer operations, for instance.  Kepp the latter sorted by
timer expiration date to find easily the timers that have expired.
Also, suspended threads (threads waiting on internal events such as
mutexes and conditions) are not in those two queues, but added back to
the runnable queue when woken up.

This should get the complexity of context switches down to O(N_io),
where N_io is the number of threads waiting on I/O.  You could do
better by using heavyweight threads or signal-based async I/O instead
of select(), but it becomes less portable.

- Xavier Leroy