Make computational threads leave user interface usable

Make computational threads leave user interface usable

[Paul Pogonyshev]

Since several versions Emacs has Lisp threads, but they are not used
much, because 1) only one thread executes at any given time; 2)
threads yield control to each other only with explicit (thread-yield)
call or IO blocks. Which means that it is pointless to start a new
thread for heavy computation: it will lock UI until finished anyway.

Attached patch tries to solve point 2 only by making threads
automatically yield control to each other from time to time. The patch
is mainly for discussion.

To see its effect, evaluate this expression:

    (make-thread (lambda ()
                   (dotimes (n 10000000)
                     (when (= (% n 1000000) 0)
                       (message "%s" n)))
                   (message "done")))

In normal Emacs, UI is frozen until the thread completes. You see
messages in the echo area, but that's rather a special case: you
cannot e.g. navigate or type in the current buffer.

With the patch, however, computation thread periodically (and
automatically: no alteration of the expression is needed) yields to UI
thread, leaving Emacs responsive while computation is going on.

There are some problems, though.

* Computation is 3-4 times slower than without auto-yielding. You can
compare to unpatched Emacs or bind `thread-inhibit-auto-yield' to t in
the thread function. This is probably due to the fact it auto-yields
~50 times per second. But on the other hand, does it really have to be
that slow? I don't know much about Emacs internals, maybe someone with
more knowledge can say if it is unavoidable, or yielding is just not
optimized because it is just not done that frequently currently.

* Message buffer contents seems screwed. But this is probably
"normal", as non-main threads shouldn't touch UI as I understand. This
expression is just an example.

* Variable `thread-auto-yield-after' is accessible from Lisp, but
rebinding doesn't take effect immediately. Which is especially bad if
you rebind from nil to a non-nil value.

In general, what are the thoughts about the patch? Does it look
interesting, or is auto-yielding simply out of question?

Paul

P.S. Please CC me on replies, I'm not subscribed to the list.

Re: Make computational threads leave user interface usable

[Paul Pogonyshev]

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

And, of course, I forgot to attach the patch.

Paul

On 1 November 2017 at 16:06, Paul Pogonyshev <pogonyshev@gmail.com> wrote:
> Since several versions Emacs has Lisp threads, but they are not used
> much, because 1) only one thread executes at any given time; 2)
> threads yield control to each other only with explicit (thread-yield)
> call or IO blocks. Which means that it is pointless to start a new
> thread for heavy computation: it will lock UI until finished anyway.
>
> Attached patch tries to solve point 2 only by making threads
> automatically yield control to each other from time to time. The patch
> is mainly for discussion.
>
> To see its effect, evaluate this expression:
>
>     (make-thread (lambda ()
>                    (dotimes (n 10000000)
>                      (when (= (% n 1000000) 0)
>                        (message "%s" n)))
>                    (message "done")))
>
> In normal Emacs, UI is frozen until the thread completes. You see
> messages in the echo area, but that's rather a special case: you
> cannot e.g. navigate or type in the current buffer.
>
> With the patch, however, computation thread periodically (and
> automatically: no alteration of the expression is needed) yields to UI
> thread, leaving Emacs responsive while computation is going on.
>
> There are some problems, though.
>
> * Computation is 3-4 times slower than without auto-yielding. You can
> compare to unpatched Emacs or bind `thread-inhibit-auto-yield' to t in
> the thread function. This is probably due to the fact it auto-yields
> ~50 times per second. But on the other hand, does it really have to be
> that slow? I don't know much about Emacs internals, maybe someone with
> more knowledge can say if it is unavoidable, or yielding is just not
> optimized because it is just not done that frequently currently.
>
> * Message buffer contents seems screwed. But this is probably
> "normal", as non-main threads shouldn't touch UI as I understand. This
> expression is just an example.
>
> * Variable `thread-auto-yield-after' is accessible from Lisp, but
> rebinding doesn't take effect immediately. Which is especially bad if
> you rebind from nil to a non-nil value.
>
> In general, what are the thoughts about the patch? Does it look
> interesting, or is auto-yielding simply out of question?
>
> Paul
>
> P.S. Please CC me on replies, I'm not subscribed to the list.

