Re: [PATCH v2 00/16] Speeding up DEFVAR_PER_BUFFER

[Spencer Baugh]

Eli Zaretskii <eliz@gnu.org> writes:
>> From: Spencer Baugh <sbaugh@catern.com>
>> Cc: emacs-devel@gnu.org, arnold@tdrhq.com, monnier@iro.umontreal.ca,
>>  dgutov@yandex.ru, Richard Stallman <rms@gnu.org>
>> Date: Sun, 22 Nov 2020 11:28:27 -0500
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> > Thanks, but could you perhaps provide a more detailed overview of the
>> > general idea of the changeset?  It is not easy to glean that from 16
>> > patches, each one describing only the details of its narrow goal.
>> > Please include in the more detailed overview indications what parts of
>> > the series are really needed to speed up buffer-local variables and
>> > which are cleanups in the areas of the changes not directly related to
>> > speeding things up.
>> 
>> Patch 1 and 2 are tests; patch 15 is the speed-up change. Patches 3
>> through 14 all change the existing abstractions so that patch 15 can be
>> small, and should have no impact. Patch 16 is a followup further cleanup
>> enabled by 15. Only 15 should have any meaningful performance impact.
>
> Thanks, but I would also like to hear more about patches 3 to 14, and
> how they fit into the overall idea of the speedup change.  Could you
> please elaborate on that?  I'm not an expert on this stuff, and I'd
> like to understand the idea better, so that I could assess each part
> in the context of its place in the overall scheme of this changeset.
> I'm sure others could also benefit from hearing more details.

Sure, here is some overview of the change.

=== Background on DEFVAR_PER_BUFFER variables ===

DEFVAR_PER_BUFFER is a C macro which sets up a correspondence between a
Lisp symbol and a field of type Lisp_Object in the C `struct buffer'
struct.  There are a finite number of such fields, and DEFVAR_PER_BUFFER
is called for a subset of them.

Each DEFVAR_PER_BUFFER variable appears to Lisp code as a buffer-local
variable, and should behave like pure Lisp buffer-local variables.  Each
DEFVAR_PER_BUFFER variable is either permanently buffer-local, or has a
default value which is used by buffers that don't currently have a
buffer-local binding.

If a buffer has a buffer-local binding for one of these variables, then
the per-buffer value is stored in the corresponding field in that
buffer's `struct buffer'.

Default values for these variables are stored in a global `struct
buffer' C variable, `buffer_defaults'.  This struct does not correspond
to a real buffer, and its non-DEFVAR_PER_BUFFER fields are unused.  When
a variable's default value is changed, the corresponding field is
changed in (at least) buffer_defaults.  When `default-value' is used to
read a DEFVAR_PER_BUFFER variable's default value, it's read from
buffer_defaults.

The underlying fields in `struct buffer' used with DEFVAR_PER_BUFFER are
also read and written directly from C, through the BVAR macro.  The BVAR
macro takes a pointer to a `struct buffer' and the name of a field in
`struct buffer', and evaluates to the value for that field.

The variables must behave the same both when used through the symbol in
Lisp, and used through BVAR in C.  For example, if BVAR reads a field
from a buffer that does not have a buffer-local binding for that field,
it should evaluate to the default value for that field.

=== Old implementation ===

In the old implementation, the BVAR macro is essentially a no-op.  It
turns into a simple field dereference, essentially:

  #define BVAR(buf, field) (buf)->field

