multi-threaded Emacs

multi-threaded Emacs

[Giuseppe Scrivano]

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

Hello,

I attached a small patch that enables basic threads in Emacs; it is just
a proof of concept and not usable yet, my goal was the execution of the
elisp code I included at the bottom.

In the new file thread.c these functions are defined:

(create-thread) 
(with-thread id '(code))
(kill-thread id)

The first one creates a suspended thread that is waiting for requests.
These requests are done by with-thread that allows the execution of
'(code) on the specified thread.  `kill-thread' is used to terminate a
thread execution by its id.

It is a prototype and the code is not very clean, still a lot of work
must be done in order to have working threads, but I think that have a
multi-threaded Emacs worths this effort.

My idea is to share global variables among threads while local bindings
are done locally to threads.

I haven't well investigated all problems that will raise using threads
in Emacs, the first one that come to my attention is the garbage
collector and at the moment I simply disable GC while there are running
threads.


The following elisp code can be used now, it is not safe as the new
thread id is not freed after it is used:

(progn
  (setq i 0)
  (setq j 0)
  (with-thread (create-thread) '(while (< i 20)
                                  (sleep-for 0.2)
                                  (print "hello")
                                  (setq i (1+ i))))
  
  (while (< j 20)
    (print "world")
    (sleep-for 0.25)
    (setq j (1+ j))))



`with-thread' allows to use the same thread multiple times like:

(with-thread foo '(do-something-complex))
(with-thread bar '(do-another-complex-thing))
(with-thread foo '(do-another-complex-thing))

The third call will block the calling thread until `foo' has completed
its previous execution.

What do you think about?


Regards,
Giuseppe



[-- Attachment #2: emacs_multithread.diff.gz --]
[-- Type: application/octet-stream, Size: 12001 bytes --]

Re: multi-threaded Emacs

[Stefan Monnier]

> I attached a small patch that enables basic threads in Emacs; it is just
> a proof of concept and not usable yet, my goal was the execution of the
> elisp code I included at the bottom.
[...]
> It is a prototype and the code is not very clean, still a lot of work
> must be done in order to have working threads, but I think that have a
> multi-threaded Emacs worths this effort.
[...]
> What do you think about?

I agree that multithreading is a worthwhile goal, even tho it's going to
be a long ride.  It involves several problems:

- handling thread-specific data: gcprolist, mark_byte_stack, and things
  like that.  You've tackled this one.  I don't find your solution very
  elegant, but I can't think of a much better one, unless pthreads does
  provide some kind of thread-specific variables.  I guess the only
  improvement is to put those vars together, so we have an array of
  structs (that then contain gcprolist, and mark_byte_stack fields)
  rather than several arrays.  And then define `gcprolist' as a macro
  that expands into "thread_data[current_thread()].gcprolist", so as to
  reduce the amount of source-code changes.

- dynamic-scoping: your handling of specpdl is naive and
  fundamentally flawed.  For multithreading, we will have to completely
  change the implementation technique of dynamic-scoping.

- synchronization to access all the global variables/objects.
  You haven't yet have time to tackle this (other than in `put', it
  seems), and it's going to be difficult.

- concurrent GC (later to be refined to parallel concurrent GC ;-).

- redisplay in its own thread (later to be refined to one redisplay
  thread per terminal, then per frame, then per window ;-).

A first step will be to restrict the implementation such that there's no
parallelism: only one thread executes at any given time (i.e. have
a single lock and have all thread grab the lock before doing any actual
work).


        Stefan

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Hello,

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

> - handling thread-specific data: gcprolist, mark_byte_stack, and things
>   like that.  You've tackled this one.  I don't find your solution very
>   elegant, but I can't think of a much better one, unless pthreads does
>   provide some kind of thread-specific variables.  I guess the only
>   improvement is to put those vars together, so we have an array of
>   structs (that then contain gcprolist, and mark_byte_stack fields)
>   rather than several arrays.  And then define `gcprolist' as a macro
>   that expands into "thread_data[current_thread()].gcprolist", so as to
>   reduce the amount of source-code changes.

Yes, we can put thread-specific data together in a struct; what about
buffer data?  `current_buffer' must be different for every thread so as
many other global variables, should it be defined in the same
thread_data struct? 

> - dynamic-scoping: your handling of specpdl is naive and
>   fundamentally flawed.  For multithreading, we will have to completely
>   change the implementation technique of dynamic-scoping.

I know but it was the easier way to have quickly a working
proof-of-concept as I concentrated my efforts mainly on the syntax.
Do you have any idea about how dynamic scoping should be handled in a
multi-threaded environment?

> - synchronization to access all the global variables/objects.
>   You haven't yet have time to tackle this (other than in `put', it
>   seems), and it's going to be difficult.

Why do you think that a global lock (or several ones for separate kind
of data) will not be enough?  It is not easy but I think it can be done
in a reasonable time without many troubles.

> - concurrent GC (later to be refined to parallel concurrent GC ;-).
>
> - redisplay in its own thread (later to be refined to one redisplay
>   thread per terminal, then per frame, then per window ;-).

I think that this is the most difficult part, a new GC and how handle
redisplay.
Different threads can use the same buffer and a buffer can have no
threads actually using it.  I would simplify this part, maybe leave the
redisplay task only to a thread.

> A first step will be to restrict the implementation such that there's no
> parallelism: only one thread executes at any given time (i.e. have
> a single lock and have all thread grab the lock before doing any actual
> work).

IMHO it is better to avoid this middle solution and try to solve
directly the problem, it will not give real benefits and having only one
thread executes at a given time can be done differently, like saving and
restoring the thread call stack.  Real threads will not suffer I/O bound
operations and Emacs will be able to use more cores at the same time, if
needed.

Thanks,
Giuseppe

Re: multi-threaded Emacs

[Tom Tromey]

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

Stefan> - handling thread-specific data: gcprolist, mark_byte_stack, and things
Stefan>   like that.  You've tackled this one.  I don't find your solution very
Stefan>   elegant, but I can't think of a much better one, unless pthreads does
Stefan>   provide some kind of thread-specific variables.

pthreads provides the clunky pthread_getspecific / pthread_setspecific
API.

However, it is worth noting that recent versions of GCC support a
__thread storage class, which provides efficient support for
thread-local variables.  IMO, for anything that is performance
sensitive, it is worth structuring the code so that this can be used.
See (info "(gcc)Thread-Local")

Tom

Re: multi-threaded Emacs

[Stefan Monnier]

>> - handling thread-specific data: gcprolist, mark_byte_stack, and things
>> like that.  You've tackled this one.  I don't find your solution very
>> elegant, but I can't think of a much better one, unless pthreads does
>> provide some kind of thread-specific variables.  I guess the only
>> improvement is to put those vars together, so we have an array of
>> structs (that then contain gcprolist, and mark_byte_stack fields)
>> rather than several arrays.  And then define `gcprolist' as a macro
>> that expands into "thread_data[current_thread()].gcprolist", so as to
>> reduce the amount of source-code changes.

> Yes, we can put thread-specific data together in a struct; what about
> buffer data?  `current_buffer' must be different for every thread so as
> many other global variables, should it be defined in the same
> thread_data struct?

Yes, some additional variables will need to be made
thread-specific, indeed.  For some of them, we may be able to simply use
dynamic-scoping (once this is implemented).

>> - dynamic-scoping: your handling of specpdl is naive and
>> fundamentally flawed.  For multithreading, we will have to completely
>> change the implementation technique of dynamic-scoping.

> I know but it was the easier way to have quickly a working
> proof-of-concept as I concentrated my efforts mainly on the syntax.
> Do you have any idea about how dynamic scoping should be handled in a
> multi-threaded environment?

