"concurrency" branch updated

"concurrency" branch updated

[Ken Raeburn]

I’ve tried to get the concurrency branch updated with respect to master, including the handlerlist/catchlist merge and timerfd support. It seems to be working okay, passing the tests Tom checked it for it, and correctly running a few nice, simple tests that I tried. It also crashes on a not-so-nice, simple test I tried, but the old version did too. :-)

I dropped the changelogs. (Arguably maybe I should’ve pulled out just the branch-specific items and kept them?) I’ve tried to preserve the Windows-related changes, but not having a Windows box, I couldn’t test that part. I did some testing on Debian GNU/Linux and Mac OS X, but nothing fancy.

I haven’t done anything about addressing issues brought up a couple years back when this work was discussed here, but I’ve been starting to go back over some of those emails to see what’s needed.

Ken

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Ken Raeburn <raeburn@raeburn.org>
> Date: Sun, 1 Nov 2015 01:19:38 -0500
> 
> I’ve tried to get the concurrency branch updated with respect to master, including the handlerlist/catchlist merge and timerfd support. It seems to be working okay, passing the tests Tom checked it for it, and correctly running a few nice, simple tests that I tried. It also crashes on a not-so-nice, simple test I tried, but the old version did too. :-)

Thanks for working on this.

> I dropped the changelogs. (Arguably maybe I should’ve pulled out just the branch-specific items and kept them?)

There should be no need, the log messages will provide that
information when we merge the branch.

> I’ve tried to preserve the Windows-related changes, but not having a Windows box, I couldn’t test that part.

The Windows build was broken, I fixed it.

> I haven’t done anything about addressing issues brought up a couple years back when this work was discussed here, but I’ve been starting to go back over some of those emails to see what’s needed.

Thanks!

Re: "concurrency" branch updated

[John Wiegley]

>>>>> Ken Raeburn <raeburn@raeburn.org> writes:

> I’ve tried to get the concurrency branch updated with respect to master,
> including the handlerlist/catchlist merge and timerfd support. It seems to
> be working okay, passing the tests Tom checked it for it, and correctly
> running a few nice, simple tests that I tried. It also crashes on a
> not-so-nice, simple test I tried, but the old version did too. :-)

Hi Ken,

I'm unfamiliar so far with the content of the concurrency branch, what changes
it makes, and the threading model it proposes.  Could you please summarize the
state of the art for me, so that I know what this branch entails?

Opening a general discussion about concurrency is something I'd like to do
soon, but not until I better understand what has already taken place.

Thank you,
  John

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: "John Wiegley" <johnw@newartisans.com>
> Date: Mon, 02 Nov 2015 15:23:33 -0500
> Cc: "emacs-devel@gnu.org discussions" <emacs-devel@gnu.org>
> 
> I'm unfamiliar so far with the content of the concurrency branch, what changes
> it makes, and the threading model it proposes.  Could you please summarize the
> state of the art for me, so that I know what this branch entails?
> 
> Opening a general discussion about concurrency is something I'd like to do
> soon, but not until I better understand what has already taken place.

Start here:

  http://lists.gnu.org/archive/html/emacs-devel/2012-08/msg00313.html

and continue here:

  http://lists.gnu.org/archive/html/emacs-devel/2013-08/msg00704.html

(the second thread goes on for 2 or 3 months).

Re: "concurrency" branch updated

[Eli Zaretskii]

> Date: Mon, 02 Nov 2015 22:35:18 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: raeburn@raeburn.org, emacs-devel@gnu.org
> 
> Start here:
> 
>   http://lists.gnu.org/archive/html/emacs-devel/2012-08/msg00313.html
> 
> and continue here:
> 
>   http://lists.gnu.org/archive/html/emacs-devel/2013-08/msg00704.html
> 
> (the second thread goes on for 2 or 3 months).

Also, if you do

  git diff ...origin/concurrency

you will find among the changes a section for the ELisp manual that
describes the features on the Lisp level.  After that, src/thread.c,
src/systhread.c, and the rest of the C-level changes, for the gory
details.

Have fun!

Re: "concurrency" branch updated

[John Wiegley]

>>>>> Eli Zaretskii <eliz@gnu.org> writes:

> you will find among the changes a section for the ELisp manual that
> describes the features on the Lisp level. After that, src/thread.c,
> src/systhread.c, and the rest of the C-level changes, for the gory details.

> Have fun!

Thanks, Eli!  I will read through those carefully.

John

Re: "concurrency" branch updated

[Elias Mårtenson]

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

I started playing around with this branch a bit and I quickly discovered an
issue. I wanted to take the opportunity of describing this issue while at
the same time hopefully gain some insight into the design of the feature.

What I did was to write the following function:

    (defun foo ()
      (loop for i from 0 below 10
            do (message (format "Message %d" i))
            do (sit-for 1)))