We simply read the field directly out of the specific `struct buffer'
we're working with.  Neither BVAR nor surrounding C code checks whether
a buffer has a buffer-local binding for a variable before using this
field, and at no point does most code check what value is in
buffer_defaults.

This is fine for permanently buffer-local DEFVAR_PER_BUFFER variables,
which have no default value.

For variables which are not permanently buffer-local, though, this means
we need to ensure that the C Lisp_Object field always contains the
"correct" value for the variable, whether that's a currently
buffer-local value, or the global default value.

If there is a buffer-local binding, then the field contains the
per-buffer value, and all is well.

If there is no buffer-local binding, then we need to ensure that the
field contains the global default value.

To do this, whenever the global default value changes, we iterate over
all buffers, and if there's no buffer-local binding, set the field to
the new default value. This is O(n) in the number of buffers open in
Emacs - quite slow.

= Old implementation: local_flags and buffer_local_flags =

Also, we frequently need to know whether a variable has a buffer-local
binding.  We maintain this information with the `local_flags' field in
`struct buffer', which is a char array with an entry for each
DEFVAR_PER_BUFFER variable.

When we create or kill a buffer-local binding for a DEFVAR_PER_BUFFER
variable, we update local_flags.

To support local_flags, we need even further metadata;
buffer_local_flags is a global, initialized at startup and constant
after that, which maps the offsets of the DEFVAR_PER_BUFFER C fields to
indices in local_flags.  We perform a lookup in buffer_local_flags
whenever we need to change local_flags for a variable.

= Old implementation: BVAR as lvalue =

Also, the BVAR macro is, regrettably, used widely in C for fields which
are not DEFVAR_PER_BUFFER fields.

As a "benefit" of this implementation of BVAR, BVAR is an lvalue, so C
code can directly assign to it. For example:

  XSETINT (BVAR (b, save_length), -1);

For a DEFVAR_PER_BUFFER field, this code would be buggy, since it
wouldn't update local_flags, which would result in unexpected behavior
visible from Lisp.  There was already one bug of this sort in
let-binding from Lisp; fortunately, there don't appear to be any in C at
the moment.

=== New implementation ===

In the new implementation, the BVAR macro actually does some work.
Simplifying a bit:

  #define BVAR(buf, field) EQ ((buf)->field, Qunbound) ? buffer_defaults.field 
: (buf)->field

We now use Qunbound as a sentinel to tell us whether the buffer has a
buffer-local binding for this field or not.  If the field contains
Qunbound, we should use the default value out of buffer_defaults; if
not, there's a buffer-local binding, and we should use the per-buffer
value.

We no longer need to iterate over all buffers whenever we change the
default value.  So setting the default value is now fast.

= New implementation: No more local_flags and buffer_local_flags =

Both of these are now useless and can be deleted.

When we create a buffer-local binding for a DEFVAR_PER_BUFFER variable,
we simply set the field.  When we kill a buffer-local binding, we set
the field to Qunbound.  There's no additional metadata.

= New implementation: BVAR is not an lvalue =

BVAR is not an lvalue anymore.  We could preserve that property with
some hacks, but this is probably for the best.  Uses of BVAR to set
field values have been changed to use dedicated functions; there weren't
that many anyway.

BVAR is still used by C to read Lisp_Object fields which are not
DEFVAR_PER_BUFFER fields, as well as DEFVAR_PER_BUFFER fields
corresponding to permanent-buffer-local variables.  Such fields will
never be Qunbound, but they still go through the check.

We could do a mass change to all the uses of BVAR, so that accesses to
non-DEFVAR_PER_BUFFER fields and permanent-buffer-local
DEFVAR_PER_BUFFER fields don't go through the conditional.  But the
additional check adds minimal overhead anyway; it will be easily
branch-predicted by modern CPUs.

=== Individual commits ===

See the individual commit messages for more.

       Add a test for let-binding unwinding
       Assert not local-variable-p after setq in let_default binding

These are test changes; fairly self-explanatory.

       Stop checking the constant default for enable_multibyte_characters
       Take buffer field name in DEFVAR_PER_BUFFER
       Add BVAR_DEFAULT for access to buffer defaults
       Use bset_* functions instead of BVAR

These changes eliminate usage of BVAR which aren't supported by the new
implementation: either usage of BVAR as an lvalue, or usage of BVAR to
access buffer_defaults (or both at once).

       Take offset not idx in PER_BUFFER_VALUE_P
       Combine unnecessarily separate loops in buffer.c
       Add and use BUFFER_DEFAULT_VALUE_P
       Add and use KILL_PER_BUFFER_VALUE
       Assert that PER_BUFFER_IDX for Lisp variables is not 0
       Rearrange set_internal for buffer forwarded symbols

These change or add abstractions for accessing buffer Lisp_Object
fields, to remove dependencies on implementation details which will
change.

       Get rid of buffer_permanent_local_flags array

This removes some usage of the buffer_local_flags indices in favor of a
simpler special case for the two pseudo-permanent-local variables it
applied to.

       Remove unnecessary Qunbound check

This removes an impossible-to-hit conditional that might otherwise be
confusing.

       Remove local_flags array in struct buffer
       Remove usage of buffer_local_flags

These are the actual remove-complexity, speed-things-up changes. See the
individual commit messages for more explanation of what happens in each.