Subject: Re: Multiple Threads in CLISP?

From: Wilhelm Burger <[email-masked]>
Date: Thu, 14 Sep 1995 14:35:06 +0200

>>>>>> "Wilbur" == Wilhelm Burger <[email-masked]> writes:
   >
   >Wilbur> Are there any plans/intentions to implement multi-processing
   >Wilbur> (i.e., shallow processes, threads) in CLISP?
   >
   >Not as far as I know.  I've always been able to get by with IPC.  For
   >instance, via the FFI, I've used PVM (multiple hosts/processes) with
   >success.

The reason I am asking is that we consider porting a Lucid application
written with Lispview, which uses one Lisp thread (process) for event 
handling, thus leaving the listener etc. operational. Without multi-
processing, this would require a major redesign I suppose.

Thanks anyway-
Wilhelm.

---

From: Joerg Hoehle <[email-masked]>
Date: Thu, 14 Sep 1995 17:11:32 +0200

> processing, this would require a major redesign I suppose.
Maybe you should look at how CLX is integrated into CLISP. It also
needs to do X event processing. But I don't know if this may help you.

 	Joerg Hoehle.
[email-masked]			[email-masked]

---

From: Don Cohen <[email-masked]>
Date: Thu, 14 Sep 95 09:29:56 PDT

This is a much more serious issue than the last few replies would seem
to indicate.  I know several people who would seriously like to have
multiple threads in clisp.  When I originally asked about this Bruno
seemed dead set against adding it.  I may have convinced him that it
was a reasonable thing to add, and possibly even that it could be done
with relatively low cost.  At this point, of course, he's trying not to
work on clisp, and I'm not sure whether anyone else knows what pitfalls
to watch out for.  If anyone can think of a plausible plan for getting
this done, I'm sure there are a lot of us out here who would like to hear
it.

---

From: Marcus Daniels <[email-masked]>
Date: Thu, 14 Sep 1995 14:12:42 GMT

>>>>> "Don" == Don Cohen <[email-masked]> writes:

Don>  When I originally asked about
Don> this Bruno seemed dead set against adding it.  I may have
Don> convinced him that it was a reasonable thing to add, and possibly
Don> even that it could be done with relatively low cost.

To me, LispView is not a reason to dive into this effort.  I'd be 
suprised if an external server wouldn't do the the job.  It would
probably be necessary to rewrite a small amount of code, but seeing
how LispView is history anyway, a person doing the work has no 
constraints to work within w.r.t. to hacking the sources.

Outside of ports of old software, and using IPC, I think the
remaining utility of threads doesn't make up for the large amount
of labor to make it happen.

Don> At this
Don> point, of course, he's trying not to work on clisp, and I'm not
Don> sure whether anyone else knows what pitfalls to watch out for.

Probably true, but it is funny how quickly these become apparent once
you get your feet wet.  Sure, threads would be a cool feature, but someone
who really *wants* it should be the person to do it.

Don> If anyone can think of a plausible plan for getting this done,
Don> I'm sure there are a lot of us out here who would like to hear
Don> it.

I fear the `demand' for this feature is an artifact of a dated and hopelessly
deluded Lisp-centric view of the world. 

Things I think are more pressing:
  o better language integration support
   (dynamic linking, interlanguage support).
  o higher performance, maybe runtime code generation
  o Know thy enemy:  talk to NT, 95, OS/2.

---

From: Don Cohen <[email-masked]>
Date: Thu, 14 Sep 95 12:05:02 PDT

Marcus: To me, LispView is not a reason to dive into this effort.  
I don't recall ever mentioning lispview.
  Marcus: Outside of ports of old software, and using IPC, I think the
	remaining utility of threads doesn't make up for the large amount
	of labor to make it happen.
I see much more utility than you seem to, and I hope that you're over
estimating the cost.
  Marcus: someone who really *wants* it should be the person to do it
I agree - the problem (I was hoping someone would suggest a solution)
is how to combine what I think is more than adequate demand, and even
willingness to expend effort, so as to get it done.  I'm afraid we'll
need at least a little help from Bruno, who probably doesn't want to
expend much effort.

  Marcus: I fear the `demand' for this feature is an artifact of a dated 
	and hopelessly deluded Lisp-centric view of the world.
OK, I even accept that my view of the world is dated and lisp-centric.
But this feature is desired by many who do not suffer these afflictions.  
I know of several threads packages for C, for heavens sakes!  (And if I 
know several there must be lots more.)

I'll be happy to discuss technical reasons that threads are worth while.
Perhaps the mailing list isn't the best place, though.

  Marcus:   o higher performance, maybe runtime code generation
What's this about, and how does it relate to better performance?

---

From: Marcus Daniels <[email-masked]>
Date: Thu, 14 Sep 1995 16:54:01 GMT

>>>>> "Don" == Don Cohen <[email-masked]> writes:

