GNU bug report logs - #53242
[PATCH] unify reads from local_var_alist

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 53242 in the body.
You can then email your comments to 53242 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Sergey Vinokurov <serg.foo <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: [PATCH] unify reads from local_var_alist
Date: Fri, 14 Jan 2022 00:23:42 +0000

[Message part 1 (text/plain, inline)]

Hello,

I've noticed that local_var_alist field of the buffer structure is 
accessed inconsistently. Sometimes it's Fassoc, sometimes it's Fassq and 
other times it's assq_no_quit and even an explicit loop.

I think it's safe to unify all the accesses via assq_no_quit since it's 
an internaly maintained alist that definitely has no cycles and elements 
are cons cells with symbol as their car.

Sergey

[0001-Unify-getting-of-values-from-local_var_alist.patch (text/x-patch, attachment)]

Message #8 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Sergey Vinokurov <serg.foo <at> gmail.com>
Cc: 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Fri, 14 Jan 2022 08:49:48 +0100

Sergey Vinokurov <serg.foo <at> gmail.com> writes:

> I've noticed that local_var_alist field of the buffer structure is
> accessed inconsistently. Sometimes it's Fassoc, sometimes it's Fassq
> and other times it's assq_no_quit and even an explicit loop.
>
> I think it's safe to unify all the accesses via assq_no_quit since
> it's an internaly maintained alist that definitely has no cycles and
> elements are cons cells with symbol as their car.

Makes sense to me, so I've now applied your patch to Emacs 29 (and added
a ChangeLog-format commit message).

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Message #13 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Sergey Vinokurov <serg.foo <at> gmail.com>
Cc: 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Fri, 14 Jan 2022 10:08:49 +0200

> Date: Fri, 14 Jan 2022 00:23:42 +0000
> From: Sergey Vinokurov <serg.foo <at> gmail.com>
> 
> I've noticed that local_var_alist field of the buffer structure is 
> accessed inconsistently. Sometimes it's Fassoc, sometimes it's Fassq and 
> other times it's assq_no_quit and even an explicit loop.
> 
> I think it's safe to unify all the accesses via assq_no_quit since it's 
> an internaly maintained alist that definitely has no cycles and elements 
> are cons cells with symbol as their car.

How long can local_var_alist be?  This change will not allow the user
to C-g from a long search.  Do we care?  How about using Fassq
consistently instead?

Message #16 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Sergey Vinokurov <serg.foo <at> gmail.com>, 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Fri, 14 Jan 2022 09:33:11 +0100

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

> How long can local_var_alist be?  This change will not allow the user
> to C-g from a long search.  Do we care?  How about using Fassq
> consistently instead?

There was already one usage of assq_no_quit on the variable, so the
change seemed safe to me.  If it turns out that it's not, all the usages
should be changed to Fassq.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Message #19 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Sergey Vinokurov <serg.foo <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Fri, 14 Jan 2022 18:37:45 +0000

On 14/01/2022 08:08, Eli Zaretskii wrote:
>> Date: Fri, 14 Jan 2022 00:23:42 +0000
>> From: Sergey Vinokurov <serg.foo <at> gmail.com>
>>
>> I've noticed that local_var_alist field of the buffer structure is
>> accessed inconsistently. Sometimes it's Fassoc, sometimes it's Fassq and
>> other times it's assq_no_quit and even an explicit loop.
>>
>> I think it's safe to unify all the accesses via assq_no_quit since it's
>> an internaly maintained alist that definitely has no cycles and elements
>> are cons cells with symbol as their car.
> 
> How long can local_var_alist be?  This change will not allow the user
> to C-g from a long search.  Do we care?  How about using Fassq
> consistently instead?

This list is not directly observed by the user. The lookups happen 
during reads and writes of the buffer-local variables so if it's really 
slow the only effect user would observe is that elisp got slow. There's 
no single point for the user to C-g from.

This list definitely cannot be longer than a list of all the global 
variables ever defined. This upper bound is probably a high number, but 
not astronomically high. Perhaps if list gets really long it could be 
beneficial to use some other data structure, perhaps a hash table, instead.

