Re: Emacs design and architecture. How about copy-on-write?

Re: Emacs design and architecture. How about copy-on-write?

[Payas Relekar]

Po Lu <luangruo@yahoo.com> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>> Then try leaning on C-n or C-p _after_ everything is already
>> fontified.  You will still see that Emacs sometimes cannot keep up,
>> especially if lines are not too short.
>
> Long lines are, at worst, infrequently encountered in source code,

Long lines are frequently encountered in prose like say Org-mode, that
might require font lock extensively, depending on the document.

Re: Emacs design and architecture. How about copy-on-write?

[zhanghj]

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

    The same will happen if only the main thread can display.  If a
    non-main thread wants to prompt the user, it will have to wait until
    the main thread becomes available, prompts the user, and returns the
    response.

    Someone always has to wait when threads need to synchronize.  There's
    no way around that.  Doing this in the thread that needs to
    display/prompt is easier because the context and relevant variables
    don't need to be communicated to another thread.

Sorry for my poor English.

Message queue is a good solution for parallel and concurrence.

I think it is not a good idea to let all threads to do display things directly.
It will be better to let non-main threads to do display things via message queue,
like many GUI toolkit does. It is also like the message loop in Emacs.
This will make many things easier.

For GUI toolkit on windows, there are two basic API: Sendmessage and PostMessage.
Non-gui thread can use theme to do display and UI related things.

For example in Emacs, when a non-main thread calls `message', a small display task is built
and put into the message queue of the main thread, like `PostMessage` does.
If it calls `read-file-name`, an UI task is built and put into the message queue of
the main thread like `SendMessage` does, while the caller thread will be blocked until result comes.

When all display jobs are all in one thread (decoupled with other threads), display jobs may be scheduled
more efficiently and may be concurrent internally.

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

Re: Emacs design and architecture

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Yuri Khan <yuri.v.khan@gmail.com>
>> Date: Fri, 15 Sep 2023 13:51:56 +0700
>> Cc: Dmitry Gutov <dmitry@gutov.dev>, owinebar@gmail.com, rms@gnu.org, emacs-devel@gnu.org
>> 
>> On Fri, 15 Sept 2023 at 12:51, Eli Zaretskii <eliz@gnu.org> wrote:
>> 
>> > One of the important aspects to keep in mind in this regard is that
>> > Emacs must give Lisp programs dynamic control of how stuff is
>> > displayed, and should be able to exercise that control at high
>> > frequency (a trivial example: pulse.el).
>> 
>> In CSS, this is solved in core with transitions. A style specifies
>> that a certain property will change gradually, provides its target
>> value, the transition duration, and a transition curve.
>
> You have taken the pulse.el example too literally.  The fact that it
> changes the color gradually is not relevant to the point I was trying
> to make, but you made it the main point.
>
> My point is that quite a few Lisp programs affect the display in
> near-real time and at high frequency.  This is what makes Emacs so
> powerful, and we don't want to lose this power when changing the
> display engine.
>
>> The use case of pulse.el would be translated to a couple of styles
>> that say effectively “A pulsed span will instantly gain yellow
>> background” and “A non-pulsed span will linearly revert to whatever
>> background it had over the course of 200 milliseconds” and a small
>> function that sets the span to pulsed and then immediately to
>> non-pulsed.
>
> This sounds like a lot of hair, when a Lisp program just wants to
> change the color of some part of the display.
>
>> (Implementing a CSS engine over a character terminal is a nontrivial
>> matter though.)
>
> Something else to keep in mind, I guess.  TTY colors are implemented
> specially and separately in Emacs (under the hood; Lisp programs can
> disregard the differences if they want), so it isn't a non-starter,
> per se.

I think it would maybe be good to think about the following:

Random thoughts about a parallel redisplay, from a height of 10 km.

What currently happens to bring changes to the screen is that redisplay
is called quite frequently in the course of processing input for
example.  Redisplay determines what part of the a "model" (buffer) has
changed, if any.  It makes sure that all info it needs to proceed is
available; think jit-lock, i.e. it calls Lisp. Because redisplay is
called frequently, it must minimize what it does, which is the reason
for the complicated optimizations there.

Whatever is done in the end, I think it would first be necessary to
change this general principle, so that layout/drawing whatever can
happen in parallel.  Without that, I suspect redisplay would get too
slow, or would finally collapse to a black hole by its complexity.

This of course, would pose several problems.

- This form of parallel redisplay cannot call Lisp, so no jit-lock, no
  hooks, or whatever during redisplay.  And at the point where we call
  redisplay today we don't know what will be displayed...
- Parallel redisplay also needs either a copy of what it to be
  displayed, or the model must be some persistent data structure
  that makes immutable versions of buffer-text, for instance,
  available.

Re: Emacs design and architecture

[Dmitry Gutov]

On 15/09/2023 12:32, Gerd Möllmann wrote:
> I think it would maybe be good to think about the following:
> 
> Random thoughts about a parallel redisplay, from a height of 10 km.
> 
> What currently happens to bring changes to the screen is that redisplay
> is called quite frequently in the course of processing input for
> example.  Redisplay determines what part of the a "model" (buffer) has
> changed, if any.  It makes sure that all info it needs to proceed is
> available; think jit-lock, i.e. it calls Lisp. Because redisplay is
> called frequently, it must minimize what it does, which is the reason
> for the complicated optimizations there.
> 
> Whatever is done in the end, I think it would first be necessary to
> change this general principle, so that layout/drawing whatever can
> happen in parallel.  Without that, I suspect redisplay would get too
> slow, or would finally collapse to a black hole by its complexity.

I think it'd be an interesting project to study how an existing Emacs 
could output into a web page. Or a web driver, etc. How a "toolkit port" 
into HTML/JS could work.

That system is historically more complex than what you described, 
including lots of callbacks, e.g. it might be possible to implement 
jit-lock using the 'DOMContentLoaded' and 'scroll' events.

Consequently, though, parallel layout has been historically a hard 
problem for web browsers, but the current engines do that, at least to 
an extend (I think that was one of the selling features of Servo, later 
incorporated into Gecko). Complexity is definitely an issue, though.

Re: Emacs design and architecture

[Gerd Möllmann]

Dmitry Gutov <dmitry@gutov.dev> writes:

> On 15/09/2023 12:32, Gerd Möllmann wrote:
>> I think it would maybe be good to think about the following:
>> Random thoughts about a parallel redisplay, from a height of 10 km.
>> What currently happens to bring changes to the screen is that
>> redisplay
>> is called quite frequently in the course of processing input for
>> example.  Redisplay determines what part of the a "model" (buffer) has
>> changed, if any.  It makes sure that all info it needs to proceed is
>> available; think jit-lock, i.e. it calls Lisp. Because redisplay is
>> called frequently, it must minimize what it does, which is the reason
>> for the complicated optimizations there.
>> Whatever is done in the end, I think it would first be necessary to
>> change this general principle, so that layout/drawing whatever can
>> happen in parallel.  Without that, I suspect redisplay would get too
>> slow, or would finally collapse to a black hole by its complexity.
>
> I think it'd be an interesting project to study how an existing Emacs
> could output into a web page. Or a web driver, etc. How a "toolkit
> port" into HTML/JS could work.
>
> That system is historically more complex than what you described,
> including lots of callbacks, e.g. it might be possible to implement
> jit-lock using the 'DOMContentLoaded' and 'scroll' events.
>
> Consequently, though, parallel layout has been historically a hard
> problem for web browsers, but the current engines do that, at least to
> an extend (I think that was one of the selling features of Servo,
> later incorporated into Gecko). Complexity is definitely an issue,
> though.

Maybe it would be worth looking at emacs-ng

  https://github.com/emacs-ng/emacs-ng

The README lists the feature

  Webrender

  WebRender is a GPU-based 2D rendering engine written in Rust from
  Mozilla. Firefox, the research web browser Servo, and other GUI
  frameworks draw with it. emacs-ng use it as a new experimental graphic
  backend to leverage GPU hardware.

Re: Emacs design and architecture

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Eli Zaretskii <eliz@gnu.org>,  Yuri Khan <yuri.v.khan@gmail.com>,
>   owinebar@gmail.com,  rms@gnu.org,  emacs-devel@gnu.org
> Date: Fri, 15 Sep 2023 20:36:07 +0200
> 
> Maybe it would be worth looking at emacs-ng
> 
>   https://github.com/emacs-ng/emacs-ng
> 
> The README lists the feature
> 
>   Webrender
> 
>   WebRender is a GPU-based 2D rendering engine written in Rust from
>   Mozilla. Firefox, the research web browser Servo, and other GUI
>   frameworks draw with it. emacs-ng use it as a new experimental graphic
>   backend to leverage GPU hardware.

I didn't look at this, but if by "graphic backend" they mean a
replacement for xterm.c, then this is much less interesting, because
the basic limitations of the current display engine's layout and
iterator (which are all implemented in xdisp.c and dispnew.c) will
still be with us.

Re: Emacs design and architecture

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: Eli Zaretskii <eliz@gnu.org>,  Yuri Khan <yuri.v.khan@gmail.com>,
>>   owinebar@gmail.com,  rms@gnu.org,  emacs-devel@gnu.org
>> Date: Fri, 15 Sep 2023 20:36:07 +0200
>> 
>> Maybe it would be worth looking at emacs-ng
>> 
>>   https://github.com/emacs-ng/emacs-ng
>> 
>> The README lists the feature
>> 
>>   Webrender
>> 
>>   WebRender is a GPU-based 2D rendering engine written in Rust from
>>   Mozilla. Firefox, the research web browser Servo, and other GUI
>>   frameworks draw with it. emacs-ng use it as a new experimental graphic
>>   backend to leverage GPU hardware.
>
> I didn't look at this, but if by "graphic backend" they mean a
> replacement for xterm.c, then this is much less interesting, because
> the basic limitations of the current display engine's layout and
> iterator (which are all implemented in xdisp.c and dispnew.c) will
> still be with us.

I've cloned the repo now, and it seems indeed to be a backend like xterm
or nsterm etc.  It's called wrterm, and is implemented in ca. 8.5 kloc
of Rust.  I can't read Rust fluently, but I'd say It implements the
usual functions for such a backend and not more.

So, I agree, that's not very interesting in this context.

Re: Emacs design and architecture

[Dmitry Gutov]

On 15/09/2023 22:19, Gerd Möllmann wrote:
> Eli Zaretskii<eliz@gnu.org>  writes:
> 
>>> From: Gerd Möllmann<gerd.moellmann@gmail.com>
>>> Cc: Eli Zaretskii<eliz@gnu.org>,  Yuri Khan<yuri.v.khan@gmail.com>,
>>>    owinebar@gmail.com,rms@gnu.org,emacs-devel@gnu.org
>>> Date: Fri, 15 Sep 2023 20:36:07 +0200
>>>
>>> Maybe it would be worth looking at emacs-ng
>>>
>>>    https://github.com/emacs-ng/emacs-ng
>>>
>>> The README lists the feature
>>>
>>>    Webrender
>>>
>>>    WebRender is a GPU-based 2D rendering engine written in Rust from
>>>    Mozilla. Firefox, the research web browser Servo, and other GUI
>>>    frameworks draw with it. emacs-ng use it as a new experimental graphic
>>>    backend to leverage GPU hardware.
>> I didn't look at this, but if by "graphic backend" they mean a
>> replacement for xterm.c, then this is much less interesting, because
>> the basic limitations of the current display engine's layout and
>> iterator (which are all implemented in xdisp.c and dispnew.c) will
>> still be with us.
> I've cloned the repo now, and it seems indeed to be a backend like xterm
> or nsterm etc.  It's called wrterm, and is implemented in ca. 8.5 kloc
> of Rust.  I can't read Rust fluently, but I'd say It implements the
> usual functions for such a backend and not more.
> 
> So, I agree, that's not very interesting in this context.

Yes, looks like it renders everything to a <canvas> element. Which is 
not so interesting from the layout POV - I had in mind a translation 
with more different HTML elements, I guess.

Practically speaking, it is a good choice. I recall some development 
blog post either for Atom or for VS Code where they described a decision 
to move from HTML elements to rendering the code file contents on a 
canvas as well. GitHub's online text editor uses <textarea> now (so it's 
probably the same in VS Code), although how the syntax highlighting gets 
applied anyway I don't quite understand.

Anyway, the previous approach was functional as well, if slower with 
larger files. But Atom or VS Code don't support free-form layout or 
embedding images in the buffer text, I think. The "newmacs" could as 
well have both kinds of buffers (one for large files/performance, 
another for advanced layout features).

Even if <canvas> is used for buffers, it doesn't have to be used for 
"chrome" (menus, buttons, window delimiters, fringes, mode lines). Using 
HTML (for example) just for that could bring the ability to render stuff 
on top of it all, such as alerts, popups, etc.

Microsoft also has a project that could be tried as a base (MIT 
Licensed): https://github.com/microsoft/vscode-webview-ui-toolkit. Or 
one could just use its internals for inspiration, because "Visual Studio 
Code design language" is probably not one of our goals.

Re: Emacs design and architecture

[Emanuel Berg]

When we speak of parallelism, i.e. the use of multicore CPUs,
that is, true concurrency, are we talking Lisp parallelism for
constructs that are parallel in nature, e.g.

(let ((a execute-on-core-one)
      (b execute-on-core-two) )
  (+ a b) )

or are we talking parallelism in the sense to make Emacs as
a program make use of multicores? One could then think of
several arrangement, for example, do display on one core, user
input on the next, and so on?

The former, Lisp parallelism, would be amazingly cool, but
maybe the latter would bring more actual benefit since one
could, if modules were skillfully separated, do lots of
optimization for their specific purposes and needs.

Maybe one could do both since they are not, uhm,
mutually exclusive?

Microkernel Emacs with concurrent Lisp anyone?

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture

[Eli Zaretskii]

> From: Emanuel Berg <incal@dataswamp.org>
> Date: Sat, 16 Sep 2023 01:58:42 +0200
> 
> When we speak of parallelism, i.e. the use of multicore CPUs,
> that is, true concurrency, are we talking Lisp parallelism for
> constructs that are parallel in nature, e.g.
> 
> (let ((a execute-on-core-one)
>       (b execute-on-core-two) )
>   (+ a b) )
> 
> or are we talking parallelism in the sense to make Emacs as
> a program make use of multicores?

We are talking about both.  Except that true parallelism doesn't care
which core will do what job, but leaves that to the OS, asking only
that each job be done independently of the other. i.e. usually by
different cores.

> The former, Lisp parallelism, would be amazingly cool, but
> maybe the latter would bring more actual benefit since one
> could, if modules were skillfully separated, do lots of
> optimization for their specific purposes and needs.

If you know how to do one of them, you also know how to do the other,
because Emacs is a Lisp machine.

Re: Emacs design and architecture

[Emanuel Berg]

Eli Zaretskii wrote:

> If you know how to do one of them, you also know how to do
> the other, because Emacs is a Lisp machine.

How do other applications, that are multi-threaded, solve the
same obstacle, i.e. that of concurrent access to a big, shared
global state?

Because if the whole thing has to be locked for each thread to
access, it can be disputed if that is indeed any parallelism
at all. It will be multi-threaded and multi-core alright, but
not parallel execution unless one counts waiting for a shared
resource to become available as a sensible passivity.

So one would have to have a more fine-grained access to the
resource - by splitting it up in pieces. That way one thread
could access r_i while another accesses r_j and so on.

Don't know how such a division would look in practice tho?
Again it would be interesting to hear of how other
applications are doing it.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture

[Eli Zaretskii]

> From: Emanuel Berg <incal@dataswamp.org>
> Date: Sun, 17 Sep 2023 14:16:57 +0200
> 
> Eli Zaretskii wrote:
> 
> > If you know how to do one of them, you also know how to do
> > the other, because Emacs is a Lisp machine.
> 
> How do other applications, that are multi-threaded, solve the
> same obstacle, i.e. that of concurrent access to a big, shared
> global state?

Mult-threading and global state are two opposites: an application that
wants to be multi-threaded should have as small a global state as
possible, and where it cannot be avoided, use locking to access global
state from different threads.

> Because if the whole thing has to be locked for each thread to
> access, it can be disputed if that is indeed any parallelism
> at all. It will be multi-threaded and multi-core alright, but
> not parallel execution unless one counts waiting for a shared
> resource to become available as a sensible passivity.

That's what we have with Lisp threads now: while one thread runs, all
the others are stopped by a global lock.

> So one would have to have a more fine-grained access to the
> resource - by splitting it up in pieces. That way one thread
> could access r_i while another accesses r_j and so on.

This was discussed here earlier, and ion is that it's easier said than
done.

> Again it would be interesting to hear of how other
> applications are doing it.

There's a separate mutex for each global data structure.

Re: Emacs design and architecture. How about copy-on-write?

[Alan Mackenzie]

Hello, Eli.

On Sun, Sep 17, 2023 at 17:24:18 +0300, Eli Zaretskii wrote:
> > From: Emanuel Berg <incal@dataswamp.org>
> > Date: Sun, 17 Sep 2023 14:16:57 +0200

[ .... ]

> Mult-threading and global state are two opposites: an application that
> wants to be multi-threaded should have as small a global state as
> possible, and where it cannot be avoided, use locking to access global
> state from different threads.

> > Because if the whole thing has to be locked for each thread to
> > access, it can be disputed if that is indeed any parallelism
> > at all. It will be multi-threaded and multi-core alright, but
> > not parallel execution unless one counts waiting for a shared
> > resource to become available as a sensible passivity.

> That's what we have with Lisp threads now: while one thread runs, all
> the others are stopped by a global lock.

> > So one would have to have a more fine-grained access to the
> > resource - by splitting it up in pieces. That way one thread
> > could access r_i while another accesses r_j and so on.

> This was discussed here earlier, and ion is that it's easier said than
> done.

How about copy-on-write at a symbol
value-cell/function-cell/property-list level?

A value in a value-cell (etc.) would have an associated thread value, the
thread which "owns" it.  When thread1 gets cloned from thread0, it
continues to use thread0's data state until it writes foo (e.g. by
binding it).  This would create a new value/thread pair, foo/thread1.
Further writes of foo by thread1 would continue to access foo/thread1.

Possibly, we could use just one owning thread for all the cells of a
symbol.

When a thread terminates, all its owned variables would become garbage,
to be collected by our new garbage collector.  ;-)

Clearly, there would have to be some variables which would be
thread-global, i.e. there would be a single value cell shared by all
threads.  There would also doubltless be other complications.

The advantage of this approach, if it could be made to work, is that it
doesn't try to fight the massive global state which is Emacs Lisp,
instead accepting it and embracing it.

What do you think?

> > Again it would be interesting to hear of how other
> > applications are doing it.

> There's a separate mutex for each global data structure.

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Sun, 17 Sep 2023 15:36:11 +0000
> Cc: Emanuel Berg <incal@dataswamp.org>, emacs-devel@gnu.org
> From: Alan Mackenzie <acm@muc.de>
> 
> How about copy-on-write at a symbol
> value-cell/function-cell/property-list level?
> 
> A value in a value-cell (etc.) would have an associated thread value, the
> thread which "owns" it.  When thread1 gets cloned from thread0, it
> continues to use thread0's data state until it writes foo (e.g. by
> binding it).  This would create a new value/thread pair, foo/thread1.
> Further writes of foo by thread1 would continue to access foo/thread1.
> 
> Possibly, we could use just one owning thread for all the cells of a
> symbol.
> 
> When a thread terminates, all its owned variables would become garbage,
> to be collected by our new garbage collector.  ;-)

You assume that whatever the thread does can be discarded as garbage?
That's definitely not true in general: most things we do in Emacs
should leave some trace behind.  It is not clear when and how this
would happen under your proposal.  E.g., imagine that a thread runs
Gnus fetching articles, and try to describe how this will work.

> Clearly, there would have to be some variables which would be
> thread-global, i.e. there would be a single value cell shared by all
> threads.  There would also doubltless be other complications.

"Some variables"?  Our problem is that their name is a legion.  E.g.,
what do you propose to do with variables and changes to buffer text
that affect the display?  Or are you suggesting to have a separate
redisplay for each thread?  Or maybe you propose that each window has
its own thread, complete with its own display (and a separate thread
for each frame)?

These aspects need to be figured out if we want to discuss something
like this seriously.

> The advantage of this approach, if it could be made to work, is that it
> doesn't try to fight the massive global state which is Emacs Lisp,
> instead accepting it and embracing it.

I don't think you can avoid "fighting" it.  It's the elephant in the
room, and there's no way around that, because that global is the
backbone of the Emacs design, and all the Lisp programs and other
features implicitly assume it.

Re: Emacs design and architecture. How about copy-on-write?

[Alan Mackenzie]

Hello, Eli.

On Mon, Sep 18, 2023 at 13:30:15 +0300, Eli Zaretskii wrote:
> > Date: Sun, 17 Sep 2023 15:36:11 +0000
> > Cc: Emanuel Berg <incal@dataswamp.org>, emacs-devel@gnu.org
> > From: Alan Mackenzie <acm@muc.de>

> > How about copy-on-write at a symbol
> > value-cell/function-cell/property-list level?

> > A value in a value-cell (etc.) would have an associated thread value, the
> > thread which "owns" it.  When thread1 gets cloned from thread0, it
> > continues to use thread0's data state until it writes foo (e.g. by
> > binding it).  This would create a new value/thread pair, foo/thread1.
> > Further writes of foo by thread1 would continue to access foo/thread1.

> > Possibly, we could use just one owning thread for all the cells of a
> > symbol.

> > When a thread terminates, all its owned variables would become garbage,
> > to be collected by our new garbage collector.  ;-)

> You assume that whatever the thread does can be discarded as garbage?
> That's definitely not true in general: most things we do in Emacs
> should leave some trace behind.  It is not clear when and how this
> would happen under your proposal.  E.g., imagine that a thread runs
> Gnus fetching articles, and try to describe how this will work.

You mean that at the end of a thread, it will need to write results back
to variables "owned" by the calling thread.  Yes.  Either these variables
get marked as thread-global (not very attractive), or else we would need
to mark specific variables as not to be copied on write.

With a thread fetching Gnus articles, there is the additional
complication of having several such threads fetching from several servers
at once.  Then access to the result variables would need to be locked, to
prevent two threads overwriting eachother's results.  But this is so in
any multithreading system, no matter how it's done.

> > Clearly, there would have to be some variables which would be
> > thread-global, i.e. there would be a single value cell shared by all
> > threads.  There would also doubltless be other complications.

> "Some variables"?  Our problem is that their name is a legion.  E.g.,
> what do you propose to do with variables and changes to buffer text
> that affect the display?

I envisage each buffer being "owned" by a thread, possibly a special
thread just controlling access to the buffer.  Variables like
scroll-margin would be the thread's own binding of it.  There are a large
number of dynamic variables in redisplay which, in the current Emacs,
when bound by a thread would affect Emacs globally.  This c-o-w proposal
would fix this problem.

> Or are you suggesting to have a separate redisplay for each thread?  Or
> maybe you propose that each window has its own thread, complete with
> its own display (and a separate thread for each frame)?

I don't think several redisplay threads would be a good idea - usually,
there is just one screen Emacs is drawing on.  If we get down into
details, it might be worth having separate threads for each frame, or
even each window.

> These aspects need to be figured out if we want to discuss something
> like this seriously.

I'd like to emphasise that this copy-on-write idea is still just a vague
idea which might help, not a worked out firm proposal.

> > The advantage of this approach, if it could be made to work, is that it
> > doesn't try to fight the massive global state which is Emacs Lisp,
> > instead accepting it and embracing it.

> I don't think you can avoid "fighting" it.  It's the elephant in the
> room, and there's no way around that, because that global is the
> backbone of the Emacs design, and all the Lisp programs and other
> features implicitly assume it.

The c-o-w idea could steer around at least part of the globality.  I
think it would be relatively simple to implement (hah!) and wouldn't have
a large run-time cost, though of course there would be some.

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Mon, 18 Sep 2023 11:38:56 +0000
> Cc: incal@dataswamp.org, emacs-devel@gnu.org
> From: Alan Mackenzie <acm@muc.de>
> 
> > > When a thread terminates, all its owned variables would become garbage,
> > > to be collected by our new garbage collector.  ;-)
> 
> > You assume that whatever the thread does can be discarded as garbage?
> > That's definitely not true in general: most things we do in Emacs
> > should leave some trace behind.  It is not clear when and how this
> > would happen under your proposal.  E.g., imagine that a thread runs
> > Gnus fetching articles, and try to describe how this will work.
> 
> You mean that at the end of a thread, it will need to write results back
> to variables "owned" by the calling thread.  Yes.  Either these variables
> get marked as thread-global (not very attractive), or else we would need
> to mark specific variables as not to be copied on write.

After the thread terminates, and perhaps also while it still runs.
E.g., consider some kind of progress-reporting facility.

> With a thread fetching Gnus articles, there is the additional
> complication of having several such threads fetching from several servers
> at once.  Then access to the result variables would need to be locked, to
> prevent two threads overwriting eachother's results.  But this is so in
> any multithreading system, no matter how it's done.

The danger is indeed that most of the variables will need to be
protected by locks.  If we cannot find a way of avoiding that, we are
back at the current "only one thread at a time" model, and there's
nothing to gain.

> > > Clearly, there would have to be some variables which would be
> > > thread-global, i.e. there would be a single value cell shared by all
> > > threads.  There would also doubltless be other complications.
> 
> > "Some variables"?  Our problem is that their name is a legion.  E.g.,
> > what do you propose to do with variables and changes to buffer text
> > that affect the display?
> 
> I envisage each buffer being "owned" by a thread, possibly a special
> thread just controlling access to the buffer.  Variables like
> scroll-margin would be the thread's own binding of it.  There are a large
> number of dynamic variables in redisplay which, in the current Emacs,
> when bound by a thread would affect Emacs globally.  This c-o-w proposal
> would fix this problem.

I'm confused: suppose one thread modifies scroll-margin -- does that
affect the (global) redisplay?  If it does, how will this "solve" the
problem?  If it doesn't affect redisplay, how _can_ a thread change
scroll-margin in order to affect redisplay?

> > Or are you suggesting to have a separate redisplay for each thread?  Or
> > maybe you propose that each window has its own thread, complete with
> > its own display (and a separate thread for each frame)?
> 
> I don't think several redisplay threads would be a good idea - usually,
> there is just one screen Emacs is drawing on.

It's one screen, but each window is redrawn separately (on GUI
terminals).

> If we get down into details, it might be worth having separate
> threads for each frame, or even each window.

I think this aspect of multithreading is so crucial that it must be
considered from the get-go.  Redisplay is one of the few places in
Emacs where the assumption of global state is entrenched as deep as
possible, so without some new ideas it will basically preclude
multithreading.

> > I don't think you can avoid "fighting" it.  It's the elephant in the
> > room, and there's no way around that, because that global is the
> > backbone of the Emacs design, and all the Lisp programs and other
> > features implicitly assume it.
> 
> The c-o-w idea could steer around at least part of the globality.  I
> think it would be relatively simple to implement (hah!) and wouldn't have
> a large run-time cost, though of course there would be some.

I think the copy-on-write idea will work only for thread-local
variables, and we already have those in the form of let-bindings.  The
important (and the hard) part of this is elsewhere.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> You mean that at the end of a thread, it will need to write results back
>> to variables "owned" by the calling thread.  Yes.  Either these variables
>> get marked as thread-global (not very attractive), or else we would need
>> to mark specific variables as not to be copied on write.
>
> After the thread terminates, and perhaps also while it still runs.
> E.g., consider some kind of progress-reporting facility.

I think this can be approached similar to buffer-local values - all the
symbols will have default value (global), and per-thread values. When
threads set symbol value normally (for example, via setq), the
per-thread value is modified (and possibly written back to "global"
after the thread terminates). But thread might need to write "global"
directly - something similar to `set-default-toplevel-value' might be
used then.

