Are there plans for a multi-threaded Emacs?

Are there plans for a multi-threaded Emacs?

[Frank Schmitt]

Hello

I'm wondering if there are any plans for implementing multi-threaded
program execution into Gnu Emacs. 
http://groups.google.com/groups?selm=9005292346.AA13875%40denali.sun.com
shows that this issue isn't really new, but AFAIK there isn't something
like this actually implemented, is it?

Of course this might reduce platform independence, but hey: For a
multi-threaded Emacs, I'd be willing to leave my homely home and switch
to whatever system able offering it to me.

MFG Frank

-- 
Did you ever realize how much text fits in eighty columns? If you now consider
that a signature usually consists of up to four lines, this gives you enough
space to spread a tremendous amount of information with your messages. So seize
this opportunity and don't waste your signature with bullshit nobody will read.

Re: Are there plans for a multi-threaded Emacs?

[Alex Schroeder]

Frank Schmitt <ich@Frank-Schmitt.net> writes:

> I'm wondering if there are any plans for implementing multi-threaded
> program execution into Gnu Emacs. 

There are no plans for this, and even if we'd switch to Guile,
multi-threading would not be an option, as far as I remember.  The
last time I read some discussion on this was related to using Guile
and the promise of multi-threading it would offer.

Alex.
-- 
http://www.emacswiki.org/alex/
There is no substitute for experience.

Re: Are there plans for a multi-threaded Emacs?

[Dhruva Krishnamurthy]

Hello,
 Is there some place/person who can elaborate the reason for not
 supporting multi-threading for GNU Emacs. Is it because there is no
 strong case for supporting/requiring a multi-threaded GNU Emacs or the
 sheer complexity in making GNU Emacs a multi-threaded application.

with best regards,
dhruva

On Mon, 17 Nov 2003 01:49:34 +0100, "Alex Schroeder" <alex@emacswiki.org>
said:
> Frank Schmitt <ich@Frank-Schmitt.net> writes:
> 
> > I'm wondering if there are any plans for implementing multi-threaded
> > program execution into Gnu Emacs. 
> 
> There are no plans for this, and even if we'd switch to Guile,
> multi-threading would not be an option, as far as I remember.  The
> last time I read some discussion on this was related to using Guile
> and the promise of multi-threading it would offer.
________________________________________
Dhruva Krishnamurthy
http://schemer.fateback.com/
General:www@furby.fastmail.fm
GNU/FSF:gnu@furby.fastmail.fm 
GNU Emacs:gnu.emacs@furby.fastmail.fm

Re: Are there plans for a multi-threaded Emacs?

[Miles Bader]

"Dhruva Krishnamurthy" <gnu@furby.fastmail.fm> writes:
>  Is there some place/person who can elaborate the reason for not
>  supporting multi-threading for GNU Emacs. Is it because there is no
>  strong case for supporting/requiring a multi-threaded GNU Emacs or the
>  sheer complexity in making GNU Emacs a multi-threaded application.

Because it's very hard, or at the least would require a lot of work.

Multi-threading would require all of emacs -- including elisp code -- to
be made thread-safe.