[-- Attachment #2: auto-yielding.diff --]
[-- Type: text/plain, Size: 6917 bytes --]

diff --git a/src/bytecode.c b/src/bytecode.c
index 50c7abe289..d52fab43d2 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -403,6 +403,9 @@ exec_byte_code (Lisp_Object bytestr, Lisp_Object vector, Lisp_Object maxdepth,
       if (BYTE_CODE_SAFE && ! (stack_base <= top && top < stack_lim))
 	emacs_abort ();
 
+      if (auto_yield_pending && !thread_inhibit_auto_yield)
+        Fthread_yield ();
+
 #ifdef BYTE_CODE_METER
       int prev_op = this_op;
       this_op = op = FETCH;
diff --git a/src/eval.c b/src/eval.c
index 063deb4ba0..43a6fca2ff 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -2136,6 +2136,8 @@ eval_sub (Lisp_Object form)
     return form;
 
   maybe_quit ();
+  if (auto_yield_pending && !thread_inhibit_auto_yield)
+    Fthread_yield ();
 
   maybe_gc ();
 
diff --git a/src/systhread.c b/src/systhread.c
index 6f9baabaf2..cc0f7e0127 100644
--- a/src/systhread.c
+++ b/src/systhread.c
@@ -53,6 +53,12 @@ sys_cond_wait (sys_cond_t *c, sys_mutex_t *m)
 {
 }
 
+bool
+sys_cond_timedwait (sys_cond_t *c, sys_mutex_t *m, const struct timespec *t)
+{
+  return false;
+}
+
 void
 sys_cond_signal (sys_cond_t *c)
 {
@@ -88,6 +94,7 @@ sys_thread_yield (void)
 
 #elif defined (HAVE_PTHREAD)
 
+#include <errno.h>
 #include <sched.h>
 
 #ifdef HAVE_SYS_PRCTL_H
@@ -124,6 +131,12 @@ sys_cond_wait (sys_cond_t *cond, sys_mutex_t *mutex)
   pthread_cond_wait (cond, mutex);
 }
 
+bool
+sys_cond_timedwait (sys_cond_t *cond, sys_mutex_t *mutex, const struct timespec *abstime)
+{
+  return pthread_cond_timedwait (cond, mutex, abstime) == ETIMEDOUT;
+}
+
 void
 sys_cond_signal (sys_cond_t *cond)
 {
@@ -269,6 +282,14 @@ sys_cond_wait (sys_cond_t *cond, sys_mutex_t *mutex)
   EnterCriticalSection ((LPCRITICAL_SECTION)mutex);
 }
 
+bool
+sys_cond_timedwait (sys_cond_t *cond, sys_mutex_t *mutex, const struct timespec *abstime)
+{
+  /* FIXME: Write. */
+  sys_cond_wait (cond, mutex);
+  return false;
+}
+
 void
 sys_cond_signal (sys_cond_t *cond)
 {
diff --git a/src/systhread.h b/src/systhread.h
index 443dc55c6a..075207efec 100644
--- a/src/systhread.h
+++ b/src/systhread.h
@@ -19,6 +19,8 @@ along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
 #ifndef SYSTHREAD_H
 #define SYSTHREAD_H
 
+#include <time.h>
+
 #ifdef THREADS_ENABLED
 
 #ifdef HAVE_PTHREAD
@@ -95,6 +97,7 @@ extern void sys_mutex_unlock (sys_mutex_t *);
 
 extern void sys_cond_init (sys_cond_t *);
 extern void sys_cond_wait (sys_cond_t *, sys_mutex_t *);
+extern bool sys_cond_timedwait (sys_cond_t *, sys_mutex_t *, const struct timespec *);
 extern void sys_cond_signal (sys_cond_t *);
 extern void sys_cond_broadcast (sys_cond_t *);
 extern void sys_cond_destroy (sys_cond_t *);
diff --git a/src/thread.c b/src/thread.c
index c03cdda0fa..dcddd6d63d 100644
--- a/src/thread.c
+++ b/src/thread.c
@@ -29,6 +29,7 @@ along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
 static struct thread_state main_thread;
 
 struct thread_state *current_thread = &main_thread;
+bool auto_yield_pending = false;
 
 static struct thread_state *all_threads = &main_thread;
 
@@ -37,6 +38,12 @@ static sys_mutex_t global_lock;
 extern int poll_suppress_count;
 extern volatile int interrupt_input_blocked;
 
+static int auto_yield_thread_started;
+static sys_thread_t auto_yield_thread;
+static sys_mutex_t auto_yield_lock;
+static sys_cond_t auto_yield_rules_changed;
+static bool auto_yield_thread_switched;
+
 \f
 
 /* m_specpdl is set when the thread is created and cleared when the
@@ -65,6 +72,9 @@ post_acquire_global_lock (struct thread_state *self)
 
   if (prev_thread != current_thread)
     {
+      if (auto_yield_thread_started)
+        sys_mutex_lock (&auto_yield_lock);
+
       /* PREV_THREAD is NULL if the previously current thread
 	 exited.  In this case, there is no reason to unbind, and
 	 trying will crash.  */
@@ -72,6 +82,14 @@ post_acquire_global_lock (struct thread_state *self)
 	unbind_for_thread_switch (prev_thread);
       rebind_for_thread_switch ();
 
+      if (auto_yield_thread_started)
+        {
+          auto_yield_pending = false;
+          auto_yield_thread_switched = true;
+          sys_cond_signal (&auto_yield_rules_changed);
+          sys_mutex_unlock (&auto_yield_lock);
+        }
+
        /* Set the new thread's current buffer.  This needs to be done
 	  even if it is the same buffer as that of the previous thread,
 	  because of thread-local bindings.  */
@@ -747,6 +765,38 @@ run_thread (void *state)
   return NULL;
 }
 
+static void *
+auto_yielder (void *unused)
+{
+  sys_mutex_lock (&auto_yield_lock);
+
+  while (true)
+    {
+      int timed_out = 0;
+      auto_yield_thread_switched = false;
+
+      if (auto_yield_pending || NILP (Vthread_auto_yield_after))
+        sys_cond_wait (&auto_yield_rules_changed, &auto_yield_lock);
+      else
+        {
+          double after = extract_float (Vthread_auto_yield_after);
+
+          if (after > 0)
+            {
+              struct timespec until = timespec_add (current_timespec (), dtotimespec (after));
+              timed_out = sys_cond_timedwait (&auto_yield_rules_changed, &auto_yield_lock, &until);
+            }
+          else
+            sys_cond_wait (&auto_yield_rules_changed, &auto_yield_lock);
+        }
+
+      if (timed_out && !auto_yield_thread_switched)
+        auto_yield_pending = true;
+    }
+
+  return NULL;
+}
+
 void
 finalize_one_thread (struct thread_state *state)
 {
@@ -815,6 +865,10 @@ If NAME is given, it must be a string; it names the new thread.  */)
 
   /* FIXME: race here where new thread might not be filled in?  */
   XSETTHREAD (result, new_thread);
+
+  if (!auto_yield_thread_started)
+    auto_yield_thread_started = sys_thread_create (&auto_yield_thread, "auto-yield", auto_yielder, NULL);
+
   return result;
 }
 
@@ -1024,10 +1078,20 @@ init_threads_once (void)
 void
 init_threads (void)
 {
+  DEFVAR_LISP ("thread-auto-yield-after", Vthread_auto_yield_after,
+    doc: /* Make current thread yield automatically after this many seconds. */);
+  Vthread_auto_yield_after = make_float (0.02);
+
+  DEFVAR_BOOL ("thread-inhibit-auto-yield", thread_inhibit_auto_yield,
+    doc: /* Non-nil means never auto-yield. */);
+  thread_inhibit_auto_yield = false;
+
   init_main_thread ();
   sys_cond_init (&main_thread.thread_condvar);
   sys_mutex_init (&global_lock);
   sys_mutex_lock (&global_lock);
+  sys_mutex_init (&auto_yield_lock);
+  sys_cond_init (&auto_yield_rules_changed);
   current_thread = &main_thread;
   main_thread.thread_id = sys_thread_self ();
 }
diff --git a/src/thread.h b/src/thread.h
index 19baafbf8a..d5f76d0e05 100644
--- a/src/thread.h
+++ b/src/thread.h
@@ -293,6 +293,7 @@ XCONDVAR (Lisp_Object a)
 }
 
 extern struct thread_state *current_thread;