me> LispView is not a reason to dive into this effort. 

Don> I don't recall ever mentioning lispview.

It was one concrete example of a potential win.  You didn't provide any.

me> Outside of ports of old software, and using IPC, I think the
me> remaining utility of threads doesn't make up for the large amount
me> of labor to make it happen.  

Don> I see much more utility than you
Don> seem to, and I hope that you're over estimating the cost.

There isn't just the cost in writing it. There is also the
cost in maintaining it, and the cost in the constraints it would
surely add to future enhancements (like in the performance area).
Similar arguments come up with makine C libraries thread-safe.

me> someone who really *wants* it should be the person to do
me> it

Don> I agree - the problem (I was hoping someone would suggest a
Don> solution) is how to combine what I think is more than adequate
Don> demand, and even willingness to expend effort, so as to get it
Don> done.  I'm afraid we'll need at least a little help from Bruno,
Don> who probably doesn't want to expend much effort.

What `we' would need is to start bumping into problems, and solving
them independently.  Supplication isn't going to help get it done.  :-)

me> I fear the `demand' for this feature is an artifact of
me> a dated and hopelessly deluded Lisp-centric view of the world.

Don> OK, I even accept that my view of the world is dated and
Don> lisp-centric.  But this feature is desired by many who do not
Don> suffer these afflictions.  I know of several threads packages for
Don> C, for heavens sakes!  (And if I know several there must be lots
Don> more.)

What are you doing that a event-based or callback-based IPC approach
won't cut it?  In this day and age of Linux and Windows 95 the
argument of expense just doesn't cut it.  And resource-wise, even a couple
of CLISP processes is still fairly small.

Don> I'll be happy to discuss technical reasons that threads are worth
Don> while.  Perhaps the mailing list isn't the best place, though.

The mailing list seems like a good place to me; just keep the subject
line accurate.

me> higher performance, maybe runtime code generation

Don> What's this about, and how does it relate to better performance?

I've got a portable package (so far for Sun and SGI) that writes
native code on the fly.  None of this ucky compile-to-C stuff.  I'm
looking at using it with CLISP.  An optional post-compiler, perhaps.
(having to worry about making the compiler, and potentially a
post-compiler worry about threads sounds like a pain).

---

From: Don Cohen <[email-masked]>
Date: Fri, 15 Sep 95 13:52:01 PDT

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...

---

From: Marcus Daniels <[email-masked]>
Date: Fri, 15 Sep 1995 23:50:42 GMT

>>>>> "Don" == Don Cohen <[email-masked]> writes:

Don> In order to separate
Don> such a program into processes, you have to duplicate the
Don> information to be shared, and if both processes read and write
Don> that data, all the writes done by one have to be propagated to
Don> the other.  This can clearly get to be an expensive proposition,
Don> not only in execution resources, but also in programming effort.
Don> And even if you did send updates back and forth, you'd probably
Don> want multiple threads so that one could read the updates from
Don> other processes while another performed computations requested
Don> from its own input.

As a practical matter, in the world of object-oriented applications,
I don't believe that this notion of syncronizing data is good
example of where threads are crucial.  I mean, you've got an object
running in process A, and a object running in process B.  Whether
they are written in C++ or CLOS they ought to use accessors for
modifying data.  Even in the Windows(TM) world there exists a relatively
straightforward way to redirect such calls over RPC.  A RPC object
library may or may not use threads for buffering -- that is another
matter.

Just because CLISP lacks Lispy multiple threads, doesn't mean it isn't
possible to have multiple threads. There exists a CL music package
which uses threads on NEXTSTEP (via a few C functions and the FFI).
I suspect most of the applications of threads are so fine grained
that this approach is sensible.

I glanced at the xview-input.lisp file from LispView.  It looks
to me like all it does is watch for input from the X server, and call
XView a C notify routine.  One idea would be to rewrite this code
in C, using the OS-level threads.  LispView isn't "pure Lisp"
anyway.

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

I'm not primarily concerned about the execution cost.  At worst,
there would be a build-time conditional compilation feature to make a
"with-threads" and "without-threads" CLISP.  The cost I speak of is
the development and maintenance cost.  Is this feature worth putting
time into compared to other things?  It really sounds like a big glob
of complexity that probably wouldn't get used much.  

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

I suppose one could initially ignore the problem of dynamic variables
and only worry about declared globals.

---

From: Don Cohen <[email-masked]>
Date: Sat, 16 Sep 95 10:39:13 PDT

Marcus:
 As a practical matter, in the world of object-oriented applications,
 I don't believe that this notion of syncronizing data is good
 example of where threads are crucial.  I mean, you've got an object
 running in process A, and a object running in process B.  Whether
 they are written in C++ or CLOS they ought to use accessors for
 modifying data.  Even in the Windows(TM) world there exists a relatively
 straightforward way to redirect such calls over RPC.