>> With a thread fetching Gnus articles, there is the additional
>> complication of having several such threads fetching from several servers
>> at once.  Then access to the result variables would need to be locked, to
>> prevent two threads overwriting eachother's results.  But this is so in
>> any multithreading system, no matter how it's done.
>
> The danger is indeed that most of the variables will need to be
> protected by locks.  If we cannot find a way of avoiding that, we are
> back at the current "only one thread at a time" model, and there's
> nothing to gain.

I think that there is a limit to what can be done generically without
affecting the existing Elisp code. Modifying a global variable
asynchronously might need to be coded explicitly on Elisp level by more
granular locks (to be provided as a part of async thread API).

For example, if Gnus is collecting all the articles into a list of
(("server1" . articles) ("server2" . articles)), only Gnus will know
that it is enough to lock cdr of "server1" when fetching articles from
server 1.

In other scenarios, like modifying hash table, it might be possible to
provide thread-safe implementations on C level. Those might or might not
be good enough, depending on the use-case.

>> I envisage each buffer being "owned" by a thread, possibly a special
>> thread just controlling access to the buffer.  Variables like
>> scroll-margin would be the thread's own binding of it.  There are a large
>> number of dynamic variables in redisplay which, in the current Emacs,
>> when bound by a thread would affect Emacs globally.  This c-o-w proposal
>> would fix this problem.
>
> I'm confused: suppose one thread modifies scroll-margin -- does that
> affect the (global) redisplay?  If it does, how will this "solve" the
> problem?  If it doesn't affect redisplay, how _can_ a thread change
> scroll-margin in order to affect redisplay?

IMHO, the only sane way to utilize the existing redisplay is redisplay
lock - only one thread can request redisplay at a time, using its
thread-local state.

>> I don't think several redisplay threads would be a good idea - usually,
>> there is just one screen Emacs is drawing on.
>
> It's one screen, but each window is redrawn separately (on GUI
> terminals).

Technically yes, but AFAIU the code is written assuming single-threaded
execution. Decoupling redisplay of different windows would require
significant non-trivial changes in xdisp.c

>> The c-o-w idea could steer around at least part of the globality.  I
>> think it would be relatively simple to implement (hah!) and wouldn't have
>> a large run-time cost, though of course there would be some.
>
> I think the copy-on-write idea will work only for thread-local
> variables, and we already have those in the form of let-bindings.  The
> important (and the hard) part of this is elsewhere.

Yup. For example, buffer-local symbols are implemented using forward
pointers, overriding buffer object any time we alter (like let-bind) a
buffer-local value.

From implementation perspective, it might be easier to extend symbol
value slots of symbol object and buffer-local variable slots of buffer
objects to store values for multiple threads + a default value.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Alan Mackenzie <acm@muc.de>, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Mon, 18 Sep 2023 12:49:21 +0000
> 
> > I'm confused: suppose one thread modifies scroll-margin -- does that
> > affect the (global) redisplay?  If it does, how will this "solve" the
> > problem?  If it doesn't affect redisplay, how _can_ a thread change
> > scroll-margin in order to affect redisplay?
> 
> IMHO, the only sane way to utilize the existing redisplay is redisplay
> lock - only one thread can request redisplay at a time, using its
> thread-local state.

So if one thread changes scroll-margin and triggers redisplay, then
another thread triggers redisplay with its (different value of
scroll-margin), the display will scroll or move point back? and then
forward again? and then back again?

> >> I don't think several redisplay threads would be a good idea - usually,
> >> there is just one screen Emacs is drawing on.
> >
> > It's one screen, but each window is redrawn separately (on GUI
> > terminals).
> 
> Technically yes, but AFAIU the code is written assuming single-threaded
> execution.

In what way does it assume single-threaded execution?  We walk the
window tree of a frame and redisplay each leaf window in the tree,
that's all.  Maybe I don't understand what you mean by "assuming
single-threaded execution".

> Decoupling redisplay of different windows would require significant
> non-trivial changes in xdisp.c

In which part(s) of xdisp.c?  Most of xdisp.c handles redisplay of a
single window.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> IMHO, the only sane way to utilize the existing redisplay is redisplay
>> lock - only one thread can request redisplay at a time, using its
>> thread-local state.
>
> So if one thread changes scroll-margin and triggers redisplay, then
> another thread triggers redisplay with its (different value of
> scroll-margin), the display will scroll or move point back? and then
> forward again? and then back again?

Nope. I consider that redisplay is always synchronous (because of global
redisplay lock). If multiple threads trigger redisplay with different
scroll-margin values, it will be not different compared to the following
example:

(let ((scroll-margin 500)) (redisplay))
<...>
(redisplay)
<...>
(let ((scroll-margin 10)) (redisplay))
<...>

A better illustration is probably

