Multithreading, again and again

Multithreading, again and again

[Dmitry Antipov]

Hello all,

this is an attempt to refresh the most important ideas everyone has about
threads support in Emacs. Thanks in advance to all who spent their time
thinking on answers. If someone thinks that I miss something important,
notices and references to previous discussions around this topic are highly
appreciated.

0. What we have, and where we go.
    What's the status of git://gitorious.org/emacs-mt/emacs-mt.git and
    http://bzr.savannah.gnu.org/r/emacs/concurrency? Whether there are
    plans for further development?

1. To thread or not to thread?
    Is there a consensus whether it's worth doing at all? If I don't miss
    something important from previous discussions (referenced from
    http://www.emacswiki.org/emacs/NoThreading, what a title), everyone
    agrees that some kind of threading is useful - but maybe someone has
    the votum separatum?

2. Hide them all!
    Should the threads be visible (may be created and managed) from Lisp,
    or they can just do some work orthogonal to it? If latter, which tasks may
    be implicitly threaded? Redisplay (one thread per frame)? Buffer/socket
    I/O? GC? Is it feasible to implement full implicit concurrency? For the
    rough example, with the Lisp engine as the pool of threads, where (eval
    FORM) just queues the FORM and then ask the pool to find a free thread
    and evaluate it?

3. Too big, too global.
    How to split/share/synchronize huge global state between threads?
    What should be thread-local? (I feel (current-buffer) should be
    global and max-lisp-eval-depth should be thread-local, but I suspect
    that there are much more controversial cases). Is it reasonable to
    have become-thread-local-on-write globals?

4. Say "thread"!
    What should be done in C to implement thread management in Lisp?
    I feel basically

      (let ((th (make-thread FUNCTION ARGS))) ...)

    should create thread object TH which represents running thread executing
    Lisp function FUNCTION with ARGS (like funcall, but within separate thread),
    and such thread object may be examined with stuff like (thread-running-p TH),
    canceled with (thread-cancel TH), asked for FUNCTION's return value with
    (thread-return TH), and so. But is this nothing more than adding some
    builtins? Will it require some more substantial language changes? What
    about old controversial topic on lexical vs. dynamic binding?

5. You and I.
    What synchronization primitives should be implemented? Atomic variables?
    Mutexes/semaphores? Barriers? Higher-level not-so-primitives like
    thread pools or multithreaded queues? Should some basic operations,
    like setq, be always atomic? Is it reasonable/feasible/useful to have
    special form like (with-atomic BODY...), where all BODY forms are evaluated
    atomically with respect to all other threads?

6. Under the cover.
    What other low-level changes are required for thread support?
    Basic structure of Lisp objects? Multiple stacks scanning for GC?
    Per-thread heaps for small objects?

7. Look around.
    Has someone an experience with development of multithreaded code for
    commercial Common Lisp implementations, most probably LispWorks and/or
    Allegro CL? If yes, can someone briefly explain pros and cons of their
    approach to multithreading?

Dmitry

Re: Multithreading, again and again

[joakim]

Dmitry Antipov <dmantipov@yandex.ru> writes:

> Hello all,
>
> this is an attempt to refresh the most important ideas everyone has about
> threads support in Emacs. Thanks in advance to all who spent their time
> thinking on answers. If someone thinks that I miss something important,
> notices and references to previous discussions around this topic are highly
> appreciated.
>
> 0. What we have, and where we go.
>    What's the status of git://gitorious.org/emacs-mt/emacs-mt.git and
>    http://bzr.savannah.gnu.org/r/emacs/concurrency? Whether there are
>    plans for further development?
>
> 1. To thread or not to thread?
>    Is there a consensus whether it's worth doing at all? If I don't miss
>    something important from previous discussions (referenced from
>    http://www.emacswiki.org/emacs/NoThreading, what a title), everyone
>    agrees that some kind of threading is useful - but maybe someone has
>    the votum separatum?
>
> 2. Hide them all!
>    Should the threads be visible (may be created and managed) from Lisp,
>    or they can just do some work orthogonal to it? If latter, which tasks may
>    be implicitly threaded? Redisplay (one thread per frame)? Buffer/socket
>    I/O? GC? Is it feasible to implement full implicit concurrency? For the
>    rough example, with the Lisp engine as the pool of threads, where (eval
>    FORM) just queues the FORM and then ask the pool to find a free thread
>    and evaluate it?
>
> 3. Too big, too global.
>    How to split/share/synchronize huge global state between threads?
>    What should be thread-local? (I feel (current-buffer) should be
>    global and max-lisp-eval-depth should be thread-local, but I suspect
>    that there are much more controversial cases). Is it reasonable to
>    have become-thread-local-on-write globals?
>
> 4. Say "thread"!
>    What should be done in C to implement thread management in Lisp?
>    I feel basically
>
>      (let ((th (make-thread FUNCTION ARGS))) ...)
>
>    should create thread object TH which represents running thread executing
>    Lisp function FUNCTION with ARGS (like funcall, but within separate thread),
>    and such thread object may be examined with stuff like (thread-running-p TH),
>    canceled with (thread-cancel TH), asked for FUNCTION's return value with
>    (thread-return TH), and so. But is this nothing more than adding some
>    builtins? Will it require some more substantial language changes? What
>    about old controversial topic on lexical vs. dynamic binding?
>
> 5. You and I.
>    What synchronization primitives should be implemented? Atomic variables?
>    Mutexes/semaphores? Barriers? Higher-level not-so-primitives like
>    thread pools or multithreaded queues? Should some basic operations,
>    like setq, be always atomic? Is it reasonable/feasible/useful to have
>    special form like (with-atomic BODY...), where all BODY forms are evaluated
>    atomically with respect to all other threads?
>
> 6. Under the cover.
>    What other low-level changes are required for thread support?
>    Basic structure of Lisp objects? Multiple stacks scanning for GC?
>    Per-thread heaps for small objects?
>
> 7. Look around.
>    Has someone an experience with development of multithreaded code for
>    commercial Common Lisp implementations, most probably LispWorks and/or
>    Allegro CL? If yes, can someone briefly explain pros and cons of their
>    approach to multithreading?
>
> Dmitry

IMHO an interesting option is replacing the current Elisp implementation
with GNU Guile. The Guile-Emacs project is working on this. Guile
implements threads. That doesn't say anything about what the semantics
for threads should be in Elisp however. Guile-Emacs is IMHO the right
path for several reasons. 

-- 
Joakim Verona

Re: Multithreading, again and again

[Julien Danjou]

[-- Attachment #1: Type: text/plain, Size: 412 bytes --]

On Wed, Sep 28 2011, joakim@verona.se wrote:

> IMHO an interesting option is replacing the current Elisp implementation
> with GNU Guile. The Guile-Emacs project is working on this. Guile
> implements threads. That doesn't say anything about what the semantics
> for threads should be in Elisp however. Guile-Emacs is IMHO the right
> path for several reasons. 

I tend to agree.

-- 
Julien Danjou

[-- Attachment #2: Type: application/pgp-signature, Size: 835 bytes --]

Re: Multithreading, again and again

[Stefan Monnier]

> 0. What we have, and where we go.
>    What's the status of git://gitorious.org/emacs-mt/emacs-mt.git and
>    http://bzr.savannah.gnu.org/r/emacs/concurrency? Whether there are
>    plans for further development?

I'd like to merge this concurrency branch into Emacs-25, yes.

> 1. To thread or not to thread?
>    Is there a consensus whether it's worth doing at all? If I don't miss
>    something important from previous discussions (referenced from
>    http://www.emacswiki.org/emacs/NoThreading, what a title), everyone
>    agrees that some kind of threading is useful - but maybe someone has
>    the votum separatum?

I don't think there is such a consensus, but better support for
concurrency is something I consider important.  It is currently much too
difficult to implement "asynchronous article fetch" and things like that.

> 2. Hide them all!
>    Should the threads be visible (may be created and managed) from Lisp,

Yes.

>    be implicitly threaded? Redisplay (one thread per frame)? Buffer/socket

Parallelising the redisplay would be great, yes, but that's a completely
orthogonal issue.  Making it work concurrently with Lisp could be
interesting as well, tho probably less important.

> 3. Too big, too global.
>    How to split/share/synchronize huge global state between threads?
>    What should be thread-local? (I feel (current-buffer) should be
>    global and max-lisp-eval-depth should be thread-local, but I suspect
>    that there are much more controversial cases). Is it reasonable to
>    have become-thread-local-on-write globals?

Part of the reason I'd like to see the concurrency branch merged is in
order to get more experience with such issues.  It's hard to know what
would work and what wouldn't.  Especially interactions between
dynamic, thread-local, and buffer-local bindings are very tricky.

>    What synchronization primitives should be implemented? Atomic
>    variables?  Mutexes/semaphores? Barriers? Higher-level
>    not-so-primitives like thread pools or multithreaded queues? Should
>    some basic operations, like setq, be always atomic? Is it
>    reasonable/feasible/useful to have special form like (with-atomic
>    BODY...), where all BODY forms are evaluated atomically with
>    respect to all other threads?

I think the only realistic choice for now is `yield'.  The second best
would be transactions like `with-atomic'.

I also agree that moving towards something like Guile might be a longer
term option.  But it's not clear whether that's ever going to happen.


        Stefan

Re: Multithreading, again and again

[Juri Linkov]

> I don't think there is such a consensus, but better support for
> concurrency is something I consider important.  It is currently much too
> difficult to implement "asynchronous article fetch" and things like that.

"Asynchronous article fetch" could be implemented with a simpler approach
to run code in a "sandbox" similarly to HTML5 "workers" that run
computationally expensive scripts in the background independently of any
user interface scripts that allows for long-running scripts to be
executed without yielding to keep the application responsive.  More at:
http://www.whatwg.org/specs/web-apps/current-work/multipage/workers.html

Re: Multithreading, again and again

[Stefan Monnier]

>> I don't think there is such a consensus, but better support for
>> concurrency is something I consider important.  It is currently much too
>> difficult to implement "asynchronous article fetch" and things like that.

> "Asynchronous article fetch" could be implemented with a simpler approach
> to run code in a "sandbox" similarly to HTML5 "workers" that run
> computationally expensive scripts in the background independently of any
> user interface scripts that allows for long-running scripts to be
> executed without yielding to keep the application responsive.  More at:
> http://www.whatwg.org/specs/web-apps/current-work/multipage/workers.html

I must say my HTML/Javascript is between rusty and nonexistant, but
I can't see how they avoid global communication.  My best guess is that
they do the equivalent of a `fork' and then use communication via
messages (implemented over pipes or equivalent with automatic
marshalling/unmarshalling).

We could provide a `fork' primitive, indeed.


        Stefan

Re: Multithreading, again and again

[Tom Tromey]

[ threading ]

Stefan> We could provide a `fork' primitive, indeed.

My impression is that 'fork' is difficult to implement portably.  You
could try, I suppose.  Or there's "run a separate Emacs and communicate
over pipes":

http://lists.gnu.org/archive/html/emacs-devel/2011-02/msg00534.html

There are some aspects of sharing that may be hard (file descriptors).
Also setting up initial state of the worker process is hard if one
cannot truly fork.

I do wonder why there hasn't been more experimentation with this
approach, though, given that it is doable today just by running emacs as
a subprocess.

Tom

Re: Multithreading, again and again

[Dave Abrahams]

on Wed Oct 19 2011, Tom Tromey <tromey-AT-redhat.com> wrote:

> [ threading ]
>
> Stefan> We could provide a `fork' primitive, indeed.
>
> My impression is that 'fork' is difficult to implement portably.  You
> could try, I suppose.  Or there's "run a separate Emacs and communicate
> over pipes":
>
> http://lists.gnu.org/archive/html/emacs-devel/2011-02/msg00534.html

There are packages that do this today and it works well, but IMO there's
insufficient standard infrastructure available to make it easy, and
that, in general, keeps packages from using process-level concurrency
effectively.  For what it's worth, experiments show that launching emacs
as a scripting engine (e.g. using it in a shebang) is actually more
efficient than launching some more traditional scripting languages.

> There are some aspects of sharing that may be hard (file descriptors).
> Also setting up initial state of the worker process is hard if one
> cannot truly fork.
>
> I do wonder why there hasn't been more experimentation with this
> approach, though, given that it is doable today just by running emacs as
> a subprocess.

Again, I think some beautiful and usable library code could make this
approach much more attractive and more widely used.  Emacs IPC anyone?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Re: Multithreading, again and again

[Stefan Monnier]

> There are packages that do this today and it works well, but IMO there's
> insufficient standard infrastructure available to make it easy, and
> that, in general, keeps packages from using process-level concurrency
> effectively.

Could point to those packages that do it?  Without seeing examples it's
difficult to know what kind of infrastructure would be handy.

> For what it's worth, experiments show that launching Emacs
> as a scripting engine (e.g. using it in a shebang) is actually more
> efficient than launching some more traditional scripting languages.

That's indeed unexpected.  Can you point to some more details?


        Stefan

Re: Multithreading, again and again

[Dave Abrahams]

on Wed Oct 19 2011, Stefan Monnier <monnier-AT-IRO.UMontreal.CA> wrote:

>> There are packages that do this today and it works well, but IMO there's
>> insufficient standard infrastructure available to make it easy, and
>> that, in general, keeps packages from using process-level concurrency
>> effectively.
>
> Could point to those packages that do it?  Without seeing examples it's
> difficult to know what kind of infrastructure would be handy.

For example el-get (http://github.com/dimitri/el-get) does autoload
generation and installation of some packages (e.g. wanderlust) this way.

>> For what it's worth, experiments show that launching Emacs
>> as a scripting engine (e.g. using it in a shebang) is actually more
>> efficient than launching some more traditional scripting languages.
>
> That's indeed unexpected.  Can you point to some more details?

I think I need to ask John Wiegley to fill you in.  He did the
experiments.  John?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Re: Multithreading, again and again

[John Wiegley]

>>>>> Dave Abrahams <dave@boostpro.com> writes:

>>> For what it's worth, experiments show that launching Emacs as a scripting
>>> engine (e.g. using it in a shebang) is actually more efficient than
>>> launching some more traditional scripting languages.
>> 
>> That's indeed unexpected.  Can you point to some more details?

> I think I need to ask John Wiegley to fill you in.  He did the experiments.
> John?

I think our signals may be a little crossed.  What I had meant to tell Dave
was that an Emacs-shebang script is faster at starting up and printing "Hello,
world" than the equivalent ECL script -- which, for small little scripts,
means that using Emacs Lisp could be more efficient than using CL standalone
binaries.

I did not compare my test with Bash, however, or with using more complex
scripts, where I'd expect CL's native-language compilation to far outdo Emacs
Lisp.

John

Re: Multithreading, again and again

[Dave Abrahams]

on Thu Oct 20 2011, John Wiegley <jwiegley-AT-gmail.com> wrote:

>>>>>> Dave Abrahams <dave@boostpro.com> writes:
>
>
>>>> For what it's worth, experiments show that launching Emacs as a scripting
>>>> engine (e.g. using it in a shebang) is actually more efficient than
>>>> launching some more traditional scripting languages.
>>> 
>>> That's indeed unexpected.  Can you point to some more details?
>
>> I think I need to ask John Wiegley to fill you in.  He did the experiments.
>> John?
>
> I think our signals may be a little crossed.  What I had meant to tell Dave
> was that an Emacs-shebang script is faster at starting up and printing "Hello,
> world" than the equivalent ECL script -- which, for small little scripts,
> means that using Emacs Lisp could be more efficient than using CL standalone
> binaries.
>
> I did not compare my test with Bash, however, or with using more complex
> scripts, where I'd expect CL's native-language compilation to far outdo Emacs
> Lisp.

Dollars to doughnuts, John told me exactly what he had meant to, and I
was misremembering.  Sorry for the false... <what do you call that?>

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Re: Multithreading, again and again

[Richard Stallman]

    > For what it's worth, experiments show that launching Emacs
    > as a scripting engine (e.g. using it in a shebang) is actually more
    > efficient than launching some more traditional scripting languages.

    That's indeed unexpected.  Can you point to some more details?

I am amazed too.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use free telephony http://directory.fsf.org/category/tel/

Re: Multithreading, again and again

[SAKURAI Masashi]

Hi,

> on Wed Oct 19 2011, Tom Tromey <tromey-AT-redhat.com> wrote:
> 
> > [ threading ]
> >
> > Stefan> We could provide a `fork' primitive, indeed.
> >  :
> Again, I think some beautiful and usable library code could make this
> approach much more attractive and more widely used.  Emacs IPC anyone?

Now, I'm writing async rpc stack between Emacs and other programs
(including Emacs).  In last week, I showed a demo at YAPC::Asia 2011
at Tokyo. I'm going to show the code soon.


Well,
I think implementation of multithreading in Emacs is SO difficult to
add a threading feature after the language implementation. I think it
should be done at the language design level.

Actually, many scripting language could not get true concurrency by
the appended thread feature, such as Perl's ithread, ruby's thread,
python's one and so on. They have the GIL problem.

Ref:
  The Global Interpreter Lock and Ruby / Python concurrency | Merbist
  http://merbist.com/2011/10/03/about-concurrency-and-the-gil/

  AnyEvent, Coro, IO::AIO - a good team by Marc Lehmann (mlehmann)
  http://yapcasia.org/2011/slides/mlehmann/

Multi-threading and GUI is very sensitive topic. 

  Multithreaded toolkits: A failed dream? | Java.net
  http://weblogs.java.net/blog/kgh/archive/2004/10/multithreaded_t.html

I think this problem exists in Emacs too.


I wrote deferred.el and concurrent.el for non-preemptive threading
(Event model) in Emacs, as JavaScript's Deferred and Perl's AnyEvent
do. This elisp can retrieve some remote resources in parallel and wait
for them asynchronously. Although this implementation (deferred.el and
concurrent.el) may not be the best, I think this approach may be the
best approach to get the concurrency in Emacs.


--
SAKURAI, Masashi (family, given)
m.sakurai@kiwanami.net

Re: Multithreading, again and again

[Tom Tromey]

>>>>> ">" == SAKURAI Masashi <m.sakurai@kiwanami.net> writes:

>> Actually, many scripting language could not get true concurrency by
>> the appended thread feature, such as Perl's ithread, ruby's thread,
>> python's one and so on. They have the GIL problem.

Yeah.  On my branch, Emacs also has the GIL problem.
I don't consider it a big deal, since Emacs is also not a high
performance system.

>> Multi-threading and GUI is very sensitive topic. 
>>   Multithreaded toolkits: A failed dream? | Java.net
>>   http://weblogs.java.net/blog/kgh/archive/2004/10/multithreaded_t.html
>> I think this problem exists in Emacs too.

Emacs doesn't have this problem in the classic way, because most GUI
operations in Emacs Lisp are actually side effects of buffer- or keymap-
modifications.

Tom

Re: Multithreading, again and again

[Stefan Monnier]

>>> Multi-threading and GUI is very sensitive topic. 
>>> Multithreaded toolkits: A failed dream? | Java.net
>>> http://weblogs.java.net/blog/kgh/archive/2004/10/multithreaded_t.html
>>> I think this problem exists in Emacs too.
> Emacs doesn't have this problem in the classic way, because most GUI
> operations in Emacs Lisp are actually side effects of buffer- or keymap-
> modifications.

Or rather because Emacs's GUI is event driven and that your work doesn't
make it multithreaded.

Basically, Emacs uses a MVC approach and your work makes the controller
multithreaded but the viewer (which is implemented in C) is still single
threaded.


        Stefan

Re: Multithreading, again and again

[SAKURAI Masashi]

At Thu, 20 Oct 2011 14:17:46 -0400,
Stefan Monnier wrote:
> 
> >>> Multi-threading and GUI is very sensitive topic. 
> >>> Multithreaded toolkits: A failed dream? | Java.net
> >>> http://weblogs.java.net/blog/kgh/archive/2004/10/multithreaded_t.html
> >>> I think this problem exists in Emacs too.
> > Emacs doesn't have this problem in the classic way, because most GUI
> > operations in Emacs Lisp are actually side effects of buffer- or keymap-
> > modifications.
> 
> Or rather because Emacs's GUI is event driven and that your work doesn't
> make it multithreaded.
> 
> Basically, Emacs uses a MVC approach and your work makes the controller
> multithreaded but the viewer (which is implemented in C) is still single
> threaded.

I'm very interesting in the implementation of the event driven GUI and
MVC approach. Where should I read the sources in the Emacs repository?

Re: Multithreading, again and again

[Nix]

On 21 Oct 2011, SAKURAI Masashi uttered the following:

> At Thu, 20 Oct 2011 14:17:46 -0400,
> Stefan Monnier wrote:
>> Basically, Emacs uses a MVC approach and your work makes the controller
>> multithreaded but the viewer (which is implemented in C) is still single
>> threaded.
>
> I'm very interesting in the implementation of the event driven GUI and
> MVC approach. Where should I read the sources in the Emacs repository?

The split isn't that formal because Emacs predates even the first
academic descriptions of MVC by three years or so. But in a sense one
could consider the 'view' part to be the redisplay engine in xdisp.c and
dispnew.c (any thoughts on renaming that? It's not that 'new' anymore);
the model part is the Emacs datastructures that Lisp et al update, and
the functions that serve to keep them up to date, and the controller is
the Lisp, lisp evaluator, and assisting functions in C. The only really
solid part of this split is that nothing except redisplay draws to the
screen (except in extremis, e.g. crash messages).

-- 
NULL && (void)

Re: Multithreading, again and again

[Eli Zaretskii]

> From: Nix <nix@esperi.org.uk>
> Date: Fri, 21 Oct 2011 15:18:07 +0100
> Cc: tromey@redhat.com, monnier@IRO.UMontreal.CA, emacs-devel@gnu.org
> 
> 
> one could consider the 'view' part to be the redisplay engine in
> xdisp.c and dispnew.c

You forget the terminal-specific back-ends: xterm.c, w32term.c,
nsterm.m, term.c, and the *fns.c support functions.

> dispnew.c (any thoughts on renaming that? It's not that 'new' anymore)

What would be the purpose of such renaming, except confusing us
old-timers?  There are many modules in Emacs whose names no longer
reflect their code correctly -- xdisp.c is neither X only not
"extended", cmds.c is not the only file with commands, editfns.c is
not only about editing commands, etc. etc.

> The only really solid part of this split is that nothing except
> redisplay draws to the screen

Also note that in some situations, the "controller" in Emacs directly
calls the "view", without passing through the "model" and without
affecting it in any way.  Example: mouse highlight.

Re: Multithreading, again and again

[SAKURAI Masashi]

Thanks for comments from Nix and Eli!
I will read them and study concurrency in Emacs.


Anyway, I think the single-thread event driven approach is better for
Emacs, like Node.js and other languages do.


Thank you.

At Fri, 21 Oct 2011 16:48:05 +0200,
Eli Zaretskii wrote:
> 
> > From: Nix <nix@esperi.org.uk>
> > Date: Fri, 21 Oct 2011 15:18:07 +0100
> > Cc: tromey@redhat.com, monnier@IRO.UMontreal.CA, emacs-devel@gnu.org
> > 
> > 
> > one could consider the 'view' part to be the redisplay engine in
> > xdisp.c and dispnew.c
> 
> You forget the terminal-specific back-ends: xterm.c, w32term.c,
> nsterm.m, term.c, and the *fns.c support functions.
> 
> > dispnew.c (any thoughts on renaming that? It's not that 'new' anymore)
> 
> What would be the purpose of such renaming, except confusing us
> old-timers?  There are many modules in Emacs whose names no longer
> reflect their code correctly -- xdisp.c is neither X only not
> "extended", cmds.c is not the only file with commands, editfns.c is
> not only about editing commands, etc. etc.
> 
> > The only really solid part of this split is that nothing except
> > redisplay draws to the screen
> 
> Also note that in some situations, the "controller" in Emacs directly
> calls the "view", without passing through the "model" and without
> affecting it in any way.  Example: mouse highlight.

--
SAKURAI, Masashi (family, given)
m.sakurai@kiwanami.net

Re: Multithreading, again and again

[Tom Tromey]

>> Anyway, I think the single-thread event driven approach is better for
>> Emacs, like Node.js and other languages do.

Yes, maybe so, but I think there are two reasons concurrency is
desirable.

One reason is that, in practice, the current event-driven approach
sometimes falls down.  E.g., ERC can time out when something in Emacs
blocks too long.  These are bugs, and worse, won't be immediately fixed
by concurrency -- but at least could be, in the long run, in a permanent
way.

The other reason is that concurrency makes it easier to convert code to
run in the background, without a need for a drastic rewrite.  I think
Gnus is the prime candidate here -- make 'g' work in the background by
just inserting a (make-thread) at the appropriate juncture.  Rewriting
arbitrary code in the process-filter style is too much work, it seems to
me.

Tom

Re: Multithreading, again and again

[Dave Abrahams]

on Sat Oct 22 2011, Tom Tromey <tromey-AT-redhat.com> wrote:

>>> Anyway, I think the single-thread event driven approach is better for
>>> Emacs, like Node.js and other languages do.
>
> Yes, maybe so, but I think there are two reasons concurrency is
> desirable.
>
> One reason is that, in practice, the current event-driven approach
> sometimes falls down.  E.g., ERC can time out when something in Emacs
> blocks too long.  These are bugs, and worse, won't be immediately fixed
> by concurrency -- but at least could be, in the long run, in a permanent
> way.
>
> The other reason is that concurrency makes it easier to convert code to
> run in the background, without a need for a drastic rewrite.  I think
> Gnus is the prime candidate here -- make 'g' work in the background by
> just inserting a (make-thread) at the appropriate juncture.  Rewriting
> arbitrary code in the process-filter style is too much work, it seems to
> me.

Exactly my point.  The current facilities for doing concurrency are too
hard/unnatural to use for this kind of job.  If they were easier, it
might be more practical to offload more work to another process, and
more packages would do it.  At least until the cost of sending the
necessary s-expressions between processes becomes prohibitive, this
seems like a natural way to go that avoids making Emacs incredibly
brittle as I expect it would be if we started trying to run
single-threaded code in multiple threads.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Re: Multithreading, again and again

[Helmut Eller]

* Juri Linkov [2011-10-17 21:57] writes:

>> I don't think there is such a consensus, but better support for
>> concurrency is something I consider important.  It is currently much too
>> difficult to implement "asynchronous article fetch" and things like that.
>
> "Asynchronous article fetch" could be implemented with a simpler approach
> to run code in a "sandbox" similarly to HTML5 "workers" that run
> computationally expensive scripts in the background independently of any
> user interface scripts that allows for long-running scripts to be
> executed without yielding to keep the application responsive.  More at:
> http://www.whatwg.org/specs/web-apps/current-work/multipage/workers.html

I had proposed that here:
http://lists.gnu.org/archive/html/emacs-devel/2011-02/msg00383.html
but it was pretty much ridiculed.

Helmut

Re: Multithreading, again and again

[Helmut Eller]

* Dmitry Antipov [2011-09-28 06:49] writes:

> 7. Look around.
>    Has someone an experience with development of multithreaded code for
>    commercial Common Lisp implementations, most probably LispWorks and/or
>    Allegro CL? If yes, can someone briefly explain pros and cons of their
>    approach to multithreading?

LispWorks and Allegro support preemtive threads in the same address
space.  Decades ago, they started with an API similar to the Lisp
Machine and in recent years adapted it a bit to better match os-based
threads.  It's not very different from what you get with Java and rather
low level.

Helmut

Re: Multithreading, again and again

[Tom Tromey]

>>>>> "Dmitry" == Dmitry Antipov <dmantipov@yandex.ru> writes:

Sorry about the delay in my reply to this.
I was away for quite a while.

Dmitry> 0. What we have, and where we go.
Dmitry>    What's the status of git://gitorious.org/emacs-mt/emacs-mt.git and
Dmitry>    http://bzr.savannah.gnu.org/r/emacs/concurrency? Whether there are
Dmitry>    plans for further development?

I consider both of those obsolete.

The concurrency branch in bzr has some problems.  I think parts of it
are not a good direction to go.

I have a different branch here ("concurrency-2") but I haven't pushed it
yet.  I could do that if there is interest.  It is not yet at par with
the old concurrency branch; in fact in ways it is very far behind (I
didn't tackle bindings yet -- the code changed on the trunk and I'm not
sure the old code was correct anyhow).

I don't have much free time for hacking, so it is hard to make progress.
I could use some help!  I'd be happy to push my branch and write up what
I think should be done.

Dmitry> 1. To thread or not to thread?

I think so, but I don't know if there is consensus around it.

Dmitry> 2. Hide them all!
Dmitry>    Should the threads be visible (may be created and managed)
Dmitry>    from Lisp, or they can just do some work orthogonal to it? If
Dmitry>    latter, which tasks may be implicitly threaded? Redisplay
Dmitry>    (one thread per frame)? Buffer/socket I/O? GC? Is it feasible
Dmitry>    to implement full implicit concurrency? For the rough
Dmitry>    example, with the Lisp engine as the pool of threads, where
Dmitry>    (eval FORM) just queues the FORM and then ask the pool to
Dmitry>    find a free thread and evaluate it?

I think that generally threads should be explicit, just because that is
simpler to understand.  I find it hard to picture how some implicit
scheme could work.

There are two situations where I think some kind of hidden thread would
be useful.

One is DNS lookup.  This should be threaded internally, so that DNS
delays don't hang Emacs.  This could actually be done today without
requiring exposing threads to Emacs.

The other is the multiple keyboard case.  I think it should be possible
to have each 'emacsclient -t' run in a separate thread.

People have talked about making redisplay run in its own thread, but I
don't know anything about redisplay and so I haven't looked at it.

You could make the GC run in a separate thread, which would be pretty
cool, but I think it would be hard.

Dmitry> 3. Too big, too global.
Dmitry>    How to split/share/synchronize huge global state between threads?
Dmitry>    What should be thread-local? (I feel (current-buffer) should be
Dmitry>    global and max-lisp-eval-depth should be thread-local, but I suspect
Dmitry>    that there are much more controversial cases). Is it reasonable to
Dmitry>    have become-thread-local-on-write globals?

I think current-buffer has to be per-thread.  Anything else means that a
context switch can randomly change buffers.

A good chunk of the work is making decisions like this.  On the branch I
have moved a number of global variables into the 'struct thread' object.

I would rather not introduce new ways of doing variable bindings.  This
area is already very complicated, complicated enough that it is the main
problem in finishing this branch.  Instead, threads can use 'let' to
introduce a thread-local binding.

Dmitry> 4. Say "thread"!
Dmitry>    What should be done in C to implement thread management in Lisp?
Dmitry>    I feel basically
[...]

My plan was to follow the Bordeaux threads API, more or less.
This is something from CL.

Dmitry> 5. You and I.
Dmitry>    What synchronization primitives should be implemented? Atomic variables?
Dmitry>    Mutexes/semaphores? Barriers? Higher-level not-so-primitives like
Dmitry>    thread pools or multithreaded queues? Should some basic operations,
Dmitry>    like setq, be always atomic? Is it reasonable/feasible/useful to have
Dmitry>    special form like (with-atomic BODY...), where all BODY forms are evaluated
Dmitry>    atomically with respect to all other threads?

I was planning to just do some primitives (mutex and condition
variables) and then let people write whatever else in Lisp.

Dmitry> 6. Under the cover.
Dmitry>    What other low-level changes are required for thread support?
Dmitry>    Basic structure of Lisp objects? Multiple stacks scanning for GC?
Dmitry>    Per-thread heaps for small objects?

Lisp objects don't need to change.  I already made the GC work.  You
could do a per-thread heap if you wanted, though I don't think there is
a benefit yet, since (1) Emacs Lisp isn't exactly high performance,  and
(2) the initial threading model is "mostly cooperative", with context
switch occurring only at I/O and (thread-yield) calls.

Tom

Re: Multithreading, again and again

[Tom Tromey]

>>>>> "Dmitry" == Dmitry Antipov <dmantipov@yandex.ru> writes:

Forgot to mention...

Dmitry> 2. Hide them all!
Dmitry>    [...] Buffer/socket I/O? GC?

I think right now you can do things like:

   (let ((some-binding))
     (while (condition)
       (sit-for 0)))

... and expect that some-binding will be visible to the process filters.

So, while it is tempting to just move all process stuff to threads, that
could break code, so one must make it opt-in.

Dealing with the various aspects of this is one of the to-do items for
my branch.

Tom

Re: Multithreading, again and again

[Stefan Monnier]

> yet.  I could do that if there is interest.  It is not yet at par with
> the old concurrency branch; in fact in ways it is very far behind (I
> didn't tackle bindings yet -- the code changed on the trunk and I'm not
> sure the old code was correct anyhow).

Indeed, the bindings code has changed on the trunk a bit (hopefully it
is a bit more clear now).  Also the lexical-binding code (which mostly
hasn't touched the "bindings" code) means that the performance of
thread-local let bindings is a bit less important (only a bit, tho,
since there are still many variables one wants to let-bind and that are
used by the C code in performance sensitive areas).

> One is DNS lookup.  This should be threaded internally, so that DNS
> delays don't hang Emacs.  This could actually be done today without
> requiring exposing threads to Emacs.

Yes, that's actually largely unrelated to "multithreading in Emacs", but
making it interruptible (and maybe even let process-filters and timers
run during this time) would be a good change.

I also recently noticed that sometimes my Gnus is unresponsive for
a while (waiting for a remote server, maybe in DNS, tho I think not) and
while C-g does work, other things don't, most importantly clipboard
requests get delayed so if my Gnus session happens to own the clipboard
then C-y in another Emacs session hangs until the remote server replies.

> The other is the multiple keyboard case.  I think it should be possible
> to have each 'emacsclient -t' run in a separate thread.

This OTOH is pretty much "the general case" since it needs to deal with
running Elisp in different threads concurrently (and with recursive
edits and minibuffers, we want to be able to run one terminal's command
while some other terminal still has active let-bindings).

> People have talked about making redisplay run in its own thread, but I
> don't know anything about redisplay and so I haven't looked at it.

That one is mostly a classic "make an existing C program concurrent by
adding locks where needed".

> My plan was to follow the Bordeaux threads API, more or less.

I'm afraid that using locks is not going to work well for Elisp.  I have
much higher expectations for approaches based on yield (i.e. approaches
which are inherently safe(r), with the main risk being lack of
concurrency rather than race-conditions and corruption).

Maybe we can even make yield work for true concurrency by treating it as
a kind of "end previous transaction and then start a new one".

> I think right now you can do things like:

>    (let ((some-binding))
>      (while (condition)
>        (sit-for 0)))

> ... and expect that some-binding will be visible to the process filters.

Yes, that's a code pattern that doesn't interact well with threads.
We'll need to adjust/fix those cases one by one, I think.


        Stefan

Re: Multithreading, again and again

[Tom Tromey]

Stefan> I also recently noticed that sometimes my Gnus is unresponsive for
Stefan> a while (waiting for a remote server, maybe in DNS, tho I think not) and
Stefan> while C-g does work, other things don't, most importantly clipboard
Stefan> requests get delayed so if my Gnus session happens to own the clipboard
Stefan> then C-y in another Emacs session hangs until the remote server replies.

I have noticed this as well.  Annoyingly, it makes my ERC connections
time out.  I guess whatever is pausing is not properly accepting process
output or processing timers or something like that.

I was blaming opportunistic TLS for this but I didn't actually
investigate.

Tom> The other is the multiple keyboard case.  I think it should be possible
Tom> to have each 'emacsclient -t' run in a separate thread.

Stefan> This OTOH is pretty much "the general case" since it needs to deal with
Stefan> running Elisp in different threads concurrently (and with recursive
Stefan> edits and minibuffers, we want to be able to run one terminal's command
Stefan> while some other terminal still has active let-bindings).

I think it is doable, given the context-switching constraints I
mentioned earlier.

The long-term thing that would be cool is context-switching during QUIT.

I don't think unconstrained context-switching is possible without some
drastic changes to the implementation.

Tom> My plan was to follow the Bordeaux threads API, more or less.

Stefan> I'm afraid that using locks is not going to work well for Elisp.
Stefan> I have much higher expectations for approaches based on yield
Stefan> (i.e. approaches which are inherently safe(r), with the main
Stefan> risk being lack of concurrency rather than race-conditions and
Stefan> corruption).

Can you expand on this?

Tom> I think right now you can do things like:
Tom> (let ((some-binding))
Tom> (while (condition)
Tom> (sit-for 0)))
Tom> ... and expect that some-binding will be visible to the process filters.

Stefan> Yes, that's a code pattern that doesn't interact well with
Stefan> threads.  We'll need to adjust/fix those cases one by one, I
Stefan> think.

I was thinking of constraining a process to a particular thread by
default, then letting code set the process-thread to nil to mean that it
doesn't care where it is run.

But, if you think it is simpler to just fix the code, then I guess we
could drop this.  My general approach has been to be conservative about
changes to elisp semantics.

Tom

Re: Multithreading, again and again

[Stefan Monnier]

Stefan> I also recently noticed that sometimes my Gnus is unresponsive for
Stefan> a while (waiting for a remote server, maybe in DNS, tho I think not) and
Stefan> while C-g does work, other things don't, most importantly clipboard
Stefan> requests get delayed so if my Gnus session happens to own the clipboard
Stefan> then C-y in another Emacs session hangs until the remote server replies.
> I have noticed this as well.  Annoyingly, it makes my ERC connections
> time out.  I guess whatever is pausing is not properly accepting process
> output or processing timers or something like that.
> I was blaming opportunistic TLS for this but I didn't actually
> investigate.

Maybe you're right.  That deserves a separate bug report.

Tom> The other is the multiple keyboard case.  I think it should be possible
Tom> to have each 'emacsclient -t' run in a separate thread.
Stefan> This OTOH is pretty much "the general case" since it needs to deal with
Stefan> running Elisp in different threads concurrently (and with recursive
Stefan> edits and minibuffers, we want to be able to run one terminal's command
Stefan> while some other terminal still has active let-bindings).
> I think it is doable, given the context-switching constraints I
> mentioned earlier.

Yes a "simple" switch-on-yield should be sufficient (i.e. the old
concurrency branch should be able to handle it), but that still means
that solving such a problem requires handling interaction between the
various kinds of Elisp variable bindings (thread-local, buffer-local,
...).

> The long-term thing that would be cool is context-switching during QUIT.

I'm not sure it would be significantly easier than true concurrency.

> I don't think unconstrained context-switching is possible without some
> drastic changes to the implementation.

Why do you think so?

Tom> My plan was to follow the Bordeaux threads API, more or less.

Stefan> I'm afraid that using locks is not going to work well for Elisp.
Stefan> I have much higher expectations for approaches based on yield
Stefan> (i.e. approaches which are inherently safe(r), with the main
Stefan> risk being lack of concurrency rather than race-conditions and
Stefan> corruption).
> Can you expand on this?

I'm not sure what kind of expansion you'd like to see: if you forget
a lock you can get data corruption, whereas if you forget a yield you
may just block a bit more often than desired (but still less often than
in Emacs-23).

Tom> I think right now you can do things like:
Tom> (let ((some-binding))
Tom>   (while (condition)
Tom>   (sit-for 0)))
Tom> ... and expect that some-binding will be visible to the process filters.
Stefan> Yes, that's a code pattern that doesn't interact well with
Stefan> threads.  We'll need to adjust/fix those cases one by one, I
Stefan> think.
> I was thinking of constraining a process to a particular thread by
> default, then letting code set the process-thread to nil to mean that it
> doesn't care where it is run.

That might work, yes.  Good idea.

> But, if you think it is simpler to just fix the code, then I guess we
> could drop this.  My general approach has been to be conservative about
> changes to elisp semantics.

Indeed if we can avoid having to fix the code, it's usually better (the
"usually" is for the case where compatibility has significant adverse
effects on new clean code and the incompatibility is minor).


        Stefan

Re: Multithreading, again and again

[Tom Tromey]

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

Tom> I think it is doable, given the context-switching constraints I
Tom> mentioned earlier.

Stefan> Yes a "simple" switch-on-yield should be sufficient (i.e. the old
Stefan> concurrency branch should be able to handle it), but that still means
Stefan> that solving such a problem requires handling interaction between the
Stefan> various kinds of Elisp variable bindings (thread-local, buffer-local,
Stefan> ...).

Yes.

Tom> The long-term thing that would be cool is context-switching during QUIT.

Stefan> I'm not sure it would be significantly easier than true concurrency.

Tom> I don't think unconstrained context-switching is possible without some
Tom> drastic changes to the implementation.

Stefan> Why do you think so?

If you want all threads to run freely, then you have to make the Emacs C
code atomic with respect to any globally-visible change.  I just have no
confidence that it is this way right now.

Tom> My plan was to follow the Bordeaux threads API, more or less.

Stefan> I'm afraid that using locks is not going to work well for Elisp.
Stefan> I have much higher expectations for approaches based on yield
Stefan> (i.e. approaches which are inherently safe(r), with the main
Stefan> risk being lack of concurrency rather than race-conditions and
Stefan> corruption).

Tom> Can you expand on this?

Stefan> I'm not sure what kind of expansion you'd like to see: if you forget
Stefan> a lock you can get data corruption, whereas if you forget a yield you
Stefan> may just block a bit more often than desired (but still less often than
Stefan> in Emacs-23).

Ok, I thought by "yield" you were perhaps thinking of some kind of
co-routine-like model or something like that.  But if I read this
correctly you mean just a thread yield operation?  (Called
"thread-yield" on the concurrency-2 branch...)

I think cooperativeness doesn't really eliminate the need for locks,
especially because I plan to allow context switches at I/O (and some
other blocking operations, like mutex acquisition).

Of course, the situation is really a bit like process filters.  Probably
a lot of actually existing Emacs Lisp code will run fine with multiple
threads, even without any locking whatsoever.  That will remain true for
some time: either multiple threads will be due to multiple keyboards (in
which case users probably won't be surprised by odd behavior they caused
themselves) or multiple threads will be from new code using the new
feature, which generally won't be written to randomly stomp all over
everything.

Tom

Re: Multithreading, again and again

[Stefan Monnier]

> If you want all threads to run freely, then you have to make the Emacs C
> code atomic with respect to any globally-visible change.  I just have no
> confidence that it is this way right now.

Could be.  But even if we don't use true concurrency and only switch at
QUIT we still have the problem of higher-level synchronization: making
every primitive atomic might save us from core dumps but it won't be
sufficient to make the Elisp code work right.  Instead we'll have to
make sure the Elisp code uses proper synchronization, at which point
true concurrency should not be significantly harder.

I think I'm beginning to understand what you mean: you assume an Elisp
concurrency where synchronization is based on locking, so lack of locks
(i.e. an Elisp error) means that one thread can access a slot while
another is modifying it.  In that case, indeed, we'd want to make sure
that a mere Elisp error should not lead to core dumps.

But I assume a system where no matter how buggy the Elisp code, there
a thread will never be able to access a memory slot while it's being
modified by some other thread.

> I think cooperativeness doesn't really eliminate the need for locks,

I hope it will.

> especially because I plan to allow context switches at I/O (and some
> other blocking operations, like mutex acquisition).

Yes, I/O has a yield.  From where I stand a lock is a mutex is a lock.
And I can't think of any reason why you'd want mutexes if you have
cooperative multithreading.


        Stefan

Re: Multithreading, again and again

[Dave Abrahams]

on Thu Oct 20 2011, Stefan Monnier <monnier-AT-IRO.UMontreal.CA> wrote:

>> I think cooperativeness doesn't really eliminate the need for locks,
>
> I hope it will.

I think it can't.  If I write a (pure) function f today I should be able
to come back later and make its implementation multithreaded without
breaking all the other code that's running.  I don't see how I can do
that if instead of locking you plan to rely on people not-yielding.  If
there's no level at which parallelism can become an implementation
detail, I think you don't have a workable programming model.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Re: Multithreading, again and again

[Tom Tromey]

Stefan> I think I'm beginning to understand what you mean: you assume an Elisp
Stefan> concurrency where synchronization is based on locking, so lack of locks
Stefan> (i.e. an Elisp error) means that one thread can access a slot while
Stefan> another is modifying it.  In that case, indeed, we'd want to make sure
Stefan> that a mere Elisp error should not lead to core dumps.

Yeah, that is what I meant.  Sorry for not being totally clear.

I haven't looked for atomicity bugs in Emacs.  I can't imagine that they
do not exist, though.

Tom> especially because I plan to allow context switches at I/O (and some
To> other blocking operations, like mutex acquisition).

Stefan> Yes, I/O has a yield.  From where I stand a lock is a mutex is a lock.

Yeah, sorry for throwing that in.

Stefan> And I can't think of any reason why you'd want mutexes if you have
Stefan> cooperative multithreading.

I guess you can perhaps do without if you never change QUIT to context
switch.  Then you merely have to write all your code to know which
functions may wait for I/O or call thread-yield.

It is certainly no problem to just omit the locking code from the first
version.

Tom