I then started this function in a thread:

    (make-thread #'foo)

What happened was that the 10 messages were printed to the *Messages*
buffer without any delay between them, and then the entire Emacs session
became incredibly sluggish.

Looking at the implementation of sit-for, it seems as though it ends up
calling read-event on a different thread which is probably not a good idea.
Is this a correct assessment?

Regards,
Elias

On 3 November 2015 at 05:57, John Wiegley <johnw@newartisans.com> wrote:

> >>>>> Eli Zaretskii <eliz@gnu.org> writes:
>
> > you will find among the changes a section for the ELisp manual that
> > describes the features on the Lisp level. After that, src/thread.c,
> > src/systhread.c, and the rest of the C-level changes, for the gory
> details.
>
> > Have fun!
>
> Thanks, Eli!  I will read through those carefully.
>
> John
>
>

[-- Attachment #2: Type: text/html, Size: 2279 bytes --]

Re: "concurrency" branch updated

[Ken Raeburn]

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


> On Nov 2, 2015, at 22:58, Elias Mårtenson <lokedhs@gmail.com> wrote:
> 
> I started playing around with this branch a bit and I quickly discovered an issue. I wanted to take the opportunity of describing this issue while at the same time hopefully gain some insight into the design of the feature.
> 
> What I did was to write the following function:
> 
>     (defun foo ()
>       (loop for i from 0 below 10
>             do (message (format "Message %d" i))
>             do (sit-for 1)))
> 
> I then started this function in a thread:
> 
>     (make-thread #'foo)
> 
> What happened was that the 10 messages were printed to the *Messages* buffer without any delay between them, and then the entire Emacs session became incredibly sluggish.

Interesting… my use has been pretty minimal thus far, certainly not enough to be looking at performance issues. Though, I tried running your test case, and after displaying the messages, one per second, Emacs crashed! :-(

In my tests I’m usually running a pretty minimal environment — “emacs -Q”, no subprocesses or timers set up, Emacs should be basically quiescent when I’m not doing something to it. Could there have been any sort of input events pending (mouse motion, for example) that could cause it to skip the delay in sit-for in your test?

I do suspect that some things dealing with user input (reading, testing availability, even the flag indicating we’re waiting) might get confused in a multithreaded setup. The test I was using recently that reliably crashed Emacs was:

  (make-thread (lambda () (signal ‘foo nil)))

…though it has to be in an interactive Emacs, where the waiting_for_input flag can be set, which the “signal” routine really doesn’t like. Possibly waiting_for_input needs to be thread-local… or if it stays global, maybe Fsignal() just shouldn’t be looking at it any more.

A previous test which broke the pre-merged concurrency branch but which I haven’t tested recently was to create a thread and have it prompt for input… I think it was either yes-or-no-p or y-or-n-p; it seemed to put Emacs into a state where there were no key bindings, so it would complain about every character I typed.

So…yeah. Input seems to be a fragile area on the branch.

> Looking at the implementation of sit-for, it seems as though it ends up calling read-event on a different thread which is probably not a good idea. Is this a correct assessment?

Sounds about right to me, yes.

Ken

[-- Attachment #2: Type: text/html, Size: 4056 bytes --]

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Ken Raeburn <raeburn@raeburn.org>
> Date: Tue, 3 Nov 2015 04:40:11 -0500
> Cc: emacs-devel <emacs-devel@gnu.org>
> 
> I do suspect that some things dealing with user input (reading, testing
> availability, even the flag indicating we’re waiting) might get confused in a
> multithreaded setup. The test I was using recently that reliably crashed Emacs
> was:
> 
> (make-thread (lambda () (signal ‘foo nil)))
> 
> …though it has to be in an interactive Emacs, where the waiting_for_input flag
> can be set, which the “signal” routine really doesn’t like. Possibly
> waiting_for_input needs to be thread-local… or if it stays global, maybe
> Fsignal() just shouldn’t be looking at it any more.
> 
> A previous test which broke the pre-merged concurrency branch but which I
> haven’t tested recently was to create a thread and have it prompt for input… I
> think it was either yes-or-no-p or y-or-n-p; it seemed to put Emacs into a
> state where there were no key bindings, so it would complain about every
> character I typed.
> 
> So…yeah. Input seems to be a fragile area on the branch.

IMO, the concurrency branch needs someone motivated enough and with
enough resources to work on it, before it will be ready for prime
time.  Ideally, that should be Tom, but we can only hope he will find
time for that.  If not, then someone else.  I don't see how this could
be moved forward without some non-trivial effort.  The design is
simple and robust, and the implementation fairly simple and easy to
understand.  What's needed, IMO, is a lot of testing and debugging,
and quite a lot of the latter on the C level.

Re: "concurrency" branch updated

[Eli Zaretskii]

> Date: Tue, 3 Nov 2015 11:58:19 +0800
> From: Elias Mårtenson <lokedhs@gmail.com>
> 
> I started playing around with this branch a bit and I quickly discovered an
> issue.

If you have read the discussions to which I pointed, you know that
this branch is not yet ready for play.

> I wanted to take the opportunity of describing this issue while at the
> same time hopefully gain some insight into the design of the feature.
> 
> What I did was to write the following function:
> 
> (defun foo ()
> (loop for i from 0 below 10
> do (message (format "Message %d" i))
> do (sit-for 1)))
> 
> I then started this function in a thread:
> 
> (make-thread #'foo)
> 
> What happened was that the 10 messages were printed to the *Messages* buffer
> without any delay between them, and then the entire Emacs session became
> incredibly sluggish.

This works for me, at least in "emacs -Q".  I don't see any of the
abnormal behavior you describe.  Did you try in "emacs -Q"?

> Looking at the implementation of sit-for, it seems as though it ends up calling
> read-event on a different thread which is probably not a good idea.

How do you see that?

When I run your program under GDB, I see only one announcement of a
new thread, when I evaluate the call to make-thread.  Then I see a
single announcement of thread exit, when the thread finishes counting
to 10.  I see no additional threads.

In general, it would make very little sense for sit-for and/or
read-event to start a new thread and run there, for fairly obvious
reasons.  What can happen when you call sit-for is a switch to
another thread, if there is one.  But in this case, I don't expect
that to happen.

Re: "concurrency" branch updated

[Ken Raeburn]

> I'm unfamiliar so far with the content of the concurrency branch, what changes
> it makes, and the threading model it proposes.  Could you please summarize the
> state of the art for me, so that I know what this branch entails?

The email threads that Eli pointed to are the best starting point. I’m doing some catching up myself; I haven’t worked on this branch until recently, though I've gotten a basic understanding of some of it through working on the merge.  I’ve got to dig through the emails from earlier reviews of the code and make some notes on things not yet done.  In addition to some proposed code changes, I’m sure at a minimum much more testing and bug fixing is needed, some assessment of the performance, and possibly some utility functions would be nice to have (e.g., mutex-try-lock, mutex-timed-wait).

At some point, we’ll want to demonstrate practical utility; not a trivial demo program that displays a few messages, and nothing on the scale of rewriting all of Gnus to be multithreaded, but somewhere in between.  I’m not sure what would be a good example.  A version of generator.el that uses threads instead of the CPS transformation of everything is a possibility, and it would probably simplify the writing and compiling of the generators, but it’d probably be more heavy-weight at run time.  Prefetching files’ contents, or searching already-loaded files, while tags-query-replace waits for the user to respond to a prompt?  Improving fontification somehow?

Concurrent execution of Lisp code is a way off, but IMHO a desirable thing to shoot for, if we want Emacs to get faster as machines go for multicore rather than faster clocks.  Currently, only one thread runs Lisp at a time, and switching can happen only at certain points (when explicitly requested, or when select is called), though I think we should try to expand that set of points.  Tom suggested possibly doing it periodically when we invoke the QUIT macro, which would include various points in the bytecode interpreter.

> Opening a general discussion about concurrency is something I'd like to do
> soon, but not until I better understand what has already taken place.

Understood.  I think there may also be places where we could use threads less visible to the Lisp world; TLS and redisplay come to mind.

Ken

other "concurrency" approaches

[Nic Ferrier]

While you are all talking about the concurrency branch I thought I'd
drop a line about other approaches that may be more tactical but would
be beneficial.

Some work has done by JohnW, others and myself on concurrency through
processes and the use of the existing process interface.

It's quite difficult to do this, but very beneficial. In effect what
we've been trying to do is emulate a fork model by just starting emacs
as a separate process. The fork approach to multiprocessing, while being
the tried and tested and perhaps rather old fashioned approach, has also
been very successful in modern languages like Python
(https://docs.python.org/2/library/multiprocessing.html).

In Emacs this is difficult because we don't have fork. And we don't have
a straight forward way of starting an Emacs process without a gui. You
can start a daemon, but daemons aren't what you want. In addition the
protocol for talking to daemons over sockets isn't that easy either.

Fork looks very hard to solve, in the same way that threads are quite
hard to solve.

But starting a headless Emacs, given that we have daemon already,
wouldn't be that hard.

What you want is the ability to do something like this:


 (let ((proc (start-process "emacs" args-to-make-it-headless)))
   (process-send-string proc (prin1-to-string '(+ 1 (* 30 45))))
   (process-send-eof proc)
   (print (buffer-string (process-buffer proc))))

in other words, an Emacs that just reads forms from stdin and executes
them and outputs to stdout.

The only complex thing here is how Emacs would understand that a form
has ended. I considered here just using end of line as the terminator
and if the form couldn't be read just issuing a read error. Other more
complex readers with a better line oriented UI might come later... but
for the use case of starting an Emacs from Emacs and communicating with
it it wouldn't be necessary.

Doing just this relatively small change would make an enormous
difference to building concurrency stuff in Emacs.


Nic

Re: other "concurrency" approaches

[Eli Zaretskii]

> From: Nic Ferrier <nferrier@ferrier.me.uk>
> Date: Tue, 03 Nov 2015 11:50:37 +0000
> 
> Fork looks very hard to solve, in the same way that threads are quite
> hard to solve.
> 
> But starting a headless Emacs, given that we have daemon already,
> wouldn't be that hard.

What is a "headless Emacs"?

> What you want is the ability to do something like this:
> 
> 
>  (let ((proc (start-process "emacs" args-to-make-it-headless)))
>    (process-send-string proc (prin1-to-string '(+ 1 (* 30 45))))
>    (process-send-eof proc)
>    (print (buffer-string (process-buffer proc))))
> 
> in other words, an Emacs that just reads forms from stdin and executes
> them and outputs to stdout.

This sounds like a description of -batch, but you already know about
it, so I'm quite sure I'm missing something important here.

Re: other "concurrency" approaches

[Nic Ferrier]

Eli Zaretskii <eliz@gnu.org> writes:

>> What you want is the ability to do something like this:
>> 
>> 
>>  (let ((proc (start-process "emacs" args-to-make-it-headless)))
>>    (process-send-string proc (prin1-to-string '(+ 1 (* 30 45))))
>>    (process-send-eof proc)
>>    (print (buffer-string (process-buffer proc))))
>> 
>> in other words, an Emacs that just reads forms from stdin and executes
>> them and outputs to stdout.
>
> This sounds like a description of -batch, but you already know about
> it, so I'm quite sure I'm missing something important here.

-batch has a peculiar environment, it does not read the user's
environment.


Nic

Re: other "concurrency" approaches

[Eli Zaretskii]

> From: Nic Ferrier <nferrier@ferrier.me.uk>
> Cc: emacs-devel@gnu.org
> Date: Tue, 03 Nov 2015 17:16:10 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> What you want is the ability to do something like this:
> >> 
> >> 
> >>  (let ((proc (start-process "emacs" args-to-make-it-headless)))
> >>    (process-send-string proc (prin1-to-string '(+ 1 (* 30 45))))
> >>    (process-send-eof proc)
> >>    (print (buffer-string (process-buffer proc))))
> >> 
> >> in other words, an Emacs that just reads forms from stdin and executes
> >> them and outputs to stdout.
> >
> > This sounds like a description of -batch, but you already know about
> > it, so I'm quite sure I'm missing something important here.
> 
> -batch has a peculiar environment, it does not read the user's
> environment.

You mean, the init files?  But you can load them via -l, no?

Re: other "concurrency" approaches

[Nic Ferrier]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Nic Ferrier <nferrier@ferrier.me.uk>
>> Cc: emacs-devel@gnu.org
>> Date: Tue, 03 Nov 2015 17:16:10 +0000
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> What you want is the ability to do something like this:
>> >> 
>> >> 
>> >>  (let ((proc (start-process "emacs" args-to-make-it-headless)))
>> >>    (process-send-string proc (prin1-to-string '(+ 1 (* 30 45))))
>> >>    (process-send-eof proc)
>> >>    (print (buffer-string (process-buffer proc))))
>> >> 
>> >> in other words, an Emacs that just reads forms from stdin and executes
>> >> them and outputs to stdout.
>> >
>> > This sounds like a description of -batch, but you already know about
>> > it, so I'm quite sure I'm missing something important here.
>> 
>> -batch has a peculiar environment, it does not read the user's
>> environment.
>
> You mean, the init files?  But you can load them via -l, no?

That fixes the init files but doesn't fix the environment. There are all
sorts of little things wrong.

There's also something wrong with stdin in that scenario as I recall.

Why don't you try it and see what I mean?



Nic

Re: other "concurrency" approaches

[Eli Zaretskii]

> From: Nic Ferrier <nferrier@ferrier.me.uk>
> Cc: emacs-devel@gnu.org
> Date: Tue, 03 Nov 2015 22:28:03 +0000
> 
> >> -batch has a peculiar environment, it does not read the user's
> >> environment.
> >
> > You mean, the init files?  But you can load them via -l, no?
> 
> That fixes the init files but doesn't fix the environment. There are all
> sorts of little things wrong.

What is "environment" in this context?

Re: "concurrency" branch updated

[Filipp Gunbin]

On 03/11/2015 04:40 -0500, Ken Raeburn wrote:

> At some point, we’ll want to demonstrate practical utility; not a
> trivial demo program that displays a few messages, and nothing on the
> scale of rewriting all of Gnus to be multithreaded, but somewhere in
> between.

Tramp operations or Gnus news retrieval in parallel thread would be
highly appreciated ;-)

Re: "concurrency" branch updated

[Michael Albinus]

Filipp Gunbin <fgunbin@fastmail.fm> writes:

>> At some point, we’ll want to demonstrate practical utility; not a
>> trivial demo program that displays a few messages, and nothing on the
>> scale of rewriting all of Gnus to be multithreaded, but somewhere in
>> between.
>
> Tramp operations or Gnus news retrieval in parallel thread would be
> highly appreciated ;-)

For Tramp, this has been discussed already in the past (and I did also
some experiments). Outcome in short: We would need new asynchronous
primitive file operations (or add an asynchronous flag to the existing
operations). Otherwise, it would break too many packages, which expect a
defined result of a file operation, when the function returns.

I would be happy to add asynchronous support to Tramp. After the design
has been fixed. `copy-file' might be a good candidate for a first shot.

See (info "(elisp) Magic File Names") for a complete list of primitive
functions supported by Tramp and other file name handlers.

Best regards, Michael.

Re: "concurrency" branch updated

[Thierry Volpiatto]

Michael Albinus <michael.albinus@gmx.de> writes:

> Filipp Gunbin <fgunbin@fastmail.fm> writes:
>
>>> At some point, we’ll want to demonstrate practical utility; not a
>>> trivial demo program that displays a few messages, and nothing on the
>>> scale of rewriting all of Gnus to be multithreaded, but somewhere in
>>> between.
>>
>> Tramp operations or Gnus news retrieval in parallel thread would be
>> highly appreciated ;-)
>
> For Tramp, this has been discussed already in the past (and I did also
> some experiments). Outcome in short: We would need new asynchronous
> primitive file operations (or add an asynchronous flag to the existing
> operations). Otherwise, it would break too many packages, which expect a
> defined result of a file operation, when the function returns.
>
> I would be happy to add asynchronous support to Tramp. After the design
> has been fixed. `copy-file' might be a good candidate for a first shot.

FYI async package is already able to copy remote files async from dired
or from helm.

-- 
Thierry

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Ken Raeburn <raeburn@raeburn.org>
> Date: Tue, 3 Nov 2015 04:40:25 -0500
> Cc: "emacs-devel@gnu.org discussions" <emacs-devel@gnu.org>
> 
> At some point, we’ll want to demonstrate practical utility; not a trivial demo program that displays a few messages, and nothing on the scale of rewriting all of Gnus to be multithreaded, but somewhere in between.  I’m not sure what would be a good example.  A version of generator.el that uses threads instead of the CPS transformation of everything is a possibility, and it would probably simplify the writing and compiling of the generators, but it’d probably be more heavy-weight at run time.  Prefetching files’ contents, or searching already-loaded files, while tags-query-replace waits for the user to respond to a prompt?  Improving fontification somehow?

Given that only one thread can run Lisp, is the above even possible?

> Understood.  I think there may also be places where we could use threads less visible to the Lisp world; TLS and redisplay come to mind.

Given the general model-view-controller design of Emacs and the
structure of its main loop, is making redisplay run in a separate
thread really viable?

Re: "concurrency" branch updated

[Ken Raeburn]

> On Nov 3, 2015, at 11:29, Eli Zaretskii <eliz@gnu.org> wrote:
> 
>> From: Ken Raeburn <raeburn@raeburn.org>
>> Date: Tue, 3 Nov 2015 04:40:25 -0500
>> Cc: "emacs-devel@gnu.org discussions" <emacs-devel@gnu.org>
>> 
>> At some point, we’ll want to demonstrate practical utility; not a trivial demo program that displays a few messages, and nothing on the scale of rewriting all of Gnus to be multithreaded, but somewhere in between.  I’m not sure what would be a good example.  A version of generator.el that uses threads instead of the CPS transformation of everything is a possibility, and it would probably simplify the writing and compiling of the generators, but it’d probably be more heavy-weight at run time.  Prefetching files’ contents, or searching already-loaded files, while tags-query-replace waits for the user to respond to a prompt?  Improving fontification somehow?
> 
> Given that only one thread can run Lisp, is the above even possible?

Implementing a generator with a thread seems somewhat straightforward, needing some sort of simple communication channel between the main thread and the generator thread to pass “need next value” and “here’s the next value” messages back and forth; some extra work would be needed so that dropping all references to a generator makes everything, including the thread, go away.  Raising an error in the thread’s “yield” calls may be a way to tackle that, though it changes the semantics within the generator a bit.

For prefetching file contents or searching existing buffers, the “main” thread can release the global lock when it prompts for the user’s input, and a background thread can create buffers and load files, or search buffers for patterns, tossing results onto some sort of queue or other data structure for consumption by the main thread when it finishes with the file it’s on.

Inserting a file’s contents or searching a large buffer can take a long time, though, so these could make the interactive experience sluggish at times depending on what’s going on in background, unless we find a way to do some of these operations without holding the global lock.  (Aside: Has anyone thought about applying JIT native code generation or translation-to-C to regular expressions?)  And loading a file can prompt for local variable settings and such, which could get kind of confusing if mixed with tags-query-replace prompting relating to a different file, but refactoring insert-file-contents into a minimal file-reading routine that does no Lisp callbacks and another to deal with file name handlers and hooks and such could let us do the former on a helper thread and the latter (which could prompt the user) in the main thread at the expected time.

Both of those examples are mainly about running some extra work in the moments while we’re waiting for the user to respond to a prompt.  We may be able to do the same with idle timers or other such mechanisms.  In cases like that, I think it may come down to whether it’s easier and/or more maintainable to write code that cranks through the next step of an explicitly managed state machine, or structured code that maintains its state in program counters and variables local to each stack frame… sometimes it’s one, sometimes it’s the other.

As to fontification… I expect the code is pretty tight now, but maybe someone who knows that code has some insight into whether we could do it better with more CPU cores available.

So… yeah, I think some of them are possible, but I’m not sure any of them would be a particularly good way to show off.  Got any suggestions?


> 
>> Understood.  I think there may also be places where we could use threads less visible to the Lisp world; TLS and redisplay come to mind.
> 
> Given the general model-view-controller design of Emacs and the
> structure of its main loop, is making redisplay run in a separate
> thread really viable?

I’m not sure.  I’m not picturing redisplay running concurrently with Lisp so much as redisplay on display 1 running concurrently with redisplay on display 2, all happening at the same point in the code where we now run redisplay.  (Ignoring for the moment the bits where redisplay can trigger Lisp evaluation.)

Under X11 I doubt trying to process different frames on the same display in different threads would help at all, given that the data still all goes through one network connection.  I expect that display updates on Windows, being on the local machine, are fast enough that even if concurrent updates by two or more threads go faster than fully serialized updates, it wouldn’t make much difference in the user experience.  Though I am making some assumptions that redisplay isn’t doing many costly calculations compared to the cost of pushing the bits to the glass.

I suspect TLS is probably the more interesting case.

Ken

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Ken Raeburn <raeburn@raeburn.org>
> Date: Wed, 4 Nov 2015 04:20:37 -0500
> Cc: johnw@newartisans.com,
>  emacs-devel@gnu.org
> 
> > On Nov 3, 2015, at 11:29, Eli Zaretskii <address@hidden> wrote:
> > 
> >> From: Ken Raeburn <address@hidden>
> >> Date: Tue, 3 Nov 2015 04:40:25 -0500
> >> Cc: "address@hidden discussions" <address@hidden>
> >> 
> >> At some point, we’ll want to demonstrate practical utility; not a trivial 
> >> demo program that displays a few messages, and nothing on the scale of 
> >> rewriting all of Gnus to be multithreaded, but somewhere in between.  I’m 
> >> not sure what would be a good example.  A version of generator.el that uses 
> >> threads instead of the CPS transformation of everything is a possibility, 
> >> and it would probably simplify the writing and compiling of the generators, 
> >> but it’d probably be more heavy-weight at run time.  Prefetching files’ 
> >> contents, or searching already-loaded files, while tags-query-replace waits 
> >> for the user to respond to a prompt?  Improving fontification somehow?
> > 
> > Given that only one thread can run Lisp, is the above even possible?
> 
> Implementing a generator with a thread seems somewhat straightforward, needing 
> some sort of simple communication channel between the main thread and the 
> generator thread to pass “need next value” and “here’s the next value” messages 
> back and forth; some extra work would be needed so that dropping all references 
> to a generator makes everything, including the thread, go away.  Raising an 
> error in the thread’s “yield” calls may be a way to tackle that, though it 
> changes the semantics within the generator a bit.

Both the generator and its consumer run Lisp, so they can only run in
sequence.  How is this different from running them both in a single
thread?

> For prefetching file contents or searching existing buffers, the “main” thread 
> can release the global lock when it prompts for the user’s input, and a 
> background thread can create buffers and load files, or search buffers for 
> patterns, tossing results onto some sort of queue or other data structure for 
> consumption by the main thread when it finishes with the file it’s on.

But then you are not talking about "normal" visiting of files or
searching of buffers.  You are talking about specialized features that
visit large number of files or are capable of somehow marking lots of
search hits for future presentation to users.  That is a far cry from
how we do this stuff currently -- you ask the user first, _then_ you
search or visit the file she asked for.

> refactoring insert-file-contents into a minimal file-reading routine
> that does no Lisp callbacks and another to deal with file name
> handlers and hooks and such could let us do the former on a helper
> thread and the latter (which could prompt the user) in the main
> thread at the expected time.

You are talking about some significant refactoring here, we currently
o all of this on the fly.  In any case, I can understand how this
would be a win with remote files, but with local files I'm quite sure
most of the time for inserting a file is taken by stuff like decoding
its contents, which we also do on the fly and which can call Lisp.
The I/O itself is quite fast nowadays, I think.  Just compare
insert-file-contents with insert-file-contents-literally for the same
large file, and see the big difference, especially if it includes some
non-ASCII text.

> Both of those examples are mainly about running some extra work in the moments 
> while we’re waiting for the user to respond to a prompt.  We may be able to do 
> the same with idle timers or other such mechanisms.  In cases like that, I 
> think it may come down to whether it’s easier and/or more maintainable to write 
> code that cranks through the next step of an explicitly managed state machine, 
> or structured code that maintains its state in program counters and variables 
> local to each stack frame… sometimes it’s one, sometimes it’s the other.
> 
> As to fontification… I expect the code is pretty tight now, but maybe someone 
> who knows that code has some insight into whether we could do it better with 
> more CPU cores available.
> 
> So… yeah, I think some of them are possible, but I’m not sure any of them would 
> be a particularly good way to show off.  Got any suggestions?

I think features that use timers, and idle timers in particular, are
natural candidates for using threads.  Stealth font-lock comes to
mind, for example.

> >> Understood.  I think there may also be places where we could use threads 
> >> less visible to the Lisp world; TLS and redisplay come to mind.
> > 
> > Given the general model-view-controller design of Emacs and the
> > structure of its main loop, is making redisplay run in a separate
> > thread really viable?
> 
> I’m not sure.  I’m not picturing redisplay running concurrently with Lisp so 
> much as redisplay on display 1 running concurrently with redisplay on display 
> 2, all happening at the same point in the code where we now run redisplay.  

Why is this use case important?  Do we really believe someone might
look at 2 different X displays at the same time?  Perhaps you meant
frames, not displays.  This could make a lot of sense, except that:

> (Ignoring for the moment the bits where redisplay can trigger Lisp evaluation.)

We cannot really ignore that, because this feature is used a lot.
However, the global lock will probably solve this.

A more problematic issue is that the display engine currently assumes
that (almost) nothing happens with buffers and strings while it does
its job.  If redisplay is multithreaded, we need to make sure no other
thread that can touch Lisp data could run.

> I am making some assumptions that redisplay isn’t doing many costly
> calculations compared to the cost of pushing the bits to the glass.

That's not really true, although the display engine tries very hard to
be very fast.  But I've seen cycles taking 10 msec and even 50 msec
(which already borders on crossing the annoyance threshold).  So there
are some pretty costly calculations during redisplay, which is why the
display engine is heavily optimized to avoid them as much as possible.

> I suspect TLS is probably the more interesting case.

What do we have in TLS that we don't have in any network connection?

Re: "concurrency" branch updated

[Ken Raeburn]

>> 
>> Implementing a generator with a thread seems somewhat straightforward, needing 
>> some sort of simple communication channel between the main thread and the 
>> generator thread to pass “need next value” and “here’s the next value” messages 
>> back and forth; some extra work would be needed so that dropping all references 
>> to a generator makes everything, including the thread, go away.  Raising an 
>> error in the thread’s “yield” calls may be a way to tackle that, though it 
>> changes the semantics within the generator a bit.
> 
> Both the generator and its consumer run Lisp, so they can only run in
> sequence.  How is this different from running them both in a single
> thread?

In this case, it’s about how you'd write the generator code.  While the multithreaded version would have other issues (like having to properly quit the new thread when we’re done with the generator), it wouldn’t require writing everything using special macros to do CPS transformations.  If I want to yield values from within a function invoked via mapcar, I don’t have to write an iter-mapcar macro to turn everything inside-out under the covers.

> 
>> For prefetching file contents or searching existing buffers, the “main” thread 
>> can release the global lock when it prompts for the user’s input, and a 
>> background thread can create buffers and load files, or search buffers for 
>> patterns, tossing results onto some sort of queue or other data structure for 
>> consumption by the main thread when it finishes with the file it’s on.
> 
> But then you are not talking about "normal" visiting of files or
> searching of buffers.  You are talking about specialized features that
> visit large number of files or are capable of somehow marking lots of
> search hits for future presentation to users.  That is a far cry from
> how we do this stuff currently -- you ask the user first, _then_ you
> search or visit the file she asked for.

I haven’t used tags-query-replace in a while, but I don’t recall it asking me if I wanted to visit each file.  But yes, I’m thinking of larger operations where the next stage is fairly predictable, and probably does no harm if we optimistically start it early.  Smaller stuff may be good too (I hope), but I’d guess there’s a greater chance the thread-switching overhead could become an issue; I could well be overestimating it.  And some of the simpler ones, like highlighting all regexp matches in the visible part of the current buffer while doing a search, are already done, though we could look at how the code would compare if rewritten to use threads.


> You are talking about some significant refactoring here, we currently
> o all of this on the fly.  In any case, I can understand how this
> would be a win with remote files, but with local files I'm quite sure
> most of the time for inserting a file is taken by stuff like decoding
> its contents, which we also do on the fly and which can call Lisp.
> The I/O itself is quite fast nowadays, I think.  Just compare
> insert-file-contents with insert-file-contents-literally for the same
> large file, and see the big difference, especially if it includes some
> non-ASCII text.

I haven’t done that test, but I have used an NFS server that got slow at times.  And NFS from Amazon virtual machines back to my office, which is always a bit slow.  And sshfs, which can be slow too.  None of which Emacs can do anything about directly.

>> So… yeah, I think some of them are possible, but I’m not sure any of them would 
>> be a particularly good way to show off.  Got any suggestions?
> 
> I think features that use timers, and idle timers in particular, are
> natural candidates for using threads.  Stealth font-lock comes to
> mind, for example.

That’s what I was thinking of when I mentioned fontification.  I hope thread switches are fast enough.

>> I’m not sure.  I’m not picturing redisplay running concurrently with Lisp so 
>> much as redisplay on display 1 running concurrently with redisplay on display 
>> 2, all happening at the same point in the code where we now run redisplay.  
> 
> Why is this use case important?  Do we really believe someone might
> look at 2 different X displays at the same time?

No, but occasionally redisplay still needs to talk to multiple displays and get responses back, even with the work you and Stefan have done.  Fortunately, it’s much more rare now, and the color-handling work I did may help further.  And people using multiple displays *and* slow display connections like me are probably not very common among the user base.  So it’s an area where threads might help, but maybe not a terribly important one for the project.

>> I am making some assumptions that redisplay isn’t doing many costly
>> calculations compared to the cost of pushing the bits to the glass.
> 
> That's not really true, although the display engine tries very hard to
> be very fast.  But I've seen cycles taking 10 msec and even 50 msec
> (which already borders on crossing the annoyance threshold).  So there
> are some pretty costly calculations during redisplay, which is why the
> display engine is heavily optimized to avoid them as much as possible.

In that case, maybe it’s still worth considering after all.

> 
>> I suspect TLS is probably the more interesting case.
> 
> What do we have in TLS that we don't have in any network connection?

Encryption, optional compression, possibly key renegotiation, possible receipt of incomplete messages that can’t yet be decrypted and thus can’t give us any new data bytes.  The thread(s) running user Lisp code needn’t spend any cycles on these things.

Ken

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Ken Raeburn <raeburn@raeburn.org>
> Date: Wed, 4 Nov 2015 14:48:12 -0500
> Cc: johnw@newartisans.com,
>  emacs-devel@gnu.org
> 
> >> I suspect TLS is probably the more interesting case.
> > 
> > What do we have in TLS that we don't have in any network connection?
> 
> Encryption, optional compression, possibly key renegotiation, possible receipt of incomplete messages that can’t yet be decrypted and thus can’t give us any new data bytes.

Doesn't all that become insignificant compared to network latencies?

Re: "concurrency" branch updated

[Ken Raeburn]

>>> What do we have in TLS that we don't have in any network connection?
>> 
>> Encryption, optional compression, possibly key renegotiation, possible receipt of incomplete messages that can’t yet be decrypted and thus can’t give us any new data bytes.
> 
> Doesn't all that become insignificant compared to network latencies?

Not if I’m requesting a large amount of data from the server at once, or pipelining requests, or talking to multiple servers at once; I could have a steady stream of encrypted data coming in, and the latency from making a particular request to getting the corresponding response may not be important.

Whether the bandwidth available is enough that decrypting plus parsing (assuming we’re encrypting some network protocol and not an opaque file transfer) plus updating data structures plus UI updates plus the occasional GC is more than one thread can keep up with, that’s the question….  With additional C-level threads for managing TLS connections, we can at least take the decryption part out of that list and run it concurrently, without needing full Lisp-level thread support.

Ken

Re: "concurrency" branch updated

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

We don't need radical changes such as CPS to implement concurrent Lisp.
All we need is multiple stacks.

It seems to me that in Emacs there is no need to be able to switch threads
except when a thread is waiting.  That should make things much simpler.

-- 
Dr Richard Stallman
President, Free Software Foundation (gnu.org, fsf.org)
Internet Hall-of-Famer (internethalloffame.org)
Skype: No way! See stallman.org/skype.html.

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> CC: eliz@gnu.org, johnw@newartisans.com, emacs-devel@gnu.org
> Date: Wed, 04 Nov 2015 18:09:32 -0500
> 
> It seems to me that in Emacs there is no need to be able to switch threads
> except when a thread is waiting.  That should make things much simpler.

That's what the concurrency branch does.

Re: "concurrency" branch updated

[Ken Raeburn]

> It seems to me that in Emacs there is no need to be able to switch threads
> except when a thread is waiting.  That should make things much simpler.

Simpler, yes, but also more limiting.  Any large computational task needs to be written to surrender control now and then, if it might be used in an Emacs session that also talks to network servers that may time out and close connections if Emacs ignores them for too long.  I’ve had that happen.  Long delays waiting on a file system read operation (from NFS server or network hiccups) can have a similar effect, though we can probably arrange for some file operations to permit switching even if they’re normally quite fast.

I think preemptive thread switching (or real concurrent execution) is a better place to wind up, but cooperative thread switching is a good start.

Ken

Re: "concurrency" branch updated

[John Wiegley]

>>>>> Ken Raeburn <raeburn@raeburn.org> writes:

>> It seems to me that in Emacs there is no need to be able to switch threads
>> except when a thread is waiting. That should make things much simpler.

> I think preemptive thread switching (or real concurrent execution) is a
> better place to wind up, but cooperative thread switching is a good start.

I haven't had a chance to read this entire thread yet, but I wanted to chime
in and agree with both Richard and Ken. I have relatively few fears about
cooperative thread switching. Also, it gives us a chance to see how people
deal with debugging the sorts of issues it can lead to (e.g., a backtrace from
code unrelated to something you think you just did).

Upgrading to preemptive switching could happen later, once we've had more
experience with writing cooperative code. I hope at that point it would be a
fairly seamless upgrade, and we'd have mature facilities in place to
accommodate it (i.e., the ability to "stack" backtraces, to inspect the
environment of inactive threads, a messaging facility between threads to avoid
global mutation, etc).

What I want most is to make deadlocks and race conditions naturally hard to
write -- if not impossible. The rise of Heisenbugs could make our job as
maintainers much more difficult. All the worst bugs in my programming career
were related to preemptive threading in some way.

John

Re: "concurrency" branch updated

[David Kastrup]

John Wiegley <johnw@newartisans.com> writes:

>>>>>> Ken Raeburn <raeburn@raeburn.org> writes:
>
>>> It seems to me that in Emacs there is no need to be able to switch threads
>>> except when a thread is waiting. That should make things much simpler.
>
>> I think preemptive thread switching (or real concurrent execution) is a
>> better place to wind up, but cooperative thread switching is a good start.
>
> I haven't had a chance to read this entire thread yet, but I wanted to chime
> in and agree with both Richard and Ken. I have relatively few fears about
> cooperative thread switching. Also, it gives us a chance to see how people
> deal with debugging the sorts of issues it can lead to (e.g., a backtrace from
> code unrelated to something you think you just did).
>
> Upgrading to preemptive switching could happen later, once we've had more
> experience with writing cooperative code.

It depends on what "upgrading" means.  For example, Lua offers
"coroutines" which are basically not more than independent stacks but
not parallel execution: the corresponding functions, "yield" and
"resume" both _take_ and _return_ values.  Essentially, this is used as
a control flow mechanism similar to function calls and returns, with the
difference that such "functions" do not lose their place and local
variables when "returning" but continue upon resuming.

Since the switching of threads is accompanied by a passing of values,
executing such threads in parallel is not an option and thus there are
no concurrency issues.

I've used this kind of control flow (basically swapping in a different
stack and returning) in terminal emulators written in assembly language
to good effect: code becomes much more readable if the various code
paths interpreting terminal control sequences can just "call" the user
program for additional characters (where "call" means returning to the
user program and laying dormant until the terminal emulator gets called
with the next character) without losing the place in the logic of the
terminal emulator.

This kind of stack swap is not the same as true multithreading.  It
definitely has interesting applications with regard to things like
generators and streams as it may lead to much more straightforward code
than trying to maintain some internal state in closure variables queried
on reentry when the most natural representation of the internal state
you'd want to maintain is the current instruction and stack pointer.

I think Ada has the concept of "rendezvous" for multithreading where
there are well-defined synchronous parts of interaction as well as
asynchronous execution.

> I hope at that point it would be a fairly seamless upgrade,

For some kinds of control flow application, parallelism might not even
be an option.

-- 
David Kastrup

Re: "concurrency" branch updated

[John Wiegley]

>>>>> David Kastrup <dak@gnu.org> writes:

> For example, Lua offers "coroutines" which are basically not more than
> independent stacks but not parallel execution: the corresponding functions,
> "yield" and "resume" both _take_ and _return_ values. Essentially, this is
> used as a control flow mechanism similar to function calls and returns, with
> the difference that such "functions" do not lose their place and local
> variables when "returning" but continue upon resuming.

What you describe sounds similar to several libraries used often in Haskell,
where continuations are used to shuttle control up and down a connected
pipeline of coordinated functions (see 'pipes' if interested). Parallel
execution cannot be automatically enabled there either, though it can be
injected between stages (see 'pipes-async').

John

Re: "concurrency" branch updated

[Tom Tromey]

John> Upgrading to preemptive switching could happen later, once we've
John> had more experience with writing cooperative code. I hope at that
John> point it would be a fairly seamless upgrade, and we'd have mature
John> facilities in place to accommodate it (i.e., the ability to
John> "stack" backtraces, to inspect the environment of inactive
John> threads, a messaging facility between threads to avoid global
John> mutation, etc).

I don't understand what stacking backtraces is.

Messaging is already on the branch; or rather, locks and condition
variables are on the branch, and it's simple to build thread-safe pipes
and queues and whatnot using those.

John> What I want most is to make deadlocks and race conditions
John> naturally hard to write -- if not impossible. The rise of
John> Heisenbugs could make our job as maintainers much more
John> difficult. All the worst bugs in my programming career were
John> related to preemptive threading in some way.

Race-free-ness will not come from this branch.  It takes a traditional
threads-and-locks approach.

Tom

Re: "concurrency" branch updated

[John Wiegley]

>>>>> Tom Tromey <tom@tromey.com> writes:

> I don't understand what stacking backtraces is.

When a signal occurs while you're already looking at a backtrace.

> Messaging is already on the branch; or rather, locks and condition variables
> are on the branch, and it's simple to build thread-safe pipes and queues and
> whatnot using those.

I definitely need to examine your previous work before saying more. :)

John> What I want most is to make deadlocks and race conditions
John> naturally hard to write -- if not impossible. The rise of
John> Heisenbugs could make our job as maintainers much more
John> difficult. All the worst bugs in my programming career were
John> related to preemptive threading in some way.

> Race-free-ness will not come from this branch. It takes a traditional
> threads-and-locks approach.

This is definitely an area for further discussion; though that shouldn't stop
us from continuing to think about the cooperative approach.

John

Re: "concurrency" branch updated

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

    > Any large computational task needs to be written to surrender control now and then, if it might be used in an Emacs session that also talks to network servers that may time out and close connections if Emacs ignores them for too long.

It is easy to make a function that offers to switch threads.

    > Long delays waiting on a file system read operation (from NFS
    > server or network hiccups) can have a similar effect, though we
    > can probably arrange for some file operations to permit
    > switching even if they’re normally quite fast.

We might want those to be treated as waiting -- for instance, to handle
them through something more like tramp.


-- 
Dr Richard Stallman
President, Free Software Foundation (gnu.org, fsf.org)
Internet Hall-of-Famer (internethalloffame.org)
Skype: No way! See stallman.org/skype.html.

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> CC: johnw@newartisans.com, eliz@gnu.org, emacs-devel@gnu.org
> Date: Thu, 05 Nov 2015 17:46:29 -0500
> 
>     > Any large computational task needs to be written to surrender control now and then, if it might be used in an Emacs session that also talks to network servers that may time out and close connections if Emacs ignores them for too long.
> 
> It is easy to make a function that offers to switch threads.

Tom already wrote it, and it is part of the code on the branch.  It's
called 'thread-yield', not surprisingly.

Re: "concurrency" branch updated

[Tom Tromey]

RMS> We don't need radical changes such as CPS to implement concurrent Lisp.
RMS> All we need is multiple stacks.

This is what is done on the branch.

RMS> It seems to me that in Emacs there is no need to be able to switch threads
RMS> except when a thread is waiting.  That should make things much simpler.

This is also what is implemented.

However, it's better to eventually yield the global lock periodically in
somewhere (maybe QUIT, but that might be trouble), so that threads don't
have to explicitly yield.  FWIW this is what Python does.

Tom

Re: "concurrency" branch updated

[Tom Tromey]

Ken> So… yeah, I think some of them are possible, but I’m not sure any of
Ken> them would be a particularly good way to show off.  Got any
Ken> suggestions?

One idea would be to make it so that each terminal runs in its own
thread.  Maybe whatever accepts new connections from emacsclient could
also have its own thread as well.

This way connecting to Emacs from a tty could still work even if the X
frame is busy working (provided of course that the Lisp that is working
would yield periodically; but that is a good idea anyway for I/O).

Tom

Re: "concurrency" branch updated

[Eli Zaretskii]

> From: Tom Tromey <tom@tromey.com>
> Cc: Eli Zaretskii <eliz@gnu.org>,  johnw@newartisans.com,  emacs-devel@gnu.org
> Date: Thu, 05 Nov 2015 14:46:40 -0700
> 
> One idea would be to make it so that each terminal runs in its own
> thread.

By "terminal" do you mean X display?  If so, the w32 port already does
something like that: it reads system input messages, including
keyboard input and all the rest, in a separate thread, which feeds the
queue serviced by the read_socket hook.

Re: "concurrency" branch updated

[Tom Tromey]

>> One idea would be to make it so that each terminal runs in its own
>> thread.

Eli> By "terminal" do you mean X display?  If so, the w32 port already does
Eli> something like that: it reads system input messages, including
Eli> keyboard input and all the rest, in a separate thread, which feeds the
Eli> queue serviced by the read_socket hook.

Yeah, basically each thing with its own conceptual input queue; so each
X connection but also each tty frame.

Tom