Message #22 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Sergey Vinokurov <serg.foo <at> gmail.com>
Cc: 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Fri, 14 Jan 2022 21:01:49 +0200

> Date: Fri, 14 Jan 2022 18:37:45 +0000
> Cc: 53242 <at> debbugs.gnu.org
> From: Sergey Vinokurov <serg.foo <at> gmail.com>
> 
> > How long can local_var_alist be?  This change will not allow the user
> > to C-g from a long search.  Do we care?  How about using Fassq
> > consistently instead?
> 
> This list is not directly observed by the user. The lookups happen 
> during reads and writes of the buffer-local variables so if it's really 
> slow the only effect user would observe is that elisp got slow. There's 
> no single point for the user to C-g from.

?? What do you mean?  Long operations in Emacs generally periodically
check for user's quitting, andif they detect C-g, they throw to
top-level.  assq_no_quit doesn't.

> This list definitely cannot be longer than a list of all the global 
> variables ever defined. This upper bound is probably a high number, but 
> not astronomically high.

The question I asked was: it high enough to cause annoyingly long
operations in some cases, and whether we care that users will no
longer be able to interrupt such long operations.  You seem to assume
that the number cannot be high enough, but I see no basis for that
assumption in what you wrote.

Message #25 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Sergey Vinokurov <serg.foo <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Fri, 14 Jan 2022 21:01:46 +0000

On 14/01/2022 19:01, Eli Zaretskii wrote:
>> Date: Fri, 14 Jan 2022 18:37:45 +0000
>> Cc: 53242 <at> debbugs.gnu.org
>> From: Sergey Vinokurov <serg.foo <at> gmail.com>
>>
>>> How long can local_var_alist be?  This change will not allow the user
>>> to C-g from a long search.  Do we care?  How about using Fassq
>>> consistently instead?
>>
>> This list is not directly observed by the user. The lookups happen
>> during reads and writes of the buffer-local variables so if it's really
>> slow the only effect user would observe is that elisp got slow. There's
>> no single point for the user to C-g from.
> 
> ?? What do you mean?  Long operations in Emacs generally periodically
> check for user's quitting, andif they detect C-g, they throw to
> top-level.  assq_no_quit doesn't.
>> This list definitely cannot be longer than a list of all the global
>> variables ever defined. This upper bound is probably a high number, but
>> not astronomically high.
> 
> The question I asked was: it high enough to cause annoyingly long
> operations in some cases, and whether we care that users will no
> longer be able to interrupt such long operations.  You seem to assume
> that the number cannot be high enough, but I see no basis for that
> assumption in what you wrote.

My reasoning is as follows: consider what is stored in the 
local_var_alist. It's only for buffer-local variables, no other entries 
should get into the list. Thus the size of this list is directly 
proportional to the number of local variables in current buffer.

How many local variable bindings could be defined at the same time? Any 
amount, really. There can be no local variables or, in pathological 
case, there can be any number of them (consider a program executing 
`(dolist (i N) (set (make-local-variable (intern (format "foo%s" i))) 
i))` with arbitrary N). I argue that something's wrong if there are so 
many local variables defined that lookups into the local_var_alist would 
cause significant delays.

The lookups will happen each time a buffer-local variable is read or 
written to in elisp. If these lookups take a long time then any elisp 
working with these variables become slow. My argument is that at this 
point we don't care whether user is able to interrupt basic operations 
of reading and writing buffer-local variables. Even if we use Fassq and 
the user could interrupt, nothing is gained in my opinion - any command 
that involves reading or writing buffer-local variables will still 
remain slow.

Message #28 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Sergey Vinokurov <serg.foo <at> gmail.com>
Cc: 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Sat, 15 Jan 2022 09:32:04 +0200

> Date: Fri, 14 Jan 2022 21:01:46 +0000
> Cc: 53242 <at> debbugs.gnu.org
> From: Sergey Vinokurov <serg.foo <at> gmail.com>
> 
> I argue that something's wrong if there are so many local variables
> defined that lookups into the local_var_alist would cause
> significant delays.

I agree that something is wrong, in the sense that the implementation
of some feature(s) should probably be rethought.  But that's not the
point I'm trying to make.  The point I'm trying to make is that
formerly, the user could interrupt such a long search, and now he/she
cannot.  The user is usually not the one to "blame" for the length of
the list.  With the previous code, the user had a "fire escape".

