Re: Should we land Lisp reader optimizations?

[Ken Raeburn]

On Jun 19, 2017, at 12:58, Eli Zaretskii <address@hidden> wrote:
> Ken,
> 
> I understand that some of the optimizations you made on your startup
> branch for reading and processing *.elc files are general-purpose
> enough and mature enough to start using them in Emacs 26.  Would it
> make sense to land them on master right now?  I think significant
> speedups in that department are always a win.
> 
> TIA

I think several of them would be reasonable to merge.  Others improve speed a 
little at some maintenance cost such as having mostly-duplicated code, or using 
more complex data structure management than we have currently.  But I’ve been 
doing all my work with an eye towards the big dumped.elc file produced by 
Stefan’s changes; it has some unusual characteristics, like most of the file 
being one big “progn” with lots of multiply-referenced forms, versus having 
lots of separate “defalias” calls and the like.

It would be good to come up with some new benchmark or two by which to evaluate 
some of the individual changes to see if they’re worth the maintenance cost.  
Probably something like “read all Lisp forms from a set of .elc files 
previously loaded into buffers” or “load a set of .elc files from disk”…

Looking over the changes, here are my initial thoughts:

1. Use getc_unlocked instead of getc: Small change, makes a bigger difference 
for Darwin/mac OS than under glibc.  I don’t know if the *BSD distributions are 
similar to Darwin here.

2. Reduce lread substitutions for multiply-referenced cons cells: This change 
of Stefan’s made a big difference in handling circular structures, and is quite 
localized to a small bit of reader code.

3. Skip recursive scanning of some object types: Very localized, addresses some 
of the remaining recursive-substitution time if we don’t have to look up 
objects we know won’t be found in the list we’ve saved.  Less relevant if that 
list won’t be large anyway.

4. Use hash tables instead of lists (read_objects and/or seen_list) in 
recursive substitution code: A little bit more intrusive in the reader code 
setup, but not terribly much so.  Reduces lookups to O(log n) from O(n), so 
again, mostly interesting if we care about the case where the collections are 
large and multiply-referenced objects are common.

5. Reducing nested calls for lists in substitution: This wasn’t about 
performance per se, or reducing stack depth, but changing the list processing 
to iterative from recursive made analysis easier with some of the Apple tools 
that organize execution profile samples by stack traces.  It’s a localized 
change, though, and I tend to prefer iteration over unbounded recursion with 
possibly limited stack sizes.  I’m interested what others think.

6. Optimizing reading of ASCII symbols from a file: Very specific to that case. 
 Code duplication with specialization, in what’s already a large function.

7. Don’t memset charset maps before filling them in: Tiny change, small 
optimization. Not really a Lisp reader change.

8. Generate less garbage when reading symbols: Open-code some of the “intern” 
process so we don’t have to create a string that we’ll just throw away if the 
symbol is already interned.  Probably doesn’t make a big difference in speed 
directly unless it reduce garbage collection passes.

9. Use #N# syntax for repeated use of symbols: Reading the numbers is faster 
than reading the strings.  Only relevant if symbol names are repeated often 
within a single S-expression, so more helpful for dumped.elc than for regular 
.elc files.  Works better with the hash table changes.

There’s some overlap, obviously; the time spent reading symbols in a .elc file 
would be reduced by #6 and by #9, but either of them will reduce the impact of 
the other.

Some of these are actually expressed as multiple changes on the 
scratch/raeburn-startup branch, though I’ve been working on a rebased version 
from a recent master snapshot that cleans up and merges some of the changes, 
gets rid of a couple things no longer needed, and fixes a few more bugs with 
the dumped data.  I’ve still got an annoying coding-system problem to track 
down before I push the updated branch, though.

#1-3, and #8 are simple and straightforward enough that I think they’re 
probably good to take, even if the savings aren’t large with normal Lisp files. 
 #7 also, though it’s for charset maps, not Lisp.  #4 and #9 are dependent on 
the sorts of files being loaded; benchmarking will show us how much of a 
difference they might make.

#6 is probably the most annoying for ongoing maintenance.  Existing code is 
copied, specialized for the case of reading from files, some functions are 
expanded inline, irrelevant code is removed, and the block/unblock calls are 
pulled out from inner loops.  Depending how the numbers work out with the other 
changes, it might not be worth it, or maybe only if we go the big-elc-file 
route.

Ken