+extern bool auto_yield_pending;
 
 extern void finalize_one_thread (struct thread_state *state);
 extern void finalize_one_mutex (struct Lisp_Mutex *);

Re: Make computational threads leave user interface usable

[John Wiegley]

>>>>> "PP" == Paul Pogonyshev <pogonyshev@gmail.com> writes:

PP> Since several versions Emacs has Lisp threads, but they are not used much,
PP> because 1) only one thread executes at any given time; 2) threads yield
PP> control to each other only with explicit (thread-yield) call or IO blocks.
PP> Which means that it is pointless to start a new thread for heavy
PP> computation: it will lock UI until finished anyway.

I wouldn't say it's pointless, just that it calls for a programming regimen
where you add (thread-yield) calls at appropriate places.

PP> Attached patch tries to solve point 2 only by making threads
PP> automatically yield control to each other from time to time. The patch
PP> is mainly for discussion.

This would introduce the sort of indeterminacy that raised so much objection
to threading support last year. I'm fairly opposed to pre-emptive threading
until we've heard from the field about the success of green threading.

    (make-thread (lambda ()
                   (dotimes (n 10000000)
                     (when (= (% n 1000000) 0)
                       (message "%s" n)))
                   (message "done")))

I think the problem here is not with Emacs' threading model, but how you've
written the code. It is currently a _feature_ that control is not taken away
while engaged in such a computation. For example, this allows delicate state
manipulation without interference from other threads.