> My argument is that at this point we don't care whether user is able
> to interrupt basic operations of reading and writing buffer-local
> variables.

"We" might not care, but the user could very much care.  We in effect
locked the users without no way to handle these situations.

> Even if we use Fassq and the user could interrupt, nothing is gained
> in my opinion - any command that involves reading or writing
> buffer-local variables will still remain slow.

The commands will remain slow, but the users could stop Emacs from
wasting their time.  Now they cannot.  Saying that "we don't care"
means we don't  care about our users, which is certainly not true.

Message #31 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Sergey Vinokurov <serg.foo <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Sat, 15 Jan 2022 11:41:02 +0000

On 15/01/2022 07:32, Eli Zaretskii wrote:
>> My argument is that at this point we don't care whether user is able
>> to interrupt basic operations of reading and writing buffer-local
>> variables.
> 
> "We" might not care, but the user could very much care.  We in effect
> locked the users without no way to handle these situations.
> 
>> Even if we use Fassq and the user could interrupt, nothing is gained
>> in my opinion - any command that involves reading or writing
>> buffer-local variables will still remain slow.
> 
> The commands will remain slow, but the users could stop Emacs from
> wasting their time.  Now they cannot.  Saying that "we don't care"
> means we don't  care about our users, which is certainly not true.

I agree with your position but see a more further-reaching conclusion. 
If there's a risk of the list being really long the Emacs can employ a 
different data structure, e.g. a hash table, to make reads and writes of 
variables fast regardless of the number of entries. In my opinion such a 
change would serve users even better as there would be no need to 
interrupt any slow operations because there would be none.

Message #34 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Corwin Brust <corwin <at> bru.st>
To: Sergey Vinokurov <serg.foo <at> gmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>, 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Sat, 15 Jan 2022 10:02:31 -0600

[Message part 1 (text/plain, inline)]

Thanks for your work on Emacs,

On Sat, Jan 15, 2022, 05:42 Sergey Vinokurov <serg.foo <at> gmail.com> wrote:

> On 15/01/2022 07:32, Eli Zaretskii wrote:
> >> My argument is that at this point we don't care whether user is able
> >> to interrupt basic operations of reading and writing buffer-local
> >> variables.
>

This is my view also, fwiw.  Please consider the case of a package
developer who may be abusing buffer-local vars during experiments.  It
seems this will cause much more ’oops, time to kill Emacs/grab a coffee'.


I agree with your position but see a more further-reaching conclusion.
>
If there's a risk of the list being really long the Emacs can employ a
> different data structure, e.g. a hash table, to make reads and writes of
> variables fast regardless of the number of entries. In my opinion such a
> change would serve users even better as there would be no need to
> interrupt any slow operations because there would be none.
>


I tried to follow this conversation but it wasn't clear to me what out
motive is for this change.

I had understood we typically make (especially in the c sources) our
changes to achieve specific, tangible improvement.  Is that the case here?
is the particularly oppressive 'tech debt'?  In the latter case, does
history reflect consideration wrt the original selections in each of the
various cases we hereby change?

Also (and especially if we must 'clean for the sake of cleanliness'), could
we prefer the (seeming more conservative of UX) interruptable varient in
this case?  (Is that very costly? How costly and how have we measured that?)

It would be comforting if sweeping changes could be accompanied by analysis
of the impacted sources.  (We clearly deliberately chose interruptable
search in some cases and not others to date.  Why?)

Thanks so very much for Emacs!

[Message part 2 (text/html, inline)]

Message #37 received at 53242 <at> debbugs.gnu.org (full text, mbox):

From: Sergey Vinokurov <serg.foo <at> gmail.com>
To: Corwin Brust <corwin <at> bru.st>
Cc: Eli Zaretskii <eliz <at> gnu.org>, 53242 <at> debbugs.gnu.org
Subject: Re: bug#53242: [PATCH] unify reads from local_var_alist
Date: Sat, 15 Jan 2022 17:54:02 +0000

On 15/01/2022 16:02, Corwin Brust wrote:
> I tried to follow this conversation but it wasn't clear to me what out 
> motive is for this change.