Currently, we basically use the following implementation:

   (defun get-var (sym)
     (symbol-value 'var))
   (defun set-var (sym val)
     (setf (symbol-value 'var) val))
   (defmacro let-var (sym val body)
     `(let ((oldval (get-var ,sym)))
        (set-var ,sym ,val)
        (unwind-protect
            ,body
          (set-var ,sym ,val))))

we could instead use something like

   (defun get-var (sym)
     (cdr (assq sym specpdl)))
   (defun set-var (sym val)
     (set-cdr (assq sym specpdl) val))
   (defmacro let-var (sym val body)
     `(let ((oldpdl specpdl))
        (push (cons ,sym ,val) specpdl)
        (unwind-protect
            ,body
          (setq specpdl oldpdl))))

where specpdl is a per-thread variable.  Or

   (defun get-var (sym)
     (cdr (assq thread (symbol-value sym))))
   (defun set-var (sym val)
     (set-cdr (assq thread (symbol-value sym)) val))
   (defmacro let-var (sym val body)
     `(let ((oldval (get-var ,sym)))
        (set-var ,sym ,val)
        (unwind-protect
            ,body
          (set-var ,sym ,val))))

This latter one might be the simplest: it basically adapts the
notion of buffer-local/frame-local/terminal-local to also include
thread-local.  Currently, only one form of locality is supported at
a time (a var can't be both buffer-local and terminal-local), so this
would need to be worked out (frame-local and buffer-local was allowed
in Emacs-21 but its behavior was not clearly defined and had corner
case bugs).

Clearly this can have drastic consequences w.r.t the performance of
`get-var'.  And its interaction with buffer-local bindings needs to be
thought through.  We mostly want to handle the default-directory case
where a variable is local to every buffer and can also be
dynamically bound.

>> - synchronization to access all the global variables/objects.
>> You haven't yet have time to tackle this (other than in `put', it
>> seems), and it's going to be difficult.

> Why do you think that a global lock (or several ones for separate kind
> of data) will not be enough?  It is not easy but I think it can be done
> in a reasonable time without many troubles.

I'm not sure what you mean by "a global lock".  The question is not only
how many locks, but what they protect.  My proposal further down to
start with "only one thread active at a time" is what I'd call "a global
lock".

>> - concurrent GC (later to be refined to parallel concurrent GC ;-).
>> - redisplay in its own thread (later to be refined to one redisplay
>> thread per terminal, then per frame, then per window ;-).

> I think that this is the most difficult part, a new GC and how handle
> redisplay.

Actually, a new GC is not indispensable.  We will most likely start by
keeping the same GC and just stopping all threads when a GC is needed.

>> A first step will be to restrict the implementation such that there's no
>> parallelism: only one thread executes at any given time (i.e. have
>> a single lock and have all thread grab the lock before doing any actual
>> work).
> IMHO it is better to avoid this middle solution and try to solve
> directly the problem, it will not give real benefits and having only one
> thread executes at a given time can be done differently, like saving and
> restoring the thread call stack.

Experience shows that making a program concurrent (or even parallel)
requires a lot of work and can only be done step by step, and after each
step appears new opportunities.  I don't see my proposal as
a "middle" solution.  It's just one step out of many.  Before knowing
what other steps are most needed, we will need experience using those
primitives in Elisp packages, so the most pressing step is to provide
the primitives in a robust way.

> Real threads will not suffer I/O bound operations and Emacs will be
> able to use more cores at the same time, if needed.

That can come later.  Parallelism is important, but it will require
changes in Elisp packages, so the first thing is to provide facilities
so that Elisp packages can start using concurrency.  Then we can worry
about taking advantage of parallelism.

If we want to get parallelism without changing Elisp packages, then
I can only see two places where we could do that:
- parallelise redisplay.
- make the GC concurrent (and/or parallel).
Both are pretty difficult.  Interestingly, they're also mostly
orthogonal to the issue of providing concurrency primitives to Elisp.


        Stefan

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Hello,

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

> Currently, we basically use the following implementation:
>
>    (defun get-var (sym)
>      (symbol-value 'var))
>    (defun set-var (sym val)
>      (setf (symbol-value 'var) val))
>    (defmacro let-var (sym val body)
>      `(let ((oldval (get-var ,sym)))
>         (set-var ,sym ,val)
>         (unwind-protect
>             ,body
>           (set-var ,sym ,val))))
>
> we could instead use something like
>
>    (defun get-var (sym)
>      (cdr (assq sym specpdl)))
>    (defun set-var (sym val)
>      (set-cdr (assq sym specpdl) val))
>    (defmacro let-var (sym val body)
>      `(let ((oldpdl specpdl))
>         (push (cons ,sym ,val) specpdl)
>         (unwind-protect
>             ,body
>           (setq specpdl oldpdl))))
>
> where specpdl is a per-thread variable.  Or
>
>    (defun get-var (sym)
>      (cdr (assq thread (symbol-value sym))))
>    (defun set-var (sym val)
>      (set-cdr (assq thread (symbol-value sym)) val))
>    (defmacro let-var (sym val body)
>      `(let ((oldval (get-var ,sym)))
>         (set-var ,sym ,val)
>         (unwind-protect
>             ,body
>           (set-var ,sym ,val))))
>
> This latter one might be the simplest: it basically adapts the
> notion of buffer-local/frame-local/terminal-local to also include
> thread-local.  Currently, only one form of locality is supported at
> a time (a var can't be both buffer-local and terminal-local), so this
> would need to be worked out (frame-local and buffer-local was allowed
> in Emacs-21 but its behavior was not clearly defined and had corner
> case bugs).

I don't think that thread-local data has the same meaning as
buffer-local, frame-local or terminal-local.  Thread-local data should be
handled transparently to the user, I don't see it very useful (if not
dangerous) to give the possibility to store data on a specific thread
beside temporary variables.
Probably it is good idea to modify `with-thread' to don't accept a
thread id, but simply the code to execute on a different thread, the
caller thread local bindings will be copied to the called thread.

Do you see any situation that there is need to store a value on a
specific thread?


> I'm not sure what you mean by "a global lock".  The question is not only
> how many locks, but what they protect.  My proposal further down to
> start with "only one thread active at a time" is what I'd call "a global
> lock".

If we use a lock (or locks) to protect shared data still threads can be
executed in parallel while they working on thread local data.  On the
other hand, with only one active thread we are sure that we are not
forgetting to protect something.


Thanks,
Giuseppe

Re: multi-threaded Emacs

[Richard M Stallman]

The main issue about multiple threads in Emacs is,
when should a thread-switch be possible?  I think it should
be allowed only where quitting is allowed.  Otherwise,
internal data can be made inconsistent.

Does pthreads provide the option to forbid thread-switching except
when the code calls a specific function?  If so, we could make the
QUIT macro run that function if there is more than one thread.

    (create-thread) 
    (with-thread id '(code))
    (kill-thread id)

It seems to me that `with-thread' should be renamed to
`run-in-thread'.  Meanwhile, `with-thread' should be a macro that
creates a new thread, starts running the body code in it, and will
kill it when that body code finishes.

It is un-Lispy to represent threads with numbers.  They should be
represented by objects that contain info about them.  If there is a
table of threads, it should not have a fixed size -- it should be
extended with realloc whenever it gets full.

What should happen when another thread gets an error?  Should Emacs
run the debugger in that thread?  (Probably rather annoying.)  Kill
the thread?  Leave the thread somehow suspended to be examined (but
how?).  Kill the thread, and leave some info about the error in the
dead thread object?  Perhaps there should be a way to specify a choice
for each thread.

    I haven't well investigated all problems that will raise using threads
    in Emacs, the first one that come to my attention is the garbage
    collector and at the moment I simply disable GC while there are running
    threads.

It should not be hard to find all the existing threads and mark all
their stacks and specpdls.

Re: multi-threaded Emacs

[Richard M Stallman]

    (create-thread) 
    (with-thread id '(code))
    (kill-thread id)

It seems to me that `with-thread' should be renamed to
`run-in-thread'.  Meanwhile, `with-thread' should be a macro that
creates a new thread, starts running the body code in it, and will
kill it when that body code finishes.

It would be cleaner to represent threads by objects that contain info
about them rather than IDs.  If there is a table of threads, it should
not have a fixed size -- it should be extensible, as many other tables
inside Emacs are.

Instead of indexing by a thread number each time you access certain
data structures, you should swap the current thread's pointers in and
out of the usual variables as part of switching threads.  That would
mean far less changes throughout the evaluator.

What should happen when another thread gets an error?  Should it run
the debugger in that thread?  (Probably rather annoying.)  Kill the
thread?  Leave the thread somehow suspended to be examined (but how?).
Kill the thread, and leave some info on the error in the dead thread object?

    I haven't well investigated all problems that will raise using threads
    in Emacs, the first one that come to my attention is the garbage
    collector and at the moment I simply disable GC while there are running
    threads.

It should not be hard to find all the existing threads and mark all
their stacks.

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Hi Richard,

Richard M Stallman <rms@gnu.org> writes:

> The main issue about multiple threads in Emacs is,
> when should a thread-switch be possible?  I think it should
> be allowed only where quitting is allowed.  Otherwise,
> internal data can be made inconsistent.
>
> Does pthreads provide the option to forbid thread-switching except
> when the code calls a specific function?  If so, we could make the
> QUIT macro run that function if there is more than one thread.

Internal data shared among threads must be accessed only inside critical
sections in the .c code to have atomic operations on it.
The elisp programmer must not care about what other threads are doing
and using the shared data, only the thread local data is guaranteed to
be accessed only by a thread.
It may seem a limitation but it will allow us a real parallelism with
different threads executed at the same time, in this way we can take
advantage of modern multi-cores machines.

>     (create-thread) 
>     (with-thread id '(code))
>     (kill-thread id)
>
> It seems to me that `with-thread' should be renamed to
> `run-in-thread'.  Meanwhile, `with-thread' should be a macro that
> creates a new thread, starts running the body code in it, and will
> kill it when that body code finishes.
>
> It is un-Lispy to represent threads with numbers.  They should be
> represented by objects that contain info about them.  If there is a
> table of threads, it should not have a fixed size -- it should be
> extended with realloc whenever it gets full.

Right, I used numbers to represent threads (and many other
simplifications) to have quickly something working and understand what
later can be a problem.

> What should happen when another thread gets an error?  Should Emacs
> run the debugger in that thread?  (Probably rather annoying.)  Kill
> the thread?  Leave the thread somehow suspended to be examined (but
> how?).  Kill the thread, and leave some info about the error in the
> dead thread object?  Perhaps there should be a way to specify a choice
> for each thread.

I would avoid something magic and kill the thread.  What do you think
about running the debugger without interrupting the execution of other
threads?
If another thread will get an error then another debugger is executed in
a new buffer.  Potentially every thread can cause the execution of a
debugger in a new buffer and have the possibility to be investigated
separately from others.

> It should not be hard to find all the existing threads and mark all
> their stacks and specpdls.

I like the Stefan's idea of stopping all running threads while the GC is
executed, in this way we can use the current GC without big changes.
At least until a concurrent [parallel] GC will be alive.

Regards,
Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

> I don't think that thread-local data has the same meaning as
> buffer-local, frame-local or terminal-local.

Indeed.  But the implementation may use the same code (to a large
extent at least).

> Do you see any situation that there is need to store a value on a
> specific thread?

let-binding, of course.  It's probably the only one that matters
(besides the internal ones like current_buffer).

>> I'm not sure what you mean by "a global lock".  The question is not only
>> how many locks, but what they protect.  My proposal further down to
>> start with "only one thread active at a time" is what I'd call "a global
>> lock".
> If we use a lock (or locks) to protect shared data still threads can be
> executed in parallel while they working on thread local data.

That basically means adding lock&unlock around `symbol-value' and
pretty much every primitive.  I expect this will take a significant
amount of work, will lead to a significant performance hit, and will not
expose much parallelism, if any.


        Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

> Internal data shared among threads must be accessed only inside critical
> sections in the .c code to have atomic operations on it.

So what happens when you execute two thread both doing

   (setq a (1+ a))

if you only do the locking in C, that means that `setq' will be atomic
and reading `a' is atomic, but the whole increment is not atomic.

As mentioned earlier, synchronization primitives will need to be
provided to Elisp.


        Stefan

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

>> Internal data shared among threads must be accessed only inside critical
>> sections in the .c code to have atomic operations on it.
>
> So what happens when you execute two thread both doing
>
>    (setq a (1+ a))
>
> if you only do the locking in C, that means that `setq' will be atomic
> and reading `a' is atomic, but the whole increment is not atomic.
>
> As mentioned earlier, synchronization primitives will need to be
> provided to Elisp.

Yes, the locking in C is needed to make atomic Elisp primitives, it is
only the first step.
For atomic expressions there is need to add these functions in Elisp
too that delegate the job to the C functions.

Giuseppe

Re: multi-threaded Emacs

[Miles Bader]

Richard M Stallman <rms@gnu.org> writes:
>
>     (create-thread) 
>     (with-thread id '(code))
>     (kill-thread id)
>
> It seems to me that `with-thread' should be renamed to
> `run-in-thread'.  Meanwhile, `with-thread' should be a macro that
> creates a new thread, starts running the body code in it, and will
> kill it when that body code finishes.

Also, create-thread should be "make-thread".

-Miles

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

Re: multi-threaded Emacs

[Miles Bader]

BTW, there was a huge thread maybe a year (?) or so ago about this subject.
Have you read it?

IIRC, the basic consensus was that some sort of explicitly
non-preemptive threading was probably the best solution for emacs.

-Miles

-- 
I'm beginning to think that life is just one long Yoko Ono album; no rhyme
or reason, just a lot of incoherent shrieks and then it's over.  --Ian Wolff

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

> let-binding, of course.  It's probably the only one that matters
> (besides the internal ones like current_buffer).

Isn't enough to have a separate `specpdl' for every thread?

> That basically means adding lock&unlock around `symbol-value' and
> pretty much every primitive.  I expect this will take a significant
> amount of work, will lead to a significant performance hit, and will not
> expose much parallelism, if any.

We can increase parallelism by adding different critical sections (but
it will be more difficult to handle from Elisp).
In any case I don't expect the code flow to stay long time in a critical
section; mostly they are read/write to global variables that are done
quickly.

Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

>> let-binding, of course.  It's probably the only one that matters
>> (besides the internal ones like current_buffer).
> Isn't enough to have a separate `specpdl' for every thread?

Not sure what you mean.  My above text is talking about the provided
behavior, not about the implementation that provides it.


        Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

> IIRC, the basic consensus was that some sort of explicitly
> non-preemptive threading was probably the best solution for emacs.

At least as a first step, yes.


        Stefan

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Miles Bader <miles@gnu.org> writes:

> BTW, there was a huge thread maybe a year (?) or so ago about this subject.
> Have you read it?
>
> IIRC, the basic consensus was that some sort of explicitly
> non-preemptive threading was probably the best solution for emacs.
>
> -Miles

I found a thread of 3 years ago (maybe is it this one?  Time passes very
fast :) ) but I didn't find any conclusion.

Anyway, a non-preemptive threading will not give any real parallelism
and it will require more changes in the Elisp packages to use threads as
they will need to say explicitly when give the control to another
thread.
Instead `run-in-thread' will setup the call stack and finally give the
control to the thread.  The only change required in the Elisp packages
to be used in a multithreaded environment is to protect global data
accesses with a lock/unlock, but how many times does it happen to change
the value of a global variable?

Both solutions require changes in Elisp, a non-preemptive threading
needs to explicitly yield the control to another thread, while having
real threads needs to specify when access to global data must be
protected.  The latter one differently allows parallelism and I guess
less changes in the Elisp code too (if writes to global data are less
frequent than specify when exit from the current thread).

Giuseppe

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

>>> let-binding, of course.  It's probably the only one that matters
>>> (besides the internal ones like current_buffer).
>> Isn't enough to have a separate `specpdl' for every thread?
>
> Not sure what you mean.  My above text is talking about the provided
> behavior, not about the implementation that provides it.
>
>
>         Stefan

Sorry, I wasn't clear.  If we will store thread local data only on
`specpdl', and I think it is the proper way, thread local data will not
be persistent among calls to `run-in-thread'.

Giuseppe

Re: multi-threaded Emacs

[Chetan Pandya]

--- On Sun, 11/30/08, Giuseppe Scrivano <gscrivano@gnu.org> wrote:

> From: Giuseppe Scrivano <gscrivano@gnu.org>
> Subject: Re: multi-threaded Emacs
> To: "Miles Bader" <miles@gnu.org>
> Cc: rms@gnu.org, emacs-devel@gnu.org
> Date: Sunday, November 30, 2008, 11:09 PM
> Miles Bader <miles@gnu.org> writes:
> 
> > BTW, there was a huge thread maybe a year (?) or so
> ago about this subject.
> > Have you read it?
> >
> > IIRC, the basic consensus was that some sort of
> explicitly
> > non-preemptive threading was probably the best
> solution for emacs.
> >
> > -Miles
> 
> I found a thread of 3 years ago (maybe is it this one? 
> Time passes very
> fast :) ) but I didn't find any conclusion.
> 
> Anyway, a non-preemptive threading will not give any real
> parallelism
> and it will require more changes in the Elisp packages to
> use threads as
> they will need to say explicitly when give the control to
> another
> thread.
> Instead `run-in-thread' will setup the call stack and
> finally give the
> control to the thread.  The only change required in the
> Elisp packages
> to be used in a multithreaded environment is to protect
> global data
> accesses with a lock/unlock, but how many times does it
> happen to change
> the value of a global variable?
> 
> Both solutions require changes in Elisp, a non-preemptive
> threading
> needs to explicitly yield the control to another thread,
> while having
> real threads needs to specify when access to global data
> must be
> protected.  The latter one differently allows parallelism
> and I guess
> less changes in the Elisp code too (if writes to global
> data are less
> frequent than specify when exit from the current thread).
> 
> Giuseppe

 A non-preemptive threading model can also yield implicitly, but can have unexpected consequences - for example a global variable changing value between two uses within a function, or if two values that are modified together. In general, such transaction semantics have to be coded explicitly in a preemptive threading model, where as with a cooperative model, one has to be aware of only a few of such points.

Perhaps these things were discussed earlier. I will take a look.

Chetan

Re: multi-threaded Emacs

[Stefan Monnier]

>>>> let-binding, of course.  It's probably the only one that matters
>>>> (besides the internal ones like current_buffer).
>>> Isn't enough to have a separate `specpdl' for every thread?
>> Not sure what you mean.  My above text is talking about the provided
>> behavior, not about the implementation that provides it.
> Sorry, I wasn't clear.  If we will store thread local data only on
> `specpdl', and I think it is the proper way, thread local data will not
> be persistent among calls to `run-in-thread'.

You mean you want to use the code #2 rather than code #3 to implement
dynamic scoping?  That might be OK, but I think it's going to take more
work than #3 and will require more care w.r.t performance impact since
it tends to make `symbol-value' algorithmically slower.


        Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

> Anyway, a non-preemptive threading will not give any real parallelism

I admire your enthusiasm, but I think that if you don't want to get
burned, you should set yourself more realistic goals.  Parallelism is
going to require a very large amount of work.  We'll hopefully get there
at some point, but there are many useful steps to have to take before we
get there.

> and it will require more changes in the Elisp packages to use threads as
> they will need to say explicitly when give the control to another
> thread.

Actually no.  There are already `yield' points in Elisp: basically
whenever we wait for a process or wait for user input.  So there's no
need to change too many things before we can start using cooperative
threading (another name for "a single thread active at a time").

It's still useful because it introduces the multiple stacks, which will
allow for example using one thread per terminal, so that doing M-x in
one terminal will not screw over the other terminals.  Also it'll make
asynchronous execution easier.  So it'll be useful to Elisp packages.

It'll also be a useful implementation step on the way to parallelism,
since it will make us deal with multiple stacks, dynamic scoping, ...

We will already be able to try to tackle things like: be able to edit
a file in a window while Gnus is waiting for your newsserver to send the
list of new groups.

Then we can think of making concurrency more fine-grained to try and get
parallelism.

> accesses with a lock/unlock, but how many times does it happen to change
> the value of a global variable?

*All* the time.  Elisp is really terrible in this respect.  Remember:
all buffers are part of the "global state", same for pretty much all
objects.  Currently even "local variables" are actually global,
tho admittedly, fixing dynamic-scoping will/should improve this part.


        Stefan

Re: multi-threaded Emacs

[Richard M Stallman]

    Internal data shared among threads must be accessed only inside critical
    sections in the .c code to have atomic operations on it.

I don't think we want to make such pervasive and inconvenient changes
in the C code.  What we want, I think, is to allow thread switches
only inside the QUIT macro.

Being able to program in terms of multiple threads will be useful for
situations such as multiple terminals.  However, I don't see much need
in Emacs for real parallelism.

    > It should not be hard to find all the existing threads and mark all
    > their stacks and specpdls.

    I like the Stefan's idea of stopping all running threads while the GC is
    executed, in this way we can use the current GC without big changes.
    At least until a concurrent [parallel] GC will be alive.

Making GCC handle the existence of multiple threads should be easy
with the approach I suggested above, once thread switching is
controlled.

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Richard M Stallman <rms@gnu.org> writes:

> I don't think we want to make such pervasive and inconvenient changes
> in the C code.  What we want, I think, is to allow thread switches
> only inside the QUIT macro.

If we don't want to do immediately all changes at one time and proceed
slowly to a real parallelism then we can start with a concurrent threads
model.  I think that concurrent threads can't be considered the final
solution, what I would like to optimize using threads is I/O bound and a
concurrent model can do it only in part.  If an Elisp primitive is
waiting for some data from a file or a socket, Emacs will hang until it
is ready.  This problem can't be solved by concurrent threads that will
switch only inside the QUIT macro.

If we will implement a concurrent threads model and introduce the QUIT
macro after it can't be used by parallel threads as accesses to shared
data must be synchronized differently.

IMHO, concurrent threads itself are not very useful, they can be useful
if considered a first step in the direction of a real parallelism.

I know it is a lot of work and the question (as in everything) is: does
benefits we will have worth this effort?

Regards,
Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

> solution, what I would like to optimize using threads is I/O bound and a
> concurrent model can do it only in part.  If an Elisp primitive is
> waiting for some data from a file or a socket, Emacs will hang until it
> is ready.  This problem can't be solved by concurrent threads that will

Actually, no: while Emacs is waiting for socket data, it can already run
other async code, such as process filters.

So we can solve most I/O bound problems just by using a very coarse
notion of concurrency.  We already partly do it, except we're currently
limited to a single stack, which makes coding painful and prevents some
useful cases.

Providing a cooperative threading model will remove this problem.  But,
no it's not a "final solution": I hope there never will be a final
solution, because Emacs will always need to evolve.


        Stefan

Re: multi-threaded Emacs

[joakim]

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

>> solution, what I would like to optimize using threads is I/O bound and a
>> concurrent model can do it only in part.  If an Elisp primitive is
>> waiting for some data from a file or a socket, Emacs will hang until it
>> is ready.  This problem can't be solved by concurrent threads that will
>
> Actually, no: while Emacs is waiting for socket data, it can already run
> other async code, such as process filters.
>
> So we can solve most I/O bound problems just by using a very coarse
> notion of concurrency.  We already partly do it, except we're currently
> limited to a single stack, which makes coding painful and prevents some
> useful cases.
>
> Providing a cooperative threading model will remove this problem.  But,
> no it's not a "final solution": I hope there never will be a final
> solution, because Emacs will always need to evolve.

Beautifully put.

>
>         Stefan
>
-- 
Joakim Verona

Re: multi-threaded Emacs

[Richard M Stallman]

      If an Elisp primitive is
    waiting for some data from a file or a socket, Emacs will hang until it
    is ready.

This is a real issue, but the solution is so easy
that it is not a real problem.

Activies that can wait a long time
use wait_reading_process_output
which already implements some parallelism.
Naturally we would arrange to enable thread-switching there.

    IMHO, concurrent threads itself are not very useful, they can be useful
    if considered a first step in the direction of a real parallelism.

If "concurrent threads" means "threads that can only switch where the
program lets them", they are very useful in Emacs for the sake of multiple
terminals.

Re: multi-threaded Emacs

[Stefan Monnier]

> If "concurrent threads" means "threads that can only switch where the
> program lets them", they are very useful in Emacs for the sake of multiple
> terminals.

I rarely use multiple terminals, and when I use them, the current
restrictions are mostly bearable.  OTOH I very often would like to keep
using my Emacs while it's byte-compiling some files, or while Gnus is
fetching some newsgroup.


        Stefan

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

> I rarely use multiple terminals, and when I use them, the current
> restrictions are mostly bearable.  OTOH I very often would like to keep
> using my Emacs while it's byte-compiling some files, or while Gnus is
> fetching some newsgroup.

This is exactly the problem I had when I first thought of threads.

Do you think we can solve it (at least partially) using a concurrent
model?

Thanks,
Giuseppe

Re: multi-threaded Emacs

[Florian Beck]

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

>> If "concurrent threads" means "threads that can only switch where the
>> program lets them", they are very useful in Emacs for the sake of multiple
>> terminals.
>
> I rarely use multiple terminals, and when I use them, the current
> restrictions are mostly bearable.  OTOH I very often would like to keep
> using my Emacs while it's byte-compiling some files, or while Gnus is
> fetching some newsgroup.

As a user, I would love to see asynchronous processes.

However, I would also like to see redisplay+font-locking making use of
the four to eight processor cores that will become standard during emacs24's
lifetime. Font-locking is a powerful and quite user-accessible feature
which is currently limited by processor speed.

-- 
Florian Beck

Re: multi-threaded Emacs

[Stefan Monnier]

>> I rarely use multiple terminals, and when I use them, the current
>> restrictions are mostly bearable.  OTOH I very often would like to keep
>> using my Emacs while it's byte-compiling some files, or while Gnus is
>> fetching some newsgroup.

> This is exactly the problem I had when I first thought of threads.

> Do you think we can solve it (at least partially) using a concurrent
> model?

Of course.  Even just with cooperative threads.


        Stefan

Re[2]: multi-threaded Emacs

[ak70]

Hi, guys. I have a generic user-level thread library on Linux. Maybe it can help.
The thread system is called SMASH developed by Kurt Debattista in 2001 as his master study in University of Malta. 
It uses the two level scheduling model, i.e. we have m user level threads running on top of n kernel threads. If you guys are interested,
I can send you the thesis about it( it is a pdf file of size 1Mb). 
A few month ago, I obtained the permission from Kurt to release it under GPL. I did some work on it too for my undergraduate study.
The problems:
1. It is platform dependent. Kurt and I used some x86 assembly language to implement spin locks and lock-free algorithms.
2. It lacks some common features that you would expect in a thread library. For example it has no thread id and when a user-level terminates,
the thread structure will not be destroyed. This is however done on purpose, because our  supervisor argued that SMASH should be at the lowest
level so that any fancy(or not so fancy) features should be implemented by other libraries built on top of it.
3. Since it is developed as a academic project, a lot of decisions were made in favor of our study, not production use.

I think it is a good starting point, but it is not for immediate use. So what you guys think? Are you interested?
> -----Original Message-----
> From: Giuseppe Scrivano <gscrivano@gnu.org>
> To: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: rms@gnu.org, emacs-devel@gnu.org
> Date: 12/02/08 23:41
> Subject: Re: multi-threaded Emacs
> 
> Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
> 
> > I rarely use multiple terminals, and when I use them, the current
> > restrictions are mostly bearable.  OTOH I very often would like to keep
> > using my Emacs while it's byte-compiling some files, or while Gnus is
> > fetching some newsgroup.
> 
> This is exactly the problem I had when I first thought of threads.
> 
> Do you think we can solve it (at least partially) using a concurrent
> model?
> 
> Thanks,
> Giuseppe

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

>>> I rarely use multiple terminals, and when I use them, the current
>>> restrictions are mostly bearable.  OTOH I very often would like to keep
>>> using my Emacs while it's byte-compiling some files, or while Gnus is
>>> fetching some newsgroup.
>
>> This is exactly the problem I had when I first thought of threads.
>
>> Do you think we can solve it (at least partially) using a concurrent
>> model?
>
> Of course.  Even just with cooperative threads.

Yes, I was referring to the cooperating threads model using a QUIT
macro.  How can it be used by gnus while fetching new data?  Will it
give the control to another thread immediately after the trasfer begins?
I am concentrating on this example because usually when I fetch my
emails, I wish to have threads in Emacs.

Thanks,
Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

> Yes, I was referring to the cooperating threads model using a QUIT
> macro.

Actually, yielding in QUIT will take a lot of work.  It's definitely not
"cooperative" seen from Elisp's point of view (where QUIT can be run
implicitly all over the place).
By cooperative thread model, I mean that we can switch context either
when we already do (i.e. when waiting for user/process/network input),
or when running some new `yield' Elisp function.

> How can it be used by gnus while fetching new data?  Will it
> give the control to another thread immediately after the trasfer begins?

As written above (and earlier as well), Emacs will switch threads when
waiting for network input.


        Stefan

Re: multi-threaded Emacs

[Richard M Stallman]

It could be a useful package to develop further, for general purposes.
I cannot tell whether it might be useful in Emacs because your message
does not address the crucial questions.

    It uses the two level scheduling model, i.e. we have m user level
    threads running on top of n kernel threads.

Is the distinction between user-level threads and kernel threads
a matter of optimization, or is it a user-level feature?

Under what circumstances does it switch threads?

For the user, how does this differ from pthreads?

Re: multi-threaded Emacs

[Stefan Monnier]

> Hi, guys.  I have a generic user-level thread library on Linux.
> Maybe it can help.

Thanks.  But note that the problem with Emacs and cuncurrency doesn't
have much to do with the presence or absence of threads libraries.
There are already plenty of libraries implementing threads.  The problem
to change Emacs's Lisp and C code so as to be able to take advantage
of them.


        Stefan

Re: multi-threaded Emacs

[Richard M Stallman]

    Actually, yielding in QUIT will take a lot of work.  It's definitely not
    "cooperative" seen from Elisp's point of view (where QUIT can be run
    implicitly all over the place).

I am surprised.  Perhaps you're right, but why do you think so?
Anywhere that calls QUIT is a place where it is safe for an error to happen,
so why not a thread switch?

A slightly more conservative approach would be to thread-switch from
QUIT on certain circumstances, such as, if the innermost
unwind-protect has calls to Lisp code inside it.  We could arrange
for the specpdl to have the requisite info.

Re: multi-threaded Emacs

[Richard M Stallman]

    Yes, I was referring to the cooperating threads model using a QUIT
    macro.  How can it be used by gnus while fetching new data?

Does the code that gnus runs to fetch new data involve ever doing the
QUIT macro?  If it has a loop, then yes.  If it reads from a net
connection, then it calls wait_reading_process_output.  So it should be able
to operate in parallel with other things, even with cooperating threads.

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Richard M Stallman <rms@gnu.org> writes:

>     Actually, yielding in QUIT will take a lot of work.  It's definitely not
>     "cooperative" seen from Elisp's point of view (where QUIT can be run
>     implicitly all over the place).
>
> I am surprised.  Perhaps you're right, but why do you think so?
> Anywhere that calls QUIT is a place where it is safe for an error to happen,
> so why not a thread switch?

The cooperative threads approach moves to Elisp packages more work as
they will have explicitly to yield control but it simplifies a lot the C
code.
I already started to change my code to allow only the execution of a
thread at a time and add a `yield' primitive.

Giuseppe

Re: multi-threaded Emacs

[Miles Bader]

Giuseppe Scrivano <gscrivano@gnu.org> writes:
>> I am surprised.  Perhaps you're right, but why do you think so?
>> Anywhere that calls QUIT is a place where it is safe for an error to happen,
>> so why not a thread switch?
>
> The cooperative threads approach moves to Elisp packages more work as
> they will have explicitly to yield control but it simplifies a lot the
> C code.  I already started to change my code to allow only the
> execution of a thread at a time and add a `yield' primitive.

No, it will will likely have almost no effect on lisp code, because
99.9% of the code won't be affected, and the lack of pre-emption allows
that code to continue making traditional assumptions.

The only changes required will be in places that are known to be
long-running, where sticking in a few strategic calls to (yield) will
probably relieve most of the problem.

This is because emacs, being an interactive system, generally doesn't
have a lot of long-running code.  It's the relatively few exceptions to
this rule (e.g. gnus reading in new messages) that are the main issues
in practice.  Fixing those places will probably yield a lot of benefit
for (relatively) small amount of work.

-Miles

-- 
Brain, n. An apparatus with which we think we think.

Re: multi-threaded Emacs

[Paul R]

Miles> This is because emacs, being an interactive system, generally
Miles> doesn't have a lot of long-running code. It's the relatively few
Miles> exceptions to this rule (e.g. gnus reading in new messages) that
Miles> are the main issues in practice. Fixing those places will
Miles> probably yield a lot of benefit for (relatively) small amount of
Miles> work.

I hope this would allow a better on-the-fly processing of text as well.
I'm thinking of spell checking, code validation (this is called flymake
in emacs IIRC), or even a smoother syntax highlighting.

-- 
  Paul

Re: multi-threaded Emacs

[Eli Zaretskii]

> From: Paul R <paul.r.ml@gmail.com>
> Date: Fri, 05 Dec 2008 10:42:04 +0100
> 
> I hope this would allow a better on-the-fly processing of text as well.
> I'm thinking of spell checking, code validation (this is called flymake
> in emacs IIRC), or even a smoother syntax highlighting.

Any Emacs feature which, like spell-checking, uses a subprocess to do
its job, already uses a kind of non-preemptive multi-threading built
into wait_reading_process_output and its subroutines.  This is because
Emacs checks all the possible sources of input, including sub-process
output, when it is idle.

Re: multi-threaded Emacs

[Paul R]

Eli> Any Emacs feature which, like spell-checking, uses a subprocess to
Eli> do its job, already uses a kind of non-preemptive multi-threading
Eli> built into wait_reading_process_output and its subroutines. This is
Eli> because Emacs checks all the possible sources of input, including
Eli> sub-process output, when it is idle.

Indeed, I tried flyspell again and I felt it a lot more responsive than
I was expecting. With threads this could be extended to features not
relying on external processes.

Also, fontlocking is immediate except for multiline matches, which only
happens when idle for some time. I can feel it, but maybe the major
modes I'm using don't make proper use of fontlocking feature.



-- 
  Paul

Re: multi-threaded Emacs

[Helmut Eller]

* Miles Bader [2008-12-05 09:20+0100] writes:

> This is because emacs, being an interactive system, generally doesn't
> have a lot of long-running code.  It's the relatively few exceptions to
> this rule (e.g. gnus reading in new messages) that are the main issues
> in practice.  Fixing those places will probably yield a lot of benefit
> for (relatively) small amount of work.

I'm wondering what the exact problem with Gnus is.

Certainly, downloading the next article takes a bit of time but threads
wont make the download any faster.  Is there something the user wants to
do while waiting for the next article?

There's also something called "gnus-async" which supposedly downloads
articles in the background.  It's clearly possible to do I/O in the
background with ordinary process-filters; we need no threads for that.
It's probably a bit harder to parse messages in process-filters as with
threads, but threads are also tricky (preemptive or not).

Opening a connection can also take some time, but again, it can be done
asynchronously with the :nowait argument to make-network-process.  I
don't know if Gnus uses this possibility.  It would be interesting to
know what is easier: adding threads or rewriting Gnus with
process-filters.

Threads could probably be used to "stop" the current command and
continue it in the background.  Something like job control in a shell.
That would be a nice feature, but I don't know if it is worth all the
complexity that threads introduce.

Helmut.

Re: multi-threaded Emacs

[Li Lin]

First, all context switches between user-level threads have to be done
manually, i.e. if you need a switch, you have to call
cthread_yield(). However, on SMP systems, since we have more than one
kernel threads, user-level threads may be interrupted randmonly, but
still no user-level context switch will happen unless you yield the CPU explicitly.

Re: multi-threaded Emacs

[Stefan Monnier]

>     Actually, yielding in QUIT will take a lot of work.  It's definitely not
>     "cooperative" seen from Elisp's point of view (where QUIT can be run
>     implicitly all over the place).

> I am surprised.  Perhaps you're right, but why do you think so?
> Anywhere that calls QUIT is a place where it is safe for an error to happen,
> so why not a thread switch?

It will be safe in the sense that it won't cause a crash.  But it will
mess up Elisp's semantics.  Consider:

   (dotimes (i 1000) (toto))

if you run this code twice in separate threads and allow context
switches at QUIT, then you'll basically be doing "preemptive
concurrency" seen from Elisp's point of view.  Among other things, the
two threads will be fighting over the value of `i'.

So before this level of concurrency can be made to work we'll need to
fix dynamic scoping to be "per-thread" rather than global.

Note that the `yield' primitive won't be easy to use for the same kind
of reason (until we fix dynamic-scoping that is).


        Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

> I'm wondering what the exact problem with Gnus is.

Nothing in particular.  Gnus is already doing a fair bit of effort to
run asynchronously.  But, e.g. refreshing the *Group* buffer can take
a long time (especially if you use IMAP) and during this time, your
Emacs can't be used, even though it's not necessarily using all of
your CPU.
Similarly when downloading a large article (with say some movie
attached).

For those reasons I always have at least 2 Emacs processes running: one
for Gnus and one for pretty much everything else.


        Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

>     Yes, I was referring to the cooperating threads model using a QUIT
>     macro.  How can it be used by gnus while fetching new data?
> Does the code that gnus runs to fetch new data involve ever doing the
> QUIT macro?

Yes, the QUIT macro is executed pretty much all the time.

> If it has a loop, then yes.  If it reads from a net
> connection, then it calls wait_reading_process_output.

It does both.

> So it should be able to operate in parallel with other things, even
> with cooperating threads.

Indeed.


        Stefan

Re: multi-threaded Emacs

[Ted Zlatanov]

On Fri, 05 Dec 2008 12:02:19 +0100 Helmut Eller <eller.helmut@gmail.com> wrote: 

HE> I'm wondering what the exact problem with Gnus is.

HE> Certainly, downloading the next article takes a bit of time but threads
HE> wont make the download any faster.  Is there something the user wants to
HE> do while waiting for the next article?

Even assuming all server interactions can be backgrounded (they can't
AFAIK because of their current design, interacting with the global data
all over the place), one place that's slow is article splitting.  You
fetch an article, then run some rules (e.g. spam filters and registry
searches) to decide where it will go.  This can be 90% parallelized, I
would guess.

Reading mail normally has never been so slow that I wished it could be
done in the background.

Saving the newsrc file is sometimes slow, so backgrounding it would be
nice.  Of course, you don't want to garble that data so it's important
to do it right.

The Gnus registry should be asynchronous for:

- tracking article move/delete/copy/spool operations
- saving the registry file
- interacting with spam.el

spam.el should be asynchronous for:

- running a spam backend on an article
- determining the spam score of an article
- telling the registry the results of spam processing

Ted

Re: multi-threaded Emacs

[Tom Tromey]

>>>>> "Helmut" == Helmut Eller <eller.helmut@gmail.com> writes:

Helmut> I'm wondering what the exact problem with Gnus is.

Getting new news blocks all of Emacs, sometimes for a long time.
Also, entering a newsgroup can sometimes take quite a while.

It seems to me that this could be fixed in Gnus, by installing a
special keymap (to prevent the user from trying "bad" things) and then
doing a lot more work in the process filter.  This is a pain, of
course.

Entering a newsgroup is trickier since I am sure that it is not always
blocked on I/O.  Even this could be done -- say by doing small
increments of work each time a timer fires.

But, the problem is not limited to Gnus.  If you do a big update in
PCL-CVS (or psvn), Emacs will pause while preparing the buffer.  Some
VC things did this, too, in 22 (but now are async, I think).

I've also noticed that ERC can cause Emacs to be unusable for long
periods, I think when it has trouble contacting the nameserver.  Also,
ERC tends to disconnect from the server if Emacs pauses for too long
-- I got much more sensitive to problems in this area once I started
using ERC...

The promise of threads isn't just that it can fix these, but that it
opens Emacs to new applications without hurting usability.  Maybe
there are other ways to accomplish the same thing, though.

Tom

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Personally I don't think there is need to use a library that at the
moment is usable only on an architecture, it will be a serious
portability problem for Emacs (that probably after "Hello World" is the
most portable program out there).
All we need for a multi-threaded Emacs can be done quite easily with
pthreads.

Giuseppe

Li Lin <ak70@vanilla.net.mt> writes:

> SMASH has many different implementations. Basically, we create one
> kernel thread for each CPU(or core) in which a user-level thread
> scheduler runs, and the thread is bounded to the corresponding CPU. The
> context switches among user-level threads are done though a explicit
> call to the function cthread_yield(). However, it is the native
> scheduler that manages the kernel threads. 
> So on uniprocessor machines, it is purely cooperative, on multi-CPU(or
> -core) machines it is a mixture of cooperative and preemptive
> threads. However, it is not difficult to modify it so that on
> uniprocessor machine we still have more than one kernel threads.
> I attached Kurt's thesis about SMASH. Although a lot of implementation
> details has changed, his orginal thesis is still a good reference.
> The attachment is a DVI file. If you can read it, then I can send you
> the latex source of it, but you have to compile it by yourself.

Re: multi-threaded Emacs

[Miles Bader]

Tom Tromey <tromey@redhat.com> writes:
> The promise of threads isn't just that it can fix these, but that it
> opens Emacs to new applications without hurting usability.  Maybe
> there are other ways to accomplish the same thing, though.

I think most of these things _could_ be done by judicious use of process
filters etc... but it's a big pain, maybe requiring completely
re-designing various parts of gnus.  My hope is that with cooperative
threading, the changes required would be far smaller, maybe even just
sticking in calls to (yield) at strategic locations.

-miles

-- 
Alliance, n. In international politics, the union of two thieves who have
their hands so deeply inserted in each other's pockets that they cannot
separately plunder a third.

Re: multi-threaded Emacs

[Helmut Eller]

* Tom Tromey [2008-12-05 17:57+0100] writes:

> The promise of threads isn't just that it can fix these, but that it
> opens Emacs to new applications without hurting usability.  Maybe
> there are other ways to accomplish the same thing, though.

It also opens possibilities for concurrency related bugs.
We will see how it turns out.  

Helmut.

Re: multi-threaded Emacs

[Richard M Stallman]

    The cooperative threads approach moves to Elisp packages more work as
    they will have explicitly to yield control but it simplifies a lot the C
    code.

If thread-switching occurs inside QUIT, then Lisp code will never
need to explicitly say where switching occurs.

On the other hand, if thread-switching only occurs in
wait_reading_process_output, Lisp programs could permit
thread-switching by doing (accept-process-output).

The former would be more convenient.  Stefan said it has
problems, but didn't explain them yet.

Re: multi-threaded Emacs

[Richard M Stallman]

    It will be safe in the sense that it won't cause a crash.  But it will
    mess up Elisp's semantics.  Consider:

       (dotimes (i 1000) (toto))

    if you run this code twice in separate threads and allow context
    switches at QUIT, then you'll basically be doing "preemptive
    concurrency" seen from Elisp's point of view.  Among other things, the
    two threads will be fighting over the value of `i'.

Each thread should have its own local bindings.  To do this
requires swapping bindings in and out of the specpdls
when switching threads.  It is not hard.

This makes thread switches slower, and that makes it desirable
to do them less often.

Re: multi-threaded Emacs

[Magnus Henoch]

Giuseppe Scrivano <gscrivano@gnu.org> writes:

> Personally I don't think there is need to use a library that at the
> moment is usable only on an architecture, it will be a serious
> portability problem for Emacs (that probably after "Hello World" is the
> most portable program out there).
> All we need for a multi-threaded Emacs can be done quite easily with
> pthreads.

Or GNU pth, which I'm surprised that noone has mentioned.  It does
cooperative threading with a pthread-like interface, yielding at I/O
operations and some other syscalls.

http://www.gnu.org/software/pth/

Of course, whoever writes the code gets to choose the library.  Good
luck with your endeavour!  I look forward to the results.

Magnus

Re: multi-threaded Emacs

[Stefan Monnier]

> It also opens possibilities for concurrency related bugs.

You mean "it holds promises of concurrency bugs"?  Yes, very much so :-(


        Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

>     It will be safe in the sense that it won't cause a crash.  But it will
>     mess up Elisp's semantics.  Consider:

>        (dotimes (i 1000) (toto))

>     if you run this code twice in separate threads and allow context
>     switches at QUIT, then you'll basically be doing "preemptive
>     concurrency" seen from Elisp's point of view.  Among other things, the
>     two threads will be fighting over the value of `i'.

> Each thread should have its own local bindings.  To do this
> requires swapping bindings in and out of the specpdls
> when switching threads.  It is not hard.

> This makes thread switches slower, and that makes it desirable
> to do them less often.

It might be an acceptable temporary solution, but in the long term we
will want to allow true parallelism, so such trickery will not be
an option.

Whether it'll be a valuable intermediate point or not, I cannot say.
My gut feeling is that we'd better work on a solution that will work in
the longer run.  Currently my guess is that generalizing the existing
buffer-local/frame-local/terminal-local machinery to include
thread-local is going to work well, with fairly limited changes.


        Stefan

Re: multi-threaded Emacs

[Tom Tromey]

>> Do you see any situation that there is need to store a value on a
>> specific thread?

Stefan> let-binding, of course.  It's probably the only one that matters
Stefan> (besides the internal ones like current_buffer).

I've been wondering how `flet' will be handled.

Tom

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

>>     It will be safe in the sense that it won't cause a crash.  But it will
>>     mess up Elisp's semantics.  Consider:
>
>>        (dotimes (i 1000) (toto))
>
>>     if you run this code twice in separate threads and allow context
>>     switches at QUIT, then you'll basically be doing "preemptive
>>     concurrency" seen from Elisp's point of view.  Among other things, the
>>     two threads will be fighting over the value of `i'.
>
>> Each thread should have its own local bindings.  To do this
>> requires swapping bindings in and out of the specpdls
>> when switching threads.  It is not hard.
>
>> This makes thread switches slower, and that makes it desirable
>> to do them less often.
>
> It might be an acceptable temporary solution, but in the long term we
> will want to allow true parallelism, so such trickery will not be
> an option.

Actually I am using what Richard suggested.  Every thread has a specpdl
and on a thread switch I copy the current symbol value inside its
specbinding cell.

Still there is much to do but now I am able to do this:

(setq a-thread (make-thread))
#<thread 1>

(progn
  (run-in-thread a-thread '(dotimes (i 2)
                         (print "hello")
                         (yield)))

    (dotimes (i 2)
      (print "world")
      (yield)))

"hello"

"world"

"hello"

"world"



Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

>>> Do you see any situation that there is need to store a value on a
>>> specific thread?
Stefan> let-binding, of course.  It's probably the only one that matters
Stefan> (besides the internal ones like current_buffer).
> I've been wondering how `flet' will be handled.

Good question.  Luckily, it's too often used and it's easy to grep for
it, so it hopefully will be fixable somehow, although it may require
a completely different implementation technique, or different semantics.


        Stefan

Re: multi-threaded Emacs

[Richard M Stallman]

    > Each thread should have its own local bindings.  To do this
    > requires swapping bindings in and out of the specpdls
    > when switching threads.  It is not hard.

      Currently my guess is that generalizing the existing
    buffer-local/frame-local/terminal-local machinery to include
    thread-local is going to work well, with fairly limited changes.

That seems like a misunderstanding.  What I am talking about does
not involve adding another kind of binding.  It is a matter of
correctly implementing the existing kinds of binding in the context
of multiple threads.

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Hi,

I uploaded here a patch with the current status of my work:

http://it.gnu.org/~gscrivano/files/concurrent_threads_7_12.diff.gz

The patch adds these Elisp primitives:

(make-thread)
(run-in-thread)
(kill-thread)
(yield)

Now the garbage collector can be executed by any thread, local bindings
are done as you suggested, the symbol value is changed when Emacs
switches to another thread.
Every thread has its own current_buffer so they can work independently
on different buffers.

New code is not very clean yet, differently from the first patch I
submitted, now all thread local storage data is in a `thread_data'
struct and (make-thread) returns an object.

Any comment?  (Good impressions are welcome).

Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

>>> Each thread should have its own local bindings.  To do this
>>> requires swapping bindings in and out of the specpdls
>>> when switching threads.  It is not hard.
[...]
> Actually I am using what Richard suggested.  Every thread has a specpdl
> and on a thread switch I copy the current symbol value inside its
> specbinding cell.

Switching the value of specpdl is not enough.  Try

(progn
  (run-in-thread a-thread '(dotimes (i 2)
                         (print "hello")
                         (yield)))

    (let ((i 5))
      (while (< i 7)
        (print "world")
        (yield)
        (setq i (1+ i))))

What Richard suggests is that upon a thread-switch we walk up the specpdl
stack, undoing all the bindings, then switch specpdl to the one of the
other thread and walk down that one to reestablish the local bindings of
the new thread.


        Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

>> Each thread should have its own local bindings.  To do this
>> requires swapping bindings in and out of the specpdls
>> when switching threads.  It is not hard.
>       Currently my guess is that generalizing the existing
>     buffer-local/frame-local/terminal-local machinery to include
>     thread-local is going to work well, with fairly limited changes.
> That seems like a misunderstanding.

No, it's not a misunderstanding.  I'm just suggesting a different
implementation technique.

> What I am talking about does not involve adding another kind of
> binding.  It is a matter of correctly implementing the existing kinds
> of binding in the context of multiple threads.

Indeed, it is, and there several alternatives.


        Stefan

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

>
> Switching the value of specpdl is not enough.  Try
>
> (progn
>   (run-in-thread a-thread '(dotimes (i 2)
>                          (print "hello")
>                          (yield)))
>
>     (let ((i 5))
>       (while (< i 7)
>         (print "world")
>         (yield)
>         (setq i (1+ i))))
>
> What Richard suggests is that upon a thread-switch we walk up the specpdl
> stack, undoing all the bindings, then switch specpdl to the one of the
> other thread and walk down that one to reestablish the local bindings of
> the new thread.

It is exactly what I do in save_thread_bindings () and
restore_thread_bindings ().

Trying your code (plus initializing the thread and another ')' at the
end) I have:

(progn
 (run-in-thread a-thread '(dotimes (i 2)
                        (print "hello")
                        (yield)))

   (let ((i 5))
     (while (< i 7)
       (print "world")
       (yield)
       (setq i (1+ i)))))

"hello"

"world"

"hello"

"world"


Regards,
Giuseppe

Re: multi-threaded Emacs

[Chetan Pandya]

I am wondering if there is eally an expectation build a multi-threading emacs. There are also all of the global variables in C code that might need to be saved and restored e.g. while loading a file.

Chetan

--- On Sun, 12/7/08, Giuseppe Scrivano <gscrivano@gnu.org> wrote:

> From: Giuseppe Scrivano <gscrivano@gnu.org>
> Subject: Re: multi-threaded Emacs
> To: "Stefan Monnier" <monnier@iro.umontreal.ca>
> Cc: rms@gnu.org, emacs-devel@gnu.org
> Date: Sunday, December 7, 2008, 11:51 PM
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
> 
> >
> > Switching the value of specpdl is not enough.  Try
> >
> > (progn
> >   (run-in-thread a-thread '(dotimes (i 2)
> >                          (print "hello")
> >                          (yield)))
> >
> >     (let ((i 5))
> >       (while (< i 7)
> >         (print "world")
> >         (yield)
> >         (setq i (1+ i))))
> >
> > What Richard suggests is that upon a thread-switch we
> walk up the specpdl
> > stack, undoing all the bindings, then switch specpdl
> to the one of the
> > other thread and walk down that one to reestablish the
> local bindings of
> > the new thread.
> 
> It is exactly what I do in save_thread_bindings () and
> restore_thread_bindings ().
> 
> Trying your code (plus initializing the thread and another
> ')' at the
> end) I have:
> 
> (progn
>  (run-in-thread a-thread '(dotimes (i 2)
>                         (print "hello")
>                         (yield)))
> 
>    (let ((i 5))
>      (while (< i 7)
>        (print "world")
>        (yield)
>        (setq i (1+ i)))))
> 
> "hello"
> 
> "world"
> 
> "hello"
> 
> "world"
> 
> 
> Regards,
> Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

> It is exactly what I do in save_thread_bindings () and
> restore_thread_bindings ().

Wonderful, thanks.


        Stefan

Re: multi-threaded Emacs

[Richard M Stallman]

What is the condition for thread-switching in your latest version?

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Richard M Stallman <rms@gnu.org> writes:

> What is the condition for thread-switching in your latest version?

The `yield' primitive must be explicitly called.

Giuseppe

Re: multi-threaded Emacs

[dhruva]

Hello,

On Tue, Dec 9, 2008 at 1:19 AM, Giuseppe Scrivano <gscrivano@gnu.org> wrote:
> Richard M Stallman <rms@gnu.org> writes:
>
>> What is the condition for thread-switching in your latest version?
>
> The `yield' primitive must be explicitly called.

I hope there will be a branch with this code sometime soon being
updated from HEAD constantly. I will then be able to play with this
along with the bleeding edge features on HEAD.

-dhruva

-- 
Contents reflect my personal views only!

Re: multi-threaded Emacs

[Stephen J. Turnbull]

dhruva writes:

 > I hope there will be a branch with this code sometime soon being
 > updated from HEAD constantly. I will then be able to play with this
 > along with the bleeding edge features on HEAD.

Why don't you just make one?  I'm seriously asking; there are several
tools such as cvs2svn and tailor.  Those two are both written in
Python, which means they should be fairly portable, including to
Windows.

Have you tried one or more of these and failed?

Making a serious mirror and providing the service to third parties is
a relatively demanding task.  But for local use you can put up with
the occasional CRLF vs. NL bogosity and other minor issues that
typically arise.  Ie, maintaining a local mirror is well within the
scope of effort suggested by "play with bleeding edge features."

Re: multi-threaded Emacs

[dhruva]

Hello Stephen,

On Tue, Dec 9, 2008 at 8:19 AM, Stephen J. Turnbull <stephen@xemacs.org> wrote:
> dhruva writes:
>
>  > I hope there will be a branch with this code sometime soon being
>  > updated from HEAD constantly. I will then be able to play with this
>  > along with the bleeding edge features on HEAD.
>
> Why don't you just make one?  I'm seriously asking; there are several
> tools such as cvs2svn and tailor.  Those two are both written in
> Python, which means they should be fairly portable, including to
> Windows.

I have not used cvs2svn myself but suggested it and have seen it being
used at my previous place of work (moving ~10 years of CVS history to
svn and it went fine though I was told of issues in doing an
incremental update. They ended up doing a one time conversion and
stopped usage of CVS. Like a flip switch approach!).

> Have you tried one or more of these and failed?

Well, the point is to have a branch where the main author can push and
I could pull. I can always have a patch queue (as in mercurial) or do
it through some extra wizardry in git. I do not want to get into
merging changes that are not mine and mess up and start reporting
problems that are truly my own.

Off topic:
I have tried tailor, since I work on p4 at work, I have tried git-p4
and have developed my very own p4 to hg. I find tailor to be very
flaky. Like you correctly mentioned in a different thread that it
needs care, I ran out of patience. However, I did contribute a minor
fix to make it work with newer hg (sometime back).
 To summarize, based on my experience, I find tools that are part of
git are quite robust (among the few I have used or tested).

-dhruva

-- 
Contents reflect my personal views only!

Re: multi-threaded Emacs

[Andreas Schwab]

"Stephen J. Turnbull" <stephen@xemacs.org> writes:

> Why don't you just make one?  I'm seriously asking; there are several
> tools such as cvs2svn and tailor.

IMHO the best tool for converting a CVS repo is parsecvs.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: multi-threaded Emacs

[Richard M Stallman]

    > What is the condition for thread-switching in your latest version?

    The `yield' primitive must be explicitly called.

I think that interface won't work very well, because it would require
changing every Lisp program to make it cooperate with other threads.
We need to put this into the C level.

If making QUIT do this is not safe, we could write another macro
YIELD to do it, and call that macro where appropriate.

But that macro needs to be very fast when it does NOT switch threads!

Here's an idea.  Suppose the YIELD macro increments a counter and
switches threads (round robin?) when that counter reaches a certain
number.  Every thread-switch would reset the counter to 0.
Of course, waiting (in wait_reading_process_output) would also
switch threads.


2. 

Re: multi-threaded Emacs

[Giuseppe Scrivano]

Richard M Stallman <rms@gnu.org> writes:

>     > What is the condition for thread-switching in your latest version?
>
>     The `yield' primitive must be explicitly called.
>
> I think that interface won't work very well, because it would require
> changing every Lisp program to make it cooperate with other threads.
> We need to put this into the C level.

I think it is not safe to call `yield' from the C code, except special
cases like `run-in-thread'.  Every thread must be completely separated
from each other to allow a switch during its execution and it is not
true while threads are accessing global variables.

For example, we can't switch threads while they are executing:

(setq a-global-variable (foo a-global-variable))

This is the reason why YIELD must be explicit at Elisp level, because
the developer knows exactly that a switch can happen at that point.

In future every thread should be executed indipendently from each other
(adding synchronization primitives where they are needed) to allow real
parallelism.


> If making QUIT do this is not safe, we could write another macro
> YIELD to do it, and call that macro where appropriate.
>
> But that macro needs to be very fast when it does NOT switch threads!

Elisp developers shouldn't worry about yield efficiency because if there
are not other active threads, nothing will be done and `yield' returns
immediately.


> Here's an idea.  Suppose the YIELD macro increments a counter and
> switches threads (round robin?) when that counter reaches a certain
> number.  Every thread-switch would reset the counter to 0.
> Of course, waiting (in wait_reading_process_output) would also
> switch threads.

Thread switching is implemented using round robin.  Why would you like
to reduce the amount of switches using a counter?  I think that thread
switching doesn't take a lot of time that we need to call it carefully,
instead I think that more often we call it and more responsive Emacs
will look.
I was thinking about change the scheduler policy to give a bigger
priority to threads that are working on a buffer currently visible to
the user.  What I really expect from Emacs threads is that I can
continue working while some other tasks are executed in the background,
like fetching emails.  Personally I will not care much if it took N+1
seconds instead of N if I could continue work on another buffer.

Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

>> What is the condition for thread-switching in your latest version?
>     The `yield' primitive must be explicitly called.

> I think that interface won't work very well, because it would require
> changing every Lisp program to make it cooperate with other threads.
> We need to put this into the C level.

I think if `yield' is called in accept-process-output and read_char, the
remaining places where `yield' might be needed will be fairly few.


        Stefan

Re: multi-threaded Emacs

[Richard M Stallman]

    For example, we can't switch threads while they are executing:

    (setq a-global-variable (foo a-global-variable))

In most cases, there is no problem, because the code in the other thread
won't change this global variable.

I think it is better to have a variable `inhibit-thread-switch'
which you could bind around such sections when there is really an issue.

Re: multi-threaded Emacs

[Richard M Stallman]

      Why would you like
    to reduce the amount of switches using a counter?

Because it takes a substantial time.  Just swapping the specpdls
takes time.

Re: multi-threaded Emacs

[Richard M Stallman]

    I think if `yield' is called in accept-process-output and read_char, the
    remaining places where `yield' might be needed will be fairly few.

That sort of thing could be enough for the thread-per-terminal job.
It would also be good for specially written parallel programs.
But that's as far as it would go.

Re: multi-threaded Emacs

[Stefan Monnier]

>     I think if `yield' is called in accept-process-output and read_char, the
>     remaining places where `yield' might be needed will be fairly few.

> That sort of thing could be enough for the thread-per-terminal job.
> It would also be good for specially written parallel programs.
> But that's as far as it would go.

Indeed.  Further than that, we'd need more explicit
synchronization primitives.  We could probably start with
a (atomically &rest BODY) which guarantees that BODY will be properly
protected from other threads that it will appear to be
executed atomically.
Such a primitive should also include constraints such as "BODY cannot
include non-undoable operations", e.g. it can't save to a file.


        Stefan

Re: multi-threaded Emacs

[Ted Zlatanov]

On Wed, 10 Dec 2008 20:59:41 -0500 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

SM> Further than that, we'd need more explicit synchronization
SM> primitives.  We could probably start with a (atomically &rest BODY)
SM> which guarantees that BODY will be properly protected from other
SM> threads that it will appear to be executed atomically.  Such a
SM> primitive should also include constraints such as "BODY cannot
SM> include non-undoable operations", e.g. it can't save to a file.

Would it help to look at the C level and figure out which functions are
atomic (no I/O operations, IIUC), and perhaps mark them so with an
attribute?  Then any ELisp function that builds on atomics is atomic
itself, presumably (except for macros and other trickery).

Ted

Re: multi-threaded Emacs

[Stefan Monnier]

> Then any ELisp function that builds on atomics is atomic
> itself, presumably (except for macros and other trickery).

No, atomicity does not work that way, sadly.


        Stefan

Re: multi-threaded Emacs

[Ted Zlatanov]

On Thu, 11 Dec 2008 13:30:26 -0500 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> Then any ELisp function that builds on atomics is atomic
>> itself, presumably (except for macros and other trickery).

SM> No, atomicity does not work that way, sadly.

"atomic" was a bad word choice on my part.  I meant "safe to put in an
(atomically) body as you described it."  I think if functions A and B
are safe, then any function C that only uses A and B is safe too.  Does
that make more sense?

Ted

Re: multi-threaded Emacs

[Paul R]

SM> No, atomicity does not work that way, sadly.

Ted> "atomic" was a bad word choice on my part. I meant "safe to put in
Ted> an (atomically) body as you described it." I think if functions
Ted> A and B are safe, then any function C that only uses A and B is
Ted> safe too. Does that make more sense?

I guess Stefan means he wants a way to operate within a transaction, so
that the state of emacs (the state being defined by the all the values
of every variables accessible from the scope) is either changed exactly
as desired, or not touched at all.

If C is defined as "A then B" with A and B atomics, then if you run C,
and A is a success and B is a failure, then C won't have the 'atomic'
property, because C will exit with state half changed. Now if you totaly
avoid sequential execution (avoid the "imperative style"), so that you
construct C of B and B of A, indeed having A atomic is enought. But any
software, in particular emacs, is full of sequential processing with
intermediate states between instructions.

BTW, I'm not sure why stefan wants this atomic construction at the lisp
level, but for sure I would be amazed to see that !

-- 
  Paul

Re: multi-threaded Emacs

[Paul R]

Stefan> Indeed. Further than that, we'd need more explicit
Stefan> synchronization primitives. We could probably start with
Stefan> a (atomically &rest BODY) which guarantees that BODY will be
Stefan> properly protected from other threads that it will appear to be
Stefan> executed atomically.

Isn't it what critical sections are for ? (critical &rest BODY) would
execute body with no thread switching. I think this feature is not
necessary with cooperative-only threading because a critical section is
any section that does not contain any 'yield' instruction.


-- 
  Paul

Re: multi-threaded Emacs

[Stefan Monnier]

>>> Then any ELisp function that builds on atomics is atomic
>>> itself, presumably (except for macros and other trickery).
SM> No, atomicity does not work that way, sadly.
> "atomic" was a bad word choice on my part.  I meant "safe to put in an
> (atomically) body as you described it."  I think if functions A and B
> are safe, then any function C that only uses A and B is safe too.  Does
> that make more sense?

Yes, that makes sense.  Hopefully, most functions are "safe" in
this respect.

BTW, implementing "atomically" is not necessarily that hard.

Of course, it can be implemented with an "optimistic locking" discipline
where we track changes and undo them if the transaction aborts, but
until we get there, there are meny much simpler implementations which
will be useful.  A first implementation is

  (defmacro atomically (&rest body)
    `(let ((inhibit-thread-switch t))
       ,@body))

A better one, yet still trivial, is

  (defconst the-lock (make-lock))
  (defmacro atomically (&rest body)
    `(progn
       (lock-grab the-lock)
       (unwind-protect
           (progn ,@body)
         (lock-release the-lock))))


-- Stefan

Re: multi-threaded Emacs

[Stefan Monnier]

Stefan> Indeed. Further than that, we'd need more explicit
Stefan> synchronization primitives. We could probably start with
Stefan> a (atomically &rest BODY) which guarantees that BODY will be
Stefan> properly protected from other threads that it will appear to be
Stefan> executed atomically.

> Isn't it what critical sections are for ? (critical &rest BODY) would
> execute body with no thread switching. I think this feature is not
> necessary with cooperative-only threading because a critical section is
> any section that does not contain any 'yield' instruction.

We're talking about non-cooperative scenarios (e.g. yield in QUIT).


        Stefan

Re: multi-threaded Emacs

[Giuseppe Scrivano]

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

> Yes, that makes sense.  Hopefully, most functions are "safe" in
> this respect.
>
> BTW, implementing "atomically" is not necessarily that hard.
>
> Of course, it can be implemented with an "optimistic locking" discipline
> where we track changes and undo them if the transaction aborts, but
> until we get there, there are meny much simpler implementations which
> will be useful.  A first implementation is
>
>   (defmacro atomically (&rest body)
>     `(let ((inhibit-thread-switch t))
>        ,@body))
>
> A better one, yet still trivial, is
>
>   (defconst the-lock (make-lock))
>   (defmacro atomically (&rest body)
>     `(progn
>        (lock-grab the-lock)
>        (unwind-protect
>            (progn ,@body)
>          (lock-release the-lock))))
>

IMHO the first is the better solution for a cooperative model.  There is
only a thread active at a time, introduce lock/unlock can easily cause
deadlocks, at least for the current threads scheduler implementation.
We will need lock/unlock when we will use parallel threads and we must
protect critical sections.

Personally, I would avoid to introduce `atomically' now with a
cooperative model but I prefer instead an explicit `yield'.  In this way
Elisp packages that use `yield' can benefit of threads and at the same
time it will not break old packages designed to work with a single
thread.  Using `atomically' and hidden `yield's all around can break old
packages that don't know about threads.

On the other hand, my wish is to have an Emacs with parallel threads
someday, surely it will needs explicit threads synchronization and
`atomically' must be introduced in any case.  It will break any Elisp
package that doesn't use where it is needed.  If we introduce it now,
Elisp packages will probably work well later too.

These are the advantages/disadvantages we will have choosing explicit
yield or using atomically to inhibit thread switches.  After all it is
just choose when "cause" problems in Elisp packages, now with
cooperative threads or later with parallel ones.

What do you think?  Do you want to have `atomically' now?

Regards,
Giuseppe

Re: multi-threaded Emacs

[Stefan Monnier]

> Personally, I would avoid to introduce `atomically' now with a
> cooperative model but I prefer instead an explicit `yield'.

It looks like I wasn't clear, but if you look back in this thread,
you'll see that I only mentioned `atomically' in the context of "when
explicit yields is not enough".

IOW I fully agree that explicit yields (plus some implicit ones when
waiting) are just fine for now.


        Stefan