Multiple Threads: Costs, Benefits

[Don Cohen <donc@ISI.EDU>]

I guess I've been invited to make a case why threads are worth while.
It may be hard for me since it all seems so obvious.  Well, here's
a start...
---
The benefit of multiple threads, abstractly, is when you want to
do several things at once.  For instance, responding to input from
multiple windows, some of which require long computations and others
of which require short computations: the short ones should not have 
to wait for the long ones, and the long ones should at least proceed
when there are no short ones waiting.

So, what are the alternatives to threads, and when are they
appropriate and not?
One alternative is multiple processes.  The difference between
processes and threads is shared address space vs. unshared.
Processes are better for activities that do not trust each other
(that is, they should be protected from each other) and can conveniently
communicate whatever they need to know about each other.
Threads are better if there's a large amount of shared data and
the activities are willing to trust each other (as in activities
written as part of the same program to cooperate to perform a
common task).
In order to separate such a program into processes, you have to
duplicate the information to be shared, and if both processes read
and write that data, all the writes done by one have to be propagated
to the other.  This can clearly get to be an expensive proposition,
not only in execution resources, but also in programming effort.
And even if you did send updates back and forth, you'd probably
want multiple threads so that one could read the updates from other
processes while another performed computations requested from its
own input.

Another model is the event loop, which in effect simulates multiple
threads if one can guarantee that all events execute quickly.  The
problem is that if some of the threads do not execute quickly, then
it can be a major programming task to break them up into quickly
executing pieces.  
Note that the difficulties of multiprocessing (e.g., the need for 
locking) arises in any of the cases above.

Now the costs: It appears to me that it might (I guess only Bruno
could be sure) be relatively easy, and impose few new constraints,
to allow thread switching only between byte code instructions.
My guess is that these leave the system in a relatively consistent
state.  The execution cost in the normal case would then involve 
at most one check per byte code instruction of whether it was time to 
worry about switching.  This could certainly be done in one instruction.
It might be possible to reduce the overhead to near zero by using
interrupts appropriately, e.g., to replace a branch address that normally
leads to the top of the interpretation loop with one that leads to the
thread checking code.

The cost of actually switching threads is fairly small in common lisp,
since it's only the special bindings that have to be undone for one
thread and restored for the other, and it's relatively rare to bind
special variables.

I await a storm of objections...