I don't see what OO-ness has to do with it.  You're suggesting that
data be partitioned (so it belongs to one process or another) and that
interprocess communication be used instead of shared memory.
I think the important point is that this communication is not free.
It may represent a trivial overhead if the communication occurs at a
high enough level (= low bandwidth), but if you want to do the equivalent
of a structure access, the overhead is very significant.  It can be a lot
of work to change a program written naturally to do a lot of access of the 
second sort to a program that does the first sort.
Another programming problem is that all the things that we tend to think
of as objects in lisp compared by EQ now have to be given IDs in order
to refer to them from another process - that also costs space, time and 
programming effort.

Marcus

It looks like you're now agreeing that it makes sense to use threads
(processes sharing memory), but that whatever you need to do with them
can be done in C.  I guess you could do everything in C.  I won't try
to convince readers in this mailing list that there are reasons to use
lisp instead.  What is it about applications where threads make sense
that also makes them more appropriate to do in C?  I'm not sure what
you mean by "fine grained".  Do you mean that it's necessary to switch
threads at high frequency?  The frequency is related to how long you're
willing to wait for the process in the biggest hurry.  Even if that's
not a very short time, it may make much more sense to use threads.

Marcus:
 I'm not primarily concerned about the execution cost...
 The cost I speak of is the development and maintenance cost.
I tried to address both problems.
I suggested that this feature might not interact much with other
design decisions (if we only switch threads between byte code instructions)
so the development (and maintenance) cost might be small.
Of course, my guess could be wrong.  I'd be interested if anyone sees
why it should be.

Marcus:
  I suppose one could initially ignore the problem of dynamic variables
  and only worry about declared globals.
I don't see any point in trying so separate global from other special
variables.  I also don't see why this should be a concern to the
implementation.  Every thread starts in the global environment, and
it can rebind whatever specials it wants to.

---

From: Marcus Daniels <[email-masked]>
Date: Sat, 16 Sep 1995 15:46:06 GMT

>>>>> "Don" == Don Cohen <[email-masked]> writes:

Don> It looks like you're now agreeing that it makes sense to use
Don> threads (processes sharing memory), but that whatever you need to
Don> do with them can be done in C.  I guess you could do everything
Don> in C. 

Whatever I would need threads for would be performance
(e.g. preprocessing data); otherwise I'd use IPC.  If I needed
threads, I would write a small amount of support code in C.  Since
I've never had a need that made using C burdensome, I don't care. Is
that sufficiently qualified? 

me> I'm not primarily concerned about the execution cost...
me> The cost I speak of is the development and maintenance cost.  

The cost could be amortized by the utility.  The question is whether
or not the utility is so much higher than more economical
alternatives.  I'm remain skeptical.

me> I suppose one could initially ignore the problem of
me> dynamic variables and only worry about declared globals. 

I don't have any technical arguments I care about.  I just don't want
to divert my time away from things that I *do* care about.

Of course, if someone made the winning effort to implement this
I would help to integrate it.  It is just that, personally, I'm 
indifferent about it.

---

From: Don Cohen <[email-masked]>
Date: Mon, 18 Sep 95 09:36:47 PDT

Marcus:
  Whatever I would need threads for would be performance
  (e.g. preprocessing data); otherwise I'd use IPC...
I guess this has to do with your uses of lisp.

In hope of convincing (at least some of) the skeptics, I describe one
below.I invite other people who want multiple processes to describe
their applications.

I have what amounts to a database in a lisp virtual memory.
In the same way that databases try to offer shared access to many
users I want to offer shared access to many processes, which may 
represent many users, or just different things being done by one
user.  All the usual problems of locking arise, of course.  
The point is that I want the database accesses and updates to all
occur in the same shared memory lisp process, rather than trying to
ship the relevant data to the processes that need it and ship the
updates back.  Shipping the relevant data in most cases would be
more expensive than executing the query.  Now the processes that
share the database might themselves be either lisp threads in the
database process or separate processes, but even if they are separate
processes, they'll send queries and updates to the database process,
and those requests must be handled "in parallel", i.e., we don't want
every process that represents a person asking a simple question to have
to wait for another process that represents some long computation, just
because the long computation started before the short request arrived.
I also do not want to try to rewrite all the code that deals with the
database to try to identify places where it would be safe to switch
processes, and try to ensure that these places arise with sufficient
frequency.  This would be a very complex task, very likely to fail,
and very difficult to maintain.

Marcus:
  I don't have any technical arguments I care about.  I just don't want
  to divert my time away from things that I *do* care about.
  Of course, if someone made the winning effort to implement this
  I would help to integrate it.  It is just that, personally, I'm 
  indifferent about it.
I think this is entirely reasonable.  I was not asking YOU to do it.
I was hoping to find other people who really want it and have the
ability to contribute to the effort, and find some way to coordinate
their efforts to actually achieve something.
I haven't heard any concrete offers yet, but still hope to.