Consider a simple bit of elisp code:  (setq GLOBAL (cons 'x GLOBAL))
In a pre-emptively threaded emacs, another thread could run between
accessing GLOBAL and setting it.  Whoops.

-Miles
-- 
((lambda (x) (list x x)) (lambda (x) (list x x)))

Re: Are there plans for a multi-threaded Emacs?

[Richard Stallman]

    I'm wondering if there are any plans for implementing multi-threaded
    program execution into Gnu Emacs. 

It would be a nice feature, but very difficult.

Re: Are there plans for a multi-threaded Emacs?

[David Masterson]

>>>>> Richard Stallman writes:

>     I'm wondering if there are any plans for implementing multi-threaded
>     program execution into Gnu Emacs. 

> It would be a nice feature, but very difficult.

If not multi-threading, could Emacs be made stronger in multi-tasking?
For instance, if the display-engine could be separated from the
lisp-engine parts, then perhaps a mini-scheduler could fork off
lisp-engines as needed (or requested) to process complicated things.
The "engines" would theoretically be lighter weight than Emacs proper,
but not as light-weight as multi-threading would allow.

-- 
David Masterson

Re: Are there plans for a multi-threaded Emacs?

[Miles Bader]

David Masterson <dsm@rawbw.com> writes:
> For instance, if the display-engine could be separated from the
> lisp-engine parts, then perhaps a mini-scheduler could fork off
> lisp-engines as needed (or requested) to process complicated things.
> The "engines" would theoretically be lighter weight than Emacs proper,
> but not as light-weight as multi-threading would allow.

How would this be different than multiple threads, as far as avoiding
typical threading problems (when lisp programs modify global/globally
reachable data)?

-Miles
-- 
Come now, if we were really planning to harm you, would we be waiting here, 
 beside the path, in the very darkest part of the forest?

Re: Are there plans for a multi-threaded Emacs?

[John Wiegley]

David Masterson <dsm@rawbw.com> writes:

> If not multi-threading, could Emacs be made stronger in
> multi-tasking?  For instance, if the display-engine could be
> separated from the lisp-engine parts, then perhaps a mini-scheduler
> could fork off lisp-engines as needed (or requested) to process
> complicated things.  The "engines" would theoretically be lighter
> weight than Emacs proper, but not as light-weight as multi-threading
> would allow.

Perhaps multi-threading could be allowed in a rather brain-damaged
way, using global-scope critical regions:

    All current Lisp code would run in a MAIN region, in which only
one thread could execute at a time, and each thread would have to give
up control to allow any others to run.

    Then we add (with-critical-region NAME ...), and the ability to
create such regions, so that Gnus, for example, could run in its own
happy little space, blocking if it ever needed to do things outside of
that space (and then grabbing control when the space was available).

    This at least gives the maintainer a way of creating a world apart
that could run in conjunction with the rest of Emacs.  Since what I
think most people want from threading is the ability to give long-
running Emacs modules a chance to do their work while they continue
editing.

John

Re: Are there plans for a multi-threaded Emacs?

[David Masterson]

>>>>> Miles Bader writes:

> David Masterson <dsm@rawbw.com> writes:

>> For instance, if the display-engine could be separated from the
>> lisp-engine parts, then perhaps a mini-scheduler could fork off
>> lisp-engines as needed (or requested) to process complicated
>> things.  The "engines" would theoretically be lighter weight than
>> Emacs proper, but not as light-weight as multi-threading would
>> allow.

> How would this be different than multiple threads, as far as
> avoiding typical threading problems (when lisp programs modify
> global/globally reachable data)?

It was just speculation on my part (and not necessarily a very good
one).  In answer to your question, I would guess that a global data
server would be needed to manage such access.  I was envisioning that
major packages (Gnus, VM, Calendar, ...) would each run in their own
lisp engine and that very little data would need to be shared between
the packages.

-- 
David Masterson

Re: Are there plans for a multi-threaded Emacs?

[Richard Stallman]

    >> For instance, if the display-engine could be separated from the
    >> lisp-engine parts, then perhaps a mini-scheduler could fork off
    >> lisp-engines as needed (or requested) to process complicated
    >> things.

Nowadays redisplay calls Lisp code, so that would not be a simple approach
to carry out.

Re: Are there plans for a multi-threaded Emacs?

[Kai Grossjohann]

Miles Bader <miles@lsi.nec.co.jp> writes:

> Consider a simple bit of elisp code:  (setq GLOBAL (cons 'x GLOBAL))
> In a pre-emptively threaded emacs, another thread could run between
> accessing GLOBAL and setting it.  Whoops.

Well, I don't know a lot about threading, but Java, at least, has the
same problem: you need to synchronize access to a variable to prevent
such things from happening.  By default, synchronized access is turned
off.

So if all of what is now in Emacs continues to run in a single thread,
and you just provide a function to create a new thread and run stuff
in that new thread, then it would be the responsibility of the people
creating threads to make sure that they don't step on each other's
toes.

Then the remaining problem is that possibly a lot of functions cannot
be safely used because they access global variables.  But that is just
something that people will have to live with, and maybe it will get
better over time.  I think that it will be good enough at least for
some packages to do part of their work in the background.

What do people think?  Maybe I missed something obvious...

Kai

Re: Are there plans for a multi-threaded Emacs?

[Vinicius Jose Latorre]

Kai Grossjohann <kai@emptydomain.de> writes:

>  Miles Bader <miles@lsi.nec.co.jp> writes:
>  
>  > Consider a simple bit of elisp code:  (setq GLOBAL (cons 'x GLOBAL))
>  > In a pre-emptively threaded emacs, another thread could run between
>  > accessing GLOBAL and setting it.  Whoops.
>  
>  Well, I don't know a lot about threading, but Java, at least, has the
>  same problem: you need to synchronize access to a variable to prevent
>  such things from happening.  By default, synchronized access is turned
>  off.
>  
>  So if all of what is now in Emacs continues to run in a single thread,
>  and you just provide a function to create a new thread and run stuff
>  in that new thread, then it would be the responsibility of the people
>  creating threads to make sure that they don't step on each other's
>  toes.
>  
>  Then the remaining problem is that possibly a lot of functions cannot
>  be safely used because they access global variables.  But that is just
>  something that people will have to live with, and maybe it will get
>  better over time.  I think that it will be good enough at least for
>  some packages to do part of their work in the background.
>  
>  What do people think?  Maybe I missed something obvious...

I also don't know a lot about threads, but CHILL (old) language also has a
mechanism of mutual exclusion.  So, one could define a thread, other defines
another thread, if both of them need to share some resource (variables) they
define a region of mutual exclusion where the resources (variables) can be
accessed only by procedure calling.

Maybe I also missed something obvious...

Vinicius

Re: Are there plans for a multi-threaded Emacs?

[Benjamin Riefenstahl]

Hi Kai,


Kai Grossjohann <kai@emptydomain.de> writes:
> Well, I don't know a lot about threading, but Java, at least, has
> the same problem: you need to synchronize access to a variable to
> prevent such things from happening.  By default, synchronized access
> is turned off.
>
> [...]
>
> What do people think?  Maybe I missed something obvious...

Just a thought: The Asm/C/Java model of threads is not the only
possibility.

Another model is to create isolated contexts/interpreters for each
thread and require explicit coding to communicate between the threads
and for setting up variables that are synchronized between them.  This
is easier to use in a migration from a single-thread model, and I
think it is also easier and safer to program in general.

OTOH, with a system that does so much in LISP as Emacs does, even
going to the trouble of dump and undump, this model can lead to a lot
of duplicated state, which of course costs memory and also may create
inconsistencies at the user level, when customizations only apply to
one thread but not to the other.

As I said, just a thought...


benny

Re: Are there plans for a multi-threaded Emacs?

[Kai Grossjohann]

Vinicius Jose Latorre <vinicius@cpqd.com.br> writes:

> I also don't know a lot about threads, but CHILL (old) language also has a
> mechanism of mutual exclusion.  So, one could define a thread, other defines
> another thread, if both of them need to share some resource (variables) they
> define a region of mutual exclusion where the resources (variables) can be
> accessed only by procedure calling.

I think the point of the post I followed up to was that lots of code
already accesses global (and hence, potentially shared) variables
WITHOUT defining a region of mutual exclusion.

Kai

Re: Are there plans for a multi-threaded Emacs?

[Nic Ferrier]

Kai Grossjohann <kai@emptydomain.de> writes:

> Miles Bader <miles@lsi.nec.co.jp> writes:
> 
> > Consider a simple bit of elisp code:  (setq GLOBAL (cons 'x GLOBAL))
> > In a pre-emptively threaded emacs, another thread could run between
> > accessing GLOBAL and setting it.  Whoops.
> 
> Well, I don't know a lot about threading, but Java, at least, has the
> same problem: you need to synchronize access to a variable to prevent
> such things from happening.  By default, synchronized access is turned
> off.
> 
> So if all of what is now in Emacs continues to run in a single thread,
> and you just provide a function to create a new thread and run stuff
> in that new thread, then it would be the responsibility of the people
> creating threads to make sure that they don't step on each other's
> toes.
> 
> Then the remaining problem is that possibly a lot of functions cannot
> be safely used because they access global variables.  But that is just
> something that people will have to live with, and maybe it will get
> better over time.  I think that it will be good enough at least for
> some packages to do part of their work in the background.
> 
> What do people think?  Maybe I missed something obvious...

I think there are 2 big problems:

1. emacs _is_ global variables, there aren't any thread safe routines
right now because thread safety has not been an issue uptil now. So
display, buffer manipulation, everything becomes a thread problem.

2. I think dynamic scope also makes this a lot more complicated
because you're not talking about just globals anymore but variables
passed from a proc into a thread-proc and onwards. Very tricky.


Nic

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Sun, 30 Nov 2003, kai@emptydomain.de wrote:

> Then the remaining problem is that possibly a lot of functions
> cannot be safely used because they access global variables.  But
> that is just something that people will have to live with, and maybe
> it will get better over time.  I think that it will be good enough
> at least for some packages to do part of their work in the
> background.

I think migrating Emacs towards a threading model is possible:

- start with all primitive or ELisp functions assumed NOT thread-safe

- allow threads to run, but any access to a function needs to be
  synchronous.  At first, this will effectively make threads simple
  switched tasks, and will probably make Emacs slower.

- gradually migrate functions, starting with the primitives, towards
  whatever threading model Emacs assumes.  Use some kind of function
  attribute to mark thread-safe behavior.  With time, threads will
  become efficient and fast.

The internal implementation of threads will be the difficult part.
It took Perl a LONG time to get working threads internally.

I think heavyweight threads (multiple processes) is not a good choice
for Emacs, because of the heavy interaction and data passing between
the internal functions.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Ted Lemon]

On Dec 1, 2003, at 10:04 AM, Ted Zlatanov wrote:
> I think migrating Emacs towards a threading model is possible:

Maybe this is a stupid question, but what's the payoff you're expecting 
when you're done with this project?   What is it about Emacs that makes 
it worth a major rewrite in order to make it multithreaded?   I realize 
that multithreading will introduce small conveniences in some cases, 
but in general writing multithreaded code is a total pain in the neck, 
so my guess is that the cost of those small conveniences would be more 
than they'd be worth, and you might be able to get them cheaper using 
some other technique, if you could identify what they are.

Re: Are there plans for a multi-threaded Emacs?

[Per Abrahamsen]

Ted Lemon <mellon@fugue.com> writes:

> What is it about Emacs that makes it worth a major rewrite in order
> to make it multithreaded?

Gnus.

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Ted Lemon <mellon@fugue.com> writes:
> 
> > What is it about Emacs that makes it worth a major rewrite in order
> > to make it multithreaded?
> 
> Gnus.

gnus-asynchronous's value is nil

*If nil, inhibit all Gnus asynchronicity.
If non-nil, let the other asynch variables be heeded.

You can customize this variable.

Defined in `gnus-async'.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

>> What is it about Emacs that makes it worth a major rewrite in order
>> to make it multithreaded?
> Gnus.

Wouldn't Gnus be happy enough with cooperative multithreading ?

I keep thinking that we should provide a way to specify background tasks
that we can run while idle.  It can already be done in elisp, but it's
rather painful.


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Tue, 2 Dec 2003, mellon@fugue.com wrote:

On Dec 1, 2003, at 10:04 AM, Ted Zlatanov wrote:
>> I think migrating Emacs towards a threading model is possible:
> 
> Maybe this is a stupid question, but what's the payoff you're
> expecting when you're done with this project?  What is it about
> Emacs that makes it worth a major rewrite in order to make it
> multithreaded?  I realize that multithreading will introduce small
> conveniences in some cases, but in general writing multithreaded
> code is a total pain in the neck, so my guess is that the cost of
> those small conveniences would be more than they'd be worth, and you
> might be able to get them cheaper using some other technique, if you
> could identify what they are.

Per already mentioned Gnus.  Generally any place in Emacs where you
could be doing task A while task B is waiting for a blocking resource.
Also, an event-driven model for user interaction would be easier to
implement in a way that's functional for the user.

In a way, this is a very valid question - what can't be done with
processes that threads can do?  You can do almost everything without
threads, but the cost is very high in terms of portability, resource
usage, and ease of use.  Furthermore, as I mentioned, processes are
much harder to couple (for data sharing) than threads.

Ideally, you won't have to worry about multithreading if you don't
want to.  Java allows programmers to mark functions as synchronous,
so only one of it can be running at once.  I proposed doing this by
default for all Emacs functions, and then making them thread-safe
step by step.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Simon Josefsson]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

>>> What is it about Emacs that makes it worth a major rewrite in order
>>> to make it multithreaded?
>> Gnus.
>
> Wouldn't Gnus be happy enough with cooperative multithreading ?

I believe so too.

> I keep thinking that we should provide a way to specify background tasks
> that we can run while idle.  It can already be done in elisp, but it's
> rather painful.

Yes.  Like David Kastrup indicated, Gnus can already do several things
in the background, but it is far from what you would expect from a
normal multi-threaded mail reader.  Blocking the GUI to wait for data
from the network is poor engineering.

Re: Are there plans for a multi-threaded Emacs?

[Per Abrahamsen]

David Kastrup <dak@gnu.org> writes:

> gnus-asynchronous's value is nil

It only helps for slow I/O, there are plenty of operations in Gnus
that are CPU bound.  Creating large summary buffers for example.

Re: Are there plans for a multi-threaded Emacs?

[Per Abrahamsen]

Simon Josefsson <jas@extundo.com> writes:

> Blocking the GUI to wait for data from the network is poor
> engineering.

Blocking the GUI to wait for the result of a computation is poor
engineering as well.

Re: Are there plans for a multi-threaded Emacs?

[Richard Stallman]

    I think migrating Emacs towards a threading model is possible:

    - start with all primitive or ELisp functions assumed NOT thread-safe

    - allow threads to run, but any access to a function needs to be
      synchronous.  At first, this will effectively make threads simple
      switched tasks, and will probably make Emacs slower.

Many sections of Lisp code would need to have locking in order
to run correctly with multiple threads.  For instance, everything
of the form

  (setq global-list (cons foo global-list))

would need locking.

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Wed, 03 Dec 2003, rms@gnu.org wrote:

    > I think migrating Emacs towards a threading model is possible:
> 
>     - start with all primitive or ELisp functions assumed NOT
>       thread-safe
> 
>     - allow threads to run, but any access to a function needs to be
>       synchronous.  At first, this will effectively make threads
>       simple switched tasks, and will probably make Emacs slower.
> 
> Many sections of Lisp code would need to have locking in order
> to run correctly with multiple threads.  For instance, everything
> of the form
> 
>   (setq global-list (cons foo global-list))
> 
> would need locking.

What I proposed is that *all* functions start with the "synchronous"
atribute.  This would apply to primitives as well.

Then, they would be gradually rewritten.  For instance, a thread-safe
setq would act just like the regular setq, but it would lock its
arguments with semaphores before modifying them.  The thread-safe
setq can then be marked "asynchronous."

To deal with the example above, all buffers, variables, processes,
etc. that a synchronous function affects will have to be
thread-locked also.  So that needs to be an extension to my earlier
definition of "synchronous" - not only should concurrent copies of the
same function be forbidden, but also any objects that are used
elsewhere need to trigger thread-locking while the function is in a
scope that involves those objects.  I don't know how feasible that is.

Eventually pieces of code like the above would need to be rewritten
using atomic functions in order to avoid these problems.  For
instance, (push foo global-list) would work better above because the
push function can be made thread-safe.  I know push is not the
perfect example, but the point is that atomic modifications need to
be done atomically.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Nic Ferrier]

Richard Stallman <rms@gnu.org> writes:

>     I think migrating Emacs towards a threading model is possible:
> 
>     - start with all primitive or ELisp functions assumed NOT thread-safe
> 
>     - allow threads to run, but any access to a function needs to be
>       synchronous.  At first, this will effectively make threads simple
>       switched tasks, and will probably make Emacs slower.
> 
> Many sections of Lisp code would need to have locking in order
> to run correctly with multiple threads.  For instance, everything
> of the form
> 
>   (setq global-list (cons foo global-list))
> 
> would need locking.

And anything doing similar things using dynamic scope as well (at
least when a variable isn't local to the function but from a
previously called function). So that's about everything.


Nic

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

> And anything doing similar things using dynamic scope as well (at
> least when a variable isn't local to the function but from a
> previously called function). So that's about everything.

I think the nastiest aspect I know of is the interaction of dynamic scope
with buffer-local bindings:

  (with-current-buffer A
    (setq default-directory fooA)
    (let ((default-directory barA))
      (with-current-buffer B
        (setq default-directory fooB)
        (let ((default-directory barB))
          (with-current-buffer A default-directory)))))

This will return `barA': i.e. the value of default-directory in buffer A is
temporarilly changed to barA.  But this is a "global" variable (from
a threading point of view) changed by a let-binding (generally considered
as a thread-local, stack-allocated variable).

So I think fine-grained threading in elisp is basically out.
But maybe if we add one lock per buffer and we make `with-current-buffer'
acquire&release the lock we might get a workable model, albeit with
a necessarily very coarse grain which is probably OK for most uses.
Of course, extreme care will still be needed, but that's OK.


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[Robert J. Chassell]

Stefan Monnier <monnier@IRO.UMontreal.CA> wrote:

   But maybe if we add one lock per buffer and we make
   `with-current-buffer' acquire&release the lock we might get a
   workable model, albeit with a necessarily very coarse grain ....

Yes.  From a user interface point of view, the interactive unit is the
buffer (or a closely associated group of buffers, as in Gnus).  Users
work with buffers.  Only programmers, developers, and people on the
emacs-devel list think otherwise.... :)

When a buffer is operating asynchronously, then nothing should affect
it except a Control-c in the buffer itself.  The
process/thread/whatever gets updated *afterwards*.  

>From a user's point of view, when you run the process in the buffer,
it is as if the buffer were run by another instance of Emacs, but with
an environment that is identical to the start of the process.  (Maybe
this is how it is done; a new instance is spawned.)  The independent
buffer process goes on its own.  After it stops, it is updated.  And
after that, maybe, it updates the rest.

   Of course, extreme care will still be needed, but that's OK.

Yes.  Very true!

-- 
    Robert J. Chassell                         Rattlesnake Enterprises
    http://www.rattlesnake.com                  GnuPG Key ID: 004B4AC8
    http://www.teak.cc                             bob@rattlesnake.com

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

Ted Zlatanov <tzz@lifelogs.com> wrote:

> What I proposed is that *all* functions start with the "synchronous"
> atribute.  This would apply to primitives as well.
>
> Then, they would be gradually rewritten.  For instance, a thread-safe
> setq would act just like the regular setq, but it would lock its
> arguments with semaphores before modifying them.  The thread-safe
> setq can then be marked "asynchronous."

What about simply having a single mutex for everything? It's
essentially always held, and a thread only relinquishes it to do
blocking operations. Immediately afterwards it reacquires the lock.

This way Emacs is still effectively single threaded (in the sense that
only one thread runs at a time) but it is possible to use the
threading paradigm to do blocking operations. It's comparatively easy
to implement since all data access still goes on as usual. It's
necessary to make the C level thread safe only in the small regions
where the lock is released.

I take it this would essentially be the same as your starting point,
where all functions are synchronous - nothing runs at the same time as
anything else. There are however only small benefits to go further:

o  To be able to run several threads simultaneously in multicpu or
   hyperthreaded systems.
o  To get OS level preemption between threads.

Preemption can be simulated on the elisp level by making sure that no
significant amount of code gets to run without relinquishing the lock.
I.e. there is a function that gets called regularly that only releases
the lock, yields (if the thread implementation supports it) and then
takes the lock again.

Another possibility is to do no preemption at all, and instead
introduce an elisp function `yield' that does the above. CPU bound
code should call it explicitly every once in a while. That has the
nice property that other elisp code does not have to use locks to
avoid preemption in sensitive areas. This means "old fashioned"
cooperative multitasking, and malfunctioning code can still lock up
everything, but that's not any worse than the situation today so I
don't regard it as a significant problem.

I see these benefits with this model compared to a "fully"
multithreaded variant:

o  Fairly small changes in the C code.
o  No significant change in the elisp execution model, at least not if
   preemption is avoided.
o  Little overhead in locking - there's no fine grained locking on
   individual data structures.

Re: Are there plans for a multi-threaded Emacs?

[Richard Stallman]

Dynamic binding causes no trouble for multiple threads if each thread has
its own binding stack and switching threads swaps the bindings.

However, code like

  (setq global-list (cons foo global-list))

is a completely separate issue.  The problem here is that thread
switching needs to be prevented between the access to global-list
and the modification of global-list.  Of course, the potential
for collision exists because global-list may be referred to elsewhere.
But it does not depend on dynamic bindings.  If nobody ever binds
global-list, if its global binding is the only one, the problem
still occurs.

Re: Are there plans for a multi-threaded Emacs?

[Richard Stallman]

       But maybe if we add one lock per buffer and we make
       `with-current-buffer' acquire&release the lock we might get a
       workable model, albeit with a necessarily very coarse grain ....

A lock on with-current-buffer can't really solve the problem,
because only a few of the functions that modify a buffer
use with-current-buffer.

However, perhaps you're thinking of allowing a few specially-designated
asynchronous threads, each of which would edit only its own buffer or buffers
so that they won't get in each others' way, that might work if the code
that runs in these specially-designated threads is specially written to
be safe in such a thread.

That might be a workable idea.

In other words, there would be one thread that has full capability to run
anything, including old unmodified code, and any number of other threads
that run only specially-designed thread-safe code.  This approach
MIGHT be workable.  The devil is in the details, so someone would
probably have to study them.

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Thu, 04 Dec 2003, mast@lysator.liu.se wrote:

> What about simply having a single mutex for everything? It's
> essentially always held, and a thread only relinquishes it to do
> blocking operations. Immediately afterwards it reacquires the lock.

> I take it this would essentially be the same as your starting point,
> where all functions are synchronous - nothing runs at the same time
> as anything else. There are however only small benefits to go
> further:
> 
> o  To be able to run several threads simultaneously in multicpu or
>    hyperthreaded systems.
> o  To get OS level preemption between threads.

Those two benefits make a big difference.  Today's Pentiums have
hyper-threading technology, so even a single processor can act as
two.  The best cooperative multitasking can't make use of multiple
processors as well as premptive multithreading.  Cooperative
multitasking definitely has benefits - time-critical applications for
instance, but I don't think that applies to Emacs.

> I see these benefits with this model compared to a "fully"
> multithreaded variant:
> 
> o Fairly small changes in the C code.  

> o No significant change in the elisp execution model, at least not
> if preemption is avoided.  

> o Little overhead in locking - there's no fine grained locking on
> individual data structures.

I agree with all those.  Converting a single-threaded application to
multithreaded, especially one as complex as Emacs, is a daunting
task.  I think it's worthwhile.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Thu, 04 Dec 2003, rms@gnu.org wrote:

> Dynamic binding causes no trouble for multiple threads if each
> thread has its own binding stack and switching threads swaps the
> bindings.
> 
> However, code like
> 
>   (setq global-list (cons foo global-list))
> 
> is a completely separate issue.  The problem here is that thread
> switching needs to be prevented between the access to global-list
> and the modification of global-list.  Of course, the potential for
> collision exists because global-list may be referred to elsewhere.
> But it does not depend on dynamic bindings.  If nobody ever binds
> global-list, if its global binding is the only one, the problem
> still occurs.

Why not just lock all other threads that use that global symbol (it is
bound in that thread)?  I apologize if I'm missing the point here.

Ted

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Ted Zlatanov <tzz@lifelogs.com> writes:

> > I see these benefits with this model compared to a "fully"
> > multithreaded variant:
> > 
> > o Fairly small changes in the C code.  
> 
> > o No significant change in the elisp execution model, at least not
> > if preemption is avoided.  
> 
> > o Little overhead in locking - there's no fine grained locking on
> > individual data structures.
> 
> I agree with all those.  Converting a single-threaded application to
> multithreaded, especially one as complex as Emacs, is a daunting
> task.  I think it's worthwhile.

Not everything that is worthwhile gets done.  In order to even have a
minuscule chance of having reasonably parallel executable code, we
need to have lexical instead of dynamic scope.  Parallizing code that
is depending on changes of a global namespace for every involved local
variable is near to impossible.

So changing Emacs' scopes to lexical is a prerequisite for any
meaningful attempt at multithreading, anyway.

If we can't find the resources and volunteers for doing this step, we
will certainly not get beyond to the even more ambitious task of
multithreading for which it is an absolutely indispensible
prerequisite in my opinion.

Apart from giving people perhaps more enthusiasm for working on the
lexical binding problem, I don't see what actually workable
perspectives the multithreading buys us.  Even then, it would be
unfair to suggest people that if their desire is to get
multithreading, that finishing some lexical binding project will make
their goal come into easy reach.  It is a prerequisite in my opinion,
but quite far from making the ultimate goal easy to achieve.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[Nic Ferrier]

> So changing Emacs' scopes to lexical is a prerequisite for any
> meaningful attempt at multithreading, anyway.

Except that it's more important that Emacs uses dynamic scope than
multi-threading. Dynamic scope is _one_ of the reasons Emacs has been
sucessfull. 

rms wrote a paper about the design of Emacs which, I think,
succesfully justifies the choice of dynamic scope:

  http://www.gnu.org/software/emacs/emacs-paper.html


Nic

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

> A lock on with-current-buffer can't really solve the problem,
> because only a few of the functions that modify a buffer
> use with-current-buffer.

I don't think we can have a fool-proof solution short of using separate
processes with explicit communication.  So my proposal is just to allow
wildly dangerous multi-threading and provide a few synchronising constructs
such that if people really want to, they can write multithreaded code,
although at a cost of extreme care.

> However, perhaps you're thinking of allowing a few specially-designated
> asynchronous threads, each of which would edit only its own buffer or buffers
> so that they won't get in each others' way, that might work if the code
> that runs in these specially-designated threads is specially written to
> be safe in such a thread.

Yes, that's the idea.  I was thinking in terms of "what's the minimal amount
of parallelism needed to get similar benefits as current async-I/O (via
process-filters) but for CPU-bound tasks, such as Gnus's construction of the
summary buffer".  I think in all the important cases, the CPU-bound tasks
runs in a single buffer and that buffer is not modified/used by other code,
so locking at that level makes sense.

> MIGHT be workable.  The devil is in the details, so someone would

Yes, my proposition only addresses the issue from a "threading model for
the elisp programmer" point of view.  Given the extensive internal use of
global variables in the C code, a significant amount of code-review would
be needed to get rid of problems such as the regexp.c code being
non-reentrant, unless we do the preemption manually in Feval and even then,
we'll probably encounter unexpected problems.


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

> Dynamic binding causes no trouble for multiple threads if each thread has
> its own binding stack and switching threads swaps the bindings.

That works fine in "normal" dynamically-scoped languaged.
But can we really do that in elisp ?
I mean, how could we make it work in my example of let-binding a buffer-local
variable such as `default-directory' and then switching buffers back and
forth ?  I know such cases are rare but do exist.
Maybe there's a way, but I haven't been able to figure it out ?


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Nic Ferrier <nferrier@tapsellferrier.co.uk> writes:

> > So changing Emacs' scopes to lexical is a prerequisite for any
> > meaningful attempt at multithreading, anyway.
> 
> Except that it's more important that Emacs uses dynamic scope than
> multi-threading. Dynamic scope is _one_ of the reasons Emacs has been
> sucessfull. 
> 
> rms wrote a paper about the design of Emacs which, I think,
> succesfully justifies the choice of dynamic scope:
> 
>   http://www.gnu.org/software/emacs/emacs-paper.html

In this paper, Stallman writes

  It is not necessary for dynamic scope to be the only scope rule
  provided, just useful for it to be available.

And one has to realize the costs associated with dynamic scopes:
essentially it means that every function, no matter how large or
small, receives and uses the global binding table as an implicit
argument.  This has some principal advantages as those outlined by
Stallman in the paper.  It also has huge disadvantages where code
generation and verification are concerned.  Those disadvantages are
what makes the prospect of multithreading in connection with dynamical
scope unrealistic: there will always be contention and locking issues
with the universally accessed resource of the binding table.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[Nic Ferrier]

storm@cua.dk (Kim F. Storm) writes:

> I still wonder why people want multi-threading in Elisp -- IMHO, emacs
> works just fine without it!
> 
> I admit (synchronous) GNUS is a problem, but except for that, I don't
> really see that much code which will benefit vastly from being executed
> by a multi-threaded emacs.
> 
> And for GNUS, you can just run two instances of emacs on your
> multi-tasking OS.
> 
> Likewise, if you have some vast app writting in Elisp, just start
> a second emacs to run it.

I had wanted threads in elisp a while ago when I was working far away
from my home site. I was sending mail using my home MTA from Emacs on
a windows desktop. It was slow, really, really slow at connecting to
the MTA.

I've solved the problem now of course, I use a laptop with GNU on it
and run a local MTA and have that send stuff to my home MTA.

But if Emacs had threads I wouldn't have needed to do that.


Hmmm... maybe if most of the threading issues are with socket
communication then better sentinels would be a good idea. Maybe a
callback API for setting up and reading/writing to sockets would
really useful. Such an API would be a doddle to write of course.


Nic

Re: Are there plans for a multi-threaded Emacs?

[Kim F. Storm]

David Kastrup <dak@gnu.org> writes:

> Ted Zlatanov <tzz@lifelogs.com> writes:
> 
> > I agree with all those.  Converting a single-threaded application to
> > multithreaded, especially one as complex as Emacs, is a daunting
> > task.  I think it's worthwhile.
> 
> Not everything that is worthwhile gets done.  

I don't really agree that this is worthwhile.

IMO, there are many other improvements that are more important than
multi-threading.  Of course, if we had unlimited development _and_
_testing_ resources, it would be a nice thing to add, but I don't like
the idea of adding something _really complex_ like that which may
potentially de-stabilize emacs for a long time.

Even if you add multi-threading to Elisp, the applications need to be
made aware of that.  How much -additional- work would be it be to
rework, say, GNUS to be multi-threaded?

Actually, a lot of code could already be improved today with better
use of process filters and sentinels, but that hasn't been done.
So even if we had multi-threading, I doubt that it would be widely
used.

> So changing Emacs' scopes to lexical is a prerequisite for any
> meaningful attempt at multithreading, anyway.

The lexical binding could be on a per-project or per-file basis,
rather than an over-all change to Elisp.  That would allow projects
which requires multi-threading to use lexical scoping.  _IF_ they
use dynamic scoping, it will result in unexplicable errors, but
the byte-compiler might warn against such uses, so we don't need
run-time checking.

IIRC the plans to add lexical scoping to Elisp is per-file, and
rumours is that there already exist patches to achieve this.

> 
> Apart from giving people perhaps more enthusiasm for working on the
> lexical binding problem, I don't see what actually workable
> perspectives the multithreading buys us.  Even then, it would be
> unfair to suggest people that if their desire is to get
> multithreading, that finishing some lexical binding project will make
> their goal come into easy reach.  It is a prerequisite in my opinion,
> but quite far from making the ultimate goal easy to achieve.

I still wonder why people want multi-threading in Elisp -- IMHO, emacs
works just fine without it!

I admit (synchronous) GNUS is a problem, but except for that, I don't
really see that much code which will benefit vastly from being executed
by a multi-threaded emacs.

And for GNUS, you can just run two instances of emacs on your
multi-tasking OS.

Likewise, if you have some vast app writting in Elisp, just start
a second emacs to run it.

Problem solved!

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk

non-blocking sockets (was Re: Are there plans for a multi-threaded Emacs?)

[Nic Ferrier]

Nic Ferrier <nferrier@tapsellferrier.co.uk> writes:

> Hmmm... maybe if most of the threading issues are with socket
> communication then better sentinels would be a good idea. Maybe a
> callback API for setting up and reading/writing to sockets would
> really useful. Such an API would be a doddle to write of course.

Doh!

Elisp 21 already has non-blocking sockets... I don't remember them
from the last time I did any socket stuff but they are there.

So one big win would be to convert as much network reliant code to
using non-blocking sockets which someone already said.


Since 'open-network-stream-nowait' returns nil when it's not
supported it seems fairly safe to add it to all networking
code. Maybe a new form is needed:

   open-network-stream-nowait-if-possible

which does an nbio connection if it can but otherwise a normal one.


If your system doesn't support nbio then you'll still have to wait
for Emacs threads for faster network connections   /8->


Nic

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

Ted Zlatanov <tzz@lifelogs.com> wrote:

>> o  To be able to run several threads simultaneously in multicpu or
>>    hyperthreaded systems.
>> o  To get OS level preemption between threads.
>
> Those two benefits make a big difference.

The last does not since it's quite feasible to simulate, as I've
outlined. (I know that from practical experience with this threading
model in a language environment fairly similar to elisp.)

> Today's Pentiums have hyper-threading technology, so even a single
> processor can act as two.

True. Hyperthreading is becoming more commonplace.

> The best cooperative multitasking can't make use of multiple
> processors as well as premptive multithreading.

I don't see how preemption per se can improve parallell execution.
Fine grained locking can, but it's hard to avoid making it too fine
grained so that the locking itself becomes more time consuming than
the speedup from the improved parallellism it achieves.

> Cooperative multitasking definitely has benefits - time-critical
> applications for instance, but I don't think that applies to Emacs.

One thing that does apply to Emacs, and very heavily too, is that
cooperative task switching makes it a lot easier to cope with the
threading issues at the application level - it becomes an opt-in
feature instead of an opt-out, i.e. code that doesn't need or want to
bother with thread safety remains safe. This is important even if the
considerable transitional work to thread safe existing code is
disregarded. Thread locking is still a complex issue that easily leads
to bugs (and often very tricky ones too), so it's a big advantage to
not have to bother about it in the vast majority of code.

> /.../ Converting a single-threaded application to multithreaded,
> especially one as complex as Emacs, is a daunting task.  I think it's
> worthwhile.

I gather then that one important goal for you with the thread support
is to make Emacs utilize true parallell execution better, i.e. it's
for performance reasons and not only to let elisp developers take
advantage of the threading paradigm.

I don't regard that performance gain as significant, at least not
compared to the amount of work involved. Emacs is still an interactive
application, and as such it essentially only responds to user actions.
Granted, there are some elisp packages that occasionally can be very
heavily cpu bound, but they are afterall only a few exceptions. The
only case when true parallell execution would improve things are when
two or more such tasks are run concurrently. I regard that as an
extremely rare situation, but you would probably disagree?

Anyway, a way to cope with such heavy tasks could be to make it easy
to fork a separate interpreter with its own data set. It would then
only take the main interpreter lock explicitly and rarely to
communicate its results and request new data, or perhaps even be
restricted to communication through a pipe.

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Martin Stjernholm <mast@lysator.liu.se> writes:

> Ted Zlatanov <tzz@lifelogs.com> wrote:
> 
> >> o  To be able to run several threads simultaneously in multicpu or
> >>    hyperthreaded systems.
> >> o  To get OS level preemption between threads.
> >
> > Those two benefits make a big difference.
> 
> The last does not since it's quite feasible to simulate, as I've
> outlined. (I know that from practical experience with this threading
> model in a language environment fairly similar to elisp.)
> 
> > Today's Pentiums have hyper-threading technology, so even a single
> > processor can act as two.
> 
> True. Hyperthreading is becoming more commonplace.
> 
> > The best cooperative multitasking can't make use of multiple
> > processors as well as premptive multithreading.
> 
> I don't see how preemption per se can improve parallell execution.

It's not preemption, but preemption aware coding, and it does not
improve parallel execution but is a prerequisite for it.

> Fine grained locking can, but it's hard to avoid making it too fine
> grained so that the locking itself becomes more time consuming than
> the speedup from the improved parallellism it achieves.

For that reason it is important to have as few locks necessary as
possible.  And having to lock on the binding table would be
prohibitively expensive.

> Anyway, a way to cope with such heavy tasks could be to make it easy
> to fork a separate interpreter with its own data set. It would then
> only take the main interpreter lock explicitly and rarely to
> communicate its results and request new data, or perhaps even be
> restricted to communication through a pipe.

`fork' is a system call that is not available for a considerable
number of Emacs runtime platforms.  Relying on it might not be the
best choice for such a feature, apart from the obvious problems with
having two copies of Emacs with open buffers of their own around.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[Thien-Thi Nguyen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

   Yes, that's the idea.  I was thinking in terms of "what's the minimal
   amount of parallelism needed to get similar benefits as current
   async-I/O (via process-filters) but for CPU-bound tasks, such as
   Gnus's construction of the summary buffer".  I think in all the
   important cases, the CPU-bound tasks runs in a single buffer and that
   buffer is not modified/used by other code, so locking at that level
   makes sense.

this is a nice idea, the "locked-loopback-buffer" abstraction.  locking
requires declaration of all variables needed to be passed in, unlocking
passes out new values (if any) plus the modified buffer text.  you can
even avoid threads entirely.  for implementation, fork an inferior emacs
and use the already-in-place async-I/O facilities.  two afternoons and a
nap!  who needs multi-threadache anyway?

thi

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

David Kastrup <dak@gnu.org> wrote:

> It's not preemption, but preemption aware coding, and it does not
> improve parallel execution but is a prerequisite for it.

Maybe we have a terminology problem here. I don't regard thread yields
due to blocking operations or cooperative yielding as preemption.
Instead I reserve that term for uncooperative yielding when a time
slice is up. It's perfectly fine to have several executing tasks in
parallell without ever stopping any of them uncooperatively.

>> Fine grained locking can, but it's hard to avoid making it too fine
>> grained so that the locking itself becomes more time consuming than
>> the speedup from the improved parallellism it achieves.
>
> For that reason it is important to have as few locks necessary as
> possible.  And having to lock on the binding table would be
> prohibitively expensive.

Another reason to have only a single interpreter lock and no
preemption. It's hardly so expensive that it would take significant
time compared to blocking operations, is it?

>> Anyway, a way to cope with such heavy tasks could be to make it easy
>> to fork a separate interpreter with its own data set. It would then
>> only take the main interpreter lock explicitly and rarely to
>> communicate its results and request new data, or perhaps even be
>> restricted to communication through a pipe.
>
> `fork' is a system call that is not available for a considerable
> number of Emacs runtime platforms.

Sorry, I was not entirely clear. I meant only starting a new
interpreter with its own data set in some suitable way, be it with a
thread or a new process. The behavior of the unix fork(2) system call
is actually not very suitable since the new interpreter should not
have a copy of all the data in the original instance.

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Martin Stjernholm <mast@lysator.liu.se> writes:

> David Kastrup <dak@gnu.org> wrote:
> 
> > It's not preemption, but preemption aware coding, and it does not
> > improve parallel execution but is a prerequisite for it.
> 
> Maybe we have a terminology problem here. I don't regard thread
> yields due to blocking operations or cooperative yielding as
> preemption.

The whole proposal was geared towards parallel execution of
computation-intensive tasks (like gnus summarizing and scoring) with
the editing foreground task.  If we are not talking about
multithreading, of course talking about preemption is idle.  But if
you remember, one topic that was brought up in this discussion was
hyperthreading.  Cooperative yielding can't make use of
hyperthreading.  Tasks that require cooperative yielding must not
share any resources with any other task in between synchronization
points (yield points, whatever).  So they can't make use of multiple
CPUs available.  For multiple CPUs, you need thread safe programming.

> Instead I reserve that term for uncooperative yielding when a time
> slice is up. It's perfectly fine to have several executing tasks in
> parallel without ever stopping any of them uncooperatively.

But it will not be able to make use of multiple CPUs.  And even with
cooperative multitasking you need separate stacks for several
resources, for every task, or you can only yield when at the top
level of bindings/stacks/whatever.

> >> Fine grained locking can, but it's hard to avoid making it too
> >> fine grained so that the locking itself becomes more time
> >> consuming than the speedup from the improved parallellism it
> >> achieves.
> >
> > For that reason it is important to have as few locks necessary as
> > possible.  And having to lock on the binding table would be
> > prohibitively expensive.
> 
> Another reason to have only a single interpreter lock and no
> preemption. It's hardly so expensive that it would take significant
> time compared to blocking operations, is it?

I don't see any usefulness at all.  Certainly every nontrivial task
will need to use the interpreter?  So where is the gain?

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On 04 Dec 2003, storm@cua.dk wrote:

> David Kastrup <dak@gnu.org> writes:
> 
>> Ted Zlatanov <tzz@lifelogs.com> writes:

>> > Converting a single-threaded application to multithreaded,
>> > especially one as complex as Emacs, is a daunting task.  I think
>> > it's worthwhile.
>> 
>> Not everything that is worthwhile gets done.  
> 
> I don't really agree that this is worthwhile.
> 
> IMO, there are many other improvements that are more important than
> multi-threading.  Of course, if we had unlimited development _and_
> _testing_ resources, it would be a nice thing to add, but I don't
> like the idea of adding something _really complex_ like that which
> may potentially de-stabilize emacs for a long time.

I meant it's worthwhile to add multithreading to Emacs, not that it
should override other, more important tasks for the Emacs developers.
I'm sorry if I gave the wrong impression.

> Even if you add multi-threading to Elisp, the applications need to
> be made aware of that.  How much -additional- work would be it be to
> rework, say, GNUS to be multi-threaded?

Specifically with Gnus the work would be pretty extensive.  Gnus
relies on a lot of buffer-local and global variables.  I'd personally
commit quite a few hours to that project because it will be fun.

> Actually, a lot of code could already be improved today with better
> use of process filters and sentinels, but that hasn't been done.  So
> even if we had multi-threading, I doubt that it would be widely
> used.

I don't think process filters would help much if I wanted to look up
several entries in a hashtable in parallel to build an article
summary buffer.  Right now, doing this sequentially is the only way,
and consequently doing fancy things while building the summary buffer
is not a good idea.

What I mean is, say we have N articles in a mail-group (in Gnus, seen
in the summary buffer).  For each article, I want to look up certain
things in a hashtable.  I am sure that the lookups will not involve
any variable modifications.  I'd rather start N or (fraction of N)
threads than do N sequential lookups.

This is just an example for Gnus, because I'm most familiar with that
application.  I'm sure that other applications, for instance anything
that does parallel independent calculations, will benefit from
multithreading as opposed to process filters or sentinels.

> I still wonder why people want multi-threading in Elisp -- IMHO,
> emacs works just fine without it!

For example, gnuclient could be used to get immediate results instead
of waiting for the current task to complete.  That would be useful.

> I admit (synchronous) GNUS is a problem, but except for that, I
> don't really see that much code which will benefit vastly from being
> executed by a multi-threaded emacs.

I don't think vast improvements can be expected, either.  It will
improve the user experience, though.

> And for GNUS, you can just run two instances of emacs on your
> multi-tasking OS.
> 
> Likewise, if you have some vast app writting in Elisp, just start
> a second emacs to run it.
> 
> Problem solved!

Come on, that's giving up on the problem.  I already run two copies of
Emacs, one for editing and one for Gnus.  There's problems with that.
For instance, files I open in the one that quits first don't get in
the .session file because the second one overwrites the .session
file.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Thu, 04 Dec 2003, mast@lysator.liu.se wrote:

Ted Zlatanov <tzz@lifelogs.com> wrote:

>> The best cooperative multitasking can't make use of multiple
>> processors as well as preemptive multithreading.
> 
> I don't see how preemption per se can improve parallell execution.
> Fine grained locking can, but it's hard to avoid making it too fine
> grained so that the locking itself becomes more time consuming than
> the speedup from the improved parallellism it achieves.

Not all threads need to be aware of each other.  Not all threads will
compete for the same resources.  Not all threads, in a cooperative
setup, will cooperate with each other due to programmer or design
error.  Also, I actually think it's easier to program for preemptive
multithreading because you write thread-safe code instead of
reengineering your code to fit the cooperative model.

>> /.../ Converting a single-threaded application to multithreaded,
>> especially one as complex as Emacs, is a daunting task.  I think
>> it's worthwhile.
> 
> I gather then that one important goal for you with the thread
> support is to make Emacs utilize true parallell execution better,
> i.e. it's for performance reasons and not only to let elisp
> developers take advantage of the threading paradigm.

Yes.

> I don't regard that performance gain as significant, at least not
> compared to the amount of work involved. Emacs is still an
> interactive application, and as such it essentially only responds to
> user actions.  Granted, there are some elisp packages that
> occasionally can be very heavily cpu bound, but they are afterall
> only a few exceptions. The only case when true parallell execution
> would improve things are when two or more such tasks are run
> concurrently. I regard that as an extremely rare situation, but you
> would probably disagree?

It's rare currently because it's not possible.  I think the
application will come once the support for them is built.

Here's more examples: font-locking a buffer; reading or writing a
file.  Cooperative or preemptive multithreading would make them a more
pleasant user experience.

> Anyway, a way to cope with such heavy tasks could be to make it easy
> to fork a separate interpreter with its own data set. It would then
> only take the main interpreter lock explicitly and rarely to
> communicate its results and request new data, or perhaps even be
> restricted to communication through a pipe.

Heavyweight threads are a problem because, as I mentioned already,
Emacs is such a tightly coupled environment.  I think lightweight
threads are better for performance.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

> I don't think process filters would help much if I wanted to look up
> several entries in a hashtable in parallel to build an article
> summary buffer.  Right now, doing this sequentially is the only way,
> and consequently doing fancy things while building the summary buffer
> is not a good idea.

So you want to reduce the time it takes to build a summary buffer?
I agree that it would be good to build the summary buffer "in the
background" so I can do something else during this time, but if you want to
use parallelism to make things faster, then I think you're barking up the
wrong tree: Emacs is not optimized for speed and there are probably much
easier ways to make it faster.  Easier and safer as well (after all,
parallelising doesn't always speed things up, far from it).


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On 04 Dec 2003, monnier@iro.umontreal.ca wrote:

>> I don't think process filters would help much if I wanted to look
>> up several entries in a hashtable in parallel to build an article
>> summary buffer.  Right now, doing this sequentially is the only
>> way, and consequently doing fancy things while building the summary
>> buffer is not a good idea.
> 
> So you want to reduce the time it takes to build a summary buffer?
> I agree that it would be good to build the summary buffer "in the
> background" so I can do something else during this time, but if you
> want to use parallelism to make things faster, then I think you're
> barking up the wrong tree: Emacs is not optimized for speed and
> there are probably much easier ways to make it faster.  Easier and
> safer as well (after all, parallelising doesn't always speed things
> up, far from it).

The point is not to make Emacs *faster* but to make the user
experience better :) When Emacs can *respond* faster due to preemptive
multithreading, the user can start reading a message thread while the
summary buffer is being built, or the user can cancel the summary
build and leave the group if something else came up.  C-g is the only
option to do the latter right now, and for instance nnrss servers in
Gnus can be very slow so I often find myself hitting C-g when they
take too long.  I understand all this can be hacked into place, but
is it really necessary to avoid multithreading so desperately?

Plus, I am pretty sure that when an application uses N processors
instead of one (as Emacs might with true preemptive multithreading)
there is at least some speed improvement.  With the good ole Pentiums
this was not such an issue, but today's processors are definitely
better at simulating multiples (hyperthreading) or cooperating
(Xeons).  I don't have benchmarks, sorry, but at least on Solaris the
performance of a machine increases by at least 80% with each
additional SPARC processor.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

David Kastrup <dak@gnu.org> wrote:

> The whole proposal was geared towards parallel execution of
> computation-intensive tasks (like gnus summarizing and scoring) with
> the editing foreground task.

This discussion thread has been both about how threading should be
solved and what should be achieved with the solution. True parallel
execution is not the only discussed goal. In my opinion that goal is
fairly unimportant - the big win is instead to be able to use the
thread paradigm which in some cases is more convenient than the
alternative, i.e. callback driven programming.

As for the problem with Gnus, a threading model with a global lock is
a worthwhile improvement: It would allow that cpu intensive process to
be interrupted regularly to let Emacs respond to user actions. The big
win here is imho that Emacs remains responsive; it doesn't bother me
at all that the few milliseconds of work to achieve that is added to
the total time of the score buffer generation instead of being carried
out on another cpu.

The issue of preemption at the elisp level only affects what kind of
changes need to be done in Gnus to achieve these regular interrupts:
If there is no preemption, regular yield calls have to be added at
points where the state is consistent enough. Otherwise proper locking
has to be implemented.

> Cooperative yielding can't make use of hyperthreading.

Yes it can. Seems to me you are confusing cooperative yielding and
preemption with the use of a single global lock. A single global lock
prohibits both parallel execution and underlying preemption.
Preemption/cooperative yielding doesn't say anything about the kind of
locking being used.

> Tasks that require cooperative yielding must not share any resources
> with any other task in between synchronization points (yield points,
> whatever).

Depends on what you mean with sharing a resource. To be precise, they
can't leave any shared resource in an inconsistent state across a
yield point, and they can't assume anything about the state of any
shared resource afterwards.

Of course, even in a cooperative environment mutexes are useful to
lock out other threads from a resource that potentially is shared but
that the current thread want to retain exclusive access to.

> And even with cooperative multitasking you need separate stacks for
> several resources, for every task, /.../

Of course. That's one of two things a thread consists of (the other is
a promise of future cpu time).

>> Another reason to have only a single interpreter lock and no
>> preemption. It's hardly so expensive that it would take significant
>> time compared to blocking operations, is it?
>
> I don't see any usefulness at all.  Certainly every nontrivial task
> will need to use the interpreter?  So where is the gain?

Blocking operations, like waiting on a mutex or reading from a file or
socket, can leave the interpreter free to do other things. All
blocking operations can be fixed to not need direct access to the
interpreter data. In many cases it's such blocking operations that
make Emacs unresponsive. The alternative to threads is to rewrite all
such code to use callbacks (and in some cases the OS doesn't even
provide the necessary interface for callbacks, e.g. gethostbyname(3)).

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

> take too long.  I understand all this can be hacked into place, but
> is it really necessary to avoid multithreading so desperately?

Nobody is avoiding it here.  We're just explaining to you why nobody
bothered to do it yet and why none of us feels the urge to do it:
lots of work, unclear payoff.

> Plus, I am pretty sure that when an application uses N processors
> instead of one (as Emacs might with true preemptive multithreading)
> there is at least some speed improvement.

Your being pretty sure does not magically eliminate all the known
counter examples.

> (Xeons).  I don't have benchmarks, sorry, but at least on Solaris the
> performance of a machine increases by at least 80% with each
> additional SPARC processor.

Such naive sweeping claims would tend to ruin your credibility, I'm afraid.
Yes, things can be made to work well, but do you have an idea of the
amount of work it takes to do that ?


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

Ted Zlatanov <tzz@lifelogs.com> wrote:

> Not all threads need to be aware of each other.  Not all threads will
> compete for the same resources.

True, but these are arguments against a single lock. They have nothing
to do with preemption and cooperative yielding. Imho the advantages of
a single lock outweighs these.

> Not all threads, in a cooperative setup, will cooperate with each
> other due to programmer or design error.

Indeed. As I've said earlier, this is already the situation today.
Threads with cooperative yielding would provide a tool which I believe
makes it fairly simple to solve these cases. Some changes are
necessary, but otoh changes are necessary in the preemptive case too
since proper locking needs to be implemented.

> Also, I actually think it's easier to program for preemptive
> multithreading because you write thread-safe code instead of
> reengineering your code to fit the cooperative model.

Well, it's just as much reengineering to thread safe existing code as
to implement cooperative switching in it.

Anyway, it's not really an either-or situation. Thread tools like
mutexes are useful also in a cooperative environment. The difference
is that there's more control of where thread switches can take place
in the cooperative case. It's also possible to add a form like this:

    (auto-yield
      (while (big-task-not-finished)
        (work-on-big-task)))

`auto-yield' would instruct the elisp interpreter to yield
automatically inside the code block whenever it thinks it's time for
it. I.e. you'd get preemption inside that specific code block.

> Here's more examples: font-locking a buffer; reading or writing a
> file.

Reading or writing are blocking operations, so they would be executed
in parallel anyway.

Font locking is otoh cpu bound, but to get advantage of true
parallelism you'd need a situation where you do font locking at the
same time as something else that's cpu bound, e.g. Gnus scoring.
Otherwise it works fine to interrupt it to do display updates and so
on.

> Heavyweight threads are a problem because, as I mentioned already,
> Emacs is such a tightly coupled environment.  I think lightweight
> threads are better for performance.

Yes, I don't think it'd be useful very often either.

This is actually an argument against fine grained locking too: When
much code contend for the same resources and those are covered by many
small locks, much time will be spent in context switching due to
outlocking.

Re: Are there plans for a multi-threaded Emacs?

[Thien-Thi Nguyen]

Ted Zlatanov <tzz@lifelogs.com> writes:

   Plus, I am pretty sure that when an application uses N processors
   instead of one (as Emacs might with true preemptive multithreading)

perhaps you still don't understand the root problem: "true preemptive
multithreading" requires a certain program architecture to take
advantage of it (including but not limited to: how the functions are
written, placement of data, access patterns to the data, external
interface requirements).  if emacs does not have this particular nature,
force-fitting it to make it so is a royal PITA.  if you don't force-fit
it, you will never get the true preemptive multithreading "experience".

   there is at least some speed improvement.  [...]

here's an analogy: rollerskates on two separate people and they both go
fast.  rollerskates on a potato-sack race pair and you get injuries and
lawsuits, coredumps and bug reports.  (and the pair still goes slow.)

thi

Re: non-blocking sockets (was Re: Are there plans for a multi-threaded Emacs?)

[Kim F. Storm]

Nic Ferrier <nferrier@tapsellferrier.co.uk> writes:

> Nic Ferrier <nferrier@tapsellferrier.co.uk> writes:
> 
> > Hmmm... maybe if most of the threading issues are with socket
> > communication then better sentinels would be a good idea. Maybe a
> > callback API for setting up and reading/writing to sockets would
> > really useful. Such an API would be a doddle to write of course.
> 
> Doh!
> 
> Elisp 21 already has non-blocking sockets... I don't remember them
> from the last time I did any socket stuff but they are there.

Yes I know (I added it :-).

Problem is that often people whine about the things that are missing,
rather than trying to use the things that are already there.

> 
> So one big win would be to convert as much network reliant code to
> using non-blocking sockets which someone already said.
> 
Indeed!

Sending and receiving mail could definitely run "in the background"
using non-blocking i/o.

> 
> Since 'open-network-stream-nowait' returns nil when it's not
> supported it seems fairly safe to add it to all networking
> code. Maybe a new form is needed:
> 
>    open-network-stream-nowait-if-possible
> 
> which does an nbio connection if it can but otherwise a normal one.
> 

I considered this when I created the interface (the low-level function
is make-network-process), but I found that there is no general way in
which you could use either nbio or bio with the same sentinels and
filters, as the sequence of events is different.  

IMO it is better not to make an open-network-stream-nowait-if-possible
which pretends it is simpler than it really is!  Using nbio _is_ a
little more tricky that blocking io.

> 
> If your system doesn't support nbio then you'll still have to wait
> for Emacs threads for faster network connections   /8->
> 

Personally, I wouldn't care about such systems.

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On 05 Dec 2003, ttn@glug.org wrote:

> Ted Zlatanov <tzz@lifelogs.com> writes:
> 
>    Plus, I am pretty sure that when an application uses N processors
>    instead of one (as Emacs might with true preemptive
>    multithreading)
> 
> perhaps you still don't understand the root problem: "true
> preemptive multithreading" requires a certain program architecture
> to take advantage of it (including but not limited to: how the
> functions are written, placement of data, access patterns to the
> data, external interface requirements).  if emacs does not have this
> particular nature, force-fitting it to make it so is a royal PITA.
> if you don't force-fit it, you will never get the true preemptive
> multithreading "experience".

You and Stefan are right, I generalized too much.  I meant a specific
type of application, and I think Emacs can be such.  I do understand
the issues involved.  I just wrote carelessly.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Fri, 05 Dec 2003, mast@lysator.liu.se wrote:

> Reading or writing are blocking operations, so they would be
> executed in parallel anyway.

Right, but if the read or write don't need to block the UI thread, why
should they?  Take for example auto-save files.  When I'm editing a
large document on a NFS filesystem, Emacs often will pause completely
while auto-saving the document.  If a separate thread or process could
auto-save the document while I could keep working, that would be very
nice.  It wouldn't add new functionality, but it would improve the
user experience.

> This is actually an argument against fine grained locking too: When
> much code contend for the same resources and those are covered by
> many small locks, much time will be spent in context switching due
> to outlocking.

Yes, this is why Solaris is so slow on single-processor machines also.
Fine-grained locking exacts a baseline penalty.  Multi-threading may
need to be a completely separate branch of Emacs, if it ever happens.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On 05 Dec 2003, ttn@glug.org wrote:

> Ted Zlatanov <tzz@lifelogs.com> writes:
> 
>    Plus, I am pretty sure that when an application uses N processors
>    instead of one (as Emacs might with true preemptive
>    multithreading)
> 
> perhaps you still don't understand the root problem: "true
> preemptive multithreading" requires a certain program architecture
> to take advantage of it (including but not limited to: how the
> functions are written, placement of data, access patterns to the
> data, external interface requirements).  if emacs does not have this
> particular nature, force-fitting it to make it so is a royal PITA.
> if you don't force-fit it, you will never get the true preemptive
> multithreading "experience".

You and Stefan are right, I generalized too much.  I meant a specific
type of application, and I think Emacs can be such.  I've given
several examples of cases where multithreading or any sort of
multitasking would help, and I've repeatedly explained why I think
lightweight threads instead of heavyweight threads would be better
(because of the tight coupling of applications and functions inside
Emacs).  I think preemptive threading in particular will be the most
useful implementation, but cooperative multithreading is a valid
solution as well.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On 04 Dec 2003, monnier@iro.umontreal.ca wrote:

>> take too long.  I understand all this can be hacked into place, but
>> is it really necessary to avoid multithreading so desperately?
> 
> Nobody is avoiding it here.  We're just explaining to you why nobody
> bothered to do it yet and why none of us feels the urge to do it:
> lots of work, unclear payoff.

I was referring to hacking things into place in that particular
example, where multithreading seemed like a natural approach, not the
attitude of this group.  Sorry if it seemed otherwise.  The attitude
of this group of developers is wonderful.

>> Plus, I am pretty sure that when an application uses N processors
>> instead of one (as Emacs might with true preemptive multithreading)
>> there is at least some speed improvement.
> 
> Your being pretty sure does not magically eliminate all the known
> counter examples.

You're right.  I had specific applications in mind, not any general
application.  In the general case that is not necessarily true,
because not all applications can take advantage of multithreading of
course.  I think that Emacs in particular can use it right now, and
that applications will develop in time that will take full advantage
of multithreading.

>> (Xeons).  I don't have benchmarks, sorry, but at least on Solaris
>> the performance of a machine increases by at least 80% with each
>> additional SPARC processor.
> 
> Such naive sweeping claims would tend to ruin your credibility, I'm
> afraid.

OK, here's some Novell benchmarks that show significant increases in
performance with additional processors in Solaris in a particular
application (LDAP server):

http://www.novell.com/info/collateral/docs/4621167.01/4621167.html

I work with Solaris for a living, so I feel justified in making that
claim based on what I know - years of experience, Sun's published
benchmarks, vendors' benchmarks.  I think you'll find that Solaris
specifically is known to scale very well with additional processors,
at the penalty of being pretty slow on a single-processor machine.

The Linux kernel (2.5 especially), to give another example, scales
well with additional processors too, even when hyper-threading instead
of a real additional processor is used.  See this article for an
overview and benchmarks:

http://www-106.ibm.com/developerworks/linux/library/l-htl/

Note I did not say that an *application's* performance increases by at
least 80%.  The machine's performance, given processes or threads
within them that can be effectively run on separate processors by the
OS scheduler, is what increases.  This is generally understood but
perhaps my language was not clear enough.

> Yes, things can be made to work well, but do you have an idea of the
> amount of work it takes to do that ?

Specifically in the context of Emacs, I do not know the internals well
enough to judge that.  I hope I can help with the work in any way I
can, no matter what the eventual "multithreading or not" decision is.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Thien-Thi Nguyen]

Ted Zlatanov <tzz@lifelogs.com> writes:

   Specifically in the context of Emacs, I do not know the internals
   well enough to judge that.  I hope I can help with the work in any
   way I can, no matter what the eventual "multithreading or not"
   decision is.

the decision is made by whoever does the work, so if you decide to do
it, you need to research the internals (such as by participating in this
thread :-).  so far so good.  it seems to me you are on the right track
even if you don't know how far it is to the station...

personally, i would like to see a "multi-threaded emacs" page on the
emacs wiki where thoughts and links to thoughts can accumulate [surf
surf] wow -- even as i ponder this, there is already such a page!  so,
it is now up to you to practice your organizational skills.  the
question is not "why should it be done?" but "who will do it?"

thi

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

Ted Zlatanov <tzz@lifelogs.com> wrote:

> On Fri, 05 Dec 2003, mast@lysator.liu.se wrote:
>
>> Reading or writing are blocking operations, so they would be
>> executed in parallel anyway.
>
> Right, but if the read or write don't need to block the UI thread, why
> should they?

I didn't say they should, rather the opposite. Maybe I wasn't entirely
clear: They would be executed in parallel even with the single lock
approach.

Emacs would handle each event in a different thread (using a thread
pool, probably, since starting threads often aren't cheap) so that the
main thread always remains idle and can respond to new events. Due to
the single lock, there would still be no concurrency problems in code
that isn't adapted.

It's just a matter of reviewing the most important places doing
blocking I/O and turn on unlocked operation there (if it isn't turned
on by default). Note that only the actual system call is run unlocked,
so no surrounding C or elisp code needs to be adapted with locks. What
needs to be done in the review is to add code that rechecks the state
afterwards and fails gracefully if it has changed too much.

A nice thing is that this is opt-in; there's no need to go through and
thread safe everything - even if it only is enabled in a few common
places there's an improvement in responsiveness.

Re: Are there plans for a multi-threaded Emacs?

[Benjamin Riefenstahl]

Hi Ted,


Just an immediate reaction to your examples:

Ted Zlatanov <tzz@lifelogs.com> writes:
> font-locking a buffer;

Isn't font-locking done in parallel (in a cooperative manner) already
with lazy-lock?

> reading or writing a file.

Reading, yes, but writing, I'm not so sure.  I think usually I want to
be sure that a file is completely written, before I start some other
action.

Also I'm sure that both reading and writing can be done asynchronously
without having all of Emacs being multi-threaded.  Even if you don't
have support from the OS this can be implemented with cooperative
means, just reading/writing reasonable chunks during idle time.


benny

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On 04 Dec 2003, monnier@iro.umontreal.ca wrote:

[...]

> >> (Xeons).  I don't have benchmarks, sorry, but at least on Solaris
> >> the performance of a machine increases by at least 80% with each
> >> additional SPARC processor.
> > 
> > Such naive sweeping claims would tend to ruin your credibility,
> > I'm afraid.
> 
> OK, here's some Novell benchmarks that show significant increases in
> performance with additional processors in Solaris in a particular
> application (LDAP server):
> 
> http://www.novell.com/info/collateral/docs/4621167.01/4621167.html
> 
> I work with Solaris for a living, so I feel justified in making that
> claim based on what I know - years of experience, Sun's published
> benchmarks, vendors' benchmarks.

Sun would hardly publish benchmarks centered around applications that
don't gain from multithreading/multitasking.

We are not talking about an LDAP server, but Emacs.  Ironically,
using applications like preview-latex or in general comint-mode,
Emacs will show _vast_ speed improvements (decidedly more than 100%)
under multiprocessor machines for most operating systems, and the
reason is a scheduling anomaly for almost all operating systems on
single processor machines that keeps pipes from getting more than
minimal fill levels: as soon as there is something in the pipe, the
pipe filling process gets starved from CPU, and so even a tight loop
of
  for (;;) write(1,"\n",1);
will never manage to get more than a single character processed by
Emacs' filter functions.  With a multiple CPU box, this does not
happen as the pipe fills even while Emacs is processing the last bit.

I have gotten real time speed improvements even by starting a
completely useless busy loop that would get the scheduler involved
more often than when Emacs and the comint-run application where just
passing the CPU among each other.

So here you have a situation where a two-processor machine will
increase speed by decidedly more than 100%, and that even without
Emacs itself being multithreading.  I'd be careful about just what
conclusions to draw from this.

Similar from Solaris benchmarks.

> Note I did not say that an *application's* performance increases by
> at least 80%.  The machine's performance, given processes or threads
> within them that can be effectively run on separate processors by
> the OS scheduler, is what increases.  This is generally understood
> but perhaps my language was not clear enough.
> 
> Specifically in the context of Emacs, I do not know the internals
> well enough to judge that.  I hope I can help with the work in any
> way I can, no matter what the eventual "multithreading or not"
> decision is.

My personal opinion is that the Lisp machine would need to get
reorganized significantly to even get a modicum of advantage.  And
that implies, among others, a clean separation between global entities
and locally bound entities that I don't see usefully implemented
without lexical binding.  I may sound as though I was riding a hobby
horse here, but I am not involved in that work, and while I consider
it an issue of architectural cleanliness, I have my doubts about the
feasability of change here.  The longer it is postponed, the more
painful a change will get.  And a change in there would bear quite
more consequences to existing Lisp files than, say, the current
garbage collector and memory layout changes.

One may be able to duct tape some measure of multithreading even on
top of pervasive dynamic binding, but to be honest, I fear the
outcome.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Fri, 05 Dec 2003, mast@lysator.liu.se wrote:
> 
> > Reading or writing are blocking operations, so they would be
> > executed in parallel anyway.
> 
> Right, but if the read or write don't need to block the UI thread,
> why should they?  Take for example auto-save files.  When I'm
> editing a large document on a NFS filesystem, Emacs often will pause
> completely while auto-saving the document.  If a separate thread or
> process could auto-save the document while I could keep working,
> that would be very nice.  It wouldn't add new functionality, but it
> would improve the user experience.

And just version of the buffer would it autosave when I was allowed to
edit the file _while_ it was saving it?

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

David Kastrup <dak@gnu.org> wrote:

> And just version of the buffer would it autosave when I was allowed to
> edit the file _while_ it was saving it?

Does it matter? Buffer changes aren't transaction based anyway. For
recovery purposes, it'd be enough if a block of a suitable size, say
256 kb or so, was copied from the buffer to be written asynchronously,
and a marker is used keep track of the position for the next block.

Re: Are there plans for a multi-threaded Emacs?

[Luke A. Olbrish]

Ted Zlatanov <tzz@lifelogs.com> writes:

> You and Stefan are right, I generalized too much.  I meant a specific
> type of application, and I think Emacs can be such.  I've given
> several examples of cases where multithreading or any sort of
> multitasking would help, and I've repeatedly explained why I think
> lightweight threads instead of heavyweight threads would be better
> (because of the tight coupling of applications and functions inside
> Emacs).  I think preemptive threading in particular will be the most
> useful implementation, but cooperative multithreading is a valid
> solution as well.

Lightweight threads versus heavyweight threads?  By lightweight do you
mean user space threads or green threads?  They tend to only provide a
nice abstraction for certain applications, as the operating system
will block the process if any of the user space threads block.  There
is significant evidence to show that event driven models are quite
efficient for single processor machines.  Read the paper: "Flash: an
Efficient and Portable Web Server".  The creators implement an event
driven model for web serving and get significantly better performance
than staple web servers like apache.  Even lightweight threads have
associated baggage with threading and it seems like people think
threading will magically create more processing power.

If you mean lightweight threads in the sense of a general OS
development trend to make OS threading more of a lightweight
operation, then its OS specific and independent of emacs.

-- 
Luke Anthony Olbrish
<luke.olbrish@cc.gatech.edu>

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

I think your plan sounds reasonable, and it's definitely less
disruptive of existing practices.

Ted

non-blocking auto-save (was: Are there plans for a multi-threaded Emacs?)

[Ted Zlatanov]

On Fri, 05 Dec 2003, Benjamin.Riefenstahl@epost.de wrote:

> Also I'm sure that both reading and writing can be done
> asynchronously without having all of Emacs being multi-threaded.
> Even if you don't have support from the OS this can be implemented
> with cooperative means, just reading/writing reasonable chunks
> during idle time.

OK, that would be a very nice feature then if auto-save could be
non-blocking.  Can this be done with the current Emacs feature set?

Thanks
Ted

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On Fri, 05 Dec 2003, luke.olbrish@cc.gatech.edu wrote:

> If you mean lightweight threads in the sense of a general OS
> development trend to make OS threading more of a lightweight
> operation, then its OS specific and independent of emacs.

I have always understood lightweight threads to be those that share
memory space, and heavyweight threads to be those that have a separate
memory space (data, stack, and heap) and are usually separate
processes.  I believe the current Emacs process sentinels allow
heavyweight threading.

Ted

Re: Are there plans for a multi-threaded Emacs?

[Kai Grossjohann]

Miles Bader <miles@lsi.nec.co.jp> writes:

> Consider a simple bit of elisp code:  (setq GLOBAL (cons 'x GLOBAL))
> In a pre-emptively threaded emacs, another thread could run between
> accessing GLOBAL and setting it.  Whoops.

Somebody suggested to avoid this by putting big locks around
everything and then to relax them.

I made the suggestion to "just" let the implementor of the new thread
code worry about such things: if you start a new thread then you're
responsible for letting it run code that doesn't access globals in
problematic ways.

Apparently, the big-lock suggestion is better, but why?

Kai

Re: Are there plans for a multi-threaded Emacs?

[Thien-Thi Nguyen]

Kai Grossjohann <kai@emptydomain.de> writes:

   Apparently, the big-lock suggestion is better, but why?

because it is likely even new code will need to use old code, and if old
code is ignorant of the new conventions, you will have problems.  if new
conventions can be followed in a ways harmonious w/ the old code, you
are ok, but that is not guaranteed.  that is probably the impetus behind
the big-lock approach.

it is like implementing (or even simulating) a flip-flop (dig out your
introductory logic design book): order w/in the device matters although
it doesn't matter outside.

thi

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

Kai Grossjohann <kai@emptydomain.de> wrote:

> Somebody suggested to avoid this by putting big locks around
> everything and then to relax them.

That was me, I guess.

> I made the suggestion to "just" let the implementor of the new thread
> code worry about such things: if you start a new thread then you're
> responsible for letting it run code that doesn't access globals in
> problematic ways.

Would a thread like that would be used from the elisp level?

Re: Are there plans for a multi-threaded Emacs?

[Kai Grossjohann]

Thien-Thi Nguyen <ttn@glug.org> writes:

> because it is likely even new code will need to use old code, and if old
> code is ignorant of the new conventions, you will have problems.  if new
> conventions can be followed in a ways harmonious w/ the old code, you
> are ok, but that is not guaranteed.  that is probably the impetus behind
> the big-lock approach.

I see.  Hm.  I thought that people "just" need to be careful which
"old code" they call.  And if the old code doesn't work, it would get
rewritten.

But I guess the big-lock suggestion leads to bad performance in
problematic cases, whereas my suggestion leads to wrong results in
problematic cases.  And bad performance is better than wrong results.

Kai

Re: Are there plans for a multi-threaded Emacs?

[Kai Grossjohann]

Martin Stjernholm <mast@lysator.liu.se> writes:

> Kai Grossjohann <kai@emptydomain.de> wrote:
>
>> Somebody suggested to avoid this by putting big locks around
>> everything and then to relax them.
>
> That was me, I guess.

Yes.  Sorry for forgetting your name, and I couldn't find the right
post in this huge thread.

>> I made the suggestion to "just" let the implementor of the new thread
>> code worry about such things: if you start a new thread then you're
>> responsible for letting it run code that doesn't access globals in
>> problematic ways.
>
> Would a thread like that would be used from the elisp level?

That was my idea.

Kai

Re: Are there plans for a multi-threaded Emacs?

[Thien-Thi Nguyen]

Kai Grossjohann <kai@emptydomain.de> writes:

   I see.  Hm.  I thought that people "just" need to be careful which
   "old code" they call.  And if the old code doesn't work, it would get
   rewritten.

that's the theory, but in practice even the most simple pieces of new
code rely heavily on old code.  generally, this methodology exposes the
user to an indeterminate window where the extent and impact of the
changes to be made are unknown.  this may be acceptable but there is a
danger that the unknown becomes the permanently unknowable if no one
looks at it.  this is the problem (by design) w/ usloth and their
output, for example.

   But I guess the big-lock suggestion leads to bad performance in
   problematic cases, whereas my suggestion leads to wrong results in
   problematic cases.  And bad performance is better than wrong results.

that's a very succinct way to put it!

thi

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

Kai Grossjohann <kai@emptydomain.de> wrote:

>>> I made the suggestion to "just" let the implementor of the new thread
>>> code worry about such things: if you start a new thread then you're
>>> responsible for letting it run code that doesn't access globals in
>>> problematic ways.
>>
>> Would a thread like that be used from the elisp level?
>
> That was my idea.

I think a very sound design principle is to keep apart errors on
different implementation levels. I.e. bugs on a higher level shouldn't
have effects on a lower. E.g. if you make an elisp error, say moving
the point and changing the same buffer from two threads, you shouldn't
get an internally inconsistent buffer state which likely will cause
Emacs to dump core later on or disbehave in subtle ways (maybe some
markers get lost and simply cease to be kept up-to-date). The elisp
programmer would have a hard time tracking down an error like that,
and would probably report it as a bug in the core instead.

Another problem related to that is that the elisp programmer would
need to have extensive knowledge of the internals to know what would
be safe to do. For instance, all buffers are linked together, which
means there would probably be a race simply creating a new buffer from
a thread. That's not obvious to the elisp programmer - buffers appear
to be independent entities in elisp.

Also, it wouldn't only be a matter of adding a `create-thread' elisp
function and leave the rest to the elisp hacker. It'd still be
necessary to do away with the global state used directly by the
interpreter, e.g. the binding environment (which I've gathered is
global now). I.e. potentially a lot of global variables would have to
be moved to some thread state struct, and all the code that access
them must be updated accordingly. Something similar would of course be
necessary for the single lock solution too, but in that case it would
suffice to have swap functions that copies and restores the global
state from a thread state struct, so the code that uses global
variables wouldn't have to be changed.

I also suspect the garbage collector would be a problem if it isn't
inherently thread safe. It probably needs to have a lock that excludes
all other activities while it runs.

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

>>> (Xeons).  I don't have benchmarks, sorry, but at least on Solaris
>>> the performance of a machine increases by at least 80% with each
>>> additional SPARC processor.
>> 
>> Such naive sweeping claims would tend to ruin your credibility, I'm
>> afraid.

> OK, here's some Novell benchmarks that show significant increases in
> performance with additional processors in Solaris in a particular
> application (LDAP server):

> http://www.novell.com/info/collateral/docs/4621167.01/4621167.html

> I work with Solaris for a living, so I feel justified in making that
> claim based on what I know - years of experience, Sun's published

Solaris is indeed fairly well designed w.r.t scalability (at the cost of
single-proc performance, of course).  But that only means that Solaris is
not an obstacle: it will not magically make your application scalable
unless your application was designed for it.

Making Emacs scalable is probably best done by starting all over
from scratch.  The current structure of the C code together with the
semantics of elisp means that it's about as far from scalable as you'll
ever get.

Now, that doesn't mean you can't do it, but just that it's going to be a lot
of work and it might introduce subtle incompatibilities, so you need a lot
of motivation to start the effort and you'll need really good arguments to
convince RMS that breaking compatibility is worth the pay off.  Now what is
the payoff ?  Speed.  Given the fact that elisp is known to be slow, and
that pretty much no work has been done to speed up Emacs in the last
N years, I get the impression that nobody really cares about speed here.

What people do care about a little is the "non-blocking thingy" which might
require some form of multithreading but does not require any kind of
scalability and does not require nearly as much work (and as much breakage
of backward compatibility).
So I'd recommend people start with this if they want to work on something
like that.  Once this is done, we might be able to start thinking about
scalability.


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[Stefan Monnier]

> efficient for single processor machines.  Read the paper: "Flash: an
> Efficient and Portable Web Server".  The creators implement an event
> driven model for web serving and get significantly better performance
> than staple web servers like apache.  Even lightweight threads have

Note that there's a reason why Apache does not use an event-driven approach:
it's a lot more painful to write.  So comparing performance of X with Apache
is kind of like comparing the performance of sed with the performance of
Emacs.  Except that some people do try to make Apache faster (even though
it's not the main focus of development, far from it), whereas noone does
that for Emacs.

So I think if we want some kind of parallelism, the most important aspect
for Emacs would be convenience of elisp coding rather than efficiency.


        Stefan


PS: by the way, single-proc multithreading using an event-driven model
    can be done (and is done) in Emacs with the current code-base.
    It's just inconvenient and thus little used.

Re: Are there plans for a multi-threaded Emacs?

[Luke A. Olbrish]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> efficient for single processor machines.  Read the paper: "Flash: an
>> Efficient and Portable Web Server".  The creators implement an event
>> driven model for web serving and get significantly better performance
>> than staple web servers like apache.  Even lightweight threads have
>
> Note that there's a reason why Apache does not use an event-driven approach:
> it's a lot more painful to write.  So comparing performance of X with Apache
> is kind of like comparing the performance of sed with the performance of
> Emacs.  Except that some people do try to make Apache faster (even though
> it's not the main focus of development, far from it), whereas noone does
> that for Emacs.

My comments stem more from Ted's use of various thread implementation
keywords than the concept of threads.

It is very true that threading models tend to be more flexible than
event driven models.  Though I wonder if some more thought was put
into building an event driven paradigm for a language, if programmers
could often get what they want without resorting to threads.  Many
programmers do not know how to properly create threaded programs.
Ideally, a nice event driven mechanism and a nice threading mechanism
would exist and programmers would be free to choose the best paradigm
for their program.

> So I think if we want some kind of parallelism, the most important aspect
> for Emacs would be convenience of elisp coding rather than efficiency.

Well if we are going to get into a discussion of the convenience of
elisp, maybe its time to discuss dynamic scoping.  This would be a
personal peeve though and many mind find the willy-nilly identifier
capabilities of dynamic scoping to be convenient.

-- 
Luke Anthony Olbrish
<luke.olbrish@cc.gatech.edu>

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On 07 Dec 2003, monnier@iro.umontreal.ca wrote:

> Making Emacs scalable is probably best done by starting all over
> from scratch.  The current structure of the C code together with the
> semantics of elisp means that it's about as far from scalable as
> you'll ever get.
> 
> Now, that doesn't mean you can't do it, but just that it's going to
> be a lot of work and it might introduce subtle incompatibilities, so
> you need a lot of motivation to start the effort and you'll need
> really good arguments to convince RMS that breaking compatibility is
> worth the pay off.  Now what is the payoff ?  Speed.  Given the fact
> that elisp is known to be slow, and that pretty much no work has
> been done to speed up Emacs in the last N years, I get the
> impression that nobody really cares about speed here.

I have faith that the applications will come, once the core supports
them.  Just think, for instance, of a mapcar that spreads out onto as
many processors as possible - doesn't that sound exciting?

In addition, I should point out that speed in itself is not my stated
goal.  Yes, maybe there will be some speed improvements, but that's
not what I've been asking for.  Multithreading makes software more
responsive to the user, especially if the UI thread can be separated
from the other threads.  Even if the software is actually slower, it
will serve the user better when it's more responsive, and it will seem
faster.  I'm generalizing quite a bit, but have you ever waited for a
web browser to load all the images before proceeding to use the web
page?  That's what using Emacs feels like sometimes, as wonderful as
it is.

That being said, I realize that asking the Emacs developers to drop
other work to write multi-threading support is a tough call, and I'm
not the one to make it.  I just hope the core developers get excited
enough about the possibilities that they will plan for some sort of
multithreading.

> What people do care about a little is the "non-blocking thingy"
> which might require some form of multithreading but does not require
> any kind of scalability and does not require nearly as much work
> (and as much breakage of backward compatibility).  So I'd recommend
> people start with this if they want to work on something like that.
> Once this is done, we might be able to start thinking about
> scalability.

I'm convinced, based on the many posts made, that the best way to
approach multithreading is slowly and incrementally.  I would not
dream of imposing any particular implementation, but it does seem that
most people prefer a single "main" thread and no preemption, since
those would preserve backwards compatibility best.

Ted

Re: Are there plans for a multi-threaded Emacs?

[David Kastrup]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On 07 Dec 2003, monnier@iro.umontreal.ca wrote:
> 
> > Now, that doesn't mean you can't do it, but just that it's going
> > to be a lot of work and it might introduce subtle
> > incompatibilities, so you need a lot of motivation to start the
> > effort and you'll need really good arguments to convince RMS that
> > breaking compatibility is worth the pay off.  Now what is the
> > payoff ?  Speed.  Given the fact that elisp is known to be slow,
> > and that pretty much no work has been done to speed up Emacs in
> > the last N years, I get the impression that nobody really cares
> > about speed here.
> 
> I have faith that the applications will come, once the core supports
> them.  Just think, for instance, of a mapcar that spreads out onto
> as many processors as possible - doesn't that sound exciting?

No.  We are talking about an editor here, not a number crunching
package.  One fundamental difference is that a vast majority of Emacs
Lisp constructs is _supposed_ to have side effects, in spite of being
written in a functional language.

> In addition, I should point out that speed in itself is not my
> stated goal.  Yes, maybe there will be some speed improvements, but
> that's not what I've been asking for.  Multithreading makes software
> more responsive to the user, especially if the UI thread can be
> separated from the other threads.  Even if the software is actually
> slower, it will serve the user better when it's more responsive, and
> it will seem faster.  I'm generalizing quite a bit, but have you
> ever waited for a web browser to load all the images before
> proceeding to use the web page?  That's what using Emacs feels like
> sometimes, as wonderful as it is.

Emacs is not a browser, it is an editor.  If I execute some keystrokes
that will mark a region and then press the delete key before the
operation that will mark the region actually has completed, I won't be
happy if it instead deletes what happens to be at the time marked by
something else.  I don't want Emacs to start executing keystrokes
before it has processed the previous keystrokes.  I _want_ Emacs in
general to process the things in the correct order when editing.

> That being said, I realize that asking the Emacs developers to drop
> other work to write multi-threading support is a tough call, and I'm
> not the one to make it.  I just hope the core developers get excited
> enough about the possibilities that they will plan for some sort of
> multithreading.

See above comment from Stefan.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Are there plans for a multi-threaded Emacs?

[Ted Zlatanov]

On 08 Dec 2003, dak@gnu.org wrote:

> We are talking about an editor here, not a number crunching package.

> Emacs is not a browser, it is an editor.

David, with all due respect, this is not correct.  Applications such
as Gnus (pretty heavy on arithmetic for article scoring, for instance)
and eshell make Emacs much more than an editor.  W3, which I'm sure
you are aware of, is a full-featured web browser.  There is a
spreadsheet package for Emacs.  Clearly, Emacs is being used for many
tasks, often at the same time.

> If I execute some keystrokes that will mark a region and then press
> the delete key before the operation that will mark the region
> actually has completed, I won't be happy if it instead deletes what
> happens to be at the time marked by something else.  I don't want
> Emacs to start executing keystrokes before it has processed the
> previous keystrokes.  I _want_ Emacs in general to process the
> things in the correct order when editing.

I agree with you.

Ted

What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Luke Gorrie]

Ted Zlatanov <tzz@lifelogs.com> writes:

> I'm convinced, based on the many posts made, that the best way to
> approach multithreading is slowly and incrementally.

What's the biggest problem that threads are intended to solve?

Is it that it's too hard or ugly to write concurrent programs in Elisp
today? If so, what are some examples of bad cases that cause users
pain and _really_ can't be rewritten neatly and with happy concurrency
properties in plain old Elisp after some rethinking?

(Sorry if I have missed definitive examples earlier in the thread!)

People are writing concurrent programs in Elisp today. Most programs
interacting with external processes and sockets do so without blocking
Emacs. Can't we all just do the same?

Cheers,
Luke

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Ted Zlatanov]

On 08 Dec 2003, luke@bluetail.com wrote:

> What's the biggest problem that threads are intended to solve?

(I'm talking about my own comments in this thread, and I'll try to
summarize things)

The interactive user experience, when tasks can be parallelized or
backgrounded, could be *improved.*  This is not a problem to be
solved, it's an incremental improvement from the user's viewpoint.

> Is it that it's too hard or ugly to write concurrent programs in
> Elisp today? If so, what are some examples of bad cases that cause
> users pain and _really_ can't be rewritten neatly and with happy
> concurrency properties in plain old Elisp after some rethinking?

Note I don't claim these can't be rewritten in a concurrent fashion.
I simply gave examples that could stand to be improved.  The majority
of examples are in Gnus, because that's the Elisp application I know
best.

- auto-save on a slow file system or through Tramp

- Gnus mail retrieval, summary thread building, registry lookups

- independent hashtable lookups and calculations in parallel would be
  a very nice improvement in themselves, and I'm sure there are many
  applications that can use them

> People are writing concurrent programs in Elisp today. Most programs
> interacting with external processes and sockets do so without
> blocking Emacs. Can't we all just do the same?

There seems to be interest in a real multithreading solution, be it
cooperative or preemptive, or an event-driven API.  I'm OK with any
solution as long as it improves the user experience, and I'll work
with whatever API is best.  I would like that API to exist, though,
and that doesn't seem to be the case with concurrency in Emacs
today.  Am I wrong?

If it appears from this thread that I have a particular interest in a
radical rewrite of Emacs, that is not true.  It just seems to me,
because of the tight internal coupling of Emacs functions and
variables, that lightweight threads would be a good choice for the
internal implementation of the API because they have less baggage
than process sentinels and share data more easily.  I also mentioned
that today's hardware and OS support for it generally means that
either multiple processors or the illusion of them is available to
applications that are willing to make use of those capabilities.

Ted

Re: What's the problem?

[Simon Josefsson]

Luke Gorrie <luke@bluetail.com> writes:

> Ted Zlatanov <tzz@lifelogs.com> writes:
>
>> I'm convinced, based on the many posts made, that the best way to
>> approach multithreading is slowly and incrementally.
>
> What's the biggest problem that threads are intended to solve?
>
> Is it that it's too hard or ugly to write concurrent programs in Elisp
> today?

It is too hard and ugly to write concurrent programs in elisp today,
but that is not the only reason.

> If so, what are some examples of bad cases that cause users pain and
> _really_ can't be rewritten neatly and with happy concurrency
> properties in plain old Elisp after some rethinking?
>
> (Sorry if I have missed definitive examples earlier in the thread!)
>
> People are writing concurrent programs in Elisp today. Most programs
> interacting with external processes and sockets do so without blocking
> Emacs. Can't we all just do the same?

No.

I believe several examples have been given already, but the most
prominent I notice frequently is generating summary buffers in Gnus.
This is CPU bound.  Most of the time is NOT spent waiting from network
IO, even for 64kbps users, if you profile large groups.  It is spent
traversing internal data structures, sorting and filtering the
headers.  If this is done asynchronously, it would still lock up
Emacs.

Another example is getting new mail in Gnus.  This is probably more
network bound than CPU bound, but doing it asynchronously would still
lock up Emacs completely for many seconds, which is unacceptable.  If
you use Gnus as a offline reader, getting new mail may take minutes.

The most interesting examples doesn't exist, though, because people
have simply not implemented some ideas because of a lack of
multi-threaded support in Emacs.  If developers realized you could
have a background thread in Emacs doing various calculations and
giving the user feedback or interaction opportunities once in a while,
I'm sure we'd see many interesting add-on packages.  (SETI@Emacs?)

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[David Kastrup]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On 08 Dec 2003, luke@bluetail.com wrote:
> 
> > What's the biggest problem that threads are intended to solve?
> 
> Note I don't claim these can't be rewritten in a concurrent fashion.
> I simply gave examples that could stand to be improved.  The
> majority of examples are in Gnus, because that's the Elisp
> application I know best.

Have you already done the obvious thing of setting gnus-asynchronous
to a non-nil value?  That's the least one would expect from somebody
that wants parallelism that badly.

> - auto-save on a slow file system or through Tramp

So that if autosave starts saving a file and is half through when I
decide that the first half of the file is junk I won't need and delete
it, Emacs finds itself having saved more than enough material and
stops writing, never saving the remaining _important_ part of the
file?

You can't just throw in parallelism and hope that things will work
out somehow.

> - Gnus mail retrieval, summary thread building, registry lookups

Most of those can be controlled with gnus-asynchronous and
subordinate variables.

> - independent hashtable lookups and calculations in parallel would
>   be a very nice improvement in themselves,

Why?  What time-critical code performs them frequently?

> > People are writing concurrent programs in Elisp today. Most
> > programs interacting with external processes and sockets do so
> > without blocking Emacs. Can't we all just do the same?
> 
> There seems to be interest in a real multithreading solution, be it
> cooperative or preemptive, or an event-driven API.

The interest I have heard voiced so far has not been overly correlated
with intimate technical knowledge about the details involved and the
actual differences this would make for everyday work.

> If it appears from this thread that I have a particular interest in
> a radical rewrite of Emacs, that is not true.  It just seems to me,
> because of the tight internal coupling of Emacs functions and
> variables, that lightweight threads would be a good choice for the
> internal implementation of the API because they have less baggage
> than process sentinels and share data more easily.

And sharing data more easily is exactly what one can't afford in a
language with dynamic binding, since you get no closures whatsoever.
If I have something like

(let ((x (+ y 2)))
  do something)

then I can't afford to have some other thread change the meaning of x
in his own (let ((x ... construct.  If you want to afford a separate
binding stack for every thread, this also means that every _read_
_access_ to a symbol must run via the thread's binding stack instead
of just using the stack whenever the a binding _changes_.

And it is not only local variables that get temporarily bound: there
are common constructs like
(let ((process-connection-type nil)) [...])
where global variables get some value for some short duration.

> I also mentioned that today's hardware and OS support for it
> generally means that either multiple processors or the illusion of
> them is available to applications that are willing to make use of
> those capabilities.

Applications don't have a will of their own, even though it sometimes
may appear so.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Stefan Monnier]

> There seems to be interest in a real multithreading solution, be it
> cooperative or preemptive, or an event-driven API.  I'm OK with any

The event-drive API is available right now (see process-filters and
run-with-idle-timer), but people don't like it too much.  Especially
writing background tasks using run-with-idle-timer is inconvenient.

The next step is to provide a simple multithreading model which will
simply allow the same as the current event-driven API but more conveniently
(i.e. something like cooperative multithreading, or even with a bit of
preemption, but probably all the switching done by hand in the elisp
interpreter: no concurrency inside the C code).

As for true parallelism, as I said the only use for it is speed, so I don't
see it as particularly important.  But maybe within 10-20 years things will
have changed a little.


        Stefan

Re: Are there plans for a multi-threaded Emacs?

[Martin Stjernholm]

David Kastrup <dak@gnu.org> wrote:

> /.../ If I execute some keystrokes that will mark a region and then
> press the delete key before the operation that will mark the region
> actually has completed, I won't be happy if it instead deletes what
> happens to be at the time marked by something else. /.../

That sounds like the first bug that would be fixed after a nonblocking
command loop has been implemented. It's hardly an argument against
such a thing in general. There are still many cases where the
responsiveness can be improved. Threads (or one-shot continuations, if
you like) often makes it easier to accomplish that, especially when it
comes to fixing old applications which are written with blocking
operations (since changing them to be event driven is more or less
turning them inside-out).

As for keyboard input, I don't think one ever wants to parallelize it,
not even when loading a large file or starting Gnus. It could however
be nice to put an executing command "in the background", just like you
can press C-z bg RET in a shell if you find that a command takes too
long. That'd be a really neat feature, actually.

Things that should run in the background by default are instead those
that are trigged by non-user activities, such as timers running out,
network traffic, and display redraws.


If a thread or continuation facitility is implemented, I have some
ideas for the elisp interface to make it comparatively easy to adapt
existing code to a reasonable degree of parallelism (not to be
confused with true multi-cpu parallelism). It's basically the idea
about buffer local threads discussed earlier in this discussion
thread, but outlined in more detail:

o  There are two kinds of locks: One for everything and one for each
   buffer's local data.(*)

o  There is a form similar to `interactive' that declares a function
   to be buffer local.

o  Events that preferably should run in the background (i.e. anything
   but input events from the user, afaics) check if the function being
   called is declared as buffer local.

o  Functions declared as buffer local are allowed to run until they
   access some buffer local data, and the lock for that buffer is then
   taken automatically.

o  The global lock is taken for other functions. That implies taking
   the buffer locks for all buffers. The functions will run just like
   today.

o  If only a buffer lock is taken, the function and all code it calls
   are allowed to change the buffer local data. Any attempt to change
   global data will give an error, but reading it is fine.

o  Whenever a buffer local function waits in blocking I/O or is
   preempted (cooperative multitasking isn't necessary), a function
   local to another buffer can run. This is the improvement. Given
   that almost all activities in Emacs are correlated to a single
   buffer, this should be a common situation.

The important points with this model are that it is free from all
possible deadlocks and races, and that it gives good errors which
makes it relatively easy to adapt existing code. To improve the
parallelism of a certain piece of code, simply declare the callback as
buffer local and then run until the global write error occurs.
Investigate the error and remove the global change. Repeat.

The byte compiler can already track call trees. With a bit of work it
could probably be extended to check for global writes from buffer
local functions at compile time.

The locking model can of course be refined further. Primitives should
be available to let the elisp programmer explicitly disable this
safety net and implement custom locking instead, at least to the
extent that several threads holds the same buffer lock (allowing it
for the global lock is more questionable).


*)  Note that these are elisp level locks; on the C level there can
    still be a single "everything" lock without sacrificing
    responsiveness, as has been discussed earlier. That would probably
    avoid considerable internal complexity since things aren't as well
    separated into buffer contexts there as they appear to be on the
    elisp level.

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Martin Stjernholm]

David Kastrup <dak@gnu.org> wrote:

> So that if autosave starts saving a file and is half through when I
> decide that the first half of the file is junk I won't need and delete
> it, Emacs finds itself having saved more than enough material and
> stops writing, never saving the remaining _important_ part of the
> file?

That wouldn't happen if a marker is used to point to the beginning of
the unsaved part of the buffer.

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Ted Zlatanov]

On 08 Dec 2003, dak@gnu.org wrote:

> Ted Zlatanov <tzz@lifelogs.com> writes:
> 
>> Note I don't claim these can't be rewritten in a concurrent
>> fashion.  I simply gave examples that could stand to be improved.
>> The majority of examples are in Gnus, because that's the Elisp
>> application I know best.
> 
> Have you already done the obvious thing of setting gnus-asynchronous
> to a non-nil value?  That's the least one would expect from somebody
> that wants parallelism that badly.

I'm fairly familiar with Gnus.  gnus-asynchronous helps pre-fetch
articles, which is nice but tangential to the issues raised here.

> You can't just throw in parallelism and hope that things will work
> out somehow.

I was aware of that fact.

>> - Gnus mail retrieval, summary thread building, registry lookups
> 
> Most of those can be controlled with gnus-asynchronous and
> subordinate variables.

Only pre-fetching of articles, which is not the problem most of the
time.

>> - independent hashtable lookups and calculations in parallel would
>>   be a very nice improvement in themselves,
> 
> Why?  What time-critical code performs them frequently?

1) It's hard to write code that does parallel calculations when there
   is no API and no internal support.  Most current Emacs code would
   not use parallel calculations because if was not written with that
   in mind.  As you appropriately mention above, you can't just throw
   in parallelism, applications have to be written for it.

2) The improvement is incremental, for the user's benefit.  Emacs
   will not gain speed or simplicity, but users will gain improved
   responsiveness and will be happier using Emacs.

> If you want to afford a separate binding stack for every thread,
> this also means that every _read_ _access_ to a symbol must run via
> the thread's binding stack instead of just using the stack whenever
> the a binding _changes_.

So you're saying that it will slow down Emacs by using memory and CPU,
to manage the thread-local binding stack, correct?  I agree.

Ted

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Ted Zlatanov]

On 08 Dec 2003, monnier@iro.umontreal.ca wrote:

> The event-drive API is available right now (see process-filters and
> run-with-idle-timer), but people don't like it too much.  Especially
> writing background tasks using run-with-idle-timer is inconvenient.

> The next step is to provide a simple multithreading model which will
> simply allow the same as the current event-driven API but more
> conveniently (i.e. something like cooperative multithreading, or
> even with a bit of preemption, but probably all the switching done
> by hand in the elisp interpreter: no concurrency inside the C code).

I would be glad to help with any of this, to the best of my
abilities.  Do you think it's better as a patch, separate branch, or
built into the core?  What can I do to help?

> As for true parallelism, as I said the only use for it is speed, so
> I don't see it as particularly important.  But maybe within 10-20
> years things will have changed a little.

In 10-20 years we'll all be running Emacs neural implants :)

Thanks
Ted

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[David Kastrup]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On 08 Dec 2003, dak@gnu.org wrote:
> 
> > If you want to afford a separate binding stack for every thread,
> > this also means that every _read_ _access_ to a symbol must run
> > via the thread's binding stack instead of just using the stack
> > whenever the a binding _changes_.
> 
> So you're saying that it will slow down Emacs by using memory and
> CPU, to manage the thread-local binding stack, correct?  I agree.

Do you have an idea what figure we are speaking about here?  I repeat:
_every_ access to a symbol that now works directly instead has to work
via stack pointers.  And CPUs like the x86 do not have spare address
registers flying around.

We are quite probably talking about a _significant_ slowdown of the
Lisp machine here.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Stefan Monnier]

> I would be glad to help with any of this, to the best of my
> abilities.  Do you think it's better as a patch, separate branch, or
> built into the core?

I doubt RMS would accept it into the core without first seeing a patch
for it.  I'd recommend you create your own "arch branch" so you can extract
a patch for it later.  Ask Miles about how to use Arch to access the
Emacs repository.

> What can I do to help?

Get hacking.

> In 10-20 years we'll all be running Emacs neural implants :)

That's so old school.
I just use M-x esp RET


        Stefan

Re: What's the problem?

[Juri Linkov]

Simon Josefsson <jas@extundo.com> writes:
> Luke Gorrie <luke@bluetail.com> writes:
>> People are writing concurrent programs in Elisp today. Most programs
>> interacting with external processes and sockets do so without blocking
>> Emacs. Can't we all just do the same?
>
> No.
>
> I believe several examples have been given already, but the most
> prominent I notice frequently is generating summary buffers in Gnus.
> This is CPU bound.  Most of the time is NOT spent waiting from network
> IO, even for 64kbps users, if you profile large groups.  It is spent
> traversing internal data structures, sorting and filtering the
> headers.  If this is done asynchronously, it would still lock up
> Emacs.

Many CPU bound tasks can be improved by memoizing computation results.
Since most cited here example is generating summary buffers in Gnus,
I want to note that this particular problem can be solved by storing
computed thread trees in files similar to `.marks' and `.overview'.
To keep track of computed results input parameters should be stored
along with computed data.

> Another example is getting new mail in Gnus.  This is probably more
> network bound than CPU bound, but doing it asynchronously would still
> lock up Emacs completely for many seconds, which is unacceptable.  If
> you use Gnus as a offline reader, getting new mail may take minutes.

Many tasks can be performed by external processes.  Getting new mail
shouldn't lock up Emacs when done by an external program like movemail.

> The most interesting examples doesn't exist, though, because people
> have simply not implemented some ideas because of a lack of
> multi-threaded support in Emacs.  If developers realized you could
> have a background thread in Emacs doing various calculations and
> giving the user feedback or interaction opportunities once in a while,
> I'm sure we'd see many interesting add-on packages.  (SETI@Emacs?)

I believe too that implementing multi-threaded support in Emacs
will create more possibilities for new and existing Emacs packages,
for instance, for such computation-intensive tasks as rendering
markup languages and for creating a better web browser in Emacs.

-- 
http://www.jurta.org/emacs/

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Stefan Monnier]

> Do you have an idea what figure we are speaking about here?  I repeat:
> _every_ access to a symbol that now works directly instead has to work
> via stack pointers.  And CPUs like the x86 do not have spare address
> registers flying around.

I wouldn't worry too much about speed: there's lots of room for optimization
in the interpreter.  The problem I see is one of semantics because looking
up bindings in the stack doesn't seem to work so great when you take into
account interaction with buffer-local variables.
That is: it tends to give you subtly different semantics than the
current one.


        Stefan

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Martin Stjernholm]

David Kastrup <dak@gnu.org> wrote:

> Do you have an idea what figure we are speaking about here?  I repeat:
> _every_ access to a symbol that now works directly instead has to work
> via stack pointers. /.../

Not necessarily. State swapping can be used if only a single thread is
running at a time. I have explained how such a "limited" solution
still can give a worthwhile improvement.


I haven't yet seen any response to those constructive contributions to
this discussion that motivates they would be infeasible or
meaningless. I truly believe I have proposed a viable solution, but
the lack of comment on it is disappointing.


> And CPUs like the x86 do not have spare address registers flying
> around.

Appearance can deceive. I've heard all reasonably modern x86 cpu:s
have quite a lot of registers. They're just not accessible through the
archaic machine code format, so elaborate register renaming algorithms
are used instead.

Not that I particularly advocate making the binding environment thread
local, for the pragmatic reason of the amount of code change I fear
would be involved.

> We are quite probably talking about a _significant_ slowdown of the
> Lisp machine here.

I'm not at all certain of that; cpu optimizations can slant these
things in unexpected directions. It wouldn't surprise me if an extra
indirection on the stack is faster than a global variable due to
better memory locality.

Re: What's the problem?

[Simon Josefsson]

Juri Linkov <juri@jurta.org> writes:

> Simon Josefsson <jas@extundo.com> writes:
>> Luke Gorrie <luke@bluetail.com> writes:
>>> People are writing concurrent programs in Elisp today. Most programs
>>> interacting with external processes and sockets do so without blocking
>>> Emacs. Can't we all just do the same?
>>
>> No.
>>
>> I believe several examples have been given already, but the most
>> prominent I notice frequently is generating summary buffers in Gnus.
>> This is CPU bound.  Most of the time is NOT spent waiting from network
>> IO, even for 64kbps users, if you profile large groups.  It is spent
>> traversing internal data structures, sorting and filtering the
>> headers.  If this is done asynchronously, it would still lock up
>> Emacs.
>
> Many CPU bound tasks can be improved by memoizing computation results.
> Since most cited here example is generating summary buffers in Gnus,
> I want to note that this particular problem can be solved by storing
> computed thread trees in files similar to `.marks' and `.overview'.
> To keep track of computed results input parameters should be stored
> along with computed data.

Yes, it can be improved, but you are talking about caching.  It does
not remove the need to at some point compute the data stored in the
cache.  Then Gnus would look up, which I find unacceptable.

Furthermore, because a lot of what is done during preparing summary
buffers is dynamic, or almost so because it is influenced by hundreds
of user variables that may change over time, I'm not convinced caching
summary buffer data can be done reliable without great pain.  For me,
the summary buffer look different most time I enter it, because each
added or removed article in the group may change large parts of the
summary buffer to be recomputed (which I don't consider a bug).  It is
certainly easier to compute the summary buffer every time it is
needed, and use the user variables during that computation, than
reading from a cache and figure out what has to be re-computed given
the then-current user variables, and then re-compute the data and
store it in the cache.

>> Another example is getting new mail in Gnus.  This is probably more
>> network bound than CPU bound, but doing it asynchronously would still
>> lock up Emacs completely for many seconds, which is unacceptable.  If
>> you use Gnus as a offline reader, getting new mail may take minutes.
>
> Many tasks can be performed by external processes.  Getting new mail
> shouldn't lock up Emacs when done by an external program like movemail.

I meant parsing the new incoming articles and splitting them into the
proper group.  This is done in elisp.

If you profile Gnus with ELP, you see that the amount of time spent
waiting for external processes like movemail is not the biggest cause
of the lockups.  Most of it is spent evaluating elisp.  Even when
getting new mail.  So optimizing the movemail case to be asynchronous
would not improve the situation much, but will make it more difficult
to debug and troubleshoot Gnus.

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[David Kastrup]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> > Do you have an idea what figure we are speaking about here?  I
> > repeat: _every_ access to a symbol that now works directly instead
> > has to work via stack pointers.  And CPUs like the x86 do not have
> > spare address registers flying around.
> 
> I wouldn't worry too much about speed: there's lots of room for
> optimization in the interpreter.  The problem I see is one of
> semantics because looking up bindings in the stack doesn't seem to
> work so great when you take into account interaction with
> buffer-local variables.  That is: it tends to give you subtly
> different semantics than the current one.

Actually, considering the warnings in the manual about the necessary
orders of exception-catchers and buffer switches and let and similar,
I would expect that the different semantics would in most cases be
rather an advantage (and what the programmer would have expected
naively in the first place).  A basically static variable allocation
that gets saved and restored on a stack is more prone to surprising
side effects than a straightforward stack.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Stefan Monnier]

> Actually, considering the warnings in the manual about the necessary
> orders of exception-catchers and buffer switches and let and similar,
> I would expect that the different semantics would in most cases be
> rather an advantage (and what the programmer would have expected
> naively in the first place).  A basically static variable allocation
> that gets saved and restored on a stack is more prone to surprising
> side effects than a straightforward stack.

Yes, the semantics would be cleaner, but check the example I posted where
we rebind default-directory and switch back&forth between buffers: the
old semantics is odd but some code relies on it (basically using `let'
instead of `cd').


        Stefan

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Stefan Monnier]

> I haven't yet seen any response to those constructive contributions to
> this discussion that motivates they would be infeasible or
> meaningless. I truly believe I have proposed a viable solution, but
> the lack of comment on it is disappointing.

It's probably because most people just agree with the proposition
but don't care about implementing it.  At least that's my position.

> I'm not at all certain of that; cpu optimizations can slant these
> things in unexpected directions. It wouldn't surprise me if an extra
> indirection on the stack is faster than a global variable due to
> better memory locality.

That's always a possibility indeed.


        Stefan

Re: What's the problem?

[Miles Bader]

Simon Josefsson <jas@extundo.com> writes:
> If you profile Gnus with ELP, you see that the amount of time spent
> waiting for external processes like movemail is not the biggest cause
> of the lockups.  Most of it is spent evaluating elisp.  Even when
> getting new mail.

It depends on your environment of course -- if you have a slow network
connection (or a slow server), it can spend a _lot_ of time waiting for
external processes/data.

Personally I think making emacs generally multi-threaded is far more
trouble than it's worth, but in some cases like gnus, it would be worth
it to rewrite (small parts of) _that application_ to execute in the
background.  In my daily usage the main two places where I end up
waiting many minutes for emacs to finish something are (1) fetching my
daily mail into gnus via pop3.el, and (2) entering a newsgroup with many
unread messages on my home machine, which has a slow modem connection;
in both of these cases, the great majority of time is spent waiting for
data over the network.

Anyway my main point is that I think it's basically an application
issue, though emacs might help by adding helper functions.

-Miles
-- 
Love is a snowmobile racing across the tundra.  Suddenly it flips over,
pinning you underneath.  At night the ice weasels come.  --Nietzsche

Re: What's the problem?

[Simon Josefsson]

Miles Bader <miles@lsi.nec.co.jp> writes:

> Simon Josefsson <jas@extundo.com> writes:
>> If you profile Gnus with ELP, you see that the amount of time spent
>> waiting for external processes like movemail is not the biggest cause
>> of the lockups.  Most of it is spent evaluating elisp.  Even when
>> getting new mail.
>
> It depends on your environment of course -- if you have a slow network
> connection (or a slow server), it can spend a _lot_ of time waiting for
> external processes/data.

Right, with emphasis on _can_.

> Personally I think making emacs generally multi-threaded is far more
> trouble than it's worth, but in some cases like gnus, it would be worth
> it to rewrite (small parts of) _that application_ to execute in the
> background.

For me, this wouldn't solve the problem (CPU bound summary
computations).  For you, on a slow connection, it would solve your
problem (IO bound network access).  There is nothing that says we
can't do both.  (Except that none of us appear to be doing anything
but talking... :-))

> Anyway my main point is that I think it's basically an application
> issue, though emacs might help by adding helper functions.

I don't see how fixing my perceived problem can be done without some
kind of threading support in Emacs (co-operative or whatever).  Hence,
helper functions would do more than just help, they are critical in
improving the application.

Re: What's the problem?

[Miles Bader]

Simon Josefsson <jas@extundo.com> writes:
> > It depends on your environment of course -- if you have a slow network
> > connection (or a slow server), it can spend a _lot_ of time waiting for
> > external processes/data.
> 
> Right, with emphasis on _can_.

At least for me, this is an issue every single day; the CPU-bound parts
of summary generation &c are slightly annoying, but really not enough to
warrant any massive rewriting -- on the order of 30s or so for a large
newsgroup -- but IO-bound delays can be 10 _minutes_.  I don't know what
it's like for other people.

> > Anyway my main point is that I think it's basically an application
> > issue, though emacs might help by adding helper functions.
> 
> I don't see how fixing my perceived problem can be done without some
> kind of threading support in Emacs (co-operative or whatever).  Hence,
> helper functions would do more than just help, they are critical in
> improving the application.

What I'm trying to say is that the `threading support' need not be
particularly good, or general-purpose.  Probably something could be
hacked up right _now_, without any additional core functions, using
clever programming and emacs timers, by changing the worst-offending
part of the gnus code into something event driven.

-Miles
-- 
Run away!  Run away!

Re: What's the problem?

[Simon Josefsson]

Miles Bader <miles@lsi.nec.co.jp> writes:

> Simon Josefsson <jas@extundo.com> writes:
>> > It depends on your environment of course -- if you have a slow network
>> > connection (or a slow server), it can spend a _lot_ of time waiting for
>> > external processes/data.
>> 
>> Right, with emphasis on _can_.
>
> At least for me, this is an issue every single day; the CPU-bound parts
> of summary generation &c are slightly annoying, but really not enough to
> warrant any massive rewriting -- on the order of 30s or so for a large
> newsgroup -- but IO-bound delays can be 10 _minutes_.  I don't know what
> it's like for other people.

I'm using the Agent in recent Gnus, so almost all data is locally
cached (except for flag updates via IMAP and new-mail checks in NNTP),
so for me the delays I see are mostly CPU bound.

>> > Anyway my main point is that I think it's basically an application
>> > issue, though emacs might help by adding helper functions.
>> 
>> I don't see how fixing my perceived problem can be done without some
>> kind of threading support in Emacs (co-operative or whatever).  Hence,
>> helper functions would do more than just help, they are critical in
>> improving the application.
>
> What I'm trying to say is that the `threading support' need not be
> particularly good, or general-purpose.  Probably something could be
> hacked up right _now_, without any additional core functions, using
> clever programming and emacs timers, by changing the worst-offending
> part of the gnus code into something event driven.

I don't understand.  How would making the summary buffer generation
asynchronous stop Emacs from locking up during computations?  For me,
the summary buffer generation is CPU bound in elisp, not IO bound.
Same for getting new mail into the agent, it can take 2-3 minutes with
only a fraction of the time spent in IO (yes, it is not optimized).

I agree doing what you suggest would improve your problem, and making
Gnus more asynchronous would be useful (patches welcome!), but I don't
see how it is relevant to stopping the lockups when processing data.

I think there are two separate problems here.  They can and need to be
solved individually.

Re: What's the problem?

[Miles Bader]

Simon Josefsson <jas@extundo.com> writes:
> I'm using the Agent in recent Gnus, so almost all data is locally
> cached (except for flag updates via IMAP and new-mail checks in NNTP),
> so for me the delays I see are mostly CPU bound.

Not sure about agent mode -- the last time I tried it, it was so
completely awful that I quickly stopped.

> > What I'm trying to say is that the `threading support' need not be
> > particularly good, or general-purpose.  Probably something could be
> > hacked up right _now_, without any additional core functions, using
> > clever programming and emacs timers, by changing the worst-offending
> > part of the gnus code into something event driven.
> 
> I don't understand.  How would making the summary buffer generation
> asynchronous stop Emacs from locking up during computations?  For me,
> the summary buffer generation is CPU bound in elisp, not IO bound.

Yes, I understand.  I'd guess that a typical very long computation in
gnus is probably in the form of loops that do something fairly simple
many, many times, with other shorter calculations between them.  So
you'd like gnus to somehow yield cpu time for the user every iteration,
or every 100 iterations, or something like that.  In a cooperative
multi-tasking system, you'd just stick in a (yield) or something, but in
emacs this would be very hard to support.

So, instead, lets say you have a function like:

   (define gnus-fill-in-summary-buffer (...)
     (let (...some bindings...)
       (do-some-fairly-quick-calculation)
       (dolist (var1 potentially-big-long-list-1)
         ...something-1...)
       (dolist (var2 potentially-big-long-list)
         ...something-2...)))

change it into something like:

   (define gnus-fill-in-summary-buffer (...)
     (let ((some-state ...))
       (do-some-fairly-quick-calculation)
       (with-background-queue (bgq some-state)
         (bgq-dolist (var1 potentially-big-long-list-1 bgq)
            ...something-1...)
         (bgq-dolist (var2 potentially-big-long-list-2 bgq)
            ...something-2...))))

where `with-background-queue' and `bgq-dolist' (1) just package up their
body code into lambda(s), [effectively] shove them on the end of some
queue in bgq, and return immediately, and (2) explicitly refuse to make
any guarantees about non-global bindings; the value here called
`some-state' is stashed away in bgq somewhere, and can be used to
communicate values internal to the calculation.

IOW, it's annoying for the gnus programmer, but very easy for the emacs
implementation.

Some questions are (1) are there only a few points within gnus that
represent most of the annoying delays (2) do these places have fairly
simple code structures that could be split up into pieces like the above
example, and (3) do these pieces not depend on the long-term consistency
of any global state.

> I think there are two separate problems here.  They can and need to be
> solved individually.

I don't know.  A framework like the above could pretty simply handle the
I/O bound portion too, though.

-Miles
-- 
`To alcohol!  The cause of, and solution to,
 all of life's problems' --Homer J. Simpson

Re: What's the problem?

[Eli Zaretskii]

> From: Simon Josefsson <jas@extundo.com>
> Date: Wed, 10 Dec 2003 07:34:45 +0100
> >
> > What I'm trying to say is that the `threading support' need not be
> > particularly good, or general-purpose.  Probably something could be
> > hacked up right _now_, without any additional core functions, using
> > clever programming and emacs timers, by changing the worst-offending
> > part of the gnus code into something event driven.
> 
> I don't understand.  How would making the summary buffer generation
> asynchronous stop Emacs from locking up during computations?  For me,
> the summary buffer generation is CPU bound in elisp, not IO bound.

By doing the computation in chunks, like stealth font-lock does, for
example, you let other tasks get slots of CPU time while the long
computation runs.

It's like telling the user to go for a coffee while Gnus computes the
summary buffer, only instead of coffee she can type away something in
another buffer ;-)

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Ted Zlatanov]

On 09 Dec 2003, monnier@iro.umontreal.ca wrote:

> Yes, the semantics would be cleaner, but check the example I posted
> where we rebind default-directory and switch back&forth between
> buffers: the old semantics is odd but some code relies on it
> (basically using `let' instead of `cd').

I see the problem with that code.  Is it so common a practice that it
can't be rewritten where it already happens, and deprecated for the
future?  It seems pretty confusing for the maintainers and only
slightly convenient for the programmers.

Ted

Re: What's the problem?

[Ted Zlatanov]

On 10 Dec 2003, miles@lsi.nec.co.jp wrote:

> IOW, it's annoying for the gnus programmer, but very easy for the
> emacs implementation.

Well, that's the rub, isn't it?  Simon and I, being Gnus programmers,
would like Emacs to provide something better than the current
framework so the pain will be spread out instead of concentrated on
us.  I think that improvements to Emacs would be beneficial to far
more people than improvements to Gnus, also.

> Some questions are (1) are there only a few points within gnus that
> represent most of the annoying delays

Hashtable lookups, list traversals, and arithmetic.  Those three show
up all over the place, and they are generally not mutually dependent
when done on separate articles.

> (2) do these places have fairly simple code structures that could be
> split up into pieces like the above example,

Generally yes, but sometimes they can get pretty complex (depending
on the number of references in an article or on the number of scoring
rules, for instance).

> (3) do these pieces not depend on the long-term consistency of
> any global state.

I think so.

> I don't know.  A framework like the above could pretty simply handle
> the I/O bound portion too, though.

Remember the auto-save (over NFS or Tramp) problem I mentioned.  I
don't think it can be done the way you propose, but I'll be happy to
be proven wrong.

Ted

Re: What's the problem?

[Miles Bader]

Ted Zlatanov <tzz@lifelogs.com> writes:
> > IOW, it's annoying for the gnus programmer, but very easy for the
> > emacs implementation.
> 
> Well, that's the rub, isn't it?  Simon and I, being Gnus programmers,
> would like Emacs to provide something better than the current
> framework so the pain will be spread out instead of concentrated on
> us.  I think that improvements to Emacs would be beneficial to far
> more people than improvements to Gnus, also.

Of course.  It's just that past a certain point (e.g. providing _real_
threading), the changes to emacs are insanely complex and intrusive.

The sort of awkward `pseudo-threading' framework I gave an example of,
although it's annoying for the application programmer, is I think
relatively _less_ annoying than the sort of massive emacs changes
required for true threading.

If the number of places where you really _need_ it are fairly few, I
think it makes more sense to put the complexity in those places.
My impression is that this is the case; indeed, for me it's basically
like 2-3 operations in gnus, and that's it (most other time-consuming
commands use external processes in the background to do their work).

Now, any of my assumptions could be wrong, in which case maybe the
calculation is different, but...

> > Some questions are (1) are there only a few points within gnus that
> > represent most of the annoying delays
> 
> Hashtable lookups, list traversals, and arithmetic.  Those three show
> up all over the place, and they are generally not mutually dependent
> when done on separate articles.

No, that's not what I meant -- those sorts of operations may in
aggregate represent the bulk of the cpu time spent, but no single
operation actually takes very long.

I'm more concerned with what entry points into gnus (I mean, user
commands) hang for a long time.  Find those, and if there are only a few
of them, see if they can be split up using a pseudo-threading framework
or something.

> > I don't know.  A framework like the above could pretty simply handle
> > the I/O bound portion too, though.
> 
> Remember the auto-save (over NFS or Tramp) problem I mentioned.  I
> don't think it can be done the way you propose, but I'll be happy to
> be proven wrong.

Sure; I hate auto-save delays too (even more annoying is the !@#$%!
purposeful-delay-to-give-an-error-message autosave does when it can't
write a file), but I suppose fixing them would require low-level changes
to emacs.

-Miles
-- 
`There are more things in heaven and earth, Horatio,
 Than are dreamt of in your philosophy.'

Re: What's the problem?

[Stefan Monnier]

> or every 100 iterations, or something like that.  In a cooperative
> multi-tasking system, you'd just stick in a (yield) or something, but in
> emacs this would be very hard to support.

I don't see why this should be so hard.
What we're talking about is basically multiple-stacks, context-switches
done only from Feval (i.e. at elisp granularity so there's no concurrency
in the C code), some form of elisp forking and locking primitives (I
suggested to lock a buffer at a time, but we also need to prevent
context-switches during special cases such as jit-lock), and a lot
of experimenting.

One case I recently bumped into where using the current event-driven
functionality is not possible (even for I/O) is in Tramp where the wait can
easily be on the order of a minute for the initial connection.  In a case
like this one, I think the thread creation primitive needed would be
something akin to the shell's "C-z + bg".  Maybe something like
(if (fork) (throw 'toplevel) ...) if a `fork' like primitive makes sense,
or just a new primitive `make-new-toplevel-thread'.


        Stefan

Re: What's the problem?

[Richard Stallman]

    By doing the computation in chunks, like stealth font-lock does, for
    example, you let other tasks get slots of CPU time while the long
    computation runs.

Gnus could compute the summary in the background, piece by piece,
somewhat like stealth font-lock.  (Not exactly the same, because
whenever Emacs is otherwise idle it should work full time on
producing summary items.)

Re: What's the problem?

[Ted Zlatanov]

On 11 Dec 2003, miles@lsi.nec.co.jp wrote:

> Ted Zlatanov <tzz@lifelogs.com> writes:

>> > Some questions are (1) are there only a few points within gnus
>> > that represent most of the annoying delays
>> 
>> Hashtable lookups, list traversals, and arithmetic.  Those three
>> show up all over the place, and they are generally not mutually
>> dependent when done on separate articles.
> 
> No, that's not what I meant -- those sorts of operations may in
> aggregate represent the bulk of the cpu time spent, but no single
> operation actually takes very long.
> 
> I'm more concerned with what entry points into gnus (I mean, user
> commands) hang for a long time.  Find those, and if there are only a
> few of them, see if they can be split up using a pseudo-threading
> framework or something.

I'll list the pieces I know best.  There are probably others.

- getting new mail, read/write existing mail
  - interacting with network backends
    - nnimap: medium read, slow write
    - nntp: fast read
    - nnrss: slow initial read
  - interacting with local backends: nnml, nnmaildir, etc.
  - spam-splitting

- sending mail

- building summary buffers
  - retrieving articles from overview data
  - scoring
  - building threads
  - spam-splitting (for backends that don't get new mail, e.g. nntp)

- detecting and processing spam
  - recognizing spam (connects with spam-splitting above)
  - remembering spam with internal or external programs

- tracing article threads back to a folder (gnus-registry)
  - look up registry hashtable, look through a list for each
    reference ID and examine each cell closely
  - look up, modify, and store back registry hashtable entry

>> > I don't know.  A framework like the above could pretty simply
>> > handle the I/O bound portion too, though.
>> 
>> Remember the auto-save (over NFS or Tramp) problem I mentioned.  I
>> don't think it can be done the way you propose, but I'll be happy
>> to be proven wrong.
> 
> Sure; I hate auto-save delays too (even more annoying is the !@#$%!
> purposeful-delay-to-give-an-error-message autosave does when it
> can't write a file), but I suppose fixing them would require
> low-level changes to emacs.

I'll be the first one in line if those changes ever happen.

Thanks
Ted

Re: What's the problem?

[Ted Zlatanov]

On Thu, 11 Dec 2003, rms@gnu.org wrote:

> Gnus could compute the summary in the background, piece by piece,
> somewhat like stealth font-lock.  (Not exactly the same, because
> whenever Emacs is otherwise idle it should work full time on
> producing summary items.)

This seems to be a highly favored solution on this list because it
fits in easily with the existing interpreter.  The downside is that it
does not use multiple processors if they exist, which has become more
common with today's hardware.

Ted

Re: What's the problem?

[Miles Bader]

On Thu, Dec 11, 2003 at 09:12:17AM -0500, Stefan Monnier wrote:
> > In a cooperative multi-tasking system, you'd just stick in a (yield) or
> > something, but in emacs this would be very hard to support.
> 
> I don't see why this should be so hard.  What we're talking about is
> basically multiple-stacks, context-switches done only from Feval (i.e. at
> elisp granularity so there's no concurrency in the C code), some form of
> elisp forking and locking primitives

Hmmm, aside from application-level issues (which are probably the same
whether you use cooperative multi-tasking or a goofy framework like I
described earlier), I'd think the most annoying thing would be working around
emacs' use of shallow-binding for variables.  I.e., for local variable
bindings you'd have to unwind the bindings in one thread and wind them in the
next when you switched contexts; I'm not sure how non-normal variables would
fit into things (presumably you would unwind/wind the the same way, but...).

Of course there are other things that behave the same way, like buffer
restrictions etc., but maybe they could be treated as `application level'
issues, and dealt with via explicit or buffer locking of some sort.

If a new `rewind' field were added to unwind-markers on the binding stack, it
could identify those that _do_ matter, and say `unwind me when switching
thread, and here's how to rewind me later.'

Maybe you're right -- if the core changes could be kept fairly small, it
would at least be worth experimenting with.

-miles
-- 
`Life is a boundless sea of bitterness'

Re: What's the problem? (Was: Are there plans for a multi-threaded Emacs?)

[Martin Stjernholm]

Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> Yes, the semantics would be cleaner, but check the example I posted where
> we rebind default-directory and switch back&forth between buffers: the
> old semantics is odd but some code relies on it (basically using `let'
> instead of `cd').

It sure is odd, but how is that semantics a problem when it comes to
thread switches? From a usability perspective it sure can be a problem
if several threads changes buffer local values and combine it with
dynamic bindings, but that's an application problem. I can't see any
inherent design problem keeping the odd behavior in a threaded
environment. Is it that the implementation of dynamically bound buffer
local values makes it difficult to fix context switching for them?

Re: What's the problem?

[Luke A. Olbrish]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Thu, 11 Dec 2003, rms@gnu.org wrote:
>
>> Gnus could compute the summary in the background, piece by piece,
>> somewhat like stealth font-lock.  (Not exactly the same, because
>> whenever Emacs is otherwise idle it should work full time on
>> producing summary items.)
>
> This seems to be a highly favored solution on this list because it
> fits in easily with the existing interpreter.  The downside is that it
> does not use multiple processors if they exist, which has become more
> common with today's hardware.

is emacs so slow on today's hardware that it needs to be able to use
multiple processors?  it would seem that we could get more use out of
work on the interpreter to make it more efficient than to get emacs to
be able to utilize multiple processors.

-- 
Luke Anthony Olbrish
<luke.olbrish@cc.gatech.edu>

Re: What's the problem?

[Miles Bader]

luke.olbrish@cc.gatech.edu (Luke A. Olbrish) writes:
> is emacs so slow on today's hardware that it needs to be able to use
> multiple processors?

I'm not sure why people keep talking about threading as some way to make
emacs faster -- speed is not a major problem in general, and those
places where it _is_ (e.g., gnus summary generation) don't seem easily
parallizable.  As far as I can see, threads are desirable mostly because
they allow the user to keep working while something's happening in the
background (since typical emacs task are very non-cpu-intensive, the
background task probably won't slow down appreciably either).

-Miles
-- 
A zen-buddhist walked into a pizza shop and
said, "Make me one with everything."

Re: What's the problem?

[Richard Stallman]

    Sure; I hate auto-save delays too (even more annoying is the !@#$%!
    purposeful-delay-to-give-an-error-message autosave does when it can't
    write a file)

It would be easy to change that.  The question is, what other way
should it make sure the user sees that there is an error?

Re: What's the problem?

[Richard Stallman]

    What we're talking about is basically multiple-stacks, context-switches
    done only from Feval (i.e. at elisp granularity so there's no concurrency
    in the C code),

The number of C functions that call Feval is rather large,
and include redisplay.  So this is not quite as easy as it might seem.

Redisplay could set a flag to prevent thread-switching.  That would
remove one large piece of the problem.  How big the problem remains
after that, I am not sure.

Re: What's the problem?

[Miles Bader]

Richard Stallman <rms@gnu.org> writes:
>     Sure; I hate auto-save delays too (even more annoying is the !@#$%!
>     purposeful-delay-to-give-an-error-message autosave does when it can't
>     write a file)
> 
> It would be easy to change that.  The question is, what other way
> should it make sure the user sees that there is an error?

Some things that come to mind are:

 * Make sure the pause is cleanly canceled if you hit ^G (I'm not really
   sure what it does now, but it acts very strangely if you hit ^G)

 * Only pause to show the error message the first time the autosave for
   a particular file fails; if subsequent autosaves fail, just show the
   error message with no pause (however, if autosave then _succeeds_ at
   some point, it should presumably reset the state so that it pauses
   upon any failure after that)

 * maybe put a big obvious warning in the modeline for buffers where
   autosave failed (text, uppercase, red, blinking... :-)

-Miles
-- 
"Most attacks seem to take place at night, during a rainstorm, uphill,
 where four map sheets join."   -- Anon. British Officer in WW I

Re: What's the problem?

[Richard Stallman]

    I'm not sure why people keep talking about threading as some way to make
    emacs faster -- speed is not a major problem in general, and those
    places where it _is_ (e.g., gnus summary generation) don't seem easily
    parallizable.  As far as I can see, threads are desirable mostly because
    they allow the user to keep working while something's happening in the
    background (since typical emacs task are very non-cpu-intensive, the
    background task probably won't slow down appreciably either).

I basically agree; however, there is one other possible use for
multi-threading in Emacs.  This is for the sake of using multiple
terminals at once.  Right now, I think, only one terminal can
use the minibuffer.  Only one terminal can be running a command.
If each terminal had its own thread, they could do just about anything
in parallel.

Re: What's the problem?

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> Date: Fri, 12 Dec 2003 18:55:58 -0500
> 
> Redisplay could set a flag to prevent thread-switching.

I think making redisplay a separate thread would be one of the more
useful improvements in Emacs.  The situation where the user clicks
File->Open from the menu bar and then (under a toolkit), while the
file-selection box is active, the Emacs display never changes, looks
like a bug.  (Try moving the file-selection box to a different
position and observe the blank portions of the Emacs window.)

Re: What's the problem?

[Jan D.]

> I think making redisplay a separate thread would be one of the more
> useful improvements in Emacs.  The situation where the user clicks
> File->Open from the menu bar and then (under a toolkit), while the
> file-selection box is active, the Emacs display never changes, looks
> like a bug.  (Try moving the file-selection box to a different
> position and observe the blank portions of the Emacs window.)

This has actually been fixed in CVS for some time.  But having redisplay
in a separate thread is still a good idea.

	Jan D.

Re: What's the problem?

[David Kastrup]

"Eli Zaretskii" <eliz@elta.co.il> writes:

> > From: Richard Stallman <rms@gnu.org>
> > Date: Fri, 12 Dec 2003 18:55:58 -0500
> > 
> > Redisplay could set a flag to prevent thread-switching.
> 
> I think making redisplay a separate thread would be one of the more
> useful improvements in Emacs.  The situation where the user clicks
> File->Open from the menu bar and then (under a toolkit), while the
> file-selection box is active, the Emacs display never changes, looks
> like a bug.  (Try moving the file-selection box to a different
> position and observe the blank portions of the Emacs window.)

It would also be an idea, if one has a redisplay thread, to let it
associate mouse clicks with objects under it at the time of the click.
People rarely expect, when they click in the text area while Emacs is
busy, that half an hour later a menu pops up with a button "Really
self-destruct?" which happens to be right on the location where the
click had been half an hour ago, that this menu/text position etc will
be satisfied with the click from olden times.

More seriously, I had quite a few times paste operations go quite to
the wrong place when something affecting the buffer display was
running in background, even though at the time of the click the
display was still something quite different.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: What's the problem?

[Richard Stallman]

     * Make sure the pause is cleanly canceled if you hit ^G (I'm not really
       sure what it does now, but it acts very strangely if you hit ^G)

Coud you debug that case?

     * Only pause to show the error message the first time the autosave for
       a particular file fails; if subsequent autosaves fail, just show the
       error message with no pause (however, if autosave then _succeeds_ at
       some point, it should presumably reset the state so that it pauses
       upon any failure after that)

That sounds like a usable idea.  Would you like to try to implement it?

     * maybe put a big obvious warning in the modeline for buffers where
       autosave failed (text, uppercase, red, blinking... :-)

That would work ok for buffers that are visible, but would fail to do
the job for others.

Re: What's the problem?

[Richard Stallman]

    I think people on emacs-devel agreed that private binding stacks would
    work, but their concern was that it would slow down Emacs a lot if
    every read/write did a binding lookup (I am probably remembering
    things incorrectly, but that was my understanding).

The values would be stored in the symbols, just as now.
However, thread-switching would have to swap bindings in and out.

Here's what I sent privately:

This could work using shallow binding, if switching threads swaps
out the bindings that shouldn't apply, then swaps in those that
should.  This is similar to the technique now used for buffer-local
bindings when switching buffers; however, for buffer-switching, the
swapping is done in a lazy fashion, but I don't see how that could
be possible for thread-switching.  So thread-switching would take
some time.  We would want to make sure it does not happen very
often.

Re: What's the problem?

[Martin Stjernholm]

Richard Stallman <rms@gnu.org> wrote:

> /.../ So thread-switching would take some time.  We would want to
> make sure it does not happen very often.

That's a good design principle anyway since thread switches never are
very cheap. Avoiding fine grained locking is afaics the best way to
ensure that thread switches happens seldom. With only buffer local
locks, every callback would normally run to completion in a single
thread slice since threads can't lock out each other. Thread switches
would only occur when things have blocked in I/O (and speed isn't a
factor then), or when cpu bound work is preempted.

Re: What's the problem?

[Eli Zaretskii]

> From: David Kastrup <dak@gnu.org>
> Date: 13 Dec 2003 18:35:22 +0100
> 
> It would also be an idea, if one has a redisplay thread, to let it
> associate mouse clicks with objects under it at the time of the click.
> People rarely expect, when they click in the text area while Emacs is
> busy, that half an hour later a menu pops up with a button "Really
> self-destruct?" which happens to be right on the location where the
> click had been half an hour ago, that this menu/text position etc will
> be satisfied with the click from olden times.

I think, with a separate thread, such cases will be less probable,
actually, since the redisplay will have more chance to catch up with
the rest of Emacs than it is now.

Re: What's the problem?

[Richard Stallman]

    I think making redisplay a separate thread would be one of the more
    useful improvements in Emacs.

That could be a good idea, if all redisplay is done by that single
thread.  When other threads try to redisplay, they would instead
wait for that thread to say "I'm done".

Re: What's the problem?

[David Kastrup]

Eli Zaretskii <eliz@elta.co.il> writes:

> > From: David Kastrup <dak@gnu.org>
> > Date: 13 Dec 2003 18:35:22 +0100
> > 
> > It would also be an idea, if one has a redisplay thread, to let it
> > associate mouse clicks with objects under it at the time of the click.
> > People rarely expect, when they click in the text area while Emacs is
> > busy, that half an hour later a menu pops up with a button "Really
> > self-destruct?" which happens to be right on the location where the
> > click had been half an hour ago, that this menu/text position etc will
> > be satisfied with the click from olden times.
> 
> I think, with a separate thread, such cases will be less probable,
> actually, since the redisplay will have more chance to catch up with
> the rest of Emacs than it is now.

It can't catch up with a state of Emacs that Emacs has not yet
reached at the time of the click.  At the time posn-point is called,
the state of Emacs might be quite different from the state at the
time of the click.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Emacs kill buffer

[Camm Maguire]

Greetings!  Apparently, beginning with emacs21, 'cuts' to the kill
buffer are made directly through the X clipboard protocol or some
such.  I typically use emacs under X windows over a dialup ppp line
and ssh compression.  The general performance is OK, but this
modification in emacs21 has made any additions to the kill buffer much
slower.  Is there any way to turn this off and restore the older
emacs20 behavior?

Take care,
-- 
Camm Maguire			     			camm@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah

Re: What's the problem?

[Eli Zaretskii]

> From: David Kastrup <dak@gnu.org>
> Date: 14 Dec 2003 12:55:48 +0100
> 
> It can't catch up with a state of Emacs that Emacs has not yet
> reached at the time of the click.  At the time posn-point is called,
> the state of Emacs might be quite different from the state at the
> time of the click.

Yes, but if redisplay runs ``in parallel'' with the rest of Emacs, the
probability of this should be smaller, I think, since it will lag
behind Emacs by a smaller amount of changes to the buffer.