(progn
  (let ((bidi-paragraph-direction 'right-to-left)) (redisplay))
  (sleep-for 1)
  (redisplay)
  (sleep-for 1)
  (let ((bidi-paragraph-direction 'right-to-left)) (redisplay))
  (sleep-for 1))

>> >> I don't think several redisplay threads would be a good idea - usually,
>> >> there is just one screen Emacs is drawing on.
>> >
>> > It's one screen, but each window is redrawn separately (on GUI
>> > terminals).
>> 
>> Technically yes, but AFAIU the code is written assuming single-threaded
>> execution.
>
> In what way does it assume single-threaded execution?  We walk the
> window tree of a frame and redisplay each leaf window in the tree,
> that's all.  Maybe I don't understand what you mean by "assuming
> single-threaded execution".

1. xdisp assumes at its core logic that current_buffer is always a
   single buffer. And it affects, for example mode-line faces.

2. `display_mode_line' uses global temporary override by calling
   `push_kboard'. AFAIU, it is also relying on single-threaded code.

3. xdisp is relying on a number of global-only variables like
   `mode-line-compact', `show-trailing-whitespace', and similar.
   AFAIR, things like `show-trailing-whitespace' affect how the
   optimizations are applied when deciding which windows should be
   redisplayed and which should not. I suspect that logic related to
   optimizations may be very fragile with async execution.

4. There are complex interactions between window redisplay, mode lines,
   echo area, and toolbars. AFAIR, if some Elisp (or maybe C) code,
   recursively called during window redisplay, affects mode-line/toolbar
   height, xdisp restarts (sometimes, partially) the redisplay process.
   I expect issues when this interacts with async redisplay of
   individual windows.

>> Decoupling redisplay of different windows would require significant
>> non-trivial changes in xdisp.c
>
> In which part(s) of xdisp.c?  Most of xdisp.c handles redisplay of a
> single window.

Yup, but see (4). I recall seeing a number of non-trivial `goto' calls
where faces or window geometry are checked for changes and redisplay has
to redo redisplay according to the changed values. When such geometry
changes can also happen asynchronously, a number of places in the code
that assumed fixed geometry and glyph matrix may be broken.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Mon, 18 Sep 2023 15:55:26 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> IMHO, the only sane way to utilize the existing redisplay is redisplay
> >> lock - only one thread can request redisplay at a time, using its
> >> thread-local state.
> >
> > So if one thread changes scroll-margin and triggers redisplay, then
> > another thread triggers redisplay with its (different value of
> > scroll-margin), the display will scroll or move point back? and then
> > forward again? and then back again?
> 
> Nope. I consider that redisplay is always synchronous

Synchronous to what?

> (because of global redisplay lock)

What is the global redisplay lock?

> If multiple threads trigger redisplay with different scroll-margin
> values, it will be not different compared to the following example:

I understand the problem, I'm asking what could or should be the
possible solutions.

> > In what way does it assume single-threaded execution?  We walk the
> > window tree of a frame and redisplay each leaf window in the tree,
> > that's all.  Maybe I don't understand what you mean by "assuming
> > single-threaded execution".
> 
> 1. xdisp assumes at its core logic that current_buffer is always a
>    single buffer. And it affects, for example mode-line faces.

No, it just assumes that when working on a window, its buffer is
temporarily made the current buffer.  But since we already made the
current buffer per-thread, this is not a problem.  From thread.h:

    /* This points to the current buffer.  */
    struct buffer *m_current_buffer;
  #define current_buffer (current_thread->m_current_buffer)

> 2. `display_mode_line' uses global temporary override by calling
>    `push_kboard'. AFAIU, it is also relying on single-threaded code.

This is a non-issue.  If we don't allow non-main threads interact with
the user, we can leave this code intact.  If we do allow interaction
from non-main threads, we just need to bind kboard-local variables to
their thread-specific values when we switch to the thread.

> 3. xdisp is relying on a number of global-only variables like
>    `mode-line-compact', `show-trailing-whitespace', and similar.
>    AFAIR, things like `show-trailing-whitespace' affect how the
>    optimizations are applied when deciding which windows should be
>    redisplayed and which should not. I suspect that logic related to
>    optimizations may be very fragile with async execution.

That's completely irrelevant to the issue at hand.  The fact that
Emacs has a huge global state, and all of its code relies on that is a
separate issue.  Here, I asked you in what sense is xdisp.c's code
single-threaded; if your answer is "because of its reliance on global
state", it means there's no separate problem of xdisp.c that is based
on single thread.

And those of these global variables that aren't changing while some
thread is redisplaying a window showing a particular buffer don't even
interfere with parallel redisplay.

As for redisplay optimizations, they are entirely based on buffer- and
window-local information, so I cannot imagine why you think they will
be very fragile.

> 4. There are complex interactions between window redisplay, mode lines,
>    echo area, and toolbars. AFAIR, if some Elisp (or maybe C) code,
>    recursively called during window redisplay, affects mode-line/toolbar
>    height, xdisp restarts (sometimes, partially) the redisplay process.
>    I expect issues when this interacts with async redisplay of
>    individual windows.

Why do you expect that?

> >> Decoupling redisplay of different windows would require significant
> >> non-trivial changes in xdisp.c
> >
> > In which part(s) of xdisp.c?  Most of xdisp.c handles redisplay of a
> > single window.
> 
> Yup, but see (4). I recall seeing a number of non-trivial `goto' calls
> where faces or window geometry are checked for changes and redisplay has
> to redo redisplay according to the changed values. When such geometry
> changes can also happen asynchronously, a number of places in the code
> that assumed fixed geometry and glyph matrix may be broken.

No, it just means any such changes need to be communicated to other
"redisplaying" threads, so that they also restart.

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Eli Zaretskii wrote:

> it just means any such changes need to be communicated to
> other "redisplaying" threads, so that they also restart

Instead of focusing on specific cases that one can imagine to
be problematic, why not look for a general policy what
should happen in the first place?

So, what does it mean for a thread to lock a global variable?
and set it? and use it? and then unlock it?

What does it mean to that thread for the duration of its
execution? And what does it mean to another thread that is, or
isn't, doing or wanting to do the same thing,
possibly simultaneously?

After that, one can think of how to setup a mechanism that
will safely uphold the model.

So first thing, define what a thread T can do to a global
variable V.

Second thing, what do we want to happen, when another
thread K does the same things in parallel, also to V?

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Emanuel Berg <incal@dataswamp.org>
> Date: Tue, 19 Sep 2023 00:48:15 +0200
> 
> Eli Zaretskii wrote:
> 
> > it just means any such changes need to be communicated to
> > other "redisplaying" threads, so that they also restart
> 
> Instead of focusing on specific cases that one can imagine to
> be problematic, why not look for a general policy what
> should happen in the first place?

The general policy is a solved problem, so there's no reason to
consider it.

> So, what does it mean for a thread to lock a global variable?
> and set it? and use it? and then unlock it?
> 
> What does it mean to that thread for the duration of its
> execution? And what does it mean to another thread that is, or
> isn't, doing or wanting to do the same thing,
> possibly simultaneously?
> 
> After that, one can think of how to setup a mechanism that
> will safely uphold the model.
> 
> So first thing, define what a thread T can do to a global
> variable V.
> 
> Second thing, what do we want to happen, when another
> thread K does the same things in parallel, also to V?

We don't need to discuss all this because solutions for thread
synchronization exist for a long time.  We even use quite a few of
them already: the Lisp threads we have in Emacs now provide some of
these synchronization primitives, which are built on top of existing
capabilities built into the OS and existing thread libraries.

So the problem is not how to lock and serialize access to a variable
in general, the problem is how to do this in Emacs so that we won't
need to lock everything.

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Eli Zaretskii wrote:

> We don't need to discuss all this because solutions for
> thread synchronization exist for a long time. We even use
> quite a few of them already: the Lisp threads we have in
> Emacs now provide some of these synchronization primitives,
> which are built on top of existing capabilities built into
> the OS and existing thread libraries.
>
> So the problem is not how to lock and serialize access to
> a variable in general, the problem is how to do this in
> Emacs so that we won't need to lock everything.

Okay, excellent, but then why isn't it enough to just maintain
a register of global variables and threads?

If a thread wants to use it, look in the register, is it
available? If not, get in line. And when it becomes available,
pop a thread in the line, if there is one, and start over?

Why do we have to lock everything just because we lock
a single variable?

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Emanuel Berg <incal@dataswamp.org> writes:

>> So the problem is not how to lock and serialize access to
>> a variable in general, the problem is how to do this in
>> Emacs so that we won't need to lock everything.
>
> Okay, excellent, but then why isn't it enough to just maintain
> a register of global variables and threads?

> If a thread wants to use it, look in the register, is it
> available? If not, get in line. And when it becomes available,
> pop a thread in the line, if there is one, and start over?
>
> Why do we have to lock everything just because we lock
> a single variable?

Because implementation details are tricky - a lot of Elisp internal
machinery is relying upon modifying global symbol objects, having
certain global C variables assigned to the "right" value, and buffer
objects having the right buffer-local values.
This particular issue has been discussed in details in
https://yhetil.org/emacs-devel/871qhnr4ty.fsf@localhost/

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Ihor Radchenko wrote:

> Because implementation details are tricky - a lot of Elisp
> internal machinery is relying upon modifying global symbol
> objects, having certain global C variables assigned to the
> "right" value, and buffer objects having the right
> buffer-local values. This particular issue has been
> discussed in details in
> https://yhetil.org/emacs-devel/871qhnr4ty.fsf@localhost/

Yeah, but instead of adopting the lock mechanism to take into
account a possibly huge amount of such cases the lock
mechanism should be solid and work the same way for everyone
and everything.

If that breaks code that relies on the previous solution, that
will have to be fixed.

Because if the lock mechanism has to take into account tons of
weird cases and situations written for another solution, it
won't be good. And new code - what solution should it be
written for? The old or the new solution? Or the new
solution's exceptions not to break legacy code?

Oh, no. 2 wrongs don't make 1 right. Solid foundation
bottom-up approach, things incompatible with the sound
solution? No exceptions added to the sound solution, instead
fix them one at a time.

No shortcuts to the top!

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Emanuel Berg <incal@dataswamp.org> writes:

>> https://yhetil.org/emacs-devel/871qhnr4ty.fsf@localhost/
>
> Yeah, but instead of adopting the lock mechanism to take into
> account a possibly huge amount of such cases the lock
> mechanism should be solid and work the same way for everyone
> and everything.
> ...

Sorry, but I am completely lost. Cannot understand what you are trying
to propose.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Ihor Radchenko wrote:

>>> https://yhetil.org/emacs-devel/871qhnr4ty.fsf@localhost/
>>
>> Yeah, but instead of adopting the lock mechanism to take
>> into account a possibly huge amount of such cases the lock
>> mechanism should be solid and work the same way for
>> everyone and everything. [...]
>
> Sorry, but I am completely lost. Cannot understand what you
> are trying to propose.

We can't build a new solution filled with exceptions so it
won't break existing programs that were programmed for
another solution.

Instead we have to focus on the new solution and old programs
that break will have to be adopted to the new solution - or
discarded even, sometimes.

So one should create a minimal scenario that still includes
everything that can happen, and the worst case at that. If our
solution can solve that, then that's it.

So what is the base case? A global variable with two threads
that read, and two that write? And what is the worst case of
that base case? All of that happening at once?

When this "worst-case base case" is identified and solved in
a good way, whatever existing code that now breaks will have
to be modified.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Emanuel Berg <incal@dataswamp.org> writes:

>> Sorry, but I am completely lost. Cannot understand what you
>> are trying to propose.
>
> We can't build a new solution filled with exceptions so it
> won't break existing programs that were programmed for
> another solution.

Eli's point is that the new concurrency framework must allow the
existing code to run without modifying it to fit concurrency. Not
necessarily fast (maybe with some interlocking), but at least without
breaking.

Otherwise, making actual use of concurrency will require rewriting a lot
of Elisp, in addition to C-level support, which is too much effort - we
will have to fight many non-obvious problems any time we want to call an
"old" Elisp function from purposely-written async thread.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Ihor Radchenko wrote:

>>> Sorry, but I am completely lost. Cannot understand what
>>> you are trying to propose.
>>
>> We can't build a new solution filled with exceptions so it
>> won't break existing programs that were programmed for
>> another solution.
>
> Eli's point is that the new concurrency framework must allow
> the existing code to run without modifying it to fit
> concurrency. Not necessarily fast (maybe with some
> interlocking), but at least without breaking.
>
> Otherwise, making actual use of concurrency will require
> rewriting a lot of Elisp, in addition to C-level support,
> which is too much effort - we will have to fight many
> non-obvious problems any time we want to call an "old" Elisp
> function from purposely-written async thread.

Multi-threaded concurrent access to global variables that will
not break programs that were written using global variables
with the then correct assumption no one else would touch them?

But it is still possible, just the meaning of `setq', `let'
etc will have to be changed so that they now are referred to
the lock mechanism and also actually create local variables
transparently which are subsequently used.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: emacs-devel@gnu.org
> Date: Fri, 22 Sep 2023 19:15:27 +0300
> 
> Eli's point is that the new concurrency framework must allow the
> existing code to run without modifying it to fit concurrency. Not
> necessarily fast (maybe with some interlocking), but at least without
> breaking.
> 
> Otherwise, making actual use of concurrency will require rewriting a lot
> of Elisp

Starting from subr.el, simple.el, files.el, etc. -- stuff which every
Lisp program written for Emacs uses without thinking twice.

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Ihor Radchenko wrote:

> Because implementation details are tricky - a lot of Elisp
> internal machinery is relying upon modifying global symbol
> objects [...]

Yeah, but that should be fine, as long as they are locked and
unlocked safely, right?

But, if one aspire to reduce the number of global variables
used, a great way of doing that is lexical `let'-closures,
here is an example that allows for the same default value when
the function is called from Lisp and when used as an
interactive command, yet the data is only hardcoded once for
each variable.

With this method - and not just for that use case, also the
use case of 2 functions sharing a variable - one can reduce
global Lisp variable use a lot - I know since I've done that
do my own code, and it works great ever since.

;;; -*- lexical-binding: t -*-
;;
;; this file:
;;   https://dataswamp.org/~incal/emacs-init/math.el

(require 'cl-lib)

;; [...]

(let ((min-def 0)
      (max-def 9)
      (inc-def 1) )
  (cl-defun interval (&optional (min min-def)
                                (max max-def)
                                (inc inc-def) )
    (interactive `(,(read-number "min: " min-def)
                   ,(read-number "max: " max-def)
                   ,(read-number "inc: " inc-def)) )
    (unless (<= min max)
      (error "Bogus interval") )
    (unless (> inc 0)
      (error "Bogus increment") )
    (cl-loop
      for i from min to max by inc
      collect i) )
  (declare-function interval nil) )

;; (interval 10 5)        ; Bogus interval
;; (interval 1 3 -1)      ; Bogus increment
;; (interval 5 10)        ; (5 6 7 8 9 10)
;; (interval 1.8 2.0 0.1) ; (1.8 1.9 2.0)
;; (interval)             ; (0 1 2 3 4 5 6 7 8 9)
;; (interval 19 99)       ; (19 20 21 ... 97 98 99)

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Emanuel Berg <incal@dataswamp.org> writes:

> Ihor Radchenko wrote:
>
>> Because implementation details are tricky - a lot of Elisp
>> internal machinery is relying upon modifying global symbol
>> objects [...]
>
> Yeah, but that should be fine, as long as they are locked and
> unlocked safely, right?

No.

If we have something like (let ((case-fold-search t)) ...), we will lock
`case-fold-search' symbol for the whole duration of `let' call and block
any other threads trying to alter `case-fold-search' locally.

> But, if one aspire to reduce the number of global variables
> used, a great way of doing that is lexical `let'-closures,
> here is an example that allows for the same default value when
> the function is called from Lisp and when used as an
> interactive command, yet the data is only hardcoded once for
> each variable.

Not every variable can be used within lexical scope. In particular
special variables (see 12.10.4 Using Lexical Binding and
`special-variable-p') are always treated outside lexical binding.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Ihor Radchenko <yantar92@posteo.net> writes:

> Emanuel Berg <incal@dataswamp.org> writes:
>
>> Ihor Radchenko wrote:
>>
>>> Because implementation details are tricky - a lot of Elisp
>>> internal machinery is relying upon modifying global symbol
>>> objects [...]
>>
>> Yeah, but that should be fine, as long as they are locked and
>> unlocked safely, right?
>
> No.
>
> If we have something like (let ((case-fold-search t)) ...), we will lock
> `case-fold-search' symbol for the whole duration of `let' call and block
> any other threads trying to alter `case-fold-search' locally.

Emacs does not store the default value of each symbol in the variables
which they forward to.  All DEFVARs are thread local in this sense, for
each thread must be capable of simultaneously binding different values
to the same variable.

In my implementation, struct thread_state incorporates pointers to all
forwarded variables, each of which either points within thread_state
itself when its symbol is bound locally, or to `globals' otherwise.

Vcharset_map_path thus becomes:

#define Vcharset_map_path (*current_thread->f_Vcharset_map_path)

That being said, case-fold-search is a bad example.  I have not yet
established how buffer local variables will be efficiently represented
when multiple threads selecting the same buffer bind the same variables
simultaneously.  Once that hurdle is surmounted and the regex engine
itself is rendered thread-safe, threads will be capable of calling
regexp matching functions concurrently, with only their local bindings
of case_fold_search taking effect.  No symbol-based locking necessary.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Po Lu <luangruo@yahoo.com> writes:

>> If we have something like (let ((case-fold-search t)) ...), we will lock
>> `case-fold-search' symbol for the whole duration of `let' call and block
>> any other threads trying to alter `case-fold-search' locally.
>
> ... for
> each thread must be capable of simultaneously binding different values
> to the same variable.

Sure. I did not object this. What I mean is that some symbol values are
tricky. In particular symbols with values being forwarded.

> In my implementation, struct thread_state incorporates pointers to all
> forwarded variables, each of which either points within thread_state
> itself when its symbol is bound locally, or to `globals' otherwise.

> Vcharset_map_path thus becomes:
>
> #define Vcharset_map_path (*current_thread->f_Vcharset_map_path)

Does it mean that each threads contains a copy of the whole `globals'? I
think I proposed this in the linked thread and it was objected as
something taking a lot of memory.

IMHO, copy-of-write would be better here - only store the thread-local
values that are actually altered by the thread.
Indeed, a simple #define will not be enough then, but we would not waste
memory copying the values that will never be changed anyway.

> That being said, case-fold-search is a bad example.

Which is why I used it :) It is innocent yet tricky.

> ... I have not yet
> established how buffer local variables will be efficiently represented
> when multiple threads selecting the same buffer bind the same variables
> simultaneously.

We discussed asynchronous access to buffers earlier and concluded that
modifying a buffer (and its buffer-local values) asynchronously is a
hard problem. In particular, handling gap asynchronously is simply not
possible. It might be more practical to allow simultaneous read-only
access to the same buffer, but interlock writes to buffer object
(including moving gap, changing buffer text, and changing buffer-local
values).

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Ihor Radchenko <yantar92@posteo.net> writes:

> Does it mean that each threads contains a copy of the whole `globals'? I
> think I proposed this in the linked thread and it was objected as
> something taking a lot of memory.

It incorporates one pointer for each field within globals itself.  AFAIU
that was the initial impetus for introducing struct emacs_globals in the
first place.

> IMHO, copy-of-write would be better here - only store the thread-local
> values that are actually altered by the thread.

Of course only specbound values will be saved within each thread's
state, but each thread must maintain a pointer to the field that is
actually holding the value of the forwarded variables.

> Indeed, a simple #define will not be enough then, but we would not waste
> memory copying the values that will never be changed anyway.

On my machine, struct emacs_globals is 7490 bytes, just short of 7 KiB.
struct thread_state amounts to 12704 bytes, which does not come across
as excessive in this day and age.  Thread-local storage is then
dynamically allocated as bindings materialize.

> We discussed asynchronous access to buffers earlier and concluded that
> modifying a buffer (and its buffer-local values) asynchronously is a
> hard problem. In particular, handling gap asynchronously is simply not
> possible. It might be more practical to allow simultaneous read-only
> access to the same buffer, but interlock writes to buffer object
> (including moving gap, changing buffer text, and changing buffer-local
> values).

The gap and point are not buffer local values.  I'm referring to
variables saved within local_var_alist, which must be modified to
incorporate bindings for each thread.

The problem lies in how to perform this efficiently.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Po Lu <luangruo@yahoo.com> writes:

>> Indeed, a simple #define will not be enough then, but we would not waste
>> memory copying the values that will never be changed anyway.
>
> On my machine, struct emacs_globals is 7490 bytes, just short of 7 KiB.
> struct thread_state amounts to 12704 bytes, which does not come across
> as excessive in this day and age.  Thread-local storage is then
> dynamically allocated as bindings materialize.

Sounds reasonable then. 7k does not look like a big deal to me.

>> We discussed asynchronous access to buffers earlier and concluded that
>> modifying a buffer (and its buffer-local values) asynchronously is a
>> hard problem. In particular, handling gap asynchronously is simply not
>> possible. It might be more practical to allow simultaneous read-only
>> access to the same buffer, but interlock writes to buffer object
>> (including moving gap, changing buffer text, and changing buffer-local
>> values).
>
> The gap and point are not buffer local values.  I'm referring to
> variables saved within local_var_alist, which must be modified to
> incorporate bindings for each thread.

As an aside: point should also be thread-local to make common Elisp code
work (like re-search-forward, for example).

> The problem lies in how to perform this efficiently.

The whole process of working with Lisp_Buffer_Local_Value is a bit
arcane with all its juggling of the values (`do_symval_forwarding',
`swap_in_symval_forwarding', etc) every time current_buffer changes.

I am wondering if you solved (seemingly) simpler cases with setting
Lisp_Fwd_Obj, Lisp_Fwd_Int, and Lisp_Fwd_Bool.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Ihor Radchenko <yantar92@posteo.net> writes:

> I am wondering if you solved (seemingly) simpler cases with setting
> Lisp_Fwd_Obj, Lisp_Fwd_Int, and Lisp_Fwd_Bool.

They forward to thread local values.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Po Lu <luangruo@yahoo.com> writes:

> Ihor Radchenko <yantar92@posteo.net> writes:
>
>> I am wondering if you solved (seemingly) simpler cases with setting
>> Lisp_Fwd_Obj, Lisp_Fwd_Int, and Lisp_Fwd_Bool.
>
> They forward to thread local values.

I see. Then, one way to approach buffer-local variables could be storing
an association of (buffer . thread-local-buffer-variables) under the
thread object and forward there.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Po Lu <luangruo@yahoo.com> writes:

> Ihor Radchenko <yantar92@posteo.net> writes:
>
>> Does it mean that each threads contains a copy of the whole `globals'? I
>> think I proposed this in the linked thread and it was objected as
>> something taking a lot of memory.
>
> It incorporates one pointer for each field within globals itself.  AFAIU
> that was the initial impetus for introducing struct emacs_globals in the
> first place.
>
>> IMHO, copy-of-write would be better here - only store the thread-local
>> values that are actually altered by the thread.
>
> Of course only specbound values will be saved within each thread's
> state, but each thread must maintain a pointer to the field that is
> actually holding the value of the forwarded variables.
>
>> Indeed, a simple #define will not be enough then, but we would not waste
>> memory copying the values that will never be changed anyway.
>
> On my machine, struct emacs_globals is 7490 bytes, just short of 7 KiB.

Correction: just over 7 KiB.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: Emanuel Berg <incal@dataswamp.org>,  emacs-devel@gnu.org
> Date: Wed, 20 Sep 2023 21:35:49 +0800
> 
> Po Lu <luangruo@yahoo.com> writes:
> 
> > Ihor Radchenko <yantar92@posteo.net> writes:
> >
> >> Does it mean that each threads contains a copy of the whole `globals'? I
> >> think I proposed this in the linked thread and it was objected as
> >> something taking a lot of memory.
> >
> > It incorporates one pointer for each field within globals itself.  AFAIU
> > that was the initial impetus for introducing struct emacs_globals in the
> > first place.
> >
> >> IMHO, copy-of-write would be better here - only store the thread-local
> >> values that are actually altered by the thread.
> >
> > Of course only specbound values will be saved within each thread's
> > state, but each thread must maintain a pointer to the field that is
> > actually holding the value of the forwarded variables.
> >
> >> Indeed, a simple #define will not be enough then, but we would not waste
> >> memory copying the values that will never be changed anyway.
> >
> > On my machine, struct emacs_globals is 7490 bytes, just short of 7 KiB.
> 
> Correction: just over 7 KiB.

And don't forget that the globals defined in globals.h are just those
we define in C.  There are many globals defined in Lisp.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> And don't forget that the globals defined in globals.h are just those
> we define in C.  There are many globals defined in Lisp.

Those don't contribute to the size of struct thread_state; an alist
between threads and its local value is dynamically allocated when a
symbol is bound locally.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Po Lu <luangruo@yahoo.com> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>> And don't forget that the globals defined in globals.h are just those
>> we define in C.  There are many globals defined in Lisp.
>
> Those don't contribute to the size of struct thread_state; an alist
> between threads and its local value is dynamically allocated when a
                      ^^^^^^^^^^^^^^^

I intended to write ``and their local values.''

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: yantar92@posteo.net,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 08:55:49 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > And don't forget that the globals defined in globals.h are just those
> > we define in C.  There are many globals defined in Lisp.
> 
> Those don't contribute to the size of struct thread_state; an alist
> between threads and its local value is dynamically allocated when a
> symbol is bound locally.

I'm not sure I understand: what is the difference between a global
variable defined in C and a global variable defined, say, in
simple.el?

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> I'm not sure I understand: what is the difference between a global
> variable defined in C and a global variable defined, say, in
> simple.el?

The variable defined in C must be accessible by a C lvalue.  Namely,

  (*current_thread->f_Vname_of_the_variable)

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: yantar92@posteo.net,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 15:34:52 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > I'm not sure I understand: what is the difference between a global
> > variable defined in C and a global variable defined, say, in
> > simple.el?
> 
> The variable defined in C must be accessible by a C lvalue.  Namely,
> 
>   (*current_thread->f_Vname_of_the_variable)

How is this different from

  (setq name-of-variable SOMETHING)

done by some thread to a global variable?

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> The variable defined in C must be accessible by a C lvalue.  Namely,
>> 
>>   (*current_thread->f_Vname_of_the_variable)
>
> How is this different from
>
>   (setq name-of-variable SOMETHING)
>
> done by some thread to a global variable?

For global variables defined in C sources, Emacs maintains an actual C
variable that can be used directly to set and store the value. Then,

(setq name-of-global-variable-defined-in-C SOMETHING) must arrange to
set Vname_of_global_variable_defined_in_C C variable as well.

This is not needed for global variables defined in Elisp.

Under the hood, Vname binding is stored via Lisp_Objfwd. See #define
DEFVAR_LISP in lisp.h. This forwarding must be accounted for in threads,
if we want to make them asynchronous. Po Lu solved this by adding
thread-local "globals" structs.

In contrast, global Elisp variables defined in Elisp for not store
Lisp_Objfwd and instead contain their symbol value directly in their
Elisp symbol objects. Setting and reading these symbol values involves
the common API: Fsymbol_value and Fset, which are much easier to change
to work with async threads compared to the having to handle all the

 Vname = val;

that are expected to work in C level.

To sum up: Elisp-only globals are handled differently from globals
defined in C code and should thus be approached differently when
implementing async threads.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Po Lu <luangruo@yahoo.com>, emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 08:35:06 +0000
> 
> In contrast, global Elisp variables defined in Elisp for not store
> Lisp_Objfwd and instead contain their symbol value directly in their
> Elisp symbol objects. Setting and reading these symbol values involves
> the common API: Fsymbol_value and Fset, which are much easier to change
> to work with async threads compared to the having to handle all the
> 
>  Vname = val;
> 
> that are expected to work in C level.

Thank you for the (unnecessary) lecture, but I was actually asking
what needs to be changed and how to handle the global variables, both
those defined in C and those defined in Lisp.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> Thank you for the (unnecessary) lecture,

Well... hope it was at least useful for others reading the thread :shrug:

> ... but I was actually asking
> what needs to be changed and how to handle the global variables, both
> those defined in C and those defined in Lisp.

Po Lu can probably answer this better.

As I understand his previous explanations, global variable values are
stored per-thread, if they were changed by that thread at some point.
For C-defined globals, the Vname instances are re-defined to
point to thread-local "globals" struct.

I do not recall Po Lu providing the details on how the thread-local
variables are stored.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Ihor Radchenko <yantar92@posteo.net> writes:

> As I understand his previous explanations, global variable values are
> stored per-thread, if they were changed by that thread at some point.
> For C-defined globals, the Vname instances are re-defined to
> point to thread-local "globals" struct.
>
> I do not recall Po Lu providing the details on how the thread-local
> variables are stored.

Non-forwarded thread-local bindings are saved within a separate
association list in Lisp_Symbol, where each element ties a thread to its
local binding.  do_specbind and do_one_specbind manage this association
list by introducing new associations.  set_internal and
find_symbol_value search within this association list for a pair
matching the current thread, and set or return its cdr respectively if
it is present.

Within lispfwds, the pointer to the field itself is replaced with an
offset to a field within struct thread_state which is set to a pointer
to the matching field in `globals' or one of its local bindings.

Whenever a forwarded variable is specbound for the first time in a given
thread, the designated field within that thread's state is set to a
pointer into thread local storage, and once unbound, restored to its
initial value within globals.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 21/09/2023 14:49, Po Lu wrote:
> Ihor Radchenko<yantar92@posteo.net>  writes:
> 
>> As I understand his previous explanations, global variable values are
>> stored per-thread, if they were changed by that thread at some point.
>> For C-defined globals, the Vname instances are re-defined to
>> point to thread-local "globals" struct.
>>
>> I do not recall Po Lu providing the details on how the thread-local
>> variables are stored.
> Non-forwarded thread-local bindings are saved within a separate
> association list in Lisp_Symbol, where each element ties a thread to its
> local binding.  do_specbind and do_one_specbind manage this association
> list by introducing new associations.  set_internal and
> find_symbol_value search within this association list for a pair
> matching the current thread, and set or return its cdr respectively if
> it is present.
> 
> Within lispfwds, the pointer to the field itself is replaced with an
> offset to a field within struct thread_state which is set to a pointer
> to the matching field in `globals' or one of its local bindings.
> 
> Whenever a forwarded variable is specbound for the first time in a given
> thread, the designated field within that thread's state is set to a
> pointer into thread local storage, and once unbound, restored to its
> initial value within globals.

That reminds me of Clojure's threads and dynamic vars' semantics: 
https://clojure.org/about/concurrent_programming

   By default Vars are static, but per-thread bindings for Vars defined 
with metadata mark them as dynamic. Dynamic vars are also mutable 
references to objects. They have a (thread-shared) root binding which 
can be established by def, and can be set using *set!*, but only if they 
have been bound to a new storage location thread-locally using binding. 
Those bindings and any subsequent modifications to those bindings will 
only be seen within the thread by code in the dynamic scope of the 
binding block. Nested bindings obey a stack protocol and unwind as 
control exits the binding block.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: luangruo@yahoo.com, emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 10:13:31 +0000
> 
> As I understand his previous explanations, global variable values are
> stored per-thread, if they were changed by that thread at some point.

So if a thread changes a global variables, other threads will never
notice?  That's not what Emacs Lisp programs expect.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> So if a thread changes a global variables, other threads will never
> notice?  That's not what Emacs Lisp programs expect.

No, only if a thread specbinds a global variable.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: Ihor Radchenko <yantar92@posteo.net>,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 21:12:20 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > So if a thread changes a global variables, other threads will never
> > notice?  That's not what Emacs Lisp programs expect.
> 
> No, only if a thread specbinds a global variable.

Then my question wasn't really answered yet.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> Then my question wasn't really answered yet.

Ah, I now understand what you were asking.

The variable's global value is modified and thereafter made available to
all other threads.  If multiple threads perform coinciding alterations
to the same symbol's value, the machine bus reconciles the conflict by
selecting a single value.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: yantar92@posteo.net,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 21:35:29 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Then my question wasn't really answered yet.
> 
> Ah, I now understand what you were asking.
> 
> The variable's global value is modified and thereafter made available to
> all other threads.  If multiple threads perform coinciding alterations
> to the same symbol's value, the machine bus reconciles the conflict by
> selecting a single value.

And when this happens to globals defined in C, is it handled in the
same way? if not, why not?

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> And when this happens to globals defined in C, is it handled in the
> same way?

Yes, it is.  The underlying implementation is different (as it must
account for forwarding), but the effect is the same.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: yantar92@posteo.net,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 21:57:17 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > And when this happens to globals defined in C, is it handled in the
> > same way?
> 
> Yes, it is.  The underlying implementation is different (as it must
> account for forwarding), but the effect is the same.

OK, that's what I was asking from the beginning.  I though there was
some significant difference.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> How is this different from
>
>   (setq name-of-variable SOMETHING)
>
> done by some thread to a global variable?

That's orthogonal to the subject at hand.  If name-of-variable is
forwarded, then SOMETHING must be recorded within either thread_state or
globals.  If not, it becomes the new value held by one of
name-of-variable's value cells.

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Ihor Radchenko wrote:

>>> Because implementation details are tricky - a lot of Elisp
>>> internal machinery is relying upon modifying global symbol
>>> objects [...]
>>
>> Yeah, but that should be fine, as long as they are locked
>> and unlocked safely, right?
>
> No.
>
> If we have something like (let ((case-fold-search t)) ...),
> we will lock `case-fold-search' symbol for the whole
> duration of `let' call and block any other threads trying to
> alter `case-fold-search' locally.

Yes, but so be it if that's the best we can do with `let' and
a multi-threaded, multi-core Emacs.

But one can also think of other ways to do that, for example
local copies for the duration of the form.

Overall, we will have to have a general solution, then examine
Lisp forms that do global variable setting on a form-by-form
basis and decide how they will relate to the general solution
in the best way possible, while still playing by its rules.

>> But, if one aspire to reduce the number of global variables
>> used, a great way of doing that is lexical `let'-closures,
>> here is an example that allows for the same default value
>> when the function is called from Lisp and when used as an
>> interactive command, yet the data is only hardcoded once
>> for each variable.
>
> Not every variable can be used within lexical scope.
> In particular special variables (see 12.10.4 Using Lexical
> Binding and `special-variable-p') are always treated outside
> lexical binding.

We are never gonna come up with a bottom-level solution that
works optimally for everything. Global/dynamic/special
variables are the exception and not the norm - yes, as we hear
from the name "special" BTW :) - and yes, they will have to be
locked one by one and for as long as it takes for the
execution to proceed safely.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Emanuel Berg <incal@dataswamp.org>
> Date: Tue, 19 Sep 2023 13:14:15 +0200
> 
> Eli Zaretskii wrote:
> 
> > We don't need to discuss all this because solutions for
> > thread synchronization exist for a long time. We even use
> > quite a few of them already: the Lisp threads we have in
> > Emacs now provide some of these synchronization primitives,
> > which are built on top of existing capabilities built into
> > the OS and existing thread libraries.
> >
> > So the problem is not how to lock and serialize access to
> > a variable in general, the problem is how to do this in
> > Emacs so that we won't need to lock everything.
> 
> Okay, excellent, but then why isn't it enough to just maintain
> a register of global variables and threads?
> 
> If a thread wants to use it, look in the register, is it
> available? If not, get in line. And when it becomes available,
> pop a thread in the line, if there is one, and start over?

You are describing what we already do, what every multithreading
program does.  You just call it "register", whereas its real name is
"mutex".

> Why do we have to lock everything just because we lock
> a single variable?

If we need to lock 99.99% of Emacs "single" variables, it is easier to
lock everything.  Faster, too.

Once again, you are looking at the wrong aspects of the problem.
These aspects are easily solvable, and we have even solved some of
them in the current Emacs.  The difficulties are elsewhere.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> If we need to lock 99.99% of Emacs "single" variables, it is easier to
> lock everything.  Faster, too.

Interlocking variables is not necessary.  Extant buses guarantee that
word-sized (Lisp_Object) writes and reads from one CPU are always
coherently propagated to other processors.  And otherwise, interlocking
every global variables would incur an extreme performance penalty; two
extra load-locked / store-conditional pairs (or interlocked
instructions) for each read or write at the minimum.

Interlocking Lisp_Objects themselves is only mandatory under wide int
builds, where the size of each object is larger than the machine's word
size.  Supporting such builds in a multiprocessing Emacs will be an
extreme burden that I don't think we should shoulder.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: Emanuel Berg <incal@dataswamp.org>,  emacs-devel@gnu.org
> Date: Tue, 19 Sep 2023 20:57:30 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > If we need to lock 99.99% of Emacs "single" variables, it is easier to
> > lock everything.  Faster, too.
> 
> Interlocking variables is not necessary.  Extant buses guarantee that
> word-sized (Lisp_Object) writes and reads from one CPU are always
> coherently propagated to other processors.  And otherwise, interlocking
> every global variables would incur an extreme performance penalty; two
> extra load-locked / store-conditional pairs (or interlocked
> instructions) for each read or write at the minimum.

That avoids garbled values where part of a value is from one thread,
the other part from another thread.  But it does nothing to protect
the threads other than the one which changed the value from the
"surprise" of having stuff change under its feet.  Which is the main
problem to solve, since Emacs code is written under the assumption
that a variable in the global state doesn't change while some code
runs that doesn't change that variable.  That is why access to at
least some things will have to be serialized -- to allow threads that
access some part of the global state some level of control on what can
and cannot change while they are doing their job.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> That avoids garbled values where part of a value is from one thread,
> the other part from another thread.  But it does nothing to protect
> the threads other than the one which changed the value from the
> "surprise" of having stuff change under its feet.  Which is the main
> problem to solve, since Emacs code is written under the assumption
> that a variable in the global state doesn't change while some code
> runs that doesn't change that variable.  That is why access to at
> least some things will have to be serialized -- to allow threads that
> access some part of the global state some level of control on what can
> and cannot change while they are doing their job.

My solution (which I've put into practice in redisplay) is to save those
values before sensitive code is executed, and to refer to those saved
values within said code.

But right now I'm stymied by the representation of buffer-local
variables (or rather the lack thereof in a multiprocessing Emacs), so I
plan to give this subject a break for a week or two and revisit it
later.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Wed, 20 Sep 2023 09:05:39 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > That avoids garbled values where part of a value is from one thread,
> > the other part from another thread.  But it does nothing to protect
> > the threads other than the one which changed the value from the
> > "surprise" of having stuff change under its feet.  Which is the main
> > problem to solve, since Emacs code is written under the assumption
> > that a variable in the global state doesn't change while some code
> > runs that doesn't change that variable.  That is why access to at
> > least some things will have to be serialized -- to allow threads that
> > access some part of the global state some level of control on what can
> > and cannot change while they are doing their job.
> 
> My solution (which I've put into practice in redisplay) is to save those
> values before sensitive code is executed, and to refer to those saved
> values within said code.

That is _everyone's_ solution, not just yours.  But it is not as easy
in practice as it may sound.  E.g., imagine a subroutine that is
called by some higher-level functions, where both the callers and the
subroutine need to access the same variable.  When other threads are
running, there's no longer a guarantee that both the caller and the
callee will see the same value of that variable.  If they must use the
same value, you now need to pass that variable to the callee via its
API, and this is not scalable when you have more than a couple,
especially if the callee is not called directly, but via several
intermediate callers.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> My solution (which I've put into practice in redisplay) is to save those
>> values before sensitive code is executed, and to refer to those saved
>> values within said code.
>
> That is _everyone's_ solution, not just yours.  But it is not as easy
> in practice as it may sound.  E.g., imagine a subroutine that is
> called by some higher-level functions, where both the callers and the
> subroutine need to access the same variable.  When other threads are
> running, there's no longer a guarantee that both the caller and the
> callee will see the same value of that variable.  If they must use the
> same value, you now need to pass that variable to the callee via its
> API, and this is not scalable when you have more than a couple,
> especially if the callee is not called directly, but via several
> intermediate callers.

May the state be captured and passed to the callee under the hood?
Something like forking, but using thread-local state.

For lexical bindings, it is just a matter of passing over current
Vinternal_interpreter_environment; and for global bindings, it is a
matter of passing whatever is altered by the caller thread (with
copy-on-write, this info should be available).

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> That is _everyone's_ solution, not just yours.  But it is not as easy
> in practice as it may sound.  E.g., imagine a subroutine that is
> called by some higher-level functions, where both the callers and the
> subroutine need to access the same variable.  When other threads are
> running, there's no longer a guarantee that both the caller and the
> callee will see the same value of that variable.  If they must use the
> same value, you now need to pass that variable to the callee via its
> API, and this is not scalable when you have more than a couple,
> especially if the callee is not called directly, but via several
> intermediate callers.

Then the other solution is to establish temporary thread-local bindings
for each of those variables.  I'm not looking forward to the drudgery of
ascertaining precisely which variables warrant such treatment...

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Eli Zaretskii wrote:

> If we need to lock 99.99% of Emacs "single" variables, it is
> easier to lock everything. Faster, too.

Why do we need to do that?

For one thread, one write operation, and one variable, only
that variable has to be locked?

(operate-on var1) ; here we need a lock on var1
(operate-on var2) ; etc

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Emanuel Berg <incal@dataswamp.org>
> Date: Tue, 19 Sep 2023 21:38:39 +0200
> 
> Eli Zaretskii wrote:
> 
> > If we need to lock 99.99% of Emacs "single" variables, it is
> > easier to lock everything. Faster, too.
> 
> Why do we need to do that?
> 
> For one thread, one write operation, and one variable, only
> that variable has to be locked?
> 
> (operate-on var1) ; here we need a lock on var1
> (operate-on var2) ; etc

We don't have 'operate' in Emacs, but we do have setq, setf, and
others.  Where do you locak and where do you unlock in that case?

Just try to write a simplest Lisp program, and you will see the
problem.

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Eli Zaretskii wrote:

>>> If we need to lock 99.99% of Emacs "single" variables, it
>>> is easier to lock everything. Faster, too.
>> 
>> Why do we need to do that?
>> 
>> For one thread, one write operation, and one variable, only
>> that variable has to be locked?
>> 
>> (operate-on var1) ; here we need a lock on var1
>> (operate-on var2) ; etc
>
> We don't have 'operate' in Emacs, but we do have setq, setf,
> and others. Where do you locak and where do you unlock in
> that case?
>
> Just try to write a simplest Lisp program, and you will see
> the problem.

There is no way around it, in order to prevent a race
condition any global variable must be locked before it's value
can be altered.

So `setq', `setf' and any other setter of global variables
must first be refered to the locking mechanism where they
either acquire the lock, perform the write, and release the
lock; or, if the variable is already locked by some other
thread wanting to do the same thing, they must be queued so
they will get it in due time.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Emanuel Berg <incal@dataswamp.org>
> Date: Fri, 22 Sep 2023 16:22:10 +0200
> 
> There is no way around it, in order to prevent a race
> condition any global variable must be locked before it's value
> can be altered.
> 
> So `setq', `setf' and any other setter of global variables
> must first be refered to the locking mechanism where they
> either acquire the lock, perform the write, and release the
> lock; or, if the variable is already locked by some other
> thread wanting to do the same thing, they must be queued so
> they will get it in due time.

So one thread uses setq, releases the lock, then another thread comes,
takes the lock and changes the value of that variable, and when the
first thread uses the variable after that, it will have a value
different from the one the thread used in its setq?  How can one write
a program under these conditions and know what it will do?

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Eli Zaretskii wrote:

>> There is no way around it, in order to prevent a race
>> condition any global variable must be locked before it's
>> value can be altered.
>> 
>> So `setq', `setf' and any other setter of global variables
>> must first be refered to the locking mechanism where they
>> either acquire the lock, perform the write, and release the
>> lock; or, if the variable is already locked by some other
>> thread wanting to do the same thing, they must be queued so
>> they will get it in due time.
>
> So one thread uses setq, releases the lock, then another
> thread comes, takes the lock and changes the value of that
> variable, and when the first thread uses the variable after
> that, it will have a value different from the one the thread
> used in its setq? How can one write a program under these
> conditions and know what it will do?

By relying not on global variables but on local variables.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Emanuel Berg <incal@dataswamp.org>
> Date: Fri, 22 Sep 2023 18:00:42 +0200
> 
> Eli Zaretskii wrote:
> 
> >> There is no way around it, in order to prevent a race
> >> condition any global variable must be locked before it's
> >> value can be altered.
> >> 
> >> So `setq', `setf' and any other setter of global variables
> >> must first be refered to the locking mechanism where they
> >> either acquire the lock, perform the write, and release the
> >> lock; or, if the variable is already locked by some other
> >> thread wanting to do the same thing, they must be queued so
> >> they will get it in due time.
> >
> > So one thread uses setq, releases the lock, then another
> > thread comes, takes the lock and changes the value of that
> > variable, and when the first thread uses the variable after
> > that, it will have a value different from the one the thread
> > used in its setq? How can one write a program under these
> > conditions and know what it will do?
> 
> By relying not on global variables but on local variables.

It is impossible in Emacs to write a useful Lisp program that doesn't
rely on global variables and other parts of the global state.  You can
only write toy programs without that.

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Eli Zaretskii wrote:

> It is impossible in Emacs to write a useful Lisp program
> that doesn't rely on global variables and other parts of the
> global state. You can only write toy programs without that.

Lisp programs are not toy programs just because they don't use
global variables. One can reduce the reliance on global
variables to a huge degree with various methods. But that's
another discussion.

Because, if one is unallowed to break existing code
implementing an envisioned multi-threaded, multi-core model
one would have to deal with them, and it would then not matter
if they are few or if they are many in that regard.

But note that such a solution would favor any program that
would minimize their use, since those would have much less
overhead to deal with them, obviously. That, however, is
a good thing as it would favor a sound programming style that
minimize their use.

Again, first one would have to agree on a model how things
would work. Say that we go for the idea that each thread has
a superstructure of local variables, that would be accessible
as if they were globals. In a way, this would not be unlike
lexical `let'-closures which can also be used as if they were
globals, and that is one of the use cases of that method BTW.

Second, one would have to identify all Lisp constructs that
interact with the global state. Without changing how those are
used, one would have to think - what do they mean in the new,
thread model? Of many possibly interpretations, which ones do
not contradict how they were previously used?

This will have to be done on a case-by-case basis. One could
start with the most obvious cases, i.e. `setq', `setf', `let',
and so on.

It sounds like a lot but actually don't have to be that much.
Because first, there are a limited number of such constructs.
Second, even tho in terms of implementation it would have to
be done case-by-case, if one can identify a good way of
solving it for on such case, it is likely that method can be
brought over to the rest quite easily.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> So one thread uses setq, releases the lock, then another thread comes,
> takes the lock and changes the value of that variable, and when the
> first thread uses the variable after that, it will have a value
> different from the one the thread used in its setq?  How can one write
> a program under these conditions and know what it will do?

IMHO, there should be a new API to lock global variables by async
threads and/or set them.

I can imagine 3 possible scenarios:

1. Thread does not rely upon global variable value being constant, only
   upon being able to set it.

2. Thread sets global variable value and uses it later, expecting the
   value to remain constant.

3. Thread let-binds global variable.

(1) is easy - we just allow setting global value as we did in the past.
(2) is trickier. We might need to provide a new API, so that thread can
    put a lock onto the variables it works with.
    Or, alternatively, we might keep the global values thread-local
    until the thread terminates - it will most closely resemble what the
    existing Elisp code expects. Then, an API for explicitly setting
    top-level values will be needed for new code that will be written
    with concurrency in mind.
(3) is what Po Lu implemented in his current experimental code (AFAIU) -
    only set thread-local value with global variable is let-bound inside
    the thread. We know for sure that this value is neither reused by
    the concurrent threads nor needs to be kept outside the let-binding.

    BTW, Po Lu, what will happen when a thread spawns another async
    thread while some global variable is let-bound. Should the spawned
    thread somehow inherit the parent thread state?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Emanuel Berg <incal@dataswamp.org>, emacs-devel@gnu.org
> Date: Fri, 22 Sep 2023 16:11:38 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > So one thread uses setq, releases the lock, then another thread comes,
> > takes the lock and changes the value of that variable, and when the
> > first thread uses the variable after that, it will have a value
> > different from the one the thread used in its setq?  How can one write
> > a program under these conditions and know what it will do?
> 
> IMHO, there should be a new API to lock global variables by async
> threads and/or set them.

Which again means existing Lisp programs will be unable to run without
very serious changes.

> 1. Thread does not rely upon global variable value being constant, only
>    upon being able to set it.

This is an almost empty set in Emacs.

> 2. Thread sets global variable value and uses it later, expecting the
>    value to remain constant.

This is the problem to solve.

> 3. Thread let-binds global variable.

This is already solved in the current Lisp threadfs.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> 2. Thread sets global variable value and uses it later, expecting the
>>    value to remain constant.
>
> This is the problem to solve.

My suggestion is to (1) create a thread-local copy of a global variable
value at the moment a thread reads/writes that global variable; (2) If a
thread writes a global variable, write the thread-local value back to
global when the thread terminates.

IMHO, this approach will keep all the existing Elisp working.

And if some new Elisp wants to set global value which running
concurrently, introduce a new API.

>> 3. Thread let-binds global variable.
>
> This is already solved in the current Lisp threadfs.

Not really. Current Lisp threads (1) specbind the old value
thread-locally; (2) set symbol value globally; (3) unwind/rewind when
switching between threads.

The global symbol value is directly modified, which won't fly for
concurrent threads.

That said, AFAIU, Po Lu knows how to address this particular problem.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Emanuel Berg]

Ihor Radchenko wrote:

> My suggestion is to [...] create a thread-local copy of
> a global variable value at the moment a thread reads/writes
> that global variable [...]

Yes, if one isn't allowed to break existing code one would
have to do something like that.

Each thread would have a thread space of variables so that
while thinking it would access global variables, it would in
fact populate that thread space little by little and from then
on use those variables.

We could have OO-inspired interface to that thread space with
getters and setters, and all the Lisp that would have to be
modified to first look for a thread space instead of the
global variable, would use such getters and setters.

-- 
underground experts united
https://dataswamp.org/~incal

Re: Emacs design and architecture. How about copy-on-write?

[tomas]

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

On Fri, Sep 22, 2023 at 06:51:43PM +0300, Eli Zaretskii wrote:
> > From: Emanuel Berg <incal@dataswamp.org>
> > Date: Fri, 22 Sep 2023 16:22:10 +0200
> > 
> > There is no way around it, in order to prevent a race
> > condition any global variable must be locked before it's value
> > can be altered.
> > 
> > So `setq', `setf' and any other setter of global variables
> > must first be refered to the locking mechanism where they
> > either acquire the lock, perform the write, and release the
> > lock; or, if the variable is already locked by some other
> > thread wanting to do the same thing, they must be queued so
> > they will get it in due time.
> 
> So one thread uses setq, releases the lock, then another thread comes,
> takes the lock and changes the value of that variable, and when the
> first thread uses the variable after that, it will have a value
> different from the one the thread used in its setq?  How can one write
> a program under these conditions and know what it will do?

Nicer even. Imagine the compiler saying "oh, we have the value
of this var already in this register!" (this is, after all, why
compiled code is significantly faster).

You can't do this anymore, because each global var is potentially
volatile.

Three quarter of your optimisation opportunities *poof* gone.

Another: suppose you have three globals which have to be
changed in sync. Do you lock around the whole change, although
each var is locked in itself?

Concurrency isn't easy. Most of the application has to "know",
in a way.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> Nope. I consider that redisplay is always synchronous
>
> Synchronous to what?

Synchronous in a sense that no two `redisplay' calls can be executed in
parallel.

>> (because of global redisplay lock)
>
> What is the global redisplay lock?

I imagine that the implementation can involve global redisplay lock that
`redisplay' (or its internal functions) need to acquire before running.

>> If multiple threads trigger redisplay with different scroll-margin
>> values, it will be not different compared to the following example:
>
> I understand the problem, I'm asking what could or should be the
> possible solutions.

Sorry, I was not clear. My illustration was not to describe that there
is a problem. My illustration was to show that it is already possible to
run redisplay in various contexts (in the example - let-binding
contexts). Having multiple async threads call re-display with different
settings will be no different from what is already possible without
parallelism.

So, I claim that it is not a problem that should be solved (given that
we make sure that only a single redisplay call can run at a time).

>> 3. xdisp is relying on a number of global-only variables like
>>    `mode-line-compact', `show-trailing-whitespace', and similar.
>>    AFAIR, things like `show-trailing-whitespace' affect how the
>>    optimizations are applied when deciding which windows should be
>>    redisplayed and which should not. I suspect that logic related to
>>    optimizations may be very fragile with async execution.
>
> That's completely irrelevant to the issue at hand.  The fact that
> Emacs has a huge global state, and all of its code relies on that is a
> separate issue.  Here, I asked you in what sense is xdisp.c's code
> single-threaded; if your answer is "because of its reliance on global
> state", it means there's no separate problem of xdisp.c that is based
> on single thread.

Then, we had a misunderstanding. My point is exactly that xdisp.c relies
on global state _a lot_. And it will be non-trivial to change it.

In my mind, it is easier to first solve the problem with generic Elisp
async threads and only then try to look into async redisplay. Because
redisplay is already difficult to alter - untangling its global state
will be a huge task by itself.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Tue, 19 Sep 2023 11:36:24 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> Nope. I consider that redisplay is always synchronous
> >
> > Synchronous to what?
> 
> Synchronous in a sense that no two `redisplay' calls can be executed in
> parallel.

I think they can, if they display different buffers in different
windows.

> >> (because of global redisplay lock)
> >
> > What is the global redisplay lock?
> 
> I imagine that the implementation can involve global redisplay lock that
> `redisplay' (or its internal functions) need to acquire before running.

I thought you were describing the current implementation (where
there's no lock).  If you are describing some hypothetical future
implementation, I don't see how we could usefully discuss this without
much more details of that hypothetical design.

> >> 3. xdisp is relying on a number of global-only variables like
> >>    `mode-line-compact', `show-trailing-whitespace', and similar.
> >>    AFAIR, things like `show-trailing-whitespace' affect how the
> >>    optimizations are applied when deciding which windows should be
> >>    redisplayed and which should not. I suspect that logic related to
> >>    optimizations may be very fragile with async execution.
> >
> > That's completely irrelevant to the issue at hand.  The fact that
> > Emacs has a huge global state, and all of its code relies on that is a
> > separate issue.  Here, I asked you in what sense is xdisp.c's code
> > single-threaded; if your answer is "because of its reliance on global
> > state", it means there's no separate problem of xdisp.c that is based
> > on single thread.
> 
> Then, we had a misunderstanding. My point is exactly that xdisp.c relies
> on global state _a lot_. And it will be non-trivial to change it.

It doesn't _rely_ on the state, not on the level of the code.  It
_accesses_ the state as every other Lisp program does, since that's
how Emacs accesses it everywhere.  But there are no hidden assumptions
that the variables used by xdisp.c are global.  If each one of them
will become buffer-local or thread-local, nothing significant will
change in the xdisp.c code.  All xdisp.c needs is to be able to access
the value when needed.  And since each window is processed separately,
there's no assumption that something observed when displaying window
W1 will necessarily hold when displaying window W2.

> In my mind, it is easier to first solve the problem with generic Elisp
> async threads and only then try to look into async redisplay.

We tried that already, with the existing Lisp threads.  One reason why
those are almost never used is that the display issue was left
unresolved.  Any real-life Lisp programs that tries to use threads
bumps into this issue sooner or later.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> > What is the global redisplay lock?
>> 
>> I imagine that the implementation can involve global redisplay lock that
>> `redisplay' (or its internal functions) need to acquire before running.
>
> I thought you were describing the current implementation (where
> there's no lock).  If you are describing some hypothetical future
> implementation, I don't see how we could usefully discuss this without
> much more details of that hypothetical design.

This is very simple - I suggest to not touch xdisp.c as much as
possible, just make sure that it is interlocked. And focus on async
support in Elisp code. Once there is async support in Elisp code, we can
move further and look into xdisp.

(I suggest this because I feel that xdisp is a rabbit hole we may sink
in instead of doing something more productive)

>> Then, we had a misunderstanding. My point is exactly that xdisp.c relies
>> on global state _a lot_. And it will be non-trivial to change it.
>
> It doesn't _rely_ on the state, not on the level of the code.  It
> _accesses_ the state as every other Lisp program does, since that's
> how Emacs accesses it everywhere.  But there are no hidden assumptions
> that the variables used by xdisp.c are global.  If each one of them
> will become buffer-local or thread-local, nothing significant will
> change in the xdisp.c code.  All xdisp.c needs is to be able to access
> the value when needed.  And since each window is processed separately,
> there's no assumption that something observed when displaying window
> W1 will necessarily hold when displaying window W2.

I am particularly worried about scenarios when window geometry changes
by asynchronous threads. Or, say, face definitions. Imagine that it
happens at point when we are already drawing the now obsolete geometry
onto glass?

IMHO, it is similar to the problem with GC - for synchronous code, it is
enough to sprinkle maybe_gc in strategic places in the code; for
asynchronous code, we have to somehow make sure that GC is not running
in parallel with another thread trying to allocate memory at the very
same moment.

>> In my mind, it is easier to first solve the problem with generic Elisp
>> async threads and only then try to look into async redisplay.
>
> We tried that already, with the existing Lisp threads.  One reason why
> those are almost never used is that the display issue was left
> unresolved.

That might be one reason, but not the only reason. And certainly not the
most important reason for the use cases where I did try to use threads
myself.

> ... Any real-life Lisp programs that tries to use threads
> bumps into this issue sooner or later.

This is not true. Some Lisp programs? Yes. "Any"? No.
As we discussed previously, a number of Elisp programs can benefit from
async threads even when redisplay is not asynchronous - network queries
(gnus), text parsing (org-mode, slow LSP server communication, xml
processing).

To be clear, it would indeed be nice to have async redisplay. But before
having that we should have async Elisp code (otherwise we cannot run
Elisp from inside async redisplay). And I suggest to focus on this
first, necessary, step of getting async Elisp.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Tue, 19 Sep 2023 13:35:49 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> > What is the global redisplay lock?
> >> 
> >> I imagine that the implementation can involve global redisplay lock that
> >> `redisplay' (or its internal functions) need to acquire before running.
> >
> > I thought you were describing the current implementation (where
> > there's no lock).  If you are describing some hypothetical future
> > implementation, I don't see how we could usefully discuss this without
> > much more details of that hypothetical design.
> 
> This is very simple - I suggest to not touch xdisp.c as much as
> possible, just make sure that it is interlocked. And focus on async
> support in Elisp code. Once there is async support in Elisp code, we can
> move further and look into xdisp.
> 
> (I suggest this because I feel that xdisp is a rabbit hole we may sink
> in instead of doing something more productive)

I'm actually of the opposite opinion.  I think trying to parallelize
redisplay is a lower-hanging fruit, and if successful, it could bring
non-trivial gains to Emacs even if the rest remains single-threaded.

> >> Then, we had a misunderstanding. My point is exactly that xdisp.c relies
> >> on global state _a lot_. And it will be non-trivial to change it.
> >
> > It doesn't _rely_ on the state, not on the level of the code.  It
> > _accesses_ the state as every other Lisp program does, since that's
> > how Emacs accesses it everywhere.  But there are no hidden assumptions
> > that the variables used by xdisp.c are global.  If each one of them
> > will become buffer-local or thread-local, nothing significant will
> > change in the xdisp.c code.  All xdisp.c needs is to be able to access
> > the value when needed.  And since each window is processed separately,
> > there's no assumption that something observed when displaying window
> > W1 will necessarily hold when displaying window W2.
> 
> I am particularly worried about scenarios when window geometry changes
> by asynchronous threads. Or, say, face definitions. Imagine that it
> happens at point when we are already drawing the now obsolete geometry
> onto glass?

xdisp.c has solutions for these two (and other similar) situations.
The problems have nothing to do with parallelism, they happen today
because we call Lisp at certain places in the display engine.

> >> In my mind, it is easier to first solve the problem with generic Elisp
> >> async threads and only then try to look into async redisplay.
> >
> > We tried that already, with the existing Lisp threads.  One reason why
> > those are almost never used is that the display issue was left
> > unresolved.
> 
> That might be one reason, but not the only reason. And certainly not the
> most important reason for the use cases where I did try to use threads
> myself.

There's more than one reason, that's true.  But it doesn't change the
fact that all those problems have to be resolved before we have
reasonably usable threads.

> > ... Any real-life Lisp programs that tries to use threads
> > bumps into this issue sooner or later.
> 
> This is not true. Some Lisp programs? Yes. "Any"? No.

Only toy Lisp programs can get away.

> As we discussed previously, a number of Elisp programs can benefit from
> async threads even when redisplay is not asynchronous - network queries
> (gnus), text parsing (org-mode, slow LSP server communication, xml
> processing).

You forget that almost every Lisp program in Emacs either displays
something or affects stuff that affects redisplay.  It's easy to
forget, I know, because in Emacs redisplay "just happens" by some
magic.

> To be clear, it would indeed be nice to have async redisplay.

I'm not talking about async redisplay, I'm talking about the ability
of non-main threads to display something or do something that would
cause redisplay change the stuff on the glass.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 19/09/2023 17:14, Eli Zaretskii wrote:
>> This is very simple - I suggest to not touch xdisp.c as much as
>> possible, just make sure that it is interlocked. And focus on async
>> support in Elisp code. Once there is async support in Elisp code, we can
>> move further and look into xdisp.
>>
>> (I suggest this because I feel that xdisp is a rabbit hole we may sink
>> in instead of doing something more productive)
> I'm actually of the opposite opinion.  I think trying to parallelize
> redisplay is a lower-hanging fruit, and if successful, it could bring
> non-trivial gains to Emacs even if the rest remains single-threaded.

Do we have evidence that the speed of redisplay is a limiting factor in 
general Emacs usage? I.e. with an optimized build and most of the 
popular modes (excepting certain display-heavy Org buffers, let's say).

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Tue, 19 Sep 2023 18:15:50 +0300
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> On 19/09/2023 17:14, Eli Zaretskii wrote:
> >> This is very simple - I suggest to not touch xdisp.c as much as
> >> possible, just make sure that it is interlocked. And focus on async
> >> support in Elisp code. Once there is async support in Elisp code, we can
> >> move further and look into xdisp.
> >>
> >> (I suggest this because I feel that xdisp is a rabbit hole we may sink
> >> in instead of doing something more productive)
> > I'm actually of the opposite opinion.  I think trying to parallelize
> > redisplay is a lower-hanging fruit, and if successful, it could bring
> > non-trivial gains to Emacs even if the rest remains single-threaded.
> 
> Do we have evidence that the speed of redisplay is a limiting factor in 
> general Emacs usage? I.e. with an optimized build and most of the 
> popular modes (excepting certain display-heavy Org buffers, let's say).

You already forgot the long-lines problems?

And there are other situations where we'd like faster redisplay, even
though they are not as bad.  For example, when a session has many
frames (I believe Stefan Monnier tends to have a lot of them in his
sessions).  To say nothing of the fact that displays become larger and
larger, and many people like to have their frames maximized.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 19/09/2023 18:37, Eli Zaretskii wrote:
>> Date: Tue, 19 Sep 2023 18:15:50 +0300
>> Cc:acm@muc.de,incal@dataswamp.org,emacs-devel@gnu.org
>> From: Dmitry Gutov<dmitry@gutov.dev>
>>
>> On 19/09/2023 17:14, Eli Zaretskii wrote:
>>>> This is very simple - I suggest to not touch xdisp.c as much as
>>>> possible, just make sure that it is interlocked. And focus on async
>>>> support in Elisp code. Once there is async support in Elisp code, we can
>>>> move further and look into xdisp.
>>>>
>>>> (I suggest this because I feel that xdisp is a rabbit hole we may sink
>>>> in instead of doing something more productive)
>>> I'm actually of the opposite opinion.  I think trying to parallelize
>>> redisplay is a lower-hanging fruit, and if successful, it could bring
>>> non-trivial gains to Emacs even if the rest remains single-threaded.
>> Do we have evidence that the speed of redisplay is a limiting factor in
>> general Emacs usage? I.e. with an optimized build and most of the
>> popular modes (excepting certain display-heavy Org buffers, let's say).
> You already forgot the long-lines problems?

The long-lines problem wasn't solvable with parallel redisplay either, 
it was a case of high algorithm complexity (a combination of them).

> And there are other situations where we'd like faster redisplay, even
> though they are not as bad.  For example, when a session has many
> frames (I believe Stefan Monnier tends to have a lot of them in his
> sessions).  To say nothing of the fact that displays become larger and
> larger, and many people like to have their frames maximized.

It would help to see some info on:

- Whether Stefan's build is optimized,
- How much time the many-frames case spends talking to the windowing 
system, compared to the time our redisplay takes internally. If there 
are many frames displayed, but the current buffer is shown in only one 
of them (or two, etc), then shouldn't the rest of the frames stay mostly 
still anyway?

I also like to have my frames maximized, and I have a 4K display -- even 
so, redisplay seems to be mostly fine (with 1-2 frames anyway). But 
rendering large windows at high resolution, while it can be taxing, 
generally bottlenecks at something else than the layout algorithms. 
Unless you're arguing that the layouts are going to become more complex 
exponentially as well.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Tue, 19 Sep 2023 19:01:31 +0300
> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> >> Do we have evidence that the speed of redisplay is a limiting factor in
> >> general Emacs usage? I.e. with an optimized build and most of the
> >> popular modes (excepting certain display-heavy Org buffers, let's say).
> > You already forgot the long-lines problems?
> 
> The long-lines problem wasn't solvable with parallel redisplay either, 
> it was a case of high algorithm complexity (a combination of them).

How do you know that parallel redisplay will not solve this?  This can
only be obvious when the detailed design of that is presented.  Until
then, it's anyone's guess.

Anyway, you asked for evidence that redisplay could benefit from
performance boost, and I gave you some.  Now you for some reason want
to claim that my evidence doesn't convince you, but it still is
evidence, right?

> It would help to see some info on:
> 
> - Whether Stefan's build is optimized,
> - How much time the many-frames case spends talking to the windowing 
> system, compared to the time our redisplay takes internally. If there 
> are many frames displayed, but the current buffer is shown in only one 
> of them (or two, etc), then shouldn't the rest of the frames stay mostly 
> still anyway?
> 
> I also like to have my frames maximized, and I have a 4K display -- even 
> so, redisplay seems to be mostly fine (with 1-2 frames anyway). But 
> rendering large windows at high resolution, while it can be taxing, 
> generally bottlenecks at something else than the layout algorithms. 
> Unless you're arguing that the layouts are going to become more complex 
> exponentially as well.

You seem to be opposed to attempts to explore ways of making Emacs
less single-threaded than it is today, unless someone provides a
proof, up front, that this will necessarily solve some particular
problem?  Why? what harm could that possibly do, if it succeeds?  And
if it doesn't succeed, at least we will have learned something
probably useful for the future.

The right time to ask the questions you are asking is when a more or
less detailed design is presented, and we can assess the complexity
and other possible downsides of the proposal against its gains, if
any.  We are not there yet.  Let's keep our minds open and see where
this leads us, okay?

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 19/09/2023 20:54, Eli Zaretskii wrote:
>> Date: Tue, 19 Sep 2023 19:01:31 +0300
>> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
>> From: Dmitry Gutov <dmitry@gutov.dev>
>>
>>>> Do we have evidence that the speed of redisplay is a limiting factor in
>>>> general Emacs usage? I.e. with an optimized build and most of the
>>>> popular modes (excepting certain display-heavy Org buffers, let's say).
>>> You already forgot the long-lines problems?
>>
>> The long-lines problem wasn't solvable with parallel redisplay either,
>> it was a case of high algorithm complexity (a combination of them).
> 
> How do you know that parallel redisplay will not solve this?  This can
> only be obvious when the detailed design of that is presented.  Until
> then, it's anyone's guess.

It's not 100%, but seems logical: the problem with long lines is that 
displaying a single line took non-linear amount of time proportional to 
its length. To be able to layout it in parallel, we would somehow have 
to be able to split it into independent pieces (perhaps using some 
caching mechanism?, IDK). If we are actually able to do that (which 
seems difficult), a non-parallel redisplay algorithm should happily use 
the same mid-line checkpoint information to work on smaller pieces of 
the line, likewise increasing the speed.

But I think we've much improved on the issue by reducing the complexity 
instead (correct me if I'm wrong here).

> Anyway, you asked for evidence that redisplay could benefit from
> performance boost, and I gave you some.  Now you for some reason want
> to claim that my evidence doesn't convince you, but it still is
> evidence, right?

I was looking for other examples, to be honest. Like, for example, 
evidence that redisplay is something that keeps an average Emacs session 
from running at 60fps. Or even at 30fps. That would make it a bottleneck.

When I asked the question, I was under the impression that people do 
have some data to point this way, and I just missed it.

> You seem to be opposed to attempts to explore ways of making Emacs
> less single-threaded than it is today, unless someone provides a
> proof, up front, that this will necessarily solve some particular
> problem?  Why? what harm could that possibly do, if it succeeds?  And
> if it doesn't succeed, at least we will have learned something
> probably useful for the future.

It is my experience that good benchmarking often helps with changing the 
design as well. Or coming up with a new one (there are a lot of options 
for how one could proceed).

I'm not saying it is necessary, but it is a good idea, I think.

> The right time to ask the questions you are asking is when a more or
> less detailed design is presented, and we can assess the complexity
> and other possible downsides of the proposal against its gains, if
> any.  We are not there yet.  Let's keep our minds open and see where
> this leads us, okay?

Sure.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Tue, 19 Sep 2023 23:21:46 +0300
> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> On 19/09/2023 20:54, Eli Zaretskii wrote:
> > 
> > How do you know that parallel redisplay will not solve this?  This can
> > only be obvious when the detailed design of that is presented.  Until
> > then, it's anyone's guess.
> 
> It's not 100%, but seems logical: the problem with long lines is that 
> displaying a single line took non-linear amount of time proportional to 
> its length. To be able to layout it in parallel, we would somehow have 
> to be able to split it into independent pieces (perhaps using some 
> caching mechanism?, IDK). If we are actually able to do that (which 
> seems difficult), a non-parallel redisplay algorithm should happily use 
> the same mid-line checkpoint information to work on smaller pieces of 
> the line, likewise increasing the speed.

You are considering only the redisplay of that single window which has
long lines.  But what about the other windows, which perhaps don't
have long lines?  And what about the main thread of Emacs itself,
which freezes for as long as redisplay didn't finish, thus preventing
user interaction and responsiveness in general?  These factors should
not be neglected.

> But I think we've much improved on the issue by reducing the complexity 
> instead (correct me if I'm wrong here).

If you mean the long-lines improvements in Emacs 29, then we traded
off correctness in at least some cases.  It wasn't for free.

> > Anyway, you asked for evidence that redisplay could benefit from
> > performance boost, and I gave you some.  Now you for some reason want
> > to claim that my evidence doesn't convince you, but it still is
> > evidence, right?
> 
> I was looking for other examples, to be honest. Like, for example, 
> evidence that redisplay is something that keeps an average Emacs session 
> from running at 60fps. Or even at 30fps. That would make it a bottleneck.

With enough text properties and overlays, you can definitely see a
tangible slowdown in frame rate.  E.g., Org developers don't want to
use text properties because they slow down redisplay, and thus they
consider them not scalable enough.

> > You seem to be opposed to attempts to explore ways of making Emacs
> > less single-threaded than it is today, unless someone provides a
> > proof, up front, that this will necessarily solve some particular
> > problem?  Why? what harm could that possibly do, if it succeeds?  And
> > if it doesn't succeed, at least we will have learned something
> > probably useful for the future.
> 
> It is my experience that good benchmarking often helps with changing the 
> design as well. Or coming up with a new one (there are a lot of options 
> for how one could proceed).

On the high-level design level, it should be clear without any need
for benchmarking that separating redisplay from the main thread could
bring benefits.  Isn't that what every GUI application out there does?
So trying to think about that is always a good thing, IMO.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> With enough text properties and overlays, you can definitely see a
> tangible slowdown in frame rate.  E.g., Org developers don't want to
> use text properties because they slow down redisplay, and thus they
> consider them not scalable enough.

I do not think that it needs be addressed by async threads.
The main problem with text properties, AFAIK, is that segment tree Emacs
uses makes searching for next single property change scale with the
total number of segments where _any_ arbitrary property changes, not
with actual number of that searched property segments.

I believe that it is more a question of rewriting text property handling
into multiple segment trees dedicated to individual properties.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Dmitry Gutov <dmitry@gutov.dev>, acm@muc.de, incal@dataswamp.org,
>  emacs-devel@gnu.org
> Date: Wed, 20 Sep 2023 11:38:00 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > With enough text properties and overlays, you can definitely see a
> > tangible slowdown in frame rate.  E.g., Org developers don't want to
> > use text properties because they slow down redisplay, and thus they
> > consider them not scalable enough.
> 
> I do not think that it needs be addressed by async threads.
> The main problem with text properties, AFAIK, is that segment tree Emacs
> uses makes searching for next single property change scale with the
> total number of segments where _any_ arbitrary property changes, not
> with actual number of that searched property segments.

Regardless of all of the above, any expensive processing that can be
divided between several execution units will take less elapsed time,
right?  So, for example, processing text properties of two buffers
sequentially by the same thread (as this is done now) will take longer
than processing them concurrently in parallel, right?  So redisplaying
two windows by two independent threads running concurrently on two
execution units will be faster, right?

> I believe that it is more a question of rewriting text property handling
> into multiple segment trees dedicated to individual properties.

Not as far as redisplay is concerned, no.  The display engine _wants_
to look for the next change in any text property, because it processes
them all "together".  That is, it finds the buffer position where any
of the text properties change, then hands that position to each of the
known methods for handling property changes so that each one of them
does its thing.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> Regardless of all of the above, any expensive processing that can be
> divided between several execution units will take less elapsed time,
> right?

Not necessarily. Only when the particular algorithm used can be
effectively converted into concurrent version. Sometimes, concurrent
version performs worse.

> ... So, for example, processing text properties of two buffers
> sequentially by the same thread (as this is done now) will take longer
> than processing them concurrently in parallel, right?
> ... So redisplaying
> two windows by two independent threads running concurrently on two
> execution units will be faster, right?

If the processing is completely independent, it is probably true.
Unless overheads to create new threads are comparable with processing
time (will matter for small buffers that can be process quickly).

>> I believe that it is more a question of rewriting text property handling
>> into multiple segment trees dedicated to individual properties.
>
> Not as far as redisplay is concerned, no.  The display engine _wants_
> to look for the next change in any text property, because it processes
> them all "together".  That is, it finds the buffer position where any
> of the text properties change, then hands that position to each of the
> known methods for handling property changes so that each one of them
> does its thing.

This is... not what I know. May you please point me where in the code it
is done?

From my previous experience, there separate processing of invisible
property and separate processing of composition property. But not
generic processing looking into all present text properties, including
the ones unrelated to redisplay.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: dmitry@gutov.dev, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 10:41:52 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> I believe that it is more a question of rewriting text property handling
> >> into multiple segment trees dedicated to individual properties.
> >
> > Not as far as redisplay is concerned, no.  The display engine _wants_
> > to look for the next change in any text property, because it processes
> > them all "together".  That is, it finds the buffer position where any
> > of the text properties change, then hands that position to each of the
> > known methods for handling property changes so that each one of them
> > does its thing.
> 
> This is... not what I know. May you please point me where in the code it
> is done?

compute_stop_pos finds the next "stop position" where properties (or
something else of interest to redisplay) change, and when the
iteration gets to that position, handle_stop calls the available
handler methods to do their thing.  The intervals of the text
properties are examined by compute_stop_pos.

> >From my previous experience, there separate processing of invisible
> property and separate processing of composition property. But not
> generic processing looking into all present text properties, including
> the ones unrelated to redisplay.

All of the handlers are called one after the other on every stop
position we process.  So the processing is sequential, but not
"separate".  In particular, the higher-level iteration routine
(get_next_display_element), which detects when a stop position was
reached, doesn't know and doesn't care which text property triggered
the stop position; each called method checks if the current iteration
position needs it to do something, and if not, immediately returns.
That's how we support several properties that change at the same
buffer position.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> This is... not what I know. May you please point me where in the code it
>> is done?
>
> compute_stop_pos finds the next "stop position" where properties (or
> something else of interest to redisplay) change, and when the
> iteration gets to that position, handle_stop calls the available
> handler methods to do their thing.  The intervals of the text
> properties are examined by compute_stop_pos.

Thanks!
"stop position" is not triggered by _all_ the properties though.
`compute_stop_pos' calculates the largest region where the properties
listed in `it_props' ('fontified, 'face, 'invisible, and 'composition)
remain the same. If any other property not in the list changes, it is
ignored (except `char-property-alias-alist' which may link other
properties to 'fontified/face/invisible/composition).

Further, handle_stop handlers do search for their corresponding handled
property via Fnext_single_property_change, which again iterates over
every interval in the buffer until that single property value changes.

IMHO, one of the bottlenecks with the current implementation is that we
have to iterate over unrelated properties to find the position of
interest. So, redisplay performance is not just affected by the
properties that matter, but by _all_ properties in buffer (strictly
speaking, by all the intervals in buffer).

I believe that having a more efficient algorithm to detect where a
single property change should speed things up significantly. handle_stop
will benefit directly, while `compute_stop_pos' could query
min (mapcar (Fnext_single_property_change, it_props))
to avoid counting unrelated properties.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: dmitry@gutov.dev, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Fri, 22 Sep 2023 10:05:23 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > compute_stop_pos finds the next "stop position" where properties (or
> > something else of interest to redisplay) change, and when the
> > iteration gets to that position, handle_stop calls the available
> > handler methods to do their thing.  The intervals of the text
> > properties are examined by compute_stop_pos.
> 
> Thanks!
> "stop position" is not triggered by _all_ the properties though.
> `compute_stop_pos' calculates the largest region where the properties
> listed in `it_props' ('fontified, 'face, 'invisible, and 'composition)
> remain the same. If any other property not in the list changes, it is
> ignored (except `char-property-alias-alist' which may link other
> properties to 'fontified/face/invisible/composition).

Does this contradict what I wrote? if so, how?

> Further, handle_stop handlers do search for their corresponding handled
> property via Fnext_single_property_change, which again iterates over
> every interval in the buffer until that single property value changes.

If they do this, it's because they need that to do their thing.
There's no requirement from the handlers to do that.  Moreover, we
could record the position of the next change of each property, when
the handler does determine that, and use that in compute_stop_pos, to
avoid repeating the same search.

> IMHO, one of the bottlenecks with the current implementation is that we
> have to iterate over unrelated properties to find the position of
> interest. So, redisplay performance is not just affected by the
> properties that matter, but by _all_ properties in buffer (strictly
> speaking, by all the intervals in buffer).
> 
> I believe that having a more efficient algorithm to detect where a
> single property change should speed things up significantly. handle_stop
> will benefit directly, while `compute_stop_pos' could query
> min (mapcar (Fnext_single_property_change, it_props))
> to avoid counting unrelated properties.

Feel free to present such a more efficient algorithm, and thanks.
And I'm not sure I understand why you think that

  min (mapcar (Fnext_single_property_change, it_props))

will be cheaper than the current algorithm in compute_stop_pos, since
Fnext_single_property_change basically examines the same intervals
again and again for each property in it_props.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> > compute_stop_pos finds the next "stop position" where properties (or
>> > something else of interest to redisplay) change, and when the
>> > iteration gets to that position, handle_stop calls the available
>> > handler methods to do their thing.  The intervals of the text
>> > properties are examined by compute_stop_pos.
>> 
>> Thanks!
>> "stop position" is not triggered by _all_ the properties though.
>> `compute_stop_pos' calculates the largest region where the properties
>> listed in `it_props' ('fontified, 'face, 'invisible, and 'composition)
>> remain the same. If any other property not in the list changes, it is
>> ignored (except `char-property-alias-alist' which may link other
>> properties to 'fontified/face/invisible/composition).
>
> Does this contradict what I wrote? if so, how?

Does not contradict, but adds some details. IMHO, it is important that
not _a_ property should change to "stop". But one of a small set of
properties.

I did not write this to argue about your statement. Just to get a reply
if I missed something when reading the code.

>> Further, handle_stop handlers do search for their corresponding handled
>> property via Fnext_single_property_change, which again iterates over
>> every interval in the buffer until that single property value changes.
>
> If they do this, it's because they need that to do their thing.
> There's no requirement from the handlers to do that.  Moreover, we
> could record the position of the next change of each property, when
> the handler does determine that, and use that in compute_stop_pos, to
> avoid repeating the same search.

That might indeed be one possible optimization.

>> I believe that having a more efficient algorithm to detect where a
>> single property change should speed things up significantly. handle_stop
>> will benefit directly, while `compute_stop_pos' could query
>> min (mapcar (Fnext_single_property_change, it_props))
>> to avoid counting unrelated properties.
>
> Feel free to present such a more efficient algorithm, and thanks.
> And I'm not sure I understand why you think that
>
>   min (mapcar (Fnext_single_property_change, it_props))
>
> will be cheaper than the current algorithm in compute_stop_pos, since
> Fnext_single_property_change basically examines the same intervals
> again and again for each property in it_props.

The algorithm I have in mind is to change interval tree to store several
trees together - a common tree storing segments delimited by _a_
property change + a tree for individual properties. That way, looking up
for next single property change will be a simple call to next_interval for
the property itself + property aliases.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: dmitry@gutov.dev, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Fri, 22 Sep 2023 15:49:21 +0300
> 
> > Feel free to present such a more efficient algorithm, and thanks.
> > And I'm not sure I understand why you think that
> >
> >   min (mapcar (Fnext_single_property_change, it_props))
> >
> > will be cheaper than the current algorithm in compute_stop_pos, since
> > Fnext_single_property_change basically examines the same intervals
> > again and again for each property in it_props.
> 
> The algorithm I have in mind is to change interval tree to store several
> trees together - a common tree storing segments delimited by _a_
> property change + a tree for individual properties. That way, looking up
> for next single property change will be a simple call to next_interval for
> the property itself + property aliases.

Feel free to implement that and benchmark it against the current
implementation.  If it's significantly faster, I';m sure we will
accept the changes.

Thanks.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> The algorithm I have in mind is to change interval tree to store several
>> trees together - a common tree storing segments delimited by _a_
>> property change + a tree for individual properties. That way, looking up
>> for next single property change will be a simple call to next_interval for
>> the property itself + property aliases.
>
> Feel free to implement that and benchmark it against the current
> implementation.  If it's significantly faster, I';m sure we will
> accept the changes.

It is on my todo list.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> On the high-level design level, it should be clear without any need
> for benchmarking that separating redisplay from the main thread could
> bring benefits.  Isn't that what every GUI application out there does?
> So trying to think about that is always a good thing, IMO.

Au contraire, almost all GUI program limit redisplay to their main
threads.

Emacs is not a video game, for which the touchstone of performance is a
measurement taken in ``frames-per-second''.  It is a text editor that
only updates the display subsequent to an editing operation.  That is,
unless you perform more than 60 edits per second and expect an
intervening redisplay after each edit.

Benchmarking redisplay with such measurements is an exercise in fatuity.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: Dmitry Gutov <dmitry@gutov.dev>,  yantar92@posteo.net,  acm@muc.de,
>   incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Wed, 20 Sep 2023 20:21:39 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > On the high-level design level, it should be clear without any need
> > for benchmarking that separating redisplay from the main thread could
> > bring benefits.  Isn't that what every GUI application out there does?
> > So trying to think about that is always a good thing, IMO.
> 
> Au contraire, almost all GUI program limit redisplay to their main
> threads.

??? On Windows at least, the UI thread is a separate thread, not
necessarily the main one.  We have that in Emacs on Windows.

> Emacs is not a video game, for which the touchstone of performance is a
> measurement taken in ``frames-per-second''.  It is a text editor that
> only updates the display subsequent to an editing operation.  That is,
> unless you perform more than 60 edits per second and expect an
> intervening redisplay after each edit.

This sounds as if you are talking about something other than Emacs,
really.  Try running some day with all the redisplay optimizations
turned off and with enough windows/frames visible, and you will see
how far we are from 60 fps goal.  There's a lot of room for
improvement even without being a video game, just an editor.

Or visit Reddit and see how many users complain that Emacs is slower
in displaying stuff than, say, VSCode.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 20/09/2023 17:51, Eli Zaretskii wrote:
>> Emacs is not a video game, for which the touchstone of performance is a
>> measurement taken in ``frames-per-second''.  It is a text editor that
>> only updates the display subsequent to an editing operation.  That is,
>> unless you perform more than 60 edits per second and expect an
>> intervening redisplay after each edit.
> This sounds as if you are talking about something other than Emacs,
> really.  Try running some day with all the redisplay optimizations
> turned off and with enough windows/frames visible, and you will see
> how far we are from 60 fps goal.  There's a lot of room for
> improvement even without being a video game, just an editor.
> 
> Or visit Reddit and see how many users complain that Emacs is slower
> in displaying stuff than, say, VSCode.

I see those voices, and see the couter-opinions as well. But note that 
those that do complain so are likely comparing the simple case of 
one-buffer-one-frame (so redisplaying multiple windows in parallel 
wouldn't quite fix that).

So their complaints can be compounded from different things:

- Anybody using CC Mode with large files might notice latency during 
editing from running before/after-change-functions (because its design 
involves keeping the syntax info up-to-date in the whole buffer).

- People using LSP likely see better performance because of VC Code 
being able to parse the server's output in a different thread (or web 
worker? I haven't seen the exact design). LSP-Mode folks wrote a POC 
branch of Emacs which parallelizes the JSON parsing as well: 
https://www.reddit.com/r/emacs/comments/ymrkyn/async_nonblocking_jsonrpc_or_lsp_performance/ 
Some work toward mainlining this feature (perhaps after generalizing) 
could help. Or maybe the "multiple concurrent interpreters" approach 
could yield similar gains.

- The "snazzy" mode-line packages sometimes slow things down more than 
expected.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Wed, 20 Sep 2023 22:39:47 +0300
> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> - The "snazzy" mode-line packages sometimes slow things down more than 
> expected.

Why shouldn't this be considered part of our problem with redisplay?
Emacs isn't supposed to be fast enough only in "emacs -Q".

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 21/09/2023 07:31, Eli Zaretskii wrote:
>> Date: Wed, 20 Sep 2023 22:39:47 +0300
>> Cc:yantar92@posteo.net,acm@muc.de,incal@dataswamp.org,emacs-devel@gnu.org
>> From: Dmitry Gutov<dmitry@gutov.dev>
>>
>> - The "snazzy" mode-line packages sometimes slow things down more than
>> expected.
> Why shouldn't this be considered part of our problem with redisplay?
> Emacs isn't supposed to be fast enough only in "emacs -Q".

Oh, I never said we don't have problems.

This one should be solved at the source, though (fixing the package so 
that the mode-line redisplays faster). Or perhaps by disallowing :eval - 
if that is at all feasible.

But I suppose throttling mode-line display should help with wayward 
customizations (which is good, of course, all other things equal).

Re: Emacs design and architecture. How about copy-on-write?

[Stefan Kangas]

Dmitry Gutov <dmitry@gutov.dev> writes:

> - People using LSP likely see better performance because of VC Code
> being able to parse the server's output in a different thread (or web
> worker? I haven't seen the exact design). LSP-Mode folks wrote a POC
> branch of Emacs which parallelizes the JSON parsing as well:
> https://www.reddit.com/r/emacs/comments/ymrkyn/async_nonblocking_jsonrpc_or_lsp_performance/
> Some work toward mainlining this feature (perhaps after generalizing)
> could help. Or maybe the "multiple concurrent interpreters" approach
> could yield similar gains.

Could someone please contact them and ask if they plan to upstream it?

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 22/09/2023 01:21, Stefan Kangas wrote:
> Dmitry Gutov<dmitry@gutov.dev>  writes:
> 
>> - People using LSP likely see better performance because of VC Code
>> being able to parse the server's output in a different thread (or web
>> worker? I haven't seen the exact design). LSP-Mode folks wrote a POC
>> branch of Emacs which parallelizes the JSON parsing as well:
>> https://www.reddit.com/r/emacs/comments/ymrkyn/async_nonblocking_jsonrpc_or_lsp_performance/
>> Some work toward mainlining this feature (perhaps after generalizing)
>> could help. Or maybe the "multiple concurrent interpreters" approach
>> could yield similar gains.
> Could someone please contact them and ask if they plan to upstream it?

I think they're too busy and not motivated enough at the moment: 
https://github.com/emacs-lsp/emacs/issues/7

Further, it seems that at least for some users the current solution is 
not working very well: https://github.com/emacs-lsp/emacs/issues/9, but 
that seems macOS specific.

Anyway, I think it might need more work to get into upstreamable shape, 
but it's up for discussion how much it's going to be. Overall, the diff 
is not huge, and the first question would be is how generic we'd want 
this feature to be, or whether a separate JSON-parsing thread is 
more-or-less fine.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> This sounds as if you are talking about something other than Emacs,
> really.  Try running some day with all the redisplay optimizations
> turned off and with enough windows/frames visible, and you will see
> how far we are from 60 fps goal.  There's a lot of room for
> improvement even without being a video game, just an editor.

We don't have a "60FPS goal."  "Frames per second" is a metric that
applies to programs which are perpetually redrawing their windows,
either as fast as the monitor refreshes or as fast as the CPU permits.

I don't type 60 characters per second -- so there is no reason for Emacs
to display at 60 frames per second.

If you open the GUI inspector tool of any Gtk+ program, then enable its
"frames per second" counter, you will quickly recognize that a GUI
program such as a text editor seldom, if ever, redraws itself at such a
rate.

> Or visit Reddit and see how many users complain that Emacs is slower
> in displaying stuff than, say, VSCode.

I seriously doubt redisplay performance is the cause of their plights.
It's much more likely to be GC, slow fontification code, or post command
hooks, all three of which present with near identical symptoms.

There's also the old experiment where Eric Naggum disabled garbage
collection messages, yielding a visible speedup.

Re: Emacs design and architecture. How about copy-on-write?

[Adam Porter]

If I may interject:

> We don't have a "60FPS goal."  "Frames per second" is a metric that
> applies to programs which are perpetually redrawing their windows,
> either as fast as the monitor refreshes or as fast as the CPU permits.
> 
> I don't type 60 characters per second -- so there is no reason for Emacs
> to display at 60 frames per second.
> 
> If you open the GUI inspector tool of any Gtk+ program, then enable its
> "frames per second" counter, you will quickly recognize that a GUI
> program such as a text editor seldom, if ever, redraws itself at such a
> rate.

There would seem to be numerous scenarios in which a 60 FPS (or higher) 
redraw rate would be desired, such as smooth scrolling (i.e. 
pixel-by-pixel at a high speed), whether text or images are in the 
buffer (especially if Emacs one day gains improved support for images, 
i.e. displaying an image across lines of text without splitting it into 
many smaller images).

As well, as we all know, Emacs is much more than merely a text editor; 
it's a platform upon which a variety of different applications are run.

Finally, attaining high redraw rates means leaving a large margin, 
helping to maintain acceptable performance under heavier loads, ones we 
may not anticipate at this time.

So I think it's very much a worthwhile goal to be able to redraw at 60+ FPS.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Adam Porter <adam@alphapapa.net> writes:

> There would seem to be numerous scenarios in which a 60 FPS (or
> higher) redraw rate would be desired, such as smooth scrolling
> (i.e. pixel-by-pixel at a high speed), whether text or images are in
> the buffer (especially if Emacs one day gains improved support for
> images, i.e. displaying an image across lines of text without
> splitting it into many smaller images).

Pixel-by-pixel scrolling triggers redisplay optimizations, and Emacs is
capable of equaling a 60 or 30 Hz display refresh rate when these
optimizations are applied.  This was measured when
pixel-scroll-precision-mode was first written.

> As well, as we all know, Emacs is much more than merely a text editor;
> it's a platform upon which a variety of different applications are
> run.

All of which edit or present text.

> Finally, attaining high redraw rates means leaving a large margin,
> helping to maintain acceptable performance under heavier loads, ones
> we may not anticipate at this time.
>
> So I think it's very much a worthwhile goal to be able to redraw at
> 60+ FPS.

I disagree.  It is by far more important to run Lisp (such as Gnus, or
JSON RPC decoding) in the background.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: dmitry@gutov.dev,  yantar92@posteo.net,  acm@muc.de,
>   incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 08:41:29 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > This sounds as if you are talking about something other than Emacs,
> > really.  Try running some day with all the redisplay optimizations
> > turned off and with enough windows/frames visible, and you will see
> > how far we are from 60 fps goal.  There's a lot of room for
> > improvement even without being a video game, just an editor.
> 
> We don't have a "60FPS goal."  "Frames per second" is a metric that
> applies to programs which are perpetually redrawing their windows,
> either as fast as the monitor refreshes or as fast as the CPU permits.

We don't have to interpret "60 fps" too literally.  A possible
Emacs-friendly interpretation is "60 display updates per second", for
example.  Here's an experiment to try:

  (global-set-key "\C-z" (function (lambda () (interactive) (scroll-up 1))))

Then visit a large file and lean on C-z.

Another possibility is to lean of C-v.

> I don't type 60 characters per second -- so there is no reason for Emacs
> to display at 60 frames per second.

Leaning on a key, as in the examples above, will produce input events
at a relatively high rate (albeit usually lower than 60 per sec), each
one of them requiring some kind of redisplay.  Even leaning on C-f
triggers redisplay at high rate.  I suggest to try this in various
non-dash-Q configurations and see how we fare in these situations.
There's nothing outlandish in expecting an editor to keep up with
high-rate scrolling commands, I hope you agree with that at least.

> > Or visit Reddit and see how many users complain that Emacs is slower
> > in displaying stuff than, say, VSCode.
> 
> I seriously doubt redisplay performance is the cause of their plights.

You can doubt all you want, but some of what they say is definitely
related to redisplay, IMNSHO.

> There's also the old experiment where Eric Naggum disabled garbage
> collection messages, yielding a visible speedup.

That's orthogonal to the issue at hand.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> We don't have to interpret "60 fps" too literally.  A possible
> Emacs-friendly interpretation is "60 display updates per second", for
> example.  Here's an experiment to try:
>
>   (global-set-key "\C-z" (function (lambda () (interactive) (scroll-up 1))))
>
> Then visit a large file and lean on C-z.
>
> Another possibility is to lean of C-v.
>
>> I don't type 60 characters per second -- so there is no reason for Emacs
>> to display at 60 frames per second.
>
> Leaning on a key, as in the examples above, will produce input events
> at a relatively high rate (albeit usually lower than 60 per sec), each
> one of them requiring some kind of redisplay.  Even leaning on C-f
> triggers redisplay at high rate.  I suggest to try this in various
> non-dash-Q configurations and see how we fare in these situations.
> There's nothing outlandish in expecting an editor to keep up with
> high-rate scrolling commands, I hope you agree with that at least.

I agree, but slow scrolling is not redisplay's fault.  If I type:

  M-: (jit-lock-fontify-all) RET

or enable c-ts-mode prior to leaning on C-v, within an Emacs session
with a 790 MiB resident set that has been executing continuously for 32
days, then Emacs scrolls (xterm.c and xdisp.c) as fast as any other
editor on my system.  Conceivably even faster than some others, that is
to say the VS Code demonstration site at vscode.dev.

> You can doubt all you want, but some of what they say is definitely
> related to redisplay, IMNSHO.

Any examples?  Because my experience with p-s-p-m demonstrates that
redisplay is absolutely capable of matching the display refresh rate
while scrolling, the very cornerstone of
`pixel-scroll-precision-use-momentum'.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: dmitry@gutov.dev,  yantar92@posteo.net,  acm@muc.de,
>   incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 15:48:58 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Leaning on a key, as in the examples above, will produce input events
> > at a relatively high rate (albeit usually lower than 60 per sec), each
> > one of them requiring some kind of redisplay.  Even leaning on C-f
> > triggers redisplay at high rate.  I suggest to try this in various
> > non-dash-Q configurations and see how we fare in these situations.
> > There's nothing outlandish in expecting an editor to keep up with
> > high-rate scrolling commands, I hope you agree with that at least.
> 
> I agree, but slow scrolling is not redisplay's fault.  If I type:
> 
>   M-: (jit-lock-fontify-all) RET
> 
> or enable c-ts-mode prior to leaning on C-v, within an Emacs session
> with a 790 MiB resident set that has been executing continuously for 32
> days, then Emacs scrolls (xterm.c and xdisp.c) as fast as any other
> editor on my system.

Then try leaning on C-n or C-p _after_ everything is already
fontified.  You will still see that Emacs sometimes cannot keep up,
especially if lines are not too short.

You will never succeed in convincing me that our redisplay is as fast
as I'd like it to be.  I've seen too many proofs to the contrary.

> > You can doubt all you want, but some of what they say is definitely
> > related to redisplay, IMNSHO.
> 
> Any examples?

Sorry, you will have to find them yourself.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> Then try leaning on C-n or C-p _after_ everything is already
> fontified.  You will still see that Emacs sometimes cannot keep up,
> especially if lines are not too short.

Long lines are, at worst, infrequently encountered in source code,
aren't they?  And our troubles with long lines are an algorithmic
impediment, which cannot be ameliorated merely by redisplaying each
window on a different CPU.

> You will never succeed in convincing me that our redisplay is as fast
> as I'd like it to be.  I've seen too many proofs to the contrary.

From my POV, we frequently encounter circumstances where GC, Font Lock,
process filters or post-command-hooks precipitate difficulties keeping
Emacs responsive to user input.  Seldom are such problems unequivocally
attributed to redisplay itself.

I guess we can only agree to disagree.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Po Lu <luangruo@yahoo.com> writes:

>> Then try leaning on C-n or C-p _after_ everything is already
>> fontified.  You will still see that Emacs sometimes cannot keep up,
>> especially if lines are not too short.
>
> Long lines are, at worst, infrequently encountered in source code,
> aren't they?  And our troubles with long lines are an algorithmic
> impediment, which cannot be ameliorated merely by redisplaying each
> window on a different CPU.

I think that there is at least one way to address long lines using
asynchronous redisplay - put a placeholder on the problematic line and
continue calculating the actual rendering in the background instead.
That will not force us to compromise between rendering time and
accuracy, as we do now, with long-line-threshold.

Similar approach might be used to render mode lines - render a
placeholder until it is fully calculated, keeping Emacs responsive.

This idea is also relevant to a situation when asynchronous threads
"locks" a buffer whose window is visible. If a user tries to switch to
such buffer, it would be nice if Emacs does not hang until the lock is
released.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 21/09/2023 12:39, Ihor Radchenko wrote:
> Po Lu<luangruo@yahoo.com>  writes:
> 
>>> Then try leaning on C-n or C-p_after_  everything is already
>>> fontified.  You will still see that Emacs sometimes cannot keep up,
>>> especially if lines are not too short.
>> Long lines are, at worst, infrequently encountered in source code,
>> aren't they?  And our troubles with long lines are an algorithmic
>> impediment, which cannot be ameliorated merely by redisplaying each
>> window on a different CPU.
> I think that there is at least one way to address long lines using
> asynchronous redisplay - put a placeholder on the problematic line and
> continue calculating the actual rendering in the background instead.
> That will not force us to compromise between rendering time and
> accuracy, as we do now, with long-line-threshold.

Until you're laid out the long line, you don't know which screen line it 
will finish at, or at which height specifically (it might have images, 
or taller text due to faces, etc). So you can't render the remainder of 
the buffer either.

> Similar approach might be used to render mode lines - render a
> placeholder until it is fully calculated, keeping Emacs responsive.

I hope by "placeholder" you mean the previous rendered image of it. But 
then the mode-line won't be refreshed at 60fps still, which some said is 
a good goal? (I tentatively agree).

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Dmitry Gutov <dmitry@gutov.dev> writes:

>> I think that there is at least one way to address long lines using
>> asynchronous redisplay - put a placeholder on the problematic line and
>> continue calculating the actual rendering in the background instead.
>> That will not force us to compromise between rendering time and
>> accuracy, as we do now, with long-line-threshold.
>
> Until you're laid out the long line, you don't know which screen line it 
> will finish at, or at which height specifically (it might have images, 
> or taller text due to faces, etc). So you can't render the remainder of 
> the buffer either.

What I had in mind is the processing to happen in two stages: (1)
calculate "quick-and-dirty" layout; (2) start calculating "accurate"
layout. If calculating "accurate" layout takes long time, go ahead and
draw the "quick-and-dirty" version on the glass, while "accurate"
version continues being computed in the background.

Of course, this threshold should be configurable.

>> Similar approach might be used to render mode lines - render a
>> placeholder until it is fully calculated, keeping Emacs responsive.
>
> I hope by "placeholder" you mean the previous rendered image of it.

More precisely, what I had in mind is the old glyph matrix + some
indication that the rendering is not up-to-date (like classic sand clock
icon)

> ... But then the mode-line won't be refreshed at 60fps still, which
> some said is a good goal? (I tentatively agree).

I also agree that it is a good goal.

The scenario I had in mind is poorly written third-party mode line
packages that, for example, query git on every redisplay. There is
nothing we can do about poor Elisp code in third-party packages, but the
proposed approach will at least prevent Emacs being laggy or hanging in
the eyes of the user.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 21/09/2023 13:48, Ihor Radchenko wrote:
> Dmitry Gutov<dmitry@gutov.dev>  writes:
> 
>>> I think that there is at least one way to address long lines using
>>> asynchronous redisplay - put a placeholder on the problematic line and
>>> continue calculating the actual rendering in the background instead.
>>> That will not force us to compromise between rendering time and
>>> accuracy, as we do now, with long-line-threshold.
>> Until you're laid out the long line, you don't know which screen line it
>> will finish at, or at which height specifically (it might have images,
>> or taller text due to faces, etc). So you can't render the remainder of
>> the buffer either.
> What I had in mind is the processing to happen in two stages: (1)
> calculate "quick-and-dirty" layout; (2) start calculating "accurate"
> layout. If calculating "accurate" layout takes long time, go ahead and
> draw the "quick-and-dirty" version on the glass, while "accurate"
> version continues being computed in the background.
> 
> Of course, this threshold should be configurable.
> 
>>> Similar approach might be used to render mode lines - render a
>>> placeholder until it is fully calculated, keeping Emacs responsive.
>> I hope by "placeholder" you mean the previous rendered image of it.
> More precisely, what I had in mind is the old glyph matrix + some
> indication that the rendering is not up-to-date (like classic sand clock
> icon)

Any visible indicators of incomplete layouts or "not yet updated" icons 
are going to be a visual nuisance if the refresh speed is still above 
5fps. So we should be careful with those.

And even the "slow" mode-line packages still manage to maintain at least 
5fps, I believe.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Dmitry Gutov <dmitry@gutov.dev> writes:

>>> I hope by "placeholder" you mean the previous rendered image of it.
>> More precisely, what I had in mind is the old glyph matrix + some
>> indication that the rendering is not up-to-date (like classic sand clock
>> icon)
>
> Any visible indicators of incomplete layouts or "not yet updated" icons 
> are going to be a visual nuisance if the refresh speed is still above 
> 5fps. So we should be careful with those.

Sure. This is a minor detail that can be customizeable, for example.

> And even the "slow" mode-line packages still manage to maintain at least 
> 5fps, I believe.

Nope. 0.2 sec is the delay that is barely noticeable. When "slow"
mode-line packages affect users it is usually much worse than 5fps.
(Though sometimes it is due to redisplay being fired frequently, not the
individual refresh times being too large).

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 21/09/2023 14:17, Ihor Radchenko wrote:
>> And even the "slow" mode-line packages still manage to maintain at least
>> 5fps, I believe.
> Nope. 0.2 sec is the delay that is barely noticeable. When "slow"
> mode-line packages affect users it is usually much worse than 5fps.
> (Though sometimes it is due to redisplay being fired frequently, not the
> individual refresh times being too large).

My own experience is finding certain mode-lines that look okay on the 
first glance, but then after measuring, finding them to be the chief 
contributor to the lower refresh rate. Those might refresh well above 
10fps, but spending 100ms (or even 50ms) on a mode-line is ridiculous.

Delays which are noticeable by humans start at around 100ms for random 
ones. But if the goal is 60fps, redisplay should finish at below 2ms.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Po Lu <luangruo@yahoo.com>, Eli Zaretskii <eliz@gnu.org>, acm@muc.de,
>  incal@dataswamp.org, emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 10:48:25 +0000
> 
> Dmitry Gutov <dmitry@gutov.dev> writes:
> 
> >> I think that there is at least one way to address long lines using
> >> asynchronous redisplay - put a placeholder on the problematic line and
> >> continue calculating the actual rendering in the background instead.
> >> That will not force us to compromise between rendering time and
> >> accuracy, as we do now, with long-line-threshold.
> >
> > Until you're laid out the long line, you don't know which screen line it 
> > will finish at, or at which height specifically (it might have images, 
> > or taller text due to faces, etc). So you can't render the remainder of 
> > the buffer either.
> 
> What I had in mind is the processing to happen in two stages: (1)
> calculate "quick-and-dirty" layout; (2) start calculating "accurate"
> layout. If calculating "accurate" layout takes long time, go ahead and
> draw the "quick-and-dirty" version on the glass, while "accurate"
> version continues being computed in the background.
> 
> Of course, this threshold should be configurable.
> 
> >> Similar approach might be used to render mode lines - render a
> >> placeholder until it is fully calculated, keeping Emacs responsive.
> >
> > I hope by "placeholder" you mean the previous rendered image of it.
> 
> More precisely, what I had in mind is the old glyph matrix + some
> indication that the rendering is not up-to-date (like classic sand clock
> icon)

You are basically proposing us to provide broken, incorrect, and
outdated display in some cases.  That won't fly, so it's a
non-starter.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 21/09/2023 16:00, Eli Zaretskii wrote:
> You are basically proposing us to provide broken, incorrect, and
> outdated display in some cases.  That won't fly, so it's a
> non-starter.

If might prove an okay experience, if the "outdated" part is within 
certain bounds. Like if the current buffer refreshes at 30/60fps, and 
the mode-line at 10/20fps, for example.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Thu, 21 Sep 2023 16:30:00 +0300
> Cc: luangruo@yahoo.com, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> On 21/09/2023 16:00, Eli Zaretskii wrote:
> > You are basically proposing us to provide broken, incorrect, and
> > outdated display in some cases.  That won't fly, so it's a
> > non-starter.
> 
> If might prove an okay experience, if the "outdated" part is within 
> certain bounds. Like if the current buffer refreshes at 30/60fps, and 
> the mode-line at 10/20fps, for example.

That's not what was proposed.  The proposal was to do a
"quick-and-dirty" layout first, and use the results if the "accurate"
layout takes too long.  The quick-and-dirty layout can only be based
on ignoring changes in fonts and disregarding images and stuff like
that, so the screen lines will be wrong, and you will see them jump
and/or rearrange after some delay, which could be some seconds.  Some
browsers do that when they need to download images, and it always jars
me when that happens.  Usually, I also lose the place where I was
reading.

I hope Emacs will never behave like that.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 21/09/2023 16:44, Eli Zaretskii wrote:
>> Date: Thu, 21 Sep 2023 16:30:00 +0300
>> Cc: luangruo@yahoo.com, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
>> From: Dmitry Gutov <dmitry@gutov.dev>
>>
>> On 21/09/2023 16:00, Eli Zaretskii wrote:
>>> You are basically proposing us to provide broken, incorrect, and
>>> outdated display in some cases.  That won't fly, so it's a
>>> non-starter.
>>
>> If might prove an okay experience, if the "outdated" part is within
>> certain bounds. Like if the current buffer refreshes at 30/60fps, and
>> the mode-line at 10/20fps, for example.
> 
> That's not what was proposed.  The proposal was to do a
> "quick-and-dirty" layout first, and use the results if the "accurate"
> layout takes too long.

I think I've also commented on the potential problems in my first reply 
to that. But since it's just an abstract suggestion at this point, we 
can try and see the constructive aspects of it.

> The quick-and-dirty layout can only be based
> on ignoring changes in fonts and disregarding images and stuff like
> that, so the screen lines will be wrong, and you will see them jump
> and/or rearrange after some delay, which could be some seconds.  Some
> browsers do that when they need to download images, and it always jars
> me when that happens.  Usually, I also lose the place where I was
> reading.

Some details on what the browsers really do:

- When the images are not downloaded yet, it's possible that the browser 
doesn't know how to lay out the page yet, and the time to download sad 
images is not guaranteed. So what you're describing is really the 
best-effort approach, which has been most noticeable in the past, over 
slow network connections (or in countries/locations with poor network 
coverage even nowadays). Either way, it's a best practice for the web 
page authors to include the dimensions of the images in the <img> tags 
-- when they are present, the layout can be done correctly even while 
the images are not downloaded yet.

- If a web page is complex enough, and I scroll it down after opening 
very quickly, it can happen so Firefox doesn't manage to render the page 
quickly enough, perhaps due to other load. When that happens, it shows 
the bottom of the page in a sort of blurry haze (which is replaced as 
soon as it's ready). Overall, it feels good enough usability-wise, 
because it doesn't look jerky or "blinky" or etc. And of course it's a 
rare occasion overall.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Dmitry Gutov <dmitry@gutov.dev> writes:

> - If a web page is complex enough, and I scroll it down after opening 
> very quickly, it can happen so Firefox doesn't manage to render the page 
> quickly enough, perhaps due to other load. When that happens, it shows 
> the bottom of the page in a sort of blurry haze (which is replaced as 
> soon as it's ready). Overall, it feels good enough usability-wise, 
> because it doesn't look jerky or "blinky" or etc. And of course it's a 
> rare occasion overall.

I think that partial rendering of a buffer might be actually tricky.
In particular, when user tries to "move into" the not-yet-rendered part
of the buffer. Many point motion commands re-use parts of the display
code to determine where to move the point to. I am not sure how to
address such situation without blocking Emacs.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> If might prove an okay experience, if the "outdated" part is within 
>> certain bounds. Like if the current buffer refreshes at 30/60fps, and 
>> the mode-line at 10/20fps, for example.
>
> That's not what was proposed.  The proposal was to do a
> "quick-and-dirty" layout first, and use the results if the "accurate"
> layout takes too long.  The quick-and-dirty layout can only be based
> on ignoring changes in fonts and disregarding images and stuff like
> that, so the screen lines will be wrong, and you will see them jump
> and/or rearrange after some delay, which could be some seconds.  Some
> browsers do that when they need to download images, and it always jars
> me when that happens.  Usually, I also lose the place where I was
> reading.
>
> I hope Emacs will never behave like that.

I can see how this can be annoying.
What about "quick-and-dirty" layout being "empty" window that is also
blocked for user interaction. (I am assuming that redisplay is
asynchronous here). Then, the user will be blocked from interacting
with a single problematic window being redisplayed, but could still work
with other windows/buffers without waiting for Emacs to "unhang".

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Dmitry Gutov <dmitry@gutov.dev>, luangruo@yahoo.com, acm@muc.de,
>  incal@dataswamp.org, emacs-devel@gnu.org
> Date: Fri, 22 Sep 2023 10:28:23 +0000
> 
> What about "quick-and-dirty" layout being "empty" window that is also
> blocked for user interaction. (I am assuming that redisplay is
> asynchronous here). Then, the user will be blocked from interacting
> with a single problematic window being redisplayed, but could still work
> with other windows/buffers without waiting for Emacs to "unhang".

You will need to describe in more detail what you mean by "user
interaction with a window".  In Emacs, users don't interact with
windows, they interact with Emacs.  Did you mean that such a window
should not be the selected one?  If so, does it mean Emacs should make
another window to be the selected one if the selected one takes too
long to display?  If that is what you mean, I'm not sure users will
like that.  For example, touch typists could be tricked into modifying
a completely different buffer in this way.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> What about "quick-and-dirty" layout being "empty" window that is also
>> blocked for user interaction. (I am assuming that redisplay is
>> asynchronous here). Then, the user will be blocked from interacting
>> with a single problematic window being redisplayed, but could still work
>> with other windows/buffers without waiting for Emacs to "unhang".
>
> You will need to describe in more detail what you mean by "user
> interaction with a window".  In Emacs, users don't interact with
> windows, they interact with Emacs.  Did you mean that such a window
> should not be the selected one?

I meant that such a window can be selected, but attempting to do
anything that interacts with the window should cause user-error while
the window is being processed by redisplay.

I imagine that users will be allowed to, at least, C-x o away from the
window or switch buffer. But not enter text or run arbitrary commands.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: dmitry@gutov.dev, luangruo@yahoo.com, acm@muc.de, incal@dataswamp.org,
>  emacs-devel@gnu.org
> Date: Fri, 22 Sep 2023 13:06:00 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > You will need to describe in more detail what you mean by "user
> > interaction with a window".  In Emacs, users don't interact with
> > windows, they interact with Emacs.  Did you mean that such a window
> > should not be the selected one?
> 
> I meant that such a window can be selected, but attempting to do
> anything that interacts with the window should cause user-error while
> the window is being processed by redisplay.
> 
> I imagine that users will be allowed to, at least, C-x o away from the
> window or switch buffer. But not enter text or run arbitrary commands.

That is still far from complete.  But in any case, this seems to
require addition of tests to many Emacs primitives, which would check
if the selected window is "kosher", and if so, produce a user-error.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: dmitry@gutov.dev,  yantar92@posteo.net,  acm@muc.de,
>   incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 17:25:07 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Then try leaning on C-n or C-p _after_ everything is already
> > fontified.  You will still see that Emacs sometimes cannot keep up,
> > especially if lines are not too short.
> 
> Long lines are, at worst, infrequently encountered in source code,
> aren't they?

_Very_ long (as in: many megabytes) lines are indeed rare.  But what I
said was "not too short", meaning that don't try this with 5-character
or 20-character lines and conclude that all is well.  Source code with
several dozens of characters are still frequent enough.

> And our troubles with long lines are an algorithmic impediment,
> which cannot be ameliorated merely by redisplaying each window on a
> different CPU.

Someone already said that, and I explained why this is false.

> I guess we can only agree to disagree.

It's about time.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 20/09/2023 14:28, Eli Zaretskii wrote:
>> Date: Tue, 19 Sep 2023 23:21:46 +0300
>> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
>> From: Dmitry Gutov <dmitry@gutov.dev>
>>
>> On 19/09/2023 20:54, Eli Zaretskii wrote:
>>>
>>> How do you know that parallel redisplay will not solve this?  This can
>>> only be obvious when the detailed design of that is presented.  Until
>>> then, it's anyone's guess.
>>
>> It's not 100%, but seems logical: the problem with long lines is that
>> displaying a single line took non-linear amount of time proportional to
>> its length. To be able to layout it in parallel, we would somehow have
>> to be able to split it into independent pieces (perhaps using some
>> caching mechanism?, IDK). If we are actually able to do that (which
>> seems difficult), a non-parallel redisplay algorithm should happily use
>> the same mid-line checkpoint information to work on smaller pieces of
>> the line, likewise increasing the speed.
> 
> You are considering only the redisplay of that single window which has
> long lines.  But what about the other windows, which perhaps don't
> have long lines?  And what about the main thread of Emacs itself,
> which freezes for as long as redisplay didn't finish, thus preventing
> user interaction and responsiveness in general?  These factors should
> not be neglected.

Splitting an N^3 program in two to run in half the time won't make it 
have adequate performance. When the problem is algorithmic, we'll have 
to fix it as such.

>> But I think we've much improved on the issue by reducing the complexity
>> instead (correct me if I'm wrong here).
> 
> If you mean the long-lines improvements in Emacs 29, then we traded
> off correctness in at least some cases.  It wasn't for free.

I see.

Well, we definitely did that WRT to font-lock (the part which we might 
tweak or roll back in the future). I wasn't sure if that's also what 
happened in the deep of the display engine as well.

>>> Anyway, you asked for evidence that redisplay could benefit from
>>> performance boost, and I gave you some.  Now you for some reason want
>>> to claim that my evidence doesn't convince you, but it still is
>>> evidence, right?
>>
>> I was looking for other examples, to be honest. Like, for example,
>> evidence that redisplay is something that keeps an average Emacs session
>> from running at 60fps. Or even at 30fps. That would make it a bottleneck.
> 
> With enough text properties and overlays, you can definitely see a
> tangible slowdown in frame rate.  E.g., Org developers don't want to
> use text properties because they slow down redisplay, and thus they
> consider them not scalable enough.
> 
>>> You seem to be opposed to attempts to explore ways of making Emacs
>>> less single-threaded than it is today, unless someone provides a
>>> proof, up front, that this will necessarily solve some particular
>>> problem?  Why? what harm could that possibly do, if it succeeds?  And
>>> if it doesn't succeed, at least we will have learned something
>>> probably useful for the future.
>>
>> It is my experience that good benchmarking often helps with changing the
>> design as well. Or coming up with a new one (there are a lot of options
>> for how one could proceed).
> 
> On the high-level design level, it should be clear without any need
> for benchmarking that separating redisplay from the main thread could
> bring benefits.  Isn't that what every GUI application out there does?
> So trying to think about that is always a good thing, IMO.

Okay, here's a question that I should have started with: what kind of 
parallelism are we discussing?

A) Initially I figured it's the ability to render a single window using 
multiple threads of execution. It's the one my mind immediately went to, 
but might the hardest of the bunch because it would require us to 
parallelize the display algorithm for a single buffer.

B) Being able to render different windows/buffers fully in parallel. I 
think that requires us to implement concurrent Lisp threads, at the very 
least. That's likely to drag down the single-thread performance (though 
it's hard to predict by how much).

C) Having only a separate (not Lisp) thread for GUI might help with 
responsiveness somewhat (by throttling certain expensive windows down, 
for example), but overall it might not improve by much. Though I suppose 
it could render in parallel those buffers which don't need to run Lisp 
to display? Anyway it would be synchronized to the one Lisp interpreter.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Wed, 20 Sep 2023 22:22:53 +0300
> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> Okay, here's a question that I should have started with: what kind of 
> parallelism are we discussing?

Not clear yet.

> A) Initially I figured it's the ability to render a single window using 
> multiple threads of execution. It's the one my mind immediately went to, 
> but might the hardest of the bunch because it would require us to 
> parallelize the display algorithm for a single buffer.
> 
> B) Being able to render different windows/buffers fully in parallel. I 
> think that requires us to implement concurrent Lisp threads, at the very 
> least. That's likely to drag down the single-thread performance (though 
> it's hard to predict by how much).
> 
> C) Having only a separate (not Lisp) thread for GUI might help with 
> responsiveness somewhat (by throttling certain expensive windows down, 
> for example), but overall it might not improve by much. Though I suppose 
> it could render in parallel those buffers which don't need to run Lisp 
> to display? Anyway it would be synchronized to the one Lisp interpreter.

All of the above need some fundamental issues to be resolved to enable
any of them.  I think at this point it is best to try to look for
solutions for those fundamental issues, and only after that see which
of the above are possible and worth our while.

Re: Emacs design and architecture. How about copy-on-write?

[Richard Stallman]

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

  > It's not 100%, but seems logical: the problem with long lines is that 
  > displaying a single line took non-linear amount of time proportional to 
  > its length. To be able to layout it in parallel, we would somehow have 
  > to be able to split it into independent pieces (perhaps using some 
  > caching mechanism?, IDK).

The usual source of very long lines, in my experience, is when people
write text and let their lines run on and on.  Many people's email
user agents encourage that.

I usually use fill-region to fix the problem, if therr are blank lines
betwee these single-line paragaphs.

Peraps we can designheeuristics for finding tre paragaph bondaries and
insert blak ines between them.  Then we could full the text
autoimatically in more cases.  This would not only fix the slowness,'it
would als make the text easier to read.


-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> (I suggest this because I feel that xdisp is a rabbit hole we may sink
>> in instead of doing something more productive)
>
> I'm actually of the opposite opinion.  I think trying to parallelize
> redisplay is a lower-hanging fruit, and if successful, it could bring
> non-trivial gains to Emacs even if the rest remains single-threaded.

Without having Elisp async threads, what you suggest is only possible
for the non-Elisp parts of the redisplay.

May you list which C-level parts of the redisplay are known to be slow?

AFAIU, long-lines performance is largely problematic when running Elisp.
(Also, isn't it solved already?)

Another one you mentioned is displaying many frames. But isn't it
optimized by the part of the code that delays redisplay of frames that
are not visible? Or does Stefan (or anyone) tend to have so many
_visible_ frames?

>> I am particularly worried about scenarios when window geometry changes
>> by asynchronous threads. Or, say, face definitions. Imagine that it
>> happens at point when we are already drawing the now obsolete geometry
>> onto glass?
>
> xdisp.c has solutions for these two (and other similar) situations.
> The problems have nothing to do with parallelism, they happen today
> because we call Lisp at certain places in the display engine.

Yes, but now we know exactly in which segments of the code the geometry
might change. And check for it in strategic places.

In the case of asynchronous threads, the geometry may change any time
(when another threads happens to run something that affects geometry),
which is not accounted for by the current code.

>> > We tried that already, with the existing Lisp threads.  One reason why
>> > those are almost never used is that the display issue was left
>> > unresolved.
>> 
>> That might be one reason, but not the only reason. And certainly not the
>> most important reason for the use cases where I did try to use threads
>> myself.
>
> There's more than one reason, that's true.  But it doesn't change the
> fact that all those problems have to be resolved before we have
> reasonably usable threads.

I disagree. Yes, _all_ the problems are to be solved eventually. But
solving _some_ of the problems will already be an improvement. IMHO, it
is not all-or-nothing; we can split the problem into several
sub-problems and solve them one by one.

>> As we discussed previously, a number of Elisp programs can benefit from
>> async threads even when redisplay is not asynchronous - network queries
>> (gnus), text parsing (org-mode, slow LSP server communication, xml
>> processing).
>
> You forget that almost every Lisp program in Emacs either displays
> something or affects stuff that affects redisplay.  It's easy to
> forget, I know, because in Emacs redisplay "just happens" by some
> magic.

I don't forget that. However, we do not have to make each and every
thread _fully_ asynchronous. It is often enough to process the
performance bottlenecks asynchronously. After that processing, we can go
ahead and present the results synchronously to user.

Let me provide a more concrete example.
Consider something as simple as grepping across project files.
The process of grepping involves: (1) opening and searching many files;
(2) presenting results to the user. Stage (1) does not really involve
user interaction or redisplay and can greatly benefit from asynchronous
threads - we can simply search multiple files at the same time. Then,
even if stage (2) has to be synchronous, it does not matter - stage (1)
is what takes most of the time and makes the user wait.

>> To be clear, it would indeed be nice to have async redisplay.
>
> I'm not talking about async redisplay, I'm talking about the ability
> of non-main threads to display something or do something that would
> cause redisplay change the stuff on the glass.

Then, how will it be possible without first having async Elisp threads?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Wed, 20 Sep 2023 09:47:46 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> (I suggest this because I feel that xdisp is a rabbit hole we may sink
> >> in instead of doing something more productive)
> >
> > I'm actually of the opposite opinion.  I think trying to parallelize
> > redisplay is a lower-hanging fruit, and if successful, it could bring
> > non-trivial gains to Emacs even if the rest remains single-threaded.
> 
> Without having Elisp async threads, what you suggest is only possible
> for the non-Elisp parts of the redisplay.

The display engine is written in C, not in Lisp.  What to do with the
few calls into Lisp we do in redisplay is an open question, but being
able to call Lisp from redisplay and being able to run several async
Lisp threads concurrently are two very different problems (although if
someone comes up with a solution for the latter, that would probably
solve the former as well).

> May you list which C-level parts of the redisplay are known to be slow?

I already did, in response to Dmitry's identical question.

> AFAIU, long-lines performance is largely problematic when running Elisp.

No, the slow parts are pure C.

> (Also, isn't it solved already?)

Not solved, but "bypassed".  The solution does have its disadvantages,
although we found them to be a much lesser evil than the original
problem.

> Another one you mentioned is displaying many frames. But isn't it
> optimized by the part of the code that delays redisplay of frames that
> are not visible? Or does Stefan (or anyone) tend to have so many
> _visible_ frames?

The latter.

> >> I am particularly worried about scenarios when window geometry changes
> >> by asynchronous threads. Or, say, face definitions. Imagine that it
> >> happens at point when we are already drawing the now obsolete geometry
> >> onto glass?
> >
> > xdisp.c has solutions for these two (and other similar) situations.
> > The problems have nothing to do with parallelism, they happen today
> > because we call Lisp at certain places in the display engine.
> 
> Yes, but now we know exactly in which segments of the code the geometry
> might change. And check for it in strategic places.

No, we don't.  We check the indications of this when a window or a
frame has been processed, that's all.

> In the case of asynchronous threads, the geometry may change any time
> (when another threads happens to run something that affects geometry),
> which is not accounted for by the current code.

The geometry cannot change by itself, because redisplay doesn't change
it.  It just detects the situation where the geometry must change, and
computes the variables that would determine the new geometry.  Then it
triggers resizing and recomputation of the geometry before retrying
redisplay.  The trigger to resize can be delivered to all redisplaying
threads, which will make them stop what they are doing, and then retry
after resize.

> >> > We tried that already, with the existing Lisp threads.  One reason why
> >> > those are almost never used is that the display issue was left
> >> > unresolved.
> >> 
> >> That might be one reason, but not the only reason. And certainly not the
> >> most important reason for the use cases where I did try to use threads
> >> myself.
> >
> > There's more than one reason, that's true.  But it doesn't change the
> > fact that all those problems have to be resolved before we have
> > reasonably usable threads.
> 
> I disagree. Yes, _all_ the problems are to be solved eventually. But
> solving _some_ of the problems will already be an improvement. IMHO, it
> is not all-or-nothing; we can split the problem into several
> sub-problems and solve them one by one.

You've lost context, and effectively changed the subject, so now this
sub-thread is not useful anymore.  To recap, I was trying to explain
why the display aspects of any concurrency cannot be disregarded if we
want to have a workable solution that can be used in practice.

> >> As we discussed previously, a number of Elisp programs can benefit from
> >> async threads even when redisplay is not asynchronous - network queries
> >> (gnus), text parsing (org-mode, slow LSP server communication, xml
> >> processing).
> >
> > You forget that almost every Lisp program in Emacs either displays
> > something or affects stuff that affects redisplay.  It's easy to
> > forget, I know, because in Emacs redisplay "just happens" by some
> > magic.
> 
> I don't forget that. However, we do not have to make each and every
> thread _fully_ asynchronous. It is often enough to process the
> performance bottlenecks asynchronously. After that processing, we can go
> ahead and present the results synchronously to user.

This assumes the display is always in the end.  But that is a false
assumption in Emacs: there are progress messages, there are prompts
and requests for confirmation, there are display updates to show the
stuff processed so far, etc.

> Let me provide a more concrete example.
> Consider something as simple as grepping across project files.
> The process of grepping involves: (1) opening and searching many files;
> (2) presenting results to the user. Stage (1) does not really involve
> user interaction or redisplay and can greatly benefit from asynchronous
> threads - we can simply search multiple files at the same time. Then,
> even if stage (2) has to be synchronous, it does not matter - stage (1)
> is what takes most of the time and makes the user wait.

You describe an Emacs without async subprocesses -- this is how it
works on MSDOS, for example.  On more capable systems we display in
parallel with running Grep.

> > I'm not talking about async redisplay, I'm talking about the ability
> > of non-main threads to display something or do something that would
> > cause redisplay change the stuff on the glass.
> 
> Then, how will it be possible without first having async Elisp threads?

Async Lisp threads is a much harder problem to solve.  If we solve it,
this one will also be solved; but the opposite is not true.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> AFAIU, long-lines performance is largely problematic when running Elisp.
>
> No, the slow parts are pure C.
>
>> (Also, isn't it solved already?)
>
> Not solved, but "bypassed".  The solution does have its disadvantages,
> although we found them to be a much lesser evil than the original
> problem.

May you point to the xdisp.c function that is being slow?

>> Another one you mentioned is displaying many frames. But isn't it
>> optimized by the part of the code that delays redisplay of frames that
>> are not visible? Or does Stefan (or anyone) tend to have so many
>> _visible_ frames?
>
> The latter.

Ok. But is it possible to redisplay the whole frame without ever calling Elisp?

>> > There's more than one reason, that's true.  But it doesn't change the
>> > fact that all those problems have to be resolved before we have
>> > reasonably usable threads.
>> 
>> I disagree. Yes, _all_ the problems are to be solved eventually. But
>> solving _some_ of the problems will already be an improvement. IMHO, it
>> is not all-or-nothing; we can split the problem into several
>> sub-problems and solve them one by one.
>
> You've lost context, and effectively changed the subject, so now this
> sub-thread is not useful anymore.  To recap, I was trying to explain
> why the display aspects of any concurrency cannot be disregarded if we
> want to have a workable solution that can be used in practice.

I believe that I did not lose the context. Unless I misunderstand
something.

What I suggested is to defer the redisplay concurrency and leave it
synchronous (interlocked) for now. Concurrency of Elisp that does not
trigger redisplay can also be useful.

It looks to me that we just disagree about the relative importance of
redisplay concurrency.

>> I don't forget that. However, we do not have to make each and every
>> thread _fully_ asynchronous. It is often enough to process the
>> performance bottlenecks asynchronously. After that processing, we can go
>> ahead and present the results synchronously to user.
>
> This assumes the display is always in the end.  But that is a false
> assumption in Emacs: there are progress messages, there are prompts
> and requests for confirmation, there are display updates to show the
> stuff processed so far, etc.

Again, not always. I do not think that the _initial_ goal should be
making every aspect of Elisp working asynchronously without
interlocking. We certainly want all Elisp to work in threads, possibly
with global lock. But if we get at least some part of useful Elisp to
run truly concurrently, it will already be a win.

>> Let me provide a more concrete example.
>> Consider something as simple as grepping across project files.
>> The process of grepping involves: (1) opening and searching many files;
>> (2) presenting results to the user. Stage (1) does not really involve
>> user interaction or redisplay and can greatly benefit from asynchronous
>> threads - we can simply search multiple files at the same time. Then,
>> even if stage (2) has to be synchronous, it does not matter - stage (1)
>> is what takes most of the time and makes the user wait.
>
> You describe an Emacs without async subprocesses -- this is how it
> works on MSDOS, for example.  On more capable systems we display in
> parallel with running Grep.

I think you misunderstood. I did not mean calling GNU grep. I meant
calling M-x grep - Elisp code searching across many Emacs buffers. It
would be useful if such code could run concurrently.

Another example is org-agenda that is running a large number of regexp
search across many buffers. Some real-world users search across as many
as 500 buffers, with results accumulated into agenda. It would certainly
be useful to run that regexp search concurrently, in multiple buffers at
once. Or maybe even on several regions of a single, large buffer.

>> > I'm not talking about async redisplay, I'm talking about the ability
>> > of non-main threads to display something or do something that would
>> > cause redisplay change the stuff on the glass.
>> 
>> Then, how will it be possible without first having async Elisp threads?
>
> Async Lisp threads is a much harder problem to solve.  If we solve it,
> this one will also be solved; but the opposite is not true.

I agree here. But do note that the interest (and some trial code by Po
Lu) so far has been focused on Elisp threads.

The problem with display code, even if it is easier to transform it to
concurrent, is that understanding display code is by itself is a
time-consuming task. Making changes in it (even small changes) is no
less trivial (I am referring to bug#64596).

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 10:29:48 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> AFAIU, long-lines performance is largely problematic when running Elisp.
> >
> > No, the slow parts are pure C.
> >
> >> (Also, isn't it solved already?)
> >
> > Not solved, but "bypassed".  The solution does have its disadvantages,
> > although we found them to be a much lesser evil than the original
> > problem.
> 
> May you point to the xdisp.c function that is being slow?

The basic iteration and layout calculations are slow because (a) they
must examine every character between point A and point B to figure out
the relative position of these points on the screen, and (b) because
this examination can only go forward, not back (so to go back, we must
"jump" very far back, and then go forward).

> >> Another one you mentioned is displaying many frames. But isn't it
> >> optimized by the part of the code that delays redisplay of frames that
> >> are not visible? Or does Stefan (or anyone) tend to have so many
> >> _visible_ frames?
> >
> > The latter.
> 
> Ok. But is it possible to redisplay the whole frame without ever calling Elisp?

Probably not "without ever", but why is it important in this context?
Most of the processing is in C, not in Lisp.

> >> > There's more than one reason, that's true.  But it doesn't change the
> >> > fact that all those problems have to be resolved before we have
> >> > reasonably usable threads.
> >> 
> >> I disagree. Yes, _all_ the problems are to be solved eventually. But
> >> solving _some_ of the problems will already be an improvement. IMHO, it
> >> is not all-or-nothing; we can split the problem into several
> >> sub-problems and solve them one by one.
> >
> > You've lost context, and effectively changed the subject, so now this
> > sub-thread is not useful anymore.  To recap, I was trying to explain
> > why the display aspects of any concurrency cannot be disregarded if we
> > want to have a workable solution that can be used in practice.
> 
> I believe that I did not lose the context. Unless I misunderstand
> something.
> 
> What I suggested is to defer the redisplay concurrency and leave it
> synchronous (interlocked) for now. Concurrency of Elisp that does not
> trigger redisplay can also be useful.
> 
> It looks to me that we just disagree about the relative importance of
> redisplay concurrency.

Yes, exactly.  My point is that without having a reasonable solution
for display, any concurrency will be dead in the water from the
get-go.

> >> I don't forget that. However, we do not have to make each and every
> >> thread _fully_ asynchronous. It is often enough to process the
> >> performance bottlenecks asynchronously. After that processing, we can go
> >> ahead and present the results synchronously to user.
> >
> > This assumes the display is always in the end.  But that is a false
> > assumption in Emacs: there are progress messages, there are prompts
> > and requests for confirmation, there are display updates to show the
> > stuff processed so far, etc.
> 
> Again, not always. I do not think that the _initial_ goal should be
> making every aspect of Elisp working asynchronously without
> interlocking. We certainly want all Elisp to work in threads, possibly
> with global lock. But if we get at least some part of useful Elisp to
> run truly concurrently, it will already be a win.

Not if we want to run the existing Lisp programs in threads with
minimal or no changes.  Because Lisp programs we have now require
display and user interaction all the time, whether by themselves or by
lower-level subroutines they call.

> >> Let me provide a more concrete example.
> >> Consider something as simple as grepping across project files.
> >> The process of grepping involves: (1) opening and searching many files;
> >> (2) presenting results to the user. Stage (1) does not really involve
> >> user interaction or redisplay and can greatly benefit from asynchronous
> >> threads - we can simply search multiple files at the same time. Then,
> >> even if stage (2) has to be synchronous, it does not matter - stage (1)
> >> is what takes most of the time and makes the user wait.
> >
> > You describe an Emacs without async subprocesses -- this is how it
> > works on MSDOS, for example.  On more capable systems we display in
> > parallel with running Grep.
> 
> I think you misunderstood. I did not mean calling GNU grep. I meant
> calling M-x grep - Elisp code searching across many Emacs buffers. It
> would be useful if such code could run concurrently.

It will be much more useful if it could also show the hits as it runs,
instead of requiring the user to wait till it finishes.

> Another example is org-agenda that is running a large number of regexp
> search across many buffers. Some real-world users search across as many
> as 500 buffers, with results accumulated into agenda. It would certainly
> be useful to run that regexp search concurrently, in multiple buffers at
> once. Or maybe even on several regions of a single, large buffer.

And you never want to show the accumulated agenda as it is
accumulated?

> >> > I'm not talking about async redisplay, I'm talking about the ability
> >> > of non-main threads to display something or do something that would
> >> > cause redisplay change the stuff on the glass.
> >> 
> >> Then, how will it be possible without first having async Elisp threads?
> >
> > Async Lisp threads is a much harder problem to solve.  If we solve it,
> > this one will also be solved; but the opposite is not true.
> 
> I agree here. But do note that the interest (and some trial code by Po
> Lu) so far has been focused on Elisp threads.

I'm quite sure people who disregard the display when they are talking
about concurrent Lisp threads are going to repeat the same mistake we
made with the existing Lisp threads.  We must learn from past
experience if we want to succeed.

> The problem with display code, even if it is easier to transform it to
> concurrent, is that understanding display code is by itself is a
> time-consuming task. Making changes in it (even small changes) is no
> less trivial (I am referring to bug#64596).

That is true about any non-trivial part of Emacs internals.  At least
with the display code we have some expertise and experience on board,
something that is not always true elsewhere in Emacs.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> May you point to the xdisp.c function that is being slow?
>
> The basic iteration and layout calculations are slow because (a) they
> must examine every character between point A and point B to figure out
> the relative position of these points on the screen, and (b) because
> this examination can only go forward, not back (so to go back, we must
> "jump" very far back, and then go forward).

In other words, processing a single window is being slow.
The question now is whether processing the whole window can be split
into multiple independent chunks. If it can, such processing can run in
parallel.

>> Ok. But is it possible to redisplay the whole frame without ever calling Elisp?
>
> Probably not "without ever", but why is it important in this context?
> Most of the processing is in C, not in Lisp.

My point is that any time we have to run Lisp during redisplay, without
async Elisp threads, we have to acquire global lock first, which will
degrade concurrency. I am not sure how bad the degradation will be.

>> Again, not always. I do not think that the _initial_ goal should be
>> making every aspect of Elisp working asynchronously without
>> interlocking. We certainly want all Elisp to work in threads, possibly
>> with global lock. But if we get at least some part of useful Elisp to
>> run truly concurrently, it will already be a win.
>
> Not if we want to run the existing Lisp programs in threads with
> minimal or no changes.  Because Lisp programs we have now require
> display and user interaction all the time, whether by themselves or by
> lower-level subroutines they call.

Sure. _existing_. What I have in mind is programs specifically written
to take advantage of concurrency. Just to address common performance
bottlenecks.

>> I think you misunderstood. I did not mean calling GNU grep. I meant
>> calling M-x grep - Elisp code searching across many Emacs buffers. It
>> would be useful if such code could run concurrently.
>
> It will be much more useful if it could also show the hits as it runs,
> instead of requiring the user to wait till it finishes.

Maybe. But reducing the overall waiting time at the cost of not seeing
the progress is an OK compromise, IMHO.

>> Another example is org-agenda that is running a large number of regexp
>> search across many buffers. Some real-world users search across as many
>> as 500 buffers, with results accumulated into agenda. It would certainly
>> be useful to run that regexp search concurrently, in multiple buffers at
>> once. Or maybe even on several regions of a single, large buffer.
>
> And you never want to show the accumulated agenda as it is
> accumulated?

Yes. Because part of the fontification is performed at the very end,
when everything is accumulated.

>> I agree here. But do note that the interest (and some trial code by Po
>> Lu) so far has been focused on Elisp threads.
>
> I'm quite sure people who disregard the display when they are talking
> about concurrent Lisp threads are going to repeat the same mistake we
> made with the existing Lisp threads.  We must learn from past
> experience if we want to succeed.

What about addressing the existing problems with cooperating Lisp
threads then?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Fri, 22 Sep 2023 10:48:46 +0000
> 
> >> Again, not always. I do not think that the _initial_ goal should be
> >> making every aspect of Elisp working asynchronously without
> >> interlocking. We certainly want all Elisp to work in threads, possibly
> >> with global lock. But if we get at least some part of useful Elisp to
> >> run truly concurrently, it will already be a win.
> >
> > Not if we want to run the existing Lisp programs in threads with
> > minimal or no changes.  Because Lisp programs we have now require
> > display and user interaction all the time, whether by themselves or by
> > lower-level subroutines they call.
> 
> Sure. _existing_. What I have in mind is programs specifically written
> to take advantage of concurrency. Just to address common performance
> bottlenecks.

If we are talking about an Emacs where programs meant for threads will
need to be written from scratch using special protocols and
primitives, then all bets are off, and I'm not sure everything we
discussed at such a great length lately is at all useful or even
relevant.  The idea was to allow existing Lisp programs run from
threads with little or no changes, by just starting a thread which
runs a function that is already written and debugged when running in
the (single) main thread.  If this is not what you have in mind, try
first to see if users will be likely to switch to such an Emacs or use
such threads, when they know they will need to drop everything and
start from scratch.  Who will want to write a "multithreaded Gnus"
starting from scratch?

> >> I think you misunderstood. I did not mean calling GNU grep. I meant
> >> calling M-x grep - Elisp code searching across many Emacs buffers. It
> >> would be useful if such code could run concurrently.
> >
> > It will be much more useful if it could also show the hits as it runs,
> > instead of requiring the user to wait till it finishes.
> 
> Maybe. But reducing the overall waiting time at the cost of not seeing
> the progress is an OK compromise, IMHO.

If the time is more than, say, a second or two, then no, such a
compromise will not be liked.  At least for Grep-style searches and
other compile-like commands.

> > I'm quite sure people who disregard the display when they are talking
> > about concurrent Lisp threads are going to repeat the same mistake we
> > made with the existing Lisp threads.  We must learn from past
> > experience if we want to succeed.
> 
> What about addressing the existing problems with cooperating Lisp
> threads then?

What about it?  Patches are welcome, of course.  Last time we
discussed these issues, we were unable to find good ideas for solving
them.  Maybe we should try discussing them again.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> If we are talking about an Emacs where programs meant for threads will
> need to be written from scratch using special protocols and
> primitives, then all bets are off, and I'm not sure everything we
> discussed at such a great length lately is at all useful or even
> relevant.  The idea was to allow existing Lisp programs run from
> threads with little or no changes, by just starting a thread which
> runs a function that is already written and debugged when running in
> the (single) main thread.  If this is not what you have in mind, try
> first to see if users will be likely to switch to such an Emacs or use
> such threads, when they know they will need to drop everything and
> start from scratch.  Who will want to write a "multithreaded Gnus"
> starting from scratch?

Let me clarify.
I am not saying that existing Elisp code should not be allowed to run
from threads. It should.

However, I think that it can be acceptable to leave certain things
interlocked - if async thread is querying, for example, user input or
redisplay, acquire a global (or input/redisplay) lock, and run that
portion of the thread synchronously.

That way, we can still allow useful Elisp to run concurrently, when
running CPU-intensive computation. These CPU-intensive parts will need
to be rewritten with concurrency in mind. But only parts - the rest of
the code could be left unchanged without breaking things.

Later, we may also figure out more tricky parts related to async
input/redisplay. 

>> Maybe. But reducing the overall waiting time at the cost of not seeing
>> the progress is an OK compromise, IMHO.
>
> If the time is more than, say, a second or two, then no, such a
> compromise will not be liked.  At least for Grep-style searches and
> other compile-like commands.

Sure. I am talking about M-x grep on large projects, when it takes tens
of seconds to finish. Same for org-agenda - it is not uncommon when
org-agenda searches last for a minute when search criteria is complex.

>> What about addressing the existing problems with cooperating Lisp
>> threads then?
>
> What about it?  Patches are welcome, of course.  Last time we
> discussed these issues, we were unable to find good ideas for solving
> them.  Maybe we should try discussing them again.

Are you referring to input discussion? Something else? I think that it
could be useful to document problems to be solved in etc/TODO.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Sat, 23 Sep 2023 11:07:54 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > If we are talking about an Emacs where programs meant for threads will
> > need to be written from scratch using special protocols and
> > primitives, then all bets are off, and I'm not sure everything we
> > discussed at such a great length lately is at all useful or even
> > relevant.  The idea was to allow existing Lisp programs run from
> > threads with little or no changes, by just starting a thread which
> > runs a function that is already written and debugged when running in
> > the (single) main thread.  If this is not what you have in mind, try
> > first to see if users will be likely to switch to such an Emacs or use
> > such threads, when they know they will need to drop everything and
> > start from scratch.  Who will want to write a "multithreaded Gnus"
> > starting from scratch?
> 
> Let me clarify.
> I am not saying that existing Elisp code should not be allowed to run
> from threads. It should.
> 
> However, I think that it can be acceptable to leave certain things
> interlocked - if async thread is querying, for example, user input or
> redisplay, acquire a global (or input/redisplay) lock, and run that
> portion of the thread synchronously.

If this is done under the hood by the infrastructure, and the Lisp
code doesn't have to be modified, this is, of course, fine.

If the Lisp program that wants to interact with the user will need to
do something special when it runs from a non-main thread, that is
worse, but maybe still feasible.

But what can we do about programs that call general-purpose
subroutines, and those subroutines decide to prompt the user?  And
this is the problem which bothers me, because we are used to call many
low-level subroutines without thinking about what that subroutine
will do and whether it will want to prompt the user.

As a trivial example, any function that modifies a file-visiting
buffer could prompt the user if the file was meanwhile modified on
disk.  This prompt is completely out of control of any Lisp program
which does something that modifies buffer text.  How do we handle
these cases? their name is a legion.

> >> What about addressing the existing problems with cooperating Lisp
> >> threads then?
> >
> > What about it?  Patches are welcome, of course.  Last time we
> > discussed these issues, we were unable to find good ideas for solving
> > them.  Maybe we should try discussing them again.
> 
> Are you referring to input discussion? Something else?

I don't know what you mean by "input discussion", but I did already
point you to the relevant discussion, so maybe that is it.

> I think that it could be useful to document problems to be solved in
> etc/TODO.

Feel free.  I don't think I can write something useful for that file,
so I didn't.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 23/09/2023 14:23, Eli Zaretskii wrote:
> As a trivial example, any function that modifies a file-visiting
> buffer could prompt the user if the file was meanwhile modified on
> disk.  This prompt is completely out of control of any Lisp program
> which does something that modifies buffer text.  How do we handle
> these cases? their name is a legion.

Any function that prompts the user is not supposed to be fast. So it 
might as well acquire any number of global locks to do that.

So it's not an issue for concurrency - though it might become a 
stumbling block for the "concurrent redisplay" sub-project.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Sat, 23 Sep 2023 15:53:11 +0300
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> On 23/09/2023 14:23, Eli Zaretskii wrote:
> > As a trivial example, any function that modifies a file-visiting
> > buffer could prompt the user if the file was meanwhile modified on
> > disk.  This prompt is completely out of control of any Lisp program
> > which does something that modifies buffer text.  How do we handle
> > these cases? their name is a legion.
> 
> Any function that prompts the user is not supposed to be fast. So it 
> might as well acquire any number of global locks to do that.

That's not my point.  My point is that if we say that changes to adapt
existing code to threads are acceptable, we will have to make those
changes all over our infrastructure, otherwise programs written for
threads will not ready for threads 100%.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 23/09/2023 16:01, Eli Zaretskii wrote:
>> Date: Sat, 23 Sep 2023 15:53:11 +0300
>> Cc:acm@muc.de,incal@dataswamp.org,emacs-devel@gnu.org
>> From: Dmitry Gutov<dmitry@gutov.dev>
>>
>> On 23/09/2023 14:23, Eli Zaretskii wrote:
>>> As a trivial example, any function that modifies a file-visiting
>>> buffer could prompt the user if the file was meanwhile modified on
>>> disk.  This prompt is completely out of control of any Lisp program
>>> which does something that modifies buffer text.  How do we handle
>>> these cases? their name is a legion.
>> Any function that prompts the user is not supposed to be fast. So it
>> might as well acquire any number of global locks to do that.
> That's not my point.  My point is that if we say that changes to adapt
> existing code to threads are acceptable, we will have to make those
> changes all over our infrastructure, otherwise programs written for
> threads will not ready for threads 100%.

I agree: functions like yes-or-no-p will have to, internally in their 
implementation, acquire the "redisplay lock" or whatever it'll be 
called, and do other things to ensure that they work from non-default 
threads too.

This will likely make them a little slower compared to the single-thread 
model, but hopefully not to a degree that's humanly noticeable.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Sat, 23 Sep 2023 16:08:23 +0300
> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> On 23/09/2023 16:01, Eli Zaretskii wrote:
> >> Date: Sat, 23 Sep 2023 15:53:11 +0300
> >> Cc:acm@muc.de,incal@dataswamp.org,emacs-devel@gnu.org
> >> From: Dmitry Gutov<dmitry@gutov.dev>
> >>
> >> On 23/09/2023 14:23, Eli Zaretskii wrote:
> >>> As a trivial example, any function that modifies a file-visiting
> >>> buffer could prompt the user if the file was meanwhile modified on
> >>> disk.  This prompt is completely out of control of any Lisp program
> >>> which does something that modifies buffer text.  How do we handle
> >>> these cases? their name is a legion.
> >> Any function that prompts the user is not supposed to be fast. So it
> >> might as well acquire any number of global locks to do that.
> > That's not my point.  My point is that if we say that changes to adapt
> > existing code to threads are acceptable, we will have to make those
> > changes all over our infrastructure, otherwise programs written for
> > threads will not ready for threads 100%.
> 
> I agree: functions like yes-or-no-p will have to, internally in their 
> implementation, acquire the "redisplay lock" or whatever it'll be 
> called, and do other things to ensure that they work from non-default 
> threads too.
> 
> This will likely make them a little slower compared to the single-thread 
> model, but hopefully not to a degree that's humanly noticeable.

I'm not bothered by slowness, I'm much more bothered by the magnitude
of the changes this will incur.  I don't even know how to identify all
the places which would need such changes.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> I'm not bothered by slowness, I'm much more bothered by the magnitude
> of the changes this will incur.  I don't even know how to identify all
> the places which would need such changes.

I _hope_ that it will be enough to acquire global lock once redisplay or
user input is requested.

If my optimism does not hold, a safe approach that can be employed is to
mark the functions that are thread-safe explicitly and acquire global
lock by default.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 23/09/2023 16:15, Eli Zaretskii wrote:
>> Date: Sat, 23 Sep 2023 16:08:23 +0300
>> Cc: yantar92@posteo.net, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
>> From: Dmitry Gutov <dmitry@gutov.dev>
>>
>> On 23/09/2023 16:01, Eli Zaretskii wrote:
>>>> Date: Sat, 23 Sep 2023 15:53:11 +0300
>>>> Cc:acm@muc.de,incal@dataswamp.org,emacs-devel@gnu.org
>>>> From: Dmitry Gutov<dmitry@gutov.dev>
>>>>
>>>> On 23/09/2023 14:23, Eli Zaretskii wrote:
>>>>> As a trivial example, any function that modifies a file-visiting
>>>>> buffer could prompt the user if the file was meanwhile modified on
>>>>> disk.  This prompt is completely out of control of any Lisp program
>>>>> which does something that modifies buffer text.  How do we handle
>>>>> these cases? their name is a legion.
>>>> Any function that prompts the user is not supposed to be fast. So it
>>>> might as well acquire any number of global locks to do that.
>>> That's not my point.  My point is that if we say that changes to adapt
>>> existing code to threads are acceptable, we will have to make those
>>> changes all over our infrastructure, otherwise programs written for
>>> threads will not ready for threads 100%.
>>
>> I agree: functions like yes-or-no-p will have to, internally in their
>> implementation, acquire the "redisplay lock" or whatever it'll be
>> called, and do other things to ensure that they work from non-default
>> threads too.
>>
>> This will likely make them a little slower compared to the single-thread
>> model, but hopefully not to a degree that's humanly noticeable.
> 
> I'm not bothered by slowness, I'm much more bothered by the magnitude
> of the changes this will incur.  I don't even know how to identify all
> the places which would need such changes.

That would be up to the implementor: do a patch, run with existing code, 
notice problems, patch some more. Etc. The issue is creating a 
reasonably complete (and useable) implementation that at least some 
developers start testing the waters.

Anyway, some concern about performance might be warranted. For example, 
the recent "Python without GIL" project describes a 9% difference in 
single-thread performance, which the author of course tried to make up 
for with new optimizations 
(https://docs.google.com/document/d/18CXhDb1ygxg-YXNBJNzfzZsDFosB5e6BfnXLlejd9l0/edit?pli=1).

I recall that even a 2% (?) difference caused by the 
symbols-with-positions feature was considered a problem not too long ago.

Re: Emacs design and architecture. How about copy-on-write?

[Yuri Khan]

On Sat, 23 Sept 2023 at 20:09, Dmitry Gutov <dmitry@gutov.dev> wrote:

> I agree: functions like yes-or-no-p will have to, internally in their
> implementation, acquire the "redisplay lock" or whatever it'll be
> called, and do other things to ensure that they work from non-default
> threads too.

That’s not the only possible implementation. A function that wants a
confirmation could package up the prompt with a continuation function,
and post that as a message to the main thread. The main thread would
pump its message queue, display the prompt, and schedule the
continuation (with the prompt result) to a worker thread.

That would require the code using prompt functions to be transformed
to continuation-passing style though, either explicitly in code, or
automatically by the lisp reader.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 23/09/2023 17:23, Yuri Khan wrote:
> On Sat, 23 Sept 2023 at 20:09, Dmitry Gutov<dmitry@gutov.dev>  wrote:
> 
>> I agree: functions like yes-or-no-p will have to, internally in their
>> implementation, acquire the "redisplay lock" or whatever it'll be
>> called, and do other things to ensure that they work from non-default
>> threads too.
> That’s not the only possible implementation. A function that wants a
> confirmation could package up the prompt with a continuation function,
> and post that as a message to the main thread. The main thread would
> pump its message queue, display the prompt, and schedule the
> continuation (with the prompt result) to a worker thread.
> 
> That would require the code using prompt functions to be transformed
> to continuation-passing style though, either explicitly in code, or
> automatically by the lisp reader.

Yes, that's the other option which would make a lot of code require 
changes to be usable in threaded environment. As I understand, people 
would like to avoid that.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> I'm confused: suppose one thread modifies scroll-margin -- does that
> affect the (global) redisplay?  If it does, how will this "solve" the
> problem?  If it doesn't affect redisplay, how _can_ a thread change
> scroll-margin in order to affect redisplay?

It can't.  Such adjustments must be performed from the main thread, as
in all other modern GUI systems.

In a prototype that I've been entertaining, this problem is simply left
unsolved.  Redisplay et all can only be called from the main thread;
attempting to call functions that are not thread safe (presently all
aside from those defined within alloc.c, that have been properly
interlocked) signal an error.  Objfwd variables consulted by redisplay
are saved around redisplay_internal (and other similar functions), so
that their values as perceived by redisplay can never change while it is
in progress.

This is no different from other GUI systems, where calling functions or
setting variables that affect the UI outside the main thread is strictly
forbidden, and either gives rise to a prompt crash or aborts with a
failure indication.  That multiple threads are incapable of sharing
control over a functioning GUI system is a lesson taught with sweat and
blood, and for it to be lost on us would be an awful shame.

I suggest that people interested in a multi-threaded Emacs answer these
two questions instead:

  - Is there a portable (in POSIX) method for reliably stopping a POSIX
    thread, with all callee-saved registers and register variables
    within leaf functions saved to the stack or some other area in
    memory?

  - How will finalizers, buffer modification hooks, symbol value
    watchers and the like be executed in response to garbage collection,
    buffer modification, or setting symbols in non-main threads?

Instead of belaboring the subject of how different threads will somehow
get away with coinciding calls to redisplay, or asynchronous
modifications to its state.  Because decades of research and experience
from an innumerable number of individuals and organizations have
produced an unequivocal answer: they won't.

Just two cents from someone who actually _HAS_ a multi-processing Emacs
in a quasi-functional state.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Po Lu <luangruo@yahoo.com> writes:

> In a prototype that I've been entertaining, this problem is simply left
> unsolved.  Redisplay et all can only be called from the main thread;
> attempting to call functions that are not thread safe (presently all
> aside from those defined within alloc.c

Also, several special forms in eval.c, data.c, fixnum arithmetic, and
the bytecode interpreter of course.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Po Lu <luangruo@yahoo.com> writes:

> I suggest that people interested in a multi-threaded Emacs answer these
> two questions instead:
>
>   - Is there a portable (in POSIX) method for reliably stopping a POSIX
>     thread, with all callee-saved registers and register variables
>     within leaf functions saved to the stack or some other area in
>     memory?

This question sounds like a part of a specific implementation detail you
have in mind. May you share more context?

>   - How will finalizers, buffer modification hooks, symbol value
>     watchers and the like be executed in response to garbage collection,
>     buffer modification, or setting symbols in non-main threads?

1. finalizers
   AFAIU, you are referring to GC finalizers.
   But is GC thread-safe?

2. symbol value watchers are triggered by let-bindings among other
   things. At least for let-binding triggers, it makes sense to keep the
   thread-local context for value watchers. I see not why other kind of
   triggers should not keep the modifier thread context either.

   Of course, one might want to process triggers in a separate thread,
   but that may be done by explicitly spawning one.

3. modification hooks are always triggered within a single buffer.
   According to previous discussions, we concluded that it would be
   difficult to allow multiple threads modify the same buffer, so,
   similar to watchers, thread context may be important, and the hooks
   should probably run from within the trigger tread.

> Just two cents from someone who actually _HAS_ a multi-processing Emacs
> in a quasi-functional state.

Is it available anywhere in public repository?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: Alan Mackenzie <acm@muc.de>,  incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Mon, 18 Sep 2023 21:30:17 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > I'm confused: suppose one thread modifies scroll-margin -- does that
> > affect the (global) redisplay?  If it does, how will this "solve" the
> > problem?  If it doesn't affect redisplay, how _can_ a thread change
> > scroll-margin in order to affect redisplay?
> 
> It can't.  Such adjustments must be performed from the main thread, as
> in all other modern GUI systems.

So a non-main thread cannot do anything that affects the display?
Like move point in a buffer that is shown in some window?

> This is no different from other GUI systems, where calling functions or
> setting variables that affect the UI outside the main thread is strictly
> forbidden, and either gives rise to a prompt crash or aborts with a
> failure indication.  That multiple threads are incapable of sharing
> control over a functioning GUI system is a lesson taught with sweat and
> blood, and for it to be lost on us would be an awful shame.

If non-main threads cannot change stuff that affects the display, what
can those threads do? compute the 10ⁿ-th digit of π?

Useful stuff in Emacs almost always affects the display, so if a
non-main threads cannot do that, they will be useless.  Or what am I
missing?

> Just two cents from someone who actually _HAS_ a multi-processing Emacs
> in a quasi-functional state.

IMNSHO, if you left the display issues unsolved, you are no closer to
the solution than we are in Emacs 30.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> So a non-main thread cannot do anything that affects the display?
> Like move point in a buffer that is shown in some window?

This is possible, but moving point won't induce a redisplay of that
window.

> If non-main threads cannot change stuff that affects the display, what
> can those threads do? compute the 10ⁿ-th digit of π?

And other tasks like this, responsible for blocking Emacs.  Since most
of the time, Emacs is not blocked in redisplay, but reading process
output or performing difficult computations.

> Useful stuff in Emacs almost always affects the display, so if a
> non-main threads cannot do that, they will be useless.  Or what am I
> missing?

Consider the case of Gnus or Eglot: it will enable either of them to
fetch news or receive LSP output from a second thread, decode it, and
subsequently transfer it to the main thread for display.  Such expensive
processing is the reason people desire a multi-processing Emacs, because
it will facilitate efficiently running these operations in the
background and possibly on a different CPU.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: acm@muc.de,  incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Tue, 19 Sep 2023 07:41:41 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > So a non-main thread cannot do anything that affects the display?
> > Like move point in a buffer that is shown in some window?
> 
> This is possible, but moving point won't induce a redisplay of that
> window.

So if point moves off the window, we will have a window that doesn't
show point?

> > If non-main threads cannot change stuff that affects the display, what
> > can those threads do? compute the 10ⁿ-th digit of π?
> 
> And other tasks like this, responsible for blocking Emacs.  Since most
> of the time, Emacs is not blocked in redisplay, but reading process
> output or performing difficult computations.

Yes, but almost everything we do in Emacs has its purpose of affecting
display, eventually.  Including process output we read and whatever
computations we do.  Emacs is a real-time display editor, first and
foremost, so this should not be a surprise.  The only notable
exception from this rule is batch-style execution in a script.

> > Useful stuff in Emacs almost always affects the display, so if a
> > non-main threads cannot do that, they will be useless.  Or what am I
> > missing?
> 
> Consider the case of Gnus or Eglot: it will enable either of them to
> fetch news or receive LSP output from a second thread, decode it, and
> subsequently transfer it to the main thread for display.

How do you "transfer it to the main thread for display", exactly?  And
won't you want to display some kind of progress indicator while
fetching? or show an error message if things fail?  Every Lisp program
invokes gazillion low-level subroutines and primitives, and some of
those feel free to ask the user questions, show messages, etc.  Even
process.c shows messages,l and modifying a file-visiting buffer might
ask about supersession locks.  We cannot just forbid display from
non-main threads, unless we are willing to rewrite most of the
application code in Emacs, and many of the primitives as well.  The
only solution that avoids the massive rewrite is to invent mechanisms
that still allow non-main threads to communicate with users.

> Such expensive processing is the reason people desire a
> multi-processing Emacs, because it will facilitate efficiently
> running these operations in the background and possibly on a
> different CPU.

I know the theory.  I'm talking about the details -- the devil is
usually there.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> So if point moves off the window, we will have a window that doesn't
> show point?

We will have a window whose point does not reflect its contents on the
display.  A supervening redisplay within the main thread will give due
consideration to its new value when it does transpire.

> Yes, but almost everything we do in Emacs has its purpose of affecting
> display, eventually.  Including process output we read and whatever
> computations we do.  Emacs is a real-time display editor, first and
> foremost, so this should not be a surprise.  The only notable
> exception from this rule is batch-style execution in a script.

These eventualities must take place within the main thread, that's all.

> How do you "transfer it to the main thread for display", exactly?

By setting a global variable that is subsequently read by the main
thread, modifying unread-command-events, and signaling a condition
variable that induces read_char to return the new value of
unread-command-events.

> And won't you want to display some kind of progress indicator while
> fetching? or show an error message if things fail?  Every Lisp program
> invokes gazillion low-level subroutines and primitives, and some of
> those feel free to ask the user questions, show messages, etc.  Even
> process.c shows messages, and modifying a file-visiting buffer might
> ask about supersession locks.  We cannot just forbid display from
> non-main threads, unless we are willing to rewrite most of the
> application code in Emacs, and many of the primitives as well.  The
> only solution that avoids the massive rewrite is to invent mechanisms
> that still allow non-main threads to communicate with users.

process.c can't be employed from non-main threads, as they are forbidden
from entering wait_reading_process_output.  Likewise for the file-lock
stuff, as it calls read_char.

My idea is that non-main threads will communicate with subprocesses and
read or write files through a different set of primitives, but they have
not been implemented.  The principle difficulty with the existing file
primitives is that they can call thread-unsafe Lisp; file name handlers
provided by TRAMP, for example.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: acm@muc.de,  incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Wed, 20 Sep 2023 09:01:56 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > So if point moves off the window, we will have a window that doesn't
> > show point?
> 
> We will have a window whose point does not reflect its contents on the
> display.  A supervening redisplay within the main thread will give due
> consideration to its new value when it does transpire.

I don't understand why only the main thread is allowed to do that.
What is special in the main thread wrt redisplay that other threads
are forbidden from doing that?  Would it be okay to have a separate
non-main redisplay thread, for example? if not, why not?

> > Yes, but almost everything we do in Emacs has its purpose of affecting
> > display, eventually.  Including process output we read and whatever
> > computations we do.  Emacs is a real-time display editor, first and
> > foremost, so this should not be a surprise.  The only notable
> > exception from this rule is batch-style execution in a script.
> 
> These eventualities must take place within the main thread, that's all.

They many times happen in the middle of processing, not just
"eventually".

> > How do you "transfer it to the main thread for display", exactly?
> 
> By setting a global variable that is subsequently read by the main
> thread, modifying unread-command-events, and signaling a condition
> variable that induces read_char to return the new value of
> unread-command-events.

How is this different from telling the main thread to stop, and then
doing the display from the thread which triggered that?  IOW, why do
we need to ask the main thread to actually display (and perform
input), as opposed to just get out of the way for a short while?

> > And won't you want to display some kind of progress indicator while
> > fetching? or show an error message if things fail?  Every Lisp program
> > invokes gazillion low-level subroutines and primitives, and some of
> > those feel free to ask the user questions, show messages, etc.  Even
> > process.c shows messages, and modifying a file-visiting buffer might
> > ask about supersession locks.  We cannot just forbid display from
> > non-main threads, unless we are willing to rewrite most of the
> > application code in Emacs, and many of the primitives as well.  The
> > only solution that avoids the massive rewrite is to invent mechanisms
> > that still allow non-main threads to communicate with users.
> 
> process.c can't be employed from non-main threads, as they are forbidden
> from entering wait_reading_process_output.  Likewise for the file-lock
> stuff, as it calls read_char.
> 
> My idea is that non-main threads will communicate with subprocesses and
> read or write files through a different set of primitives, but they have
> not been implemented.

Why do they have to be a different set, not the same set which is made
thread-aware?  E.g., if you don't want a primitive to do something
when it runs in a non-main thread, it is easy to write a condition for
that, and leave the rest of the code intact.

> The principle difficulty with the existing file primitives is that
> they can call thread-unsafe Lisp; file name handlers provided by
> TRAMP, for example.

Tramp should be the least of our problems.  The main problem with
refusing to run Lisp from non-main threads is that Emacs will cease to
be Emacs.  The various Lisp hooks, calls into Lisp from C, and control
on the internals exposed to Lisp are what makes Emacs the environment
that is flexible and powerful to unprecedented degree.  Take that
away, and programs written for such an "Emacs" will be much less
powerful and interesting, and certainly much less extensible.

Re: Emacs design and architecture. How about copy-on-write?

[Po Lu]

Eli Zaretskii <eliz@gnu.org> writes:

> I don't understand why only the main thread is allowed to do that.
> What is special in the main thread wrt redisplay that other threads
> are forbidden from doing that?  Would it be okay to have a separate
> non-main redisplay thread, for example? if not, why not?

Because toolkits forbid that.  One thread is customarily designated the
``main'' thread when the toolkit is initialized, after which any attempt
to invoke display routines from another thread induces a prompt abort.
This manifests itself most severely on NS and both GTK builds.

> They many times happen in the middle of processing, not just
> "eventually".

Then the text written to the glass will be inconsistent as long as
redisplay transpires while processing is still taking place.  Averting
such situations is not within our purview, but that of authors writing
Lisp code that exploits threads.

> How is this different from telling the main thread to stop, and then
> doing the display from the thread which triggered that?  IOW, why do
> we need to ask the main thread to actually display (and perform
> input), as opposed to just get out of the way for a short while?

Even with the toolkit problem notwithstanding, we would still have to
wait for the main thread to enter a section of code where it becomes
safe to yield to a second thread.  The main thread would then be hung
until any number of other threads complete redisplay, which IMNSHO
eliminates the raison d'etre for running multiple threads concurrently.

And there must be some other reason no other extant programs have
adopted such an approach.

> Why do they have to be a different set, not the same set which is made
> thread-aware?  E.g., if you don't want a primitive to do something
> when it runs in a non-main thread, it is easy to write a condition for
> that, and leave the rest of the code intact.

I'm not completely certain, given that the time I have dedicated to this
has mostly been committed to solving the buffer-local variable problem.

Let's bury this particular hatchet for the time being and revisit it
later, when I have the Lisp interpreter itself in a better shape.  OK?

Thanks.

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Po Lu <luangruo@yahoo.com>
> Cc: acm@muc.de,  incal@dataswamp.org,  emacs-devel@gnu.org
> Date: Wed, 20 Sep 2023 20:13:49 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > I don't understand why only the main thread is allowed to do that.
> > What is special in the main thread wrt redisplay that other threads
> > are forbidden from doing that?  Would it be okay to have a separate
> > non-main redisplay thread, for example? if not, why not?
> 
> Because toolkits forbid that.  One thread is customarily designated the
> ``main'' thread when the toolkit is initialized, after which any attempt
> to invoke display routines from another thread induces a prompt abort.
> This manifests itself most severely on NS and both GTK builds.

You are talking about the last stage of redisplay: delivering stuff to
the glass.  But xdisp.c is not about that, most of it has no
interaction with the toolkit.

> > They many times happen in the middle of processing, not just
> > "eventually".
> 
> Then the text written to the glass will be inconsistent as long as
> redisplay transpires while processing is still taking place.  Averting
> such situations is not within our purview, but that of authors writing
> Lisp code that exploits threads.

So we drop on the floor the gobs of Lisp code written during the last
40 years, and tell the authors to rewrite everything from scratch
under the new regime?

> > How is this different from telling the main thread to stop, and then
> > doing the display from the thread which triggered that?  IOW, why do
> > we need to ask the main thread to actually display (and perform
> > input), as opposed to just get out of the way for a short while?
> 
> Even with the toolkit problem notwithstanding, we would still have to
> wait for the main thread to enter a section of code where it becomes
> safe to yield to a second thread.  The main thread would then be hung
> until any number of other threads complete redisplay, which IMNSHO
> eliminates the raison d'etre for running multiple threads concurrently.

The same will happen if only the main thread can display.  If a
non-main thread wants to prompt the user, it will have to wait until
the main thread becomes available, prompts the user, and returns the
response.

Someone always has to wait when threads need to synchronize.  There's
no way around that.  Doing this in the thread that needs to
display/prompt is easier because the context and relevant variables
don't need to be communicated to another thread.

Re: Emacs design and architecture. How about copy-on-write?

[Dmitry Gutov]

On 20/09/2023 15:13, Po Lu wrote:
> Eli Zaretskii<eliz@gnu.org>  writes:
> 
>> I don't understand why only the main thread is allowed to do that.
>> What is special in the main thread wrt redisplay that other threads
>> are forbidden from doing that?  Would it be okay to have a separate
>> non-main redisplay thread, for example? if not, why not?
> Because toolkits forbid that.  One thread is customarily designated the
> ``main'' thread when the toolkit is initialized, after which any attempt
> to invoke display routines from another thread induces a prompt abort.
> This manifests itself most severely on NS and both GTK builds.

Could the "main thread" which works on the level of toolkits be/become a 
distinct notion from the "main Lisp thread"?

>> They many times happen in the middle of processing, not just
>> "eventually".
> Then the text written to the glass will be inconsistent as long as
> redisplay transpires while processing is still taking place.  Averting
> such situations is not within our purview, but that of authors writing
> Lisp code that exploits threads.
> 
>> How is this different from telling the main thread to stop, and then
>> doing the display from the thread which triggered that?  IOW, why do
>> we need to ask the main thread to actually display (and perform
>> input), as opposed to just get out of the way for a short while?
> Even with the toolkit problem notwithstanding, we would still have to
> wait for the main thread to enter a section of code where it becomes
> safe to yield to a second thread.  The main thread would then be hung
> until any number of other threads complete redisplay, which IMNSHO
> eliminates the raison d'etre for running multiple threads concurrently.
> 
> And there must be some other reason no other extant programs have
> adopted such an approach.

I would imagine (if we do get concurrent threads) that the UI thread 
might work like this: enumerate the visible buffers, "lock" each of the 
visible ones and then run redisplay on them. What's not-obvious is how 
to fit in the Lisp callbacks that are required in each of those by 
redisplay, especially, if some of the buffers are locked by non-default 
threads.

At the moment (IIUC) this just looks like recursive calls because any 
redisplay is triggered by the main thread. And the above scheme would 
require running Lisp in a buffer which is locked by the thread different 
from the one that triggered redisplay.

Though perhaps redisplay wouldn't be triggered by threads at all - not 
often, anyway. A thread could send a "request for redisplay" (if it 
needs to call something like 'redisplay' or 'posn-at-point'), at which 
point it might get suspended until the "display thread" gets to it. 
Then, if required, the thread runs any additional Lisp which is 
necessary to redisplay the current buffer. This could make those calls 
slower, but only experience would show by how much. If a Lisp thread 
doesn't really ask for redisplay, it could still be suspended by the 
"display thread" to do its thing. Could it run the necessary Lisp code 
on the suspended Lisp thread, though?

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> Date: Wed, 20 Sep 2023 21:50:59 +0300
> Cc: acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> Though perhaps redisplay wouldn't be triggered by threads at all - not 
> often, anyway. A thread could send a "request for redisplay" (if it 
> needs to call something like 'redisplay' or 'posn-at-point'), at which 
> point it might get suspended until the "display thread" gets to it. 

Nitpicking: posn-at-point and similar functions are not "redisplay",
they don't redraw any windows.  They just execute some code which is
also used by redisplay.  So there should be no problem calling
posn-at-point regardless of any UI thread and other threads, as long
as access to buffer text is possible.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> We will have a window whose point does not reflect its contents on the
>> display.  A supervening redisplay within the main thread will give due
>> consideration to its new value when it does transpire.
>
> I don't understand why only the main thread is allowed to do that.
> What is special in the main thread wrt redisplay that other threads
> are forbidden from doing that?  Would it be okay to have a separate
> non-main redisplay thread, for example? if not, why not?

Apart from toolkit considerations, consider two asynchronous threads
requesting to display something in the echo area. We cannot allow one
thread "cancel" displaying its message by another thread - this will
lose one of the messages that should be displayed to user. So, there at
least should be some kind of queue for threads trying to display
something in the same window.

Another scenario is one thread displaying multiline message while
another thread displaying a window adjacent to echo area. Let's say that
the thread redisplaying window started running first, considered its
window geometry, and started calculating the glyph matrix according to
the known number of lines fitting that window height. Then, "message"
thread wants to resize echo area to fit its multiline message. What
should the "window" thread do? Should it cancel its redisplay? Restart
it? Wait for the "message" thread to finish? It is not very clear and
likely depend on the specific scenario at hand.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Po Lu <luangruo@yahoo.com>, acm@muc.de, incal@dataswamp.org,
>  emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 10:08:21 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> We will have a window whose point does not reflect its contents on the
> >> display.  A supervening redisplay within the main thread will give due
> >> consideration to its new value when it does transpire.
> >
> > I don't understand why only the main thread is allowed to do that.
> > What is special in the main thread wrt redisplay that other threads
> > are forbidden from doing that?  Would it be okay to have a separate
> > non-main redisplay thread, for example? if not, why not?
> 
> Apart from toolkit considerations, consider two asynchronous threads
> requesting to display something in the echo area. We cannot allow one
> thread "cancel" displaying its message by another thread - this will
> lose one of the messages that should be displayed to user. So, there at
> least should be some kind of queue for threads trying to display
> something in the same window.
> 
> Another scenario is one thread displaying multiline message while
> another thread displaying a window adjacent to echo area. Let's say that
> the thread redisplaying window started running first, considered its
> window geometry, and started calculating the glyph matrix according to
> the known number of lines fitting that window height. Then, "message"
> thread wants to resize echo area to fit its multiline message. What
> should the "window" thread do? Should it cancel its redisplay? Restart
> it? Wait for the "message" thread to finish? It is not very clear and
> likely depend on the specific scenario at hand.

We have these situations already: arrange for some timer to display an
echo-area message after several seconds, then type M-x or something
else to enter the minibuffer, and watch how the message is displayed.
We solved this, more-or-less, in Emacs 29.

In any case, having to deal with multiple simultaneous messages is a
far cry from disallowing any non-main thread to display anything.

Re: Emacs design and architecture. How about copy-on-write?

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> We have these situations already: arrange for some timer to display an
> echo-area message after several seconds, then type M-x or something
> else to enter the minibuffer, and watch how the message is displayed.
> We solved this, more-or-less, in Emacs 29.

In other words, it is some kind of primitive async queue, right?

> In any case, having to deal with multiple simultaneous messages is a
> far cry from disallowing any non-main thread to display anything.

I agree. I also think that non-main threads should not be disallowed to
trigger redisplay.

However,

(1) this redisplay should better be synchronous (first waiting for all
    other threads to finish their redisplay) when using the existing
    redisplay primitives.

(2) we may want to introduce asynchronous API to not block during
    redisplay, when threads do not care about display-related call
    returning a value. For example, there is no reason to wait until a
    message if displayed for async thread reporting its progress. It
    might be better to have something like `async-message' that will
    submit a request to display when Emacs decides to. Of course, such
    async API should not rely on thread-local context.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: Emacs design and architecture. How about copy-on-write?

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: luangruo@yahoo.com, acm@muc.de, incal@dataswamp.org, emacs-devel@gnu.org
> Date: Thu, 21 Sep 2023 10:35:14 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > We have these situations already: arrange for some timer to display an
> > echo-area message after several seconds, then type M-x or something
> > else to enter the minibuffer, and watch how the message is displayed.
> > We solved this, more-or-less, in Emacs 29.
> 
> In other words, it is some kind of primitive async queue, right?

No, it's a display trick.

Re: Emacs design and architecture. How about copy-on-write?

[Björn Bidar]

Po Lu <luangruo@yahoo.com> writes:

>> Useful stuff in Emacs almost always affects the display, so if a
>> non-main threads cannot do that, they will be useless.  Or what am I
>> missing?
>
> Consider the case of Gnus or Eglot: it will enable either of them to
> fetch news or receive LSP output from a second thread, decode it, and
> subsequently transfer it to the main thread for display.  Such expensive
> processing is the reason people desire a multi-processing Emacs, because
> it will facilitate efficiently running these operations in the
> background and possibly on a different CPU.

Magit is another example: A lot of modes are busy gathering data or
search through data. If the operations can run in the background not
blocking the main thread that runs the ui it would be to kill for (so to
speak).

Rendering the ui can take some time sometimes but not as often.

Re: Emacs design and architecture. How about copy-on-write?

[Richard Stallman]

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

  > A value in a value-cell (etc.) would have an associated thread value, the
  > thread which "owns" it.  When thread1 gets cloned from thread0, it
  > continues to use thread0's data state until it writes foo (e.g. by
  > binding it).  This would create a new value/thread pair, foo/thread1.
  > Further writes of foo by thread1 would continue to access foo/thread1.

It sounds reasonable to me.  It might be feasible to implement
as part of the mechanism that handles local values.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)