The motive is that prior to change the alist with buffer-local variables 
was handled inconsistently. Sometimes with Fassoc, other times with 
Fassq and even assq_no_quit (the one that doesn't allow interrupts). 
Since the keys of alist are symbols (variable names), it doesn't make 
sense to use Fassoc which compares them with Fequal - an Fassq which 
does the comparison which simpler Feq would suffice.

> I had understood we typically make (especially in the c sources) our 
> changes to achieve specific, tangible improvement.  Is that the case 
> here?  is the particularly oppressive 'tech debt'?  In the latter case, 
> does history reflect consideration wrt the original selections in each 
> of the various cases we hereby change?

I don't know whether this is an oppressive tech debt, but from my 
perspective I have taken a look over handling of buffer-local variables 
during hacking some elisp code and saw the inconsistency. My patch is 
just an effort to reduce it and try to make Emacs a little bit better 
than it was before.

I don't know what the improvement will be, probably in will be pretty small.

My main consideration for selecting which function to use it to look at 
the types, notice that this in an associative list with symbols as keys 
and select the most appropriate function that would handle lookups in 
the list.

> Also (and especially if we must 'clean for the sake of cleanliness'), 
> could we prefer the (seeming more conservative of UX) interruptable 
> varient in this case?  (Is that very costly? How costly and how have we 
> measured that?)

Some parts before the change were already using uninterruptible variant.

The Fassq does more work than assq_no_quit because it's not only 
interruptible but also checks for circular lists whereas assq_no_quit 
does not handle them correctly and would just loop forever. It is safe 
to use assq_no_quit for buffer-local variables because this in Emacs 
internal structure not visible to the user, Emacs fully maintains it and 
does not make it into a circular list.

> Please consider the case of a package developer who may be abusing 
buffer-local vars during experiments.  It seems this will cause much 
more ’oops, time to kill Emacs/grab a coffee'.

I think it's unrealistic to introduce, even accidentally, enough 
buffer-local variables that lack of interruptibility in these particular 
functions will start to show.

This is based on the following benchmark, which I encourage everyone to 
try out. It creates a list of length n and does one lookup into it. This 
corresponds to a buffer having n local variables and the lookup is the 
operation we're arguing about (Fassq vs assq_no_quit). The assq_no_quit 
is not exposed in elisp as it's not safe so the benchmark uses Fassq but 
assq_no_quit will be pretty close as it does roughly the same amount of 
work.

(defun mk-list (n)
  (let ((res nil))
    (dotimes (i n)
      (push (cons i nil) res))
    res))

(byte-compile #'mk-list)

(let* ((n 100000)
       (xs (mk-list n)))
  (benchmark-call
   (lambda ()
     (assq 'foo xs))
   1))

It takes pretty large n to get the lookup take significant amount of 
time (please note that list creation time is not included in the 
calculation as it has nothing to do with Fassq vs assq_no_quit, so look 
at what benchmark-call returns and not on how long it all subjectively 
takes).

On my machine I need 10 000 000 elements for lookup to take 110 ms, 
which is a noticeable amount of time (probably still bearable to work 
with). For Emacs to "freeze" over, say 10 second, the number of 
variables introduced has to be even higher.

Is having millions (or hundreds of millions...) of buffer-local 
variables a reasonable scenario to consider? Please keep in mind that 
even if this occurs, interruptibility will not make lookups finish 
faster (even probably slower because of additional work that Fassq does 
compared to assq_no_quit). Yes, user would be able to C-g out of an 
operation if we use Fassq. But the operation will still be as much slow 
the next time it's performed. User will do the 'oops, time to kill 
Emacs/grab a coffee' sequence anyway in this case since any commands 
looking at local variables will be affected. AND this is the case with 
Emacs prior to my patch. Please do a benchmark and define 100 000 000 
local variables and see whether Emacs works appropriately well in this case.

I argue that if we're really concerned what would happen when someone 
defines a few hundred million local variables then we should not be 
asking a question whether reads of said variables are interruptible but 
should be asking a question whether linked list is the appropriate data 
structure to store local variables in the first place (spoiler alert: 
it's not).

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.