If periodic suspension were desired, you could have written:

    (make-thread (lambda ()
                   (dotimes (n 10000000)
                     (thread-yield)
                     (when (= (% n 1000000) 0)
                       (message "%s" n)))
                   (message "done")))

This gives the UI access to Emacs again, but otherwise keeps executing if no
other threads need control.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Make computational threads leave user interface usable

[Noam Postavsky]

On Wed, Nov 1, 2017 at 11:06 AM, Paul Pogonyshev <pogonyshev@gmail.com> wrote:
> Since several versions Emacs has Lisp threads,

Um, not even a single version of Emacs has been released with Lisp threads.

> In general, what are the thoughts about the patch? Does it look
> interesting, or is auto-yielding simply out of question?

Seems a bit premature, given we still have stuff like #25214
"Interacting with user from threads other than the primary" and #25171
"Error in thread causes Emacs to abort" unresolved.

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=25214
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=25171

Re: Make computational threads leave user interface usable

[Eli Zaretskii]

> From: "John Wiegley" <johnw@gnu.org>
> Date: Wed, 01 Nov 2017 11:12:02 -0700
> Cc: Emacs developers <emacs-devel@gnu.org>
> 
> This would introduce the sort of indeterminacy that raised so much objection
> to threading support last year. I'm fairly opposed to pre-emptive threading
> until we've heard from the field about the success of green threading.

I agree.  I would even say it more bluntly: I don't believe the
current threading code can be extended to pre-emptive threads so
easily.  Much more redesign and reimplementing of several core
internals will be needed before it will become possible to write
reliable programs with pre-emptive threading.

How do I know? by the amount of gray hair we needed to acquire and the
amount of sweat and blood we invested before the current much simpler
model got to what we have now, which is still not perfect even for the
limited features it was supposed to support.

>     (make-thread (lambda ()
>                    (dotimes (n 10000000)
>                      (thread-yield)
>                      (when (= (% n 1000000) 0)
>                        (message "%s" n)))
>                    (message "done")))
> 
> This gives the UI access to Emacs again, but otherwise keeps executing if no
> other threads need control.

I think we currently lack intermediate infrastructure to make writing
such programs easily.  Right now, a Lisp programmer who wants to take
advantage of these features needs to jump through many hoops and
overcome some counter-intuitive/surprising obstacles and issues.

Volunteers, where are you?

Re: Make computational threads leave user interface usable

[Eli Zaretskii]

> From: Noam Postavsky <npostavs@users.sourceforge.net>
> Date: Wed, 1 Nov 2017 15:10:10 -0400
> Cc: Emacs developers <emacs-devel@gnu.org>
> 
> Seems a bit premature, given we still have stuff like #25214
> "Interacting with user from threads other than the primary" and #25171
> "Error in thread causes Emacs to abort" unresolved.
> 
> https://debbugs.gnu.org/cgi/bugreport.cgi?bug=25214
> https://debbugs.gnu.org/cgi/bugreport.cgi?bug=25171

Does 25171 still happen?  Because I committed the part of the patch I
thought was a good idea back then.

Re: Make computational threads leave user interface usable

[Noam Postavsky]

tag 25171 fixed
close 25171
quit

On Wed, Nov 1, 2017 at 4:16 PM, Eli Zaretskii <eliz@gnu.org> wrote:

> Does 25171 still happen?  Because I committed the part of the patch I
> thought was a good idea back then.

Hmm, maybe not, I had already asked on its merged bug [1] and there
was no response. Given that we haven't seen any additional similar
reports, we can probably consider it solved.

[1]: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=25164#28

Re: Make computational threads leave user interface usable

[Paul Pogonyshev]

> I wouldn't say it's pointless, just that it calls for a programming regimen
> where you add (thread-yield) calls at appropriate places.

What if this auto-yield is made optional? It sort of already is in the
patch, but the default value could be made nil. Then, you can activate
it downstream by using (let ((thread-auto-yield-after ...) ...), but
normally it is not active. So, activating becomes your own decision,
not something sneaked upon you.

Peppering code with (thread-yield) has downsides in that it requires
to write every single piece of code you might at some point run in a
separate thread with that in mind. And not everything is as simple
as one loop with many iterations. And if you fail to add (thread-yield)
at reasonable intervals, it will still lead to unresponsive UI that
sometimes works smoothly, yet at other times freezes for a couple
of seconds.

I think it would be very useful to be able to run sort-of-arbitrary
computation without freezing UI. (Sort-of, because it shouldn't
interfere with UI, but otherwise can compute whatever it wants).
Imagine e.g. running 5000 ERT tests, and still continuing to work
with Emacs as normal.

Paul

Re: Make computational threads leave user interface usable

[John Wiegley]

>>>>> "PP" == Paul Pogonyshev <pogonyshev@gmail.com> writes:

PP> What if this auto-yield is made optional? It sort of already is in the
PP> patch, but the default value could be made nil. Then, you can activate it
PP> downstream by using (let ((thread-auto-yield-after ...) ...), but normally
PP> it is not active. So, activating becomes your own decision, not something
PP> sneaked upon you.

Here's what I would accept: A macro to inject (thread-yield) calls into
function definitions. This is extremely low-impact (just a new macro), works
with the existing implementation, and offers the semantics you're asking for
in a way that's good enough for now.

Of course, it only works for code defined using the macro, but I actually
don't _want_ a patch that changes code written to be cooperative into code
that evaluates pre-emptively. If, on the other hand, you want to define a set
of thread functions that allow full pre-emption by auto-injecting yield
points, then I believe such a macro would serve this need.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Make computational threads leave user interface usable

[Stefan Monnier]

> What if this auto-yield is made optional?

The problem is that the megabytes of C and Lisp code out there all
assume that there's only a single thread running.  This assumption is so
strong that we don't even really provide the synchronization primitives
necessary to make real concurrent programming usable (e.g. locks,
transactions, ...).

So such an option would be similar to a "please corrupt my Emacs state
in random ways" option.

As you've seen context switches are currently very expensive (they
undo all the dynamic-bindings of the source thread and reinstall the 
dynamic-bindings of the destination thread).

It's probably a good idea to start thinking about how to add real
concurrency to Emacs, but it needs to start by looking at how we can
make sure the concurrent threads only share read-only data (plus some
extra shared state properly protected via some transactional system, or
maybe just no shared state but some messaging mechanism instead).

That requires a serious design effort on the Elisp side, with a good
understanding of the current C code, plus some deep changes at the
C level.


        Stefan