Re: Ideal performance of ELisp (was: Why tree-sitter instead of Semantic? (was Re: CC Mode with font-lock-maximum-decoration 2))

[Lynn Winebarger <owinebar@gmail.com>]

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

On Fri, Aug 12, 2022, 5:50 PM Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> >> > I don't have this information.  Maybe someone else does.  But in
> >> > general, it is a very small wonder that a parser written in optimized
> >> > C is much faster than anything written in Emacs Lisp, given that Lisp
> >> > is an interpreted language that has no special support for writing
> >> > parsers.
> >> That can be cured over time, now that the bulk of the core of emacs
> >> uses lexical scoping.
> > I very much doubt that.
>
> Agreed.
>

I noted the switch to lexical scope, because dynamic scope prevents any
call from ever being a tail call in any meaningful sense.  It's not
automatic, but when the core of Emacs lisp code used dynamic scoping,
changes to the VM to support proper tail recursion would have been
meaningless.  That is no longer the case.
Once the VM supports proper tail recursion, it's straightforward to
generate automata that never perform a function call, at least not as part
of the recognizer.  Lisp with proper tail recursion gives you the
equivalent of computed goto's, which are not available in
standards-conformant C AFAIK.  If the compiler can prove certain local
variables are always fixnums and remove the tag/untag overhead, then the
generated IR passed to libgccjit (or clang) should be able to match
anything expressible in C for those automata.
The code in the actions may not be as optimizable as the recognition
automata, I'll grant you.

> ELisp code cannot match the speed of optimized C code.
>
> I suspect it could, to some extent, in theory.  Getting there would
> require a fair bit more work, probably using a different compilation
> strategy than the AOT compiler we have now.


> A good reference is JavaScript which shouldn't be noticeably easier to
> compile efficiently and where many millions of dollars have been poured
> over several years to speed it up.  The result is indeed able to match
> the performance of C nowadays for several non-trivial examples of code,
> but it's far from obvious that we have the resources to reproduce this
> feat for ELisp.


The claim wasn't that every piece of ELisp code could be as optimized as
sharply written C or C++ code, but that there is a subset that is (that can
be targeted by tools like parser and lexer generators), at least at the
level of an abstract RISC machine that the IRs for compiler backends like
libgccjit or llvm let you target.

I don't think the compiler has to match the level of optimization of the V8
compiler to get significant improvements in the performance of ELisp.
We're really only talking about optimizations known to Common Lisp and
Scheme compiler writers in the 1980s.  However, the most significant
improvements in performance will probably only come after changes that
remove impediments to parallelizing work and improved memory management.

Lynn

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