Re: Emacs Lisp JIT Compiler

Re: Emacs Lisp JIT Compiler

[Nickolas Lloyd]

Burton Samograd wrote:
> By showing this ida/work I’m hoping not to get it included in emacs
> proper, but to show a relatively simple way to speed things up.  I’m
> sure there are better/alternate implementations that would both be
> cleaner and give better speedups, but this was as far as this POC went
> so far.

Coincidentally, for the past few weeks I've been working on a very
similar idea, with a slightly different implementation.  Instead of
every instruction compiling down to a function call that directly mimics
the interpreter, in many places those intermediate functions are removed
and replaced by direct calls to e.g. Ffuncall, Fconcat, etc.  Instead of
adding a new instruction to replace the original bytecode, a pointer to
the function is stashed away inside of the bytecode vector.  Other than
that it looks to be largely similar.

The code is in a repo at:

    https://github.com/smindinvern/emacs.git
    
in branch `elc-jit'.  It's based off of emacs-25, and so far during my
testing enabling the JIT globally seems to be stable. There seem to be
some performance penalties with that, though, due to some functions
which are byte-compiled many times at runtime....  I was able to produce
gains of 15-20% on your ray-tracing benchmark, though, so there is a
significant speedup for individual functions.

I bring this up, for those interested, because it is fully working with
a recent version of emacs.  Maybe there are some things that could be
learned from each implementation?

I've also looked into using libgccjit, though the object model seems a
bit more complicated, with distinctions made between lvalues, rvalues,
etc.  I'll probably do some work on porting my code to libgccjit at some
point to see how the performance compares.

Thanks,
Nick

Re: Emacs Lisp JIT Compiler

[John Wiegley]

>>>>> "NL" == Nickolas Lloyd <ultrageek.lloyd@gmail.com> writes:

LN> I bring this up, for those interested, because it is fully working with a
LN> recent version of emacs. Maybe there are some things that could be learned
LN> from each implementation?

Hi Nickolas,

If your papers with the FSF are signed, could you push this also to branch?
Once both JIT/pre-compilation branches are working, it would be useful to
compare benchmarks between the two.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Emacs Lisp JIT Compiler

[Nickolas Lloyd]

John Wiegley <jwiegley@gmail.com> writes:
> Hi Nickolas,
>
> If your papers with the FSF are signed, could you push this also to branch?
> Once both JIT/pre-compilation branches are working, it would be useful to
> compare benchmarks between the two.

Hi John,

Yes, I'd be happy to!  I've not signed the papers yet, but I'll begin
that process so that I can push the changes.

Thanks,
Nick

Re: Emacs Lisp JIT Compiler

[John Wiegley]

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

>>>>> Nickolas Lloyd <ultrageek.lloyd@gmail.com> writes:

> Yes, I'd be happy to! I've not signed the papers yet, but I'll begin that
> process so that I can push the changes.

Thank you!  assign@gnu.org will get you sorted.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

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

Re: Emacs Lisp JIT Compiler

[Nickolas Lloyd]

John Wiegley <jwiegley@gmail.com> writes:

>>>>>> Nickolas Lloyd <ultrageek.lloyd@gmail.com> writes:
>
>> Yes, I'd be happy to! I've not signed the papers yet, but I'll begin that
>> process so that I can push the changes.
>
> Thank you!  assign@gnu.org will get you sorted.

Now that I've gotten commit access, I've finally sorted my code into a
logical commit sequence and pushed it to the `nick.lloyd-bytecode-jit'
branch.  I intend to do some more work on cleaning it up and
streamlining it, but it's been recently merged with master and is
available for testing/review.

Also, I did make an attempt to modify this code to use libgccjit instead
of libjit, with some success.  It was able to run Burton's ray-tracer
test in batch mode a few seconds faster than the libjit version, but
running Emacs in interactive mode caused an abort in gcc.  I haven't had
much time to investigate that so I've decided to stick with libjit for
now.

I would certainly appreciate any and all feedback.

Thanks,
Nick

Re: Emacs Lisp JIT Compiler

[Johan Bockgård]

John Wiegley <jwiegley@gmail.com> writes:

> Once both JIT/pre-compilation branches are working, it would be useful
> to compare benchmarks between the two.

There was also an old attempt to bring native compilation to Emacs by
using GNU lightning:

http://www.mundell.ukfsn.org/native/
http://lists.gnu.org/archive/html/emacs-devel/2004-03/msg00469.html

Emacs Lisp JIT Compiler

[Tom Tromey]

Hi.  I've written a JIT compiler for Emacs Lisp, and I'd like to check
it in.

This JIT is based on GNU libjit, like some other attempts that have come
before it.  However, this one is somewhat faster than those, primarily
because it does all stack manipulations at compile time, not runtime.

In some simple benchmarks, it is about 3x faster than the bytecode
interpreter.

I have only tested this on x86-64.  Whether or not the JIT works on a
given platform is primarily up to libjit.  (I suspect the JIT won't work
on x86 with --with-wide-int; but that is something I could fix.)

I currently have the JIT set up to always compile all eligible functions
(that is, just byte-compiled, lexically-bound functions).  It's robust
enough that, as far as I can tell, everything works fine in this mode.
It would be possible to have it be a bit lazier, say only compile after
100 invocations, or something like that.

Aside from the possible --with-wide-int thing, there are two bugs I know
of.

First, libjit never frees functions.  So, if a function is JIT-compiled
and then redefined, the old JIT code will linger.  It's possible to fix
this with a custom allocator and a libjit patch (that I sent but that
hasn't been checked in yet).

Second, I haven't gotten around to emulating the "quitcounter" behavior
in the bytecode interpreter.  This seems straightforward.


This version of the compiler is pretty basic.  It just compiles each
bytecode to more or less the obvious thing.  I have some plans to make
the calling convention a bit less expensive, and to allow for inlining.

Note that this change does not involve any semantic changes to Emacs Lisp.
Also, if libjit is unavailable, the JIT is simply disabled.

Tom

Re: Emacs Lisp JIT Compiler

[Paul Eggert]

This sounds very interesting. I assume you'd publish it first on a branch so 
that we could look at it? Some questions:

> I have only tested this on x86-64.  Whether or not the JIT works on a
> given platform is primarily up to libjit.  (I suspect the JIT won't work
> on x86 with --with-wide-int; but that is something I could fix.)

When you say "doesn't work", does that mean Emacs can reliably tell the JIT 
won't work and fall back on the current bytecode implementation, or something else?

> libjit never frees functions.  So, if a function is JIT-compiled
> and then redefined, the old JIT code will linger.  It's possible to fix
> this with a custom allocator and a libjit patch (that I sent but that
> hasn't been checked in yet).

libjit has only one committer, Aleksey, and no commits since March. Is there a 
bottleneck there?

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Paul" == Paul Eggert <eggert@cs.ucla.edu> writes:

Paul> When you say "doesn't work", does that mean Emacs can reliably tell
Paul> the JIT won't work and fall back on the current bytecode
Paul> implementation, or something else?

What I meant is that when I wrote this, I didn't think about
--with-wide-int, and so some of the calls into libjit are incorrect for
that situation.  It shouldn't be hard to fix.

>> libjit never frees functions.  So, if a function is JIT-compiled
>> and then redefined, the old JIT code will linger.  It's possible to fix
>> this with a custom allocator and a libjit patch (that I sent but that
>> hasn't been checked in yet).

Paul> libjit has only one committer, Aleksey, and no commits since March. Is
Paul> there a bottleneck there?

He's reasonably responsive, but it's true that the lack of an active
community around libjit is a bit of a risk.  Mostly the problems would
be either (1) missing ports or (2) lack of improvements; for example,
libjit's register allocator is not very good, but nobody is working on
improving it.

It would be possible to switch to another JIT back end, but when I
looked into the various ones that are available, libjit was both easy to
use and reasonably lightweight (without being too lightweight, like GNU
Lightning).

But, for example, GCC has a JIT interface now.  That could be used instead.
That seemed pretty heavy-weight to me; but I didn't really try it in
anger so maybe my fears are unfounded.

Tom

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

Paul> This sounds very interesting. I assume you'd publish it first on a
Paul> branch so that we could look at it?

Now it is feature/libjit.

Paul> libjit has only one committer, Aleksey, and no commits since March. Is
Paul> there a bottleneck there?

Another possibility is to switch to gcc-jit.  On the up side, it is part
of GCC, so it is maintained and widely ported.  The down side is that,
currently, it requires more capabilities at runtime; for example it
invokes the assembler and, I believe, uses dlopen under the hood.

One thing I've been thinking about with gcc-jit is that it would be
"relatively" straightforward to also have it work as an ahead-of-time
compiler.  What I picture here is a step during dumping where all the
dumped bytecode functions are compiled into a shared library.

It might be worth doing the experiment to find out.

Tom

Re: Emacs Lisp JIT Compiler

[Daniel Colascione]

> Paul> This sounds very interesting. I assume you'd publish it first on a
> Paul> branch so that we could look at it?
>
> Now it is feature/libjit.
>
> Paul> libjit has only one committer, Aleksey, and no commits since March.
> Is
> Paul> there a bottleneck there?
>
> Another possibility is to switch to gcc-jit.  On the up side, it is part
> of GCC, so it is maintained and widely ported.  The down side is that,
> currently, it requires more capabilities at runtime; for example it
> invokes the assembler and, I believe, uses dlopen under the hood.

I still think that needing binutils for ordinary use is a non-starter.

>
> One thing I've been thinking about with gcc-jit is that it would be
> "relatively" straightforward to also have it work as an ahead-of-time
> compiler.  What I picture here is a step during dumping where all the
> dumped bytecode functions are compiled into a shared library.
>
> It might be worth doing the experiment to find out.

In the end, it might be useful to adopt an SBCL-like compiled-code-only
model.

Re: Emacs Lisp JIT Compiler

[Paul Eggert]

On 08/14/2018 01:11 PM, Daniel Colascione wrote:
> I still think that needing binutils for ordinary use is a non-starter.

That shouldn't be an issue since Emacs would fall back on the 
traditional C interpreter when gcc-jit is not available or not used. So 
binutils would not be necessary for normal use, it's merely something 
that will improve performance if available.

Re: Emacs Lisp JIT Compiler

[Daniel Colascione]

> On 08/14/2018 01:11 PM, Daniel Colascione wrote:
>> I still think that needing binutils for ordinary use is a non-starter.
>
> That shouldn't be an issue since Emacs would fall back on the
> traditional C interpreter when gcc-jit is not available or not used. So
> binutils would not be necessary for normal use, it's merely something
> that will improve performance if available.

No. The performance difference under discussion here will make the
difference between certain applications being feasible or not. Randomly
varying the performance of loaded elisp code to such a degree depending on
the presence of various system tools is unacceptable and will create a
terrible impression among end users.

Re: Emacs Lisp JIT Compiler

[Paul Eggert]

On 08/14/2018 02:03 PM, Daniel Colascione wrote:
> Randomly
> varying the performance of loaded elisp code to such a degree depending on
> the presence of various system tools is unacceptable

Are you're saying you'd rather have predictably bad performance, than 
have an application that sometimes has the bad performance in some 
situations, and 3x better performance in other situations? If this is a 
real issue, we can easily arrange for Emacs to have predictably bad 
performance all the time (for people who prefer this), by having a 
configure-time or run-time option that says "I want predictably-bad 
performance". However, I expect most users would rather have 3x better 
performance when it's available.

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 14 Aug 2018 15:38:44 -0700
> Cc: Tom Tromey <tom@tromey.com>, emacs-devel@gnu.org
> 
> On 08/14/2018 02:03 PM, Daniel Colascione wrote:
> > Randomly
> > varying the performance of loaded elisp code to such a degree depending on
> > the presence of various system tools is unacceptable
> 
> Are you're saying you'd rather have predictably bad performance, than 
> have an application that sometimes has the bad performance in some 
> situations, and 3x better performance in other situations?

I agree with Daniel here: having vastly different performance due to
factors more or less out of end-user's control is bad for UX.

That doesn't mean we want to have predictably bad performance, but it
does mean that we should choose our JIT library so that it doesn't
suffer from such issues.

Re: Emacs Lisp JIT Compiler

[Paul Eggert]

Eli Zaretskii wrote:
> we should choose our JIT library so that it doesn't
> suffer from such issues

Yes, of course that would be preferable. However, performance variation is just 
one factor, and other factors in JIT libraries are just as important, if not 
more so. We shouldn't have this one factor overriding everything else.

Besides, none of the JIT approaches we're talking about are free from the issues 
Daniel raised: they all have significant performance differences on different 
platforms. If we're going to reject a JIT approach merely because a 3x 
performance improvement on one platform isn't equally shared by other platforms, 
we might as well just be up front about it and say we're going to reject all JIT 
approaches.

(If performance variation is really a problem, we could have Emacs default to 
running slowly on all platforms, and speed up only when the user asks it to. :-)

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Wed, 15 Aug 2018 10:16:55 -0700
> Cc: dancol@dancol.org, tom@tromey.com, emacs-devel@gnu.org
> 
> Besides, none of the JIT approaches we're talking about are free from the issues 
> Daniel raised: they all have significant performance differences on different 
> platforms. If we're going to reject a JIT approach merely because a 3x 
> performance improvement on one platform isn't equally shared by other platforms, 
> we might as well just be up front about it and say we're going to reject all JIT 
> approaches.

The fact there are platform-specific differences in performance
doesn't yet mean the differences are significant enough for us to
reject all of the JIT libraries.  We don't need to give up so quickly.

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

Paul> Are you're saying you'd rather have predictably bad performance, than 
Paul> have an application that sometimes has the bad performance in some 
Paul> situations, and 3x better performance in other situations?

I am not sure I agree with this logic; to me it sounds like a sort of
reductio ad absurdum of what Daniel said.  But what he said makes sense,
and it's an issue with the JIT idea.

That said I don't think it is a very important issue, I think primarily
because interested users can port the JIT as needed.

Eli> I agree with Daniel here: having vastly different performance due to
Eli> factors more or less out of end-user's control is bad for UX.

Eli> That doesn't mean we want to have predictably bad performance, but it
Eli> does mean that we should choose our JIT library so that it doesn't
Eli> suffer from such issues.

There is no JIT library that supports everything.  GCC targets
everything but I think (based on looking through bugzilla) doesn't
support all hosts; and also as Daniel points out, requires binutils at
runtime.  libjit has been ported to some targets but not all (for
example, it wouldn't support the Lemote Yeeloong that RMS used to use,
since it has a MIPS chip).

So, if this is the idea, then I fear Emacs will never have a JIT.

Now, one thing that is portable is compiling Emacs Lisp code to C.  For
example, it would be easy to compile all the bytecode that is dumped
into Emacs.  The drawback is that this is just a fraction of what users
use; and would probably not show major benefits.  But, maybe it would
help some.  And, it would certainly allow some existing C code (looking
at you, widget-put) to be moved to Lisp, which seems worthwhile to me.

Tom

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Tom Tromey <tom@tromey.com>
> Cc: Paul Eggert <eggert@cs.ucla.edu>,  dancol@dancol.org,  tom@tromey.com,  emacs-devel@gnu.org
> Date: Wed, 15 Aug 2018 18:29:37 -0600
> 
> That said I don't think it is a very important issue, I think primarily
> because interested users can port the JIT as needed.

Only if they are _very_ interested, and have the knowledge/talent to
do that.

> Eli> That doesn't mean we want to have predictably bad performance, but it
> Eli> does mean that we should choose our JIT library so that it doesn't
> Eli> suffer from such issues.
> 
> There is no JIT library that supports everything.

OK, let me rephrase: we should choose our JIT library so that it
suffers as little as possible from such issues.

> So, if this is the idea, then I fear Emacs will never have a JIT.

I don't think this is the idea.  I think the idea is to strive to
support as many popular platforms as we can.

> Now, one thing that is portable is compiling Emacs Lisp code to C.

That again needs a compiler and Binutils, so it suffers from the same
drawback.

Re: Emacs Lisp JIT Compiler

[Daniel Colascione]

>> From: Tom Tromey <tom@tromey.com>
>> Cc: Paul Eggert <eggert@cs.ucla.edu>,  dancol@dancol.org,
>> tom@tromey.com,  emacs-devel@gnu.org
>> Date: Wed, 15 Aug 2018 18:29:37 -0600
>>
>> That said I don't think it is a very important issue, I think primarily
>> because interested users can port the JIT as needed.
>
> Only if they are _very_ interested, and have the knowledge/talent to
> do that.

It only takes one such person though.

>> Eli> That doesn't mean we want to have predictably bad performance, but
>> it
>> Eli> does mean that we should choose our JIT library so that it doesn't
>> Eli> suffer from such issues.
>>
>> There is no JIT library that supports everything.
>
> OK, let me rephrase: we should choose our JIT library so that it
> suffers as little as possible from such issues.

Right. And I think a standalone library is less likely to suffer from
these issues than one that requires a full toolchain. It's easier to port
back-end machine-code generation to an architecture than it is to port all
of binutils.

I also strongly suspect (albeit without numbers ATM) that the standalone
approach will yield much better performance than one which involves a trip
through the filesystem and a compilation toolchain. A standalone system
lets us do tiered and profile-guided compilation in a way that a big batch
process really can't accommodate due to overheads.

I think it's also really important to emphasize the "IT" aspect of the JIT
system. That is, there are tons of cases where it would be a huge help to
generate specialized code (e.g., for parsing) and compile it on-the-fly.
Imagine we have decent elisp parsers for languages A and B, but we (in
some distant and glittering future) have robust multi-mode support and
want to parse the language (A|B) in the buffer. Wouldn't it be nice to
just synthesize A|B into some code and compile that straight to machine
code?

Likewise, it'd be fantastic to compile regular expressions to DFAs and
then generate machine code for the DFAs. You can't go faster than that.

All of these use cases need a level of dynamism that I'm afraid we
wouldn't be able to get with good performance via a toolchain-based
system.

Re: Emacs Lisp JIT Compiler

[Andreas Schwab]

On Aug 16 2018, "Daniel Colascione" <dancol@dancol.org> wrote:

> Right. And I think a standalone library is less likely to suffer from
> these issues than one that requires a full toolchain. It's easier to port
> back-end machine-code generation to an architecture than it is to port all
> of binutils.

Porting binutils is a zero-effort, since you have that already.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Daniel" == Daniel Colascione <dancol@dancol.org> writes:

Daniel> I also strongly suspect (albeit without numbers ATM) that the standalone
Daniel> approach will yield much better performance than one which involves a trip
Daniel> through the filesystem and a compilation toolchain. A standalone system
Daniel> lets us do tiered and profile-guided compilation in a way that a big batch
Daniel> process really can't accommodate due to overheads.

True, though it's worth noting that libjit doesn't really have
optimization passes to speak of.  Also things like deoptimization seem
hard with libjit; there's no support for patching functions or on stack
replacement or whatnot.

libjit optimizations could be written.  I haven't tried, so I don't
know how hard it is in practice.

I do have an incomplete branch where I'm changing the JIT calling
convention to try to get better performance in the common case.  This
branch would also allow inlining (with a runtime check to ensure the
callee hasn't changed).

Going beyond this sort of thing (for instance Stefan sent me this very
interesting paper about basic block versioning) probably requires a
truly custom JIT from the bottom up.

Daniel> Likewise, it'd be fantastic to compile regular expressions to DFAs and
Daniel> then generate machine code for the DFAs. You can't go faster than that.

I've been meaning to experiment with this using Stefan's lex.el.
It seems to me that the bytecode compiler could open-code some common
things like (looking-at "some constant").

One "simple" way to improve regexp matching right now would be to remove
the self-modifying code and change the implementation to use token
threading, like we did for the bytecode interpreter.  Not nearly as good
as a DFA but still a step forward.  I think removing this self-modifying
stuff is also useful if we ever want to introduce first-class regexp
objects.

Tom

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Tom Tromey <tom@tromey.com>
> Cc: "Eli Zaretskii" <eliz@gnu.org>,  emacs-devel@gnu.org,  Tom Tromey <tom@tromey.com>,  eggert@cs.ucla.edu
> Date: Sun, 19 Aug 2018 12:17:01 -0600
> 
> True, though it's worth noting that libjit doesn't really have
> optimization passes to speak of.

There's jit_optimize, although AFAIU, jit_compile already performs
optimizations.

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Eli" == Eli Zaretskii <eliz@gnu.org> writes:

>> From: Tom Tromey <tom@tromey.com>
>> Cc: "Eli Zaretskii" <eliz@gnu.org>,  emacs-devel@gnu.org,  Tom Tromey <tom@tromey.com>,  eggert@cs.ucla.edu
>> Date: Sun, 19 Aug 2018 12:17:01 -0600
>> 
>> True, though it's worth noting that libjit doesn't really have
>> optimization passes to speak of.

Eli> There's jit_optimize, although AFAIU, jit_compile already performs
Eli> optimizations.

Yeah.  jit_optimize just does some CFG cleanups.  And the JIT does some
constant folding I believe; but nothing more serious.

libjit is a nice, clean design.  Unfortunately its development seems to
have been interrupted, so consequently some parts aren't really fleshed
out.

Tom

Re: Emacs Lisp JIT Compiler

[Stefan Monnier]

> Daniel> Likewise, it'd be fantastic to compile regular expressions to DFAs and
> Daniel> then generate machine code for the DFAs. You can't go faster than that.
> I've been meaning to experiment with this using Stefan's lex.el.
> It seems to me that the bytecode compiler could open-code some common
> things like (looking-at "some constant").

lex.el's matcher (i.e. an Elisp loop interpetering the DFA
data-structure) is already pretty fast (i.e. competitive) in my
experience compared to the C based regex.c code.  So I think that
a C implementation of lex.el's matcher would already be so fast that
generating machine code for it would only make sense in extremely
rare circumstances.

> One "simple" way to improve regexp matching right now would be to remove
> the self-modifying code and change the implementation to use token
> threading, like we did for the bytecode interpreter.

Indeed, our regex.c code has a lot of room for improvement.  Given its
nasty worst case behavior, I've been reluctant to invest any more time
into it.

> I think removing this self-modifying stuff is also useful if we ever
> want to introduce first-class regexp objects.

It's also needed to make it re-entrant.


        Stefan

Re: Emacs Lisp JIT Compiler

[Steinar Bang]

>>>>> Eli Zaretskii <eliz@gnu.org>:

>> From: Tom Tromey <tom@tromey.com>

>> Now, one thing that is portable is compiling Emacs Lisp code to C.

> That again needs a compiler and Binutils, so it suffers from the same
> drawback.

It could be used ahead-of-time (or whatever the term is), to move emacs
code currently implemented in C to lisp.

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Steinar Bang <sb@dod.no>
> Date: Sat, 18 Aug 2018 12:10:01 +0200
> 
> >>>>> Eli Zaretskii <eliz@gnu.org>:
> 
> >> From: Tom Tromey <tom@tromey.com>
> 
> >> Now, one thing that is portable is compiling Emacs Lisp code to C.
> 
> > That again needs a compiler and Binutils, so it suffers from the same
> > drawback.
> 
> It could be used ahead-of-time (or whatever the term is), to move emacs
> code currently implemented in C to lisp.

The intent is to allow Emacs to compile _any_ Lisp into native code.
The main advantage of that is when the Lisp in question didn't come
with the distribution.  Because otherwise we could just JIT-compile
everything in advance and be done.

IOW, what you mention is a one-time feature, mainly useful to Emacs
developers.  The drawback I mentioned is for the Emacs users, and
AFAIU the JIT feature mainly targets the users.

Re: Emacs Lisp JIT Compiler

[Robert Pluim]

Eli Zaretskii <eliz@gnu.org> writes:

>> It could be used ahead-of-time (or whatever the term is), to move emacs
>> code currently implemented in C to lisp.
>
> The intent is to allow Emacs to compile _any_ Lisp into native code.
> The main advantage of that is when the Lisp in question didn't come
> with the distribution.  Because otherwise we could just JIT-compile
> everything in advance and be done.
>
> IOW, what you mention is a one-time feature, mainly useful to Emacs
> developers.  The drawback I mentioned is for the Emacs users, and
> AFAIU the JIT feature mainly targets the users.

Unless Iʼve misunderstood, nothing prevents us from doing both:
pre-compile all the lisp that ships with emacs to C, and also have a
JIT for 'user code'.  Personally, a JIT that sometimes gives me a
speed increase with a fallback of 'same speed as before' sounds like a
big win to me.

Robert

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Robert Pluim <rpluim@gmail.com>
> Cc: Steinar Bang <sb@dod.no>,  emacs-devel@gnu.org
> Date: Sun, 19 Aug 2018 12:00:51 +0200
> 
> Unless Iʼve misunderstood, nothing prevents us from doing both:
> pre-compile all the lisp that ships with emacs to C, and also have a
> JIT for 'user code'.  Personally, a JIT that sometimes gives me a
> speed increase with a fallback of 'same speed as before' sounds like a
> big win to me.

All true and agreed to, but the original issue was whether producing C
from Lisp could be a good alternative to implementing JIT, and that is
the context in which my response should be read.

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Eli" == Eli Zaretskii <eliz@gnu.org> writes:

>> Now, one thing that is portable is compiling Emacs Lisp code to C.

Eli> That again needs a compiler and Binutils, so it suffers from the same
Eli> drawback.

Sorry for being unclear here, as Steinar surmised, what I meant was
build-time translation of some elisp code.

Tom

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:

Tom> Now, one thing that is portable is compiling Emacs Lisp code to C.  For
Tom> example, it would be easy to compile all the bytecode that is dumped
Tom> into Emacs.  The drawback is that this is just a fraction of what users
Tom> use; and would probably not show major benefits.  But, maybe it would
Tom> help some.  And, it would certainly allow some existing C code (looking
Tom> at you, widget-put) to be moved to Lisp, which seems worthwhile to me.

I wrote a bytecode->C compiler to see what this would look like.  It is
set up to walk the obarray and compile every lexically-bound bytecode
function that it finds there.

The resulting .o files are roughly the same size as the rest of the
Emacs .o files.  So, maybe that's a bit too big.  One idea would be to
segregate the code that is to be compiled.  This would allow rewriting
some of the C code into Lisp at least.

Another issue is that runtime linking -- that is, associating the
compiled code with the bytecode -- is hard.  My current approach (which
isn't fully hooked up yet) is to use the doc string index as a key.
However, this is not fantastic because it means that undocumented
functions can't be compiled.

Runtime linking is needed because of two issues; otherwise the compiler
could just emit DEFUNs.  One, I didn't want to deal with compiling
complex lisp constants to C.  Doing this properly would mean introducing
initialization code.  Two, I think the DEFUN approach wouldn't work for
closures.

Perhaps if the segregation approach were taken, there could just be some
rules against closures and complex constants, and the compiler could
error if they were introduced.

Tom

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

I made the feature/libjit branch build with MinGW.  The
"--with-wide-int" configuration still doesn't work correctly, although
I made quite a few changes to support that.  A 32-bit build without
wide ints successfully bootstrapped, and I believe a 64-bit MinGW
build should work as well, although I didn't try that.

Tom, I'd appreciate your review on the changes, especially changes for
the function signatures, as I found a few of them to be at odds with
the actual functions they represent, and so I wonder whether I missed
some subtlety.

Thanks.

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Eli" == Eli Zaretskii <eliz@gnu.org> writes:

Eli> I made the feature/libjit branch build with MinGW.  The
Eli> "--with-wide-int" configuration still doesn't work correctly, although
Eli> I made quite a few changes to support that.  A 32-bit build without
Eli> wide ints successfully bootstrapped, and I believe a 64-bit MinGW
Eli> build should work as well, although I didn't try that.

Thanks for doing this.

Eli> Tom, I'd appreciate your review on the changes, especially changes for
Eli> the function signatures, as I found a few of them to be at odds with
Eli> the actual functions they represent, and so I wonder whether I missed
Eli> some subtlety.

It looks pretty good to me.  I was surprised to see the code to
dynamically load libjit, but I don't really know what restrictions the
MinGW port is subject to.

There are several hunks like:

+#if EMACS_INT_MAX <= LONG_MAX
       tem = jit_value_create_nint_constant (func, jit_type_sys_int,
 					    MOST_POSITIVE_FIXNUM);
+#else
+      tem = jit_value_create_long_constant (func, jit_type_sys_longlong,
+					    MOST_POSITIVE_FIXNUM);
+#endif

Here I think it would be better to define a new type at init time and
avoid #ifs in the code itself.

I like the introduction of lisp_object_type for this reason.  I think I
was being a bit lax about the types here, as you note.  Most things,
like the CONSTANT macro, I think should be using lisp_object_type,
because that's the fundamental type of bytecode operations.  Only
specialized spots like extracting a fixnum value or calling some C
function should be using other types.

Tom

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Tom Tromey <tom@tromey.com>
> Cc: Tom Tromey <tom@tromey.com>,  emacs-devel@gnu.org
> Date: Fri, 24 Aug 2018 11:54:06 -0600
> 
> It looks pretty good to me.  I was surprised to see the code to
> dynamically load libjit, but I don't really know what restrictions the
> MinGW port is subject to.

In general, any library that is not strictly required for Emacs to
work (i.e. it either supports an optional feature or we have fallback
code to provide the same feature) should on Windows ideally be probed
at run time and loaded dynamically only if it's available, because we
want to allow users to run Emacs without those libraries being
installed.  The reason is that finding and installing all those
libraries is not always easy on Windows.

> There are several hunks like:
> 
> +#if EMACS_INT_MAX <= LONG_MAX
>        tem = jit_value_create_nint_constant (func, jit_type_sys_int,
>  					    MOST_POSITIVE_FIXNUM);
> +#else
> +      tem = jit_value_create_long_constant (func, jit_type_sys_longlong,
> +					    MOST_POSITIVE_FIXNUM);
> +#endif
> 
> Here I think it would be better to define a new type at init time and
> avoid #ifs in the code itself.

Maybe I'm missing something, but I didn't see how to do that with just
a type definition.  jit_value_create_long_constant is special in that
it allows to create 64-bit constants in a 32-bit build, by allocating
a 64-bit buffer and storing it address in the jit_value_t object it
returns.  jit_value_get_long_constant is then capable to access the
value in that buffer.  By contrast, all the other jit_value_create_*
functions store the value directly in the jit_value_t object, so they
can support values that are no wider than the native intptr_t type.

> I like the introduction of lisp_object_type for this reason.  I think I
> was being a bit lax about the types here, as you note.  Most things,
> like the CONSTANT macro, I think should be using lisp_object_type,
> because that's the fundamental type of bytecode operations.  Only
> specialized spots like extracting a fixnum value or calling some C
> function should be using other types.

We could indeed use lisp_object_type more, but that won't save us from
using jit_value_create_long_constant, as long as we want to support
the --with-wide-int build.  And we cannot replace the calls to
jit_value_create_nint_constant with the long variant because that will
make the code less efficient in 32-bit builds without wide ints.

But I will take another look and see what can be done to have less
#ifdef's.

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Eli" == Eli Zaretskii <eliz@gnu.org> writes:

Eli> Maybe I'm missing something, but I didn't see how to do that with just
Eli> a type definition.  jit_value_create_long_constant is special in that
Eli> it allows to create 64-bit constants in a 32-bit build, by allocating
Eli> a 64-bit buffer and storing it address in the jit_value_t object it
Eli> returns.

Ah, I didn't pick up on that.  My illness makes me somewhat mentally
fuzzy.

Anyway maybe a helper function could be used so there's just a single #if.

Tom

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Tom Tromey <tom@tromey.com>
> Cc: Tom Tromey <tom@tromey.com>,  emacs-devel@gnu.org
> Date: Fri, 24 Aug 2018 15:03:21 -0600
> 
> >>>>> "Eli" == Eli Zaretskii <eliz@gnu.org> writes:
> 
> Eli> Maybe I'm missing something, but I didn't see how to do that with just
> Eli> a type definition.  jit_value_create_long_constant is special in that
> Eli> it allows to create 64-bit constants in a 32-bit build, by allocating
> Eli> a 64-bit buffer and storing it address in the jit_value_t object it
> Eli> returns.
> 
> Ah, I didn't pick up on that.  My illness makes me somewhat mentally
> fuzzy.

It's not just your illness, it's also the libjit docs, which never say
that.  I learned that by reading the libjit sources.

> Anyway maybe a helper function could be used so there's just a single #if.

Yes, I think so.  I will see what can be done about it.

Re: Emacs Lisp JIT Compiler

[Ergus]

Hi!

Sorry for the bother, but I am very interested in this kind of features!

I have 2 simple yes/not questions:

1) Any progress in the JIT work?

2) Do you think we will see it soon in the next release or year for example?

And an extra if you have some more time to reply.

3) I saw that the option to translate Lisp code into C and compile it is
not considered; but I couldn't understand why and how is it better to
use libJIT than a native compiler+binutils. Lisp-c or equivalents could
work to distribute all the emacs internal functions already compiled but
maybe the advanced users could enable it as an experimental feature for
his own functions (with some configuration). Also consider the
pedagogical value of this translator's code and the potential use cases.

Best,
Ergus

On Sat, Aug 25, 2018 at 09:51:02AM +0300, Eli Zaretskii wrote:
>> From: Tom Tromey <tom@tromey.com>
>> Cc: Tom Tromey <tom@tromey.com>,  emacs-devel@gnu.org
>> Date: Fri, 24 Aug 2018 15:03:21 -0600
>>
>> >>>>> "Eli" == Eli Zaretskii <eliz@gnu.org> writes:
>>
>> Eli> Maybe I'm missing something, but I didn't see how to do that with just
>> Eli> a type definition.  jit_value_create_long_constant is special in that
>> Eli> it allows to create 64-bit constants in a 32-bit build, by allocating
>> Eli> a 64-bit buffer and storing it address in the jit_value_t object it
>> Eli> returns.
>>
>> Ah, I didn't pick up on that.  My illness makes me somewhat mentally
>> fuzzy.
>
>It's not just your illness, it's also the libjit docs, which never say
>that.  I learned that by reading the libjit sources.
>
>> Anyway maybe a helper function could be used so there's just a single #if.
>
>Yes, I think so.  I will see what can be done about it.
>

Re: Emacs Lisp JIT Compiler

[Robert Pluim]

Ergus <spacibba@aol.com> writes:

> Hi!
>
> Sorry for the bother, but I am very interested in this kind of features!
>
> I have 2 simple yes/not questions:
>
> 1) Any progress in the JIT work?

Depends what you mean by progress. As far as I can tell the
feature/libjit branch compiles and runs OK.

> 2) Do you think we will see it soon in the next release or year for example?
>

Schedules are variable. Help appreciated :-)

> And an extra if you have some more time to reply.
>
> 3) I saw that the option to translate Lisp code into C and compile it is
> not considered; but I couldn't understand why and how is it better to
> use libJIT than a native compiler+binutils. Lisp-c or equivalents could
> work to distribute all the emacs internal functions already compiled but
> maybe the advanced users could enable it as an experimental feature for
> his own functions (with some configuration). Also consider the
> pedagogical value of this translator's code and the potential use cases.

Translating the lisp code into C requires the presence of a C
compiler/linker, so itʼs something that can be done by an emacs
developer, but someone using a pre-compiled emacs would not
necessarily have those tools installed. With libjit everybody would
get the benefit.

Of course, you could do both: compile the lisp shipped with emacs into
C, and support libjit, although the last time I looked at
el-compilador it didnʼt support elisp fully yet.

Robert

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Robert" == Robert Pluim <rpluim@gmail.com> writes:

>> 1) Any progress in the JIT work?

Robert> Depends what you mean by progress. As far as I can tell the
Robert> feature/libjit branch compiles and runs OK.

Eli has some work in libjit to make it work better on Windows.

I haven't done anything recently but I do have a work-in-progress patch
to improve the calling convention; and this would also provide
infrastructure to allow more direct calls to C and for inlining.  Not
sure when I will finish that.

Robert> Of course, you could do both: compile the lisp shipped with emacs into
Robert> C, and support libjit, although the last time I looked at
Robert> el-compilador it didnʼt support elisp fully yet.

Yes, el-compilador is pretty unfinished.  I think it should support
all of elisp in the front end and in the optimizers; but the C back end
is quite incomplete.

I wrote a second compiler, though, that just compiles from bytecode to
C.  This one is more complete, see my post about it from sometime in the
last month or so.  IIRC wiring it up to the build was the remaining
difficulty.

Tom

Re: Emacs Lisp JIT Compiler

[Robert Pluim]

Tom Tromey <tom@tromey.com> writes:

> Yes, el-compilador is pretty unfinished.  I think it should support
> all of elisp in the front end and in the optimizers; but the C back end
> is quite incomplete.
>

OK. Iʼm assuming completing the C back end is just a SMP? :-)

> I wrote a second compiler, though, that just compiles from bytecode to
> C.  This one is more complete, see my post about it from sometime in the
> last month or so.  IIRC wiring it up to the build was the remaining
> difficulty.

I saw that, but I donʼt remember if you said where youʼd put it. I
couldnʼt see a likely branch in the savannah emacs git repository.

Thanks

Robert

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>> Yes, el-compilador is pretty unfinished.  I think it should support
>> all of elisp in the front end and in the optimizers; but the C back end
>> is quite incomplete.
>> 

Robert> OK. Iʼm assuming completing the C back end is just a SMP? :-)

Yeah, for some value of S.  The github repo has some bugs if you're
interested.  Also you can pretty much pick a random, real elisp program,
compile it, and find failures, usually in the C back end.  I've got an
Emacs branch where I tried rewriting bits of C to elisp and then compile
them back to C; and IIRC I had to skip some functions for this reason.

Not to talk down el-compilador.  It has some nice things that are more
of a pain to do in something like the bytecode->C compiler.  For example
it can apply type inference along one side of a conditional.

>> I wrote a second compiler, though, that just compiles from bytecode to
>> C.  This one is more complete, see my post about it from sometime in the
>> last month or so.  IIRC wiring it up to the build was the remaining
>> difficulty.

Robert> I saw that, but I donʼt remember if you said where youʼd put it. I
Robert> couldnʼt see a likely branch in the savannah emacs git repository.

It's in my github in the feature/bytecode-c branch.

The C generation is ok but the rest isn't finished.  It is tricky to
associate the compiled C code with the Lisp defun.  Also see my other
post about it, it doubles (IIRC) the size of the executable.

You may recall that I was also looking at gcc-jit.  I have partially
done this translation but I got stalled by my illness.  I'm not sure if
I'll return to it, mostly because libjit is sounding perhaps more
attractive here on emacs-devel.

Tom

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

Paul> libjit has only one committer, Aleksey, and no commits since March. Is
Paul> there a bottleneck there?

Aleksey emailed me after this thread to say that a summer of code
student implemented a new register allocator for libjit.  This seems
pretty significant, as that was the biggest problem I noticed while
looking at assembly code from the JIT (btw on the JIT branch you can M-x
jit-disassemble to see the code for a function).  So, libjit may remain
a good choice.

Tom

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Tom Tromey <tom@tromey.com>
> Date: Wed, 15 Aug 2018 18:03:06 -0600
> Cc: Tom Tromey <tom@tromey.com>, emacs-devel@gnu.org
> 
> btw on the JIT branch you can M-x jit-disassemble to see the code
> for a function

Only on platforms that have open_memstream, it seems.  Which is a bad
limitation, IMO; we could easily write the output to a temp file and
then read it into a string instead.

Thanks.

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> Date: Thu, 16 Aug 2018 05:45:50 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: eggert@cs.ucla.edu, emacs-devel@gnu.org
> 
> > btw on the JIT branch you can M-x jit-disassemble to see the code
> > for a function
> 
> Only on platforms that have open_memstream, it seems.

Heh, and there's another quirk of this: it runs objdump to produce the
disassembly.  So users who don't have Binutils installed will be
unable to disassemble JIT code.

I guess we should be able to come up with a GDB command to do that,
though?

Re: Emacs Lisp JIT Compiler

[T.V Raman]

Tom Tromey <tom@tromey.com> writes:

Will it work with adviced functions?> Hi.  I've written a JIT compiler for Emacs Lisp, and I'd like to check
> it in.
>
> This JIT is based on GNU libjit, like some other attempts that have come
> before it.  However, this one is somewhat faster than those, primarily
> because it does all stack manipulations at compile time, not runtime.
>
> In some simple benchmarks, it is about 3x faster than the bytecode
> interpreter.
>
> I have only tested this on x86-64.  Whether or not the JIT works on a
> given platform is primarily up to libjit.  (I suspect the JIT won't work
> on x86 with --with-wide-int; but that is something I could fix.)
>
> I currently have the JIT set up to always compile all eligible functions
> (that is, just byte-compiled, lexically-bound functions).  It's robust
> enough that, as far as I can tell, everything works fine in this mode.
> It would be possible to have it be a bit lazier, say only compile after
> 100 invocations, or something like that.
>
> Aside from the possible --with-wide-int thing, there are two bugs I know
> of.
>
> First, libjit never frees functions.  So, if a function is JIT-compiled
> and then redefined, the old JIT code will linger.  It's possible to fix
> this with a custom allocator and a libjit patch (that I sent but that
> hasn't been checked in yet).
>
> Second, I haven't gotten around to emulating the "quitcounter" behavior
> in the bytecode interpreter.  This seems straightforward.
>
>
> This version of the compiler is pretty basic.  It just compiles each
> bytecode to more or less the obvious thing.  I have some plans to make
> the calling convention a bit less expensive, and to allow for inlining.
>
> Note that this change does not involve any semantic changes to Emacs Lisp.
> Also, if libjit is unavailable, the JIT is simply disabled.
>
> Tom
>

-- 

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "T" == T V Raman <raman@google.com> writes:

T> Will it work with adviced functions?

Yes.  The JIT works by adding another slot to the bytecode object.
This slot holds the JIT-related data, like the compiled function.
So, things like advice don't affect the way it operates.

Writing this out made me remember another possible issue with the JIT:
because it works based on the bytecode object, when a closure is made
with make-byte-code, the JIT will compile each such closure separately.
It would be possible to, instead, have it compile a closure once; but at
some cost to the generated code.

Tom

Re: Emacs Lisp JIT Compiler

[T.V Raman]

Tom Tromey <tom@tromey.com> writes:


Good to know - -asked because of the reference in your original note to
"redefined functions" (speaking from memory)>>>>>> "T" == T V Raman <raman@google.com> writes:
>
> T> Will it work with adviced functions?
>
> Yes.  The JIT works by adding another slot to the bytecode object.
> This slot holds the JIT-related data, like the compiled function.
> So, things like advice don't affect the way it operates.
>
> Writing this out made me remember another possible issue with the JIT:
> because it works based on the bytecode object, when a closure is made
> with make-byte-code, the JIT will compile each such closure separately.
> It would be possible to, instead, have it compile a closure once; but at
> some cost to the generated code.
>
> Tom
>

-- 
Id: kg:/m/0285kf1 

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Tom Tromey <tom@tromey.com>
> Date: Sun, 12 Aug 2018 22:01:34 -0600
> 
> Hi.  I've written a JIT compiler for Emacs Lisp, and I'd like to check
> it in.

Thanks.

> I have only tested this on x86-64.  Whether or not the JIT works on a
> given platform is primarily up to libjit.  (I suspect the JIT won't work
> on x86 with --with-wide-int; but that is something I could fix.)
> 
> I currently have the JIT set up to always compile all eligible functions
> (that is, just byte-compiled, lexically-bound functions).  It's robust
> enough that, as far as I can tell, everything works fine in this mode.
> It would be possible to have it be a bit lazier, say only compile after
> 100 invocations, or something like that.
> 
> Aside from the possible --with-wide-int thing, there are two bugs I know
> of.
> 
> First, libjit never frees functions.  So, if a function is JIT-compiled
> and then redefined, the old JIT code will linger.  It's possible to fix
> this with a custom allocator and a libjit patch (that I sent but that
> hasn't been checked in yet).
> 
> Second, I haven't gotten around to emulating the "quitcounter" behavior
> in the bytecode interpreter.  This seems straightforward.

I think, given the importance of byte compilation, this feature should
become more mature than it evidently is now, before we install it on
master.  The issues you mention are pretty basic, IMO.

So perhaps a feature branch where people could try JIT, and these
issues can be worked on would be the best course of action.  We could
then merge later when the issues are resolved.

Like Paul, I'm somewhat bothered by the relatively slow development of
libjit (its current version is just 0.1.2) and its small development
team.

Thanks.

Re: Emacs Lisp JIT Compiler

[John Wiegley]

>>>>> "EZ" == Eli Zaretskii <eliz@gnu.org> writes:

EZ> I think, given the importance of byte compilation, this feature should
EZ> become more mature than it evidently is now, before we install it on
EZ> master. The issues you mention are pretty basic, IMO.

EZ> So perhaps a feature branch where people could try JIT, and these issues
EZ> can be worked on would be the best course of action. We could then merge
EZ> later when the issues are resolved.

I fully concur with Eli on these points. And I want to say that this JIT
branch is interesting work, and I look forward to seeing it develop.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Emacs Lisp JIT Compiler

[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. ]]]

To replace an interpreter by a JIT compiler means more oomplexity and
also more possible problems.  (For example, if there are platforms
someday that libjit does not support.)  Reading a Lisp interpreter is
very useful for learning.

If the plan is to add a jit and keep the Lisp interpreter as well,
we don't lose its advantages for study, and we can still support all
the platforms -- but we add complexity even more.

I don't think a 3% speedup is worth those drawbacks.  Or even a 10%
speedup.  A really big speedup would justify the costs.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Richard" == Richard Stallman <rms@gnu.org> writes:

Richard> If the plan is to add a jit and keep the Lisp interpreter as well,
Richard> we don't lose its advantages for study, and we can still support all
Richard> the platforms -- but we add complexity even more.

Yes, my plan is to keep both.

Richard> I don't think a 3% speedup is worth those drawbacks.  Or even a 10%
Richard> speedup.  A really big speedup would justify the costs.

It is 3x, not 3%.

Tom

Re: Emacs Lisp JIT Compiler

[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. ]]]

  > Richard> I don't think a 3% speedup is worth those drawbacks.  Or even a 10%
  > Richard> speedup.  A really big speedup would justify the costs.

  > It is 3x, not 3%.

That is a big speedup.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Emacs Lisp JIT Compiler

[Clément Pit-Claudel]

On 2018-08-13 00:01, Tom Tromey wrote:
> Hi.  I've written a JIT compiler for Emacs Lisp, and I'd like to check
> it in.

Hi Tom,

This looks very promising! Thanks a lot :)

I compiled and installed libjit, and things seem to build fine here.  Benchmarking a simple loop yields an impressive 4x speedup (from 1 second down to 0.25s).  However, benchmarking a larger application seems to yield a 30% slowdown (from 5.5s to 7.5s).  I haven't investigated why yet.  Have you seen similar variations?

Cheers,
Clément.

Re: Emacs Lisp JIT Compiler

[Tom Tromey]

>>>>> "Clément" == Clément Pit-Claudel <cpitclaudel@gmail.com> writes:

Clément> I compiled and installed libjit, and things seem to build fine here.

Thank you for trying it.

Clément> Benchmarking a simple loop yields an impressive 4x speedup (from 1
Clément> second down to 0.25s).  However, benchmarking a larger application
Clément> seems to yield a 30% slowdown (from 5.5s to 7.5s).  I haven't
Clément> investigated why yet.  Have you seen similar variations?

I have not really done that much benchmarking.
However, please send me your test case (or tell me what it is) and I
will take a look.

I'd expect the JIT to be at its best for some kinds of integer code and
things like walking lists -- it knows how to emit some simple things
inline.

One reason it could be slower is if the compiler is compiling many
functions that don't often run.  Many JITs have some heuristic about
when to compile, this could be done here as well.

Tom

Re: Emacs Lisp JIT Compiler

[Clément Pit-Claudel]

On 2018-08-15 20:32, Tom Tromey wrote:
>>>>>> "Clément" == Clément Pit-Claudel <cpitclaudel@gmail.com> writes:
> 
> Clément> I compiled and installed libjit, and things seem to build fine here.
> 
> Thank you for trying it.
> 
> Clément> Benchmarking a simple loop yields an impressive 4x speedup (from 1
> Clément> second down to 0.25s).  However, benchmarking a larger application
> Clément> seems to yield a 30% slowdown (from 5.5s to 7.5s).  I haven't
> Clément> investigated why yet.  Have you seen similar variations?
> 
> I have not really done that much benchmarking.
> However, please send me your test case (or tell me what it is) and I
> will take a look.

Hi Tom,

My simple benchmark was this, and wow did that get fast:

;; -*- lexical-binding: t; -*-

(defun test ()
  (let ((sum 0))
    (dotimes (n (* 15 1000 1000))
      (setq sum (+ sum 1))
      (setq sum (- sum 1))
      (setq sum (+ sum 1))
      (setq sum (- sum 1))
      (setq sum (+ sum 1)))
    sum))

My application benchmark that got a bit slower is essentially fontifying and exporting to LaTeX about 200k lines of Python code.  The app is at https://github.com/cpitclaudel/esh.  If you clone it you can run this:

    # Generate test data
    cd /usr/lib/python3.5/; cat turtle.py inspect.py doctest.py pydoc.py tarfile.py pickletools.py argparse.py > /tmp/bench.py
    # Run the benchmark
    time EMACS=/build/emacs/master/src/emacs bin/esh2tex --standalone /tmp/bench.py

The EMACS= part is needed because ESH starts an Emacs server in the background.

Cheers and thanks for your work!
Clément.

Emacs Lisp JIT Compiler

[Burton Samograd]

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

Hello,

I’ve published my Emacs Lisp JIT compiler for comments and review:

    https://github.com/burtonsamograd/emacs-jit

The JIT compiler implements a strategy of turning the byte code execution loop into a series of function calls, moving the overhead of the loop into the CPU execution unit.  I call this ‘compiling down the spine’ of the byte code vector.  No other changes have been done to the byte code instructions other than to map them to the new execution strategy.

This is work in progress and about ~90% complete and was done about 4 years ago, so it’s quite a bit off of HEAD right now.  It ‘works’ to the point of being able to JIT compile and run my included ray-tracer with a 25% speed improvement.  Enabling full JIT during compilation shows bugs and will fail; I haven’t been able to track down the cause of these failures yet.

By default, this build will provide the Lisp function 'jit-compile’ which takes a lambda expression or a symbol.

A new byte code instruction has been added Bjitcall.  When a function is JIT compiled, it’s code vector is replaced by the single Bjitcall instruction followed by the JIT compiled code block.

I have already attempted to contact assign@fsf.org<mailto:assign@fsf.org> to file my papers and was asked on Reddit to contribute this to a branch, which I am willing to do once the paperwork is done.

—
Burton Samograd

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

Re: Emacs Lisp JIT Compiler

[Eli Zaretskii]

> From: Burton Samograd <burton.samograd@autodesk.com>
> Date: Mon, 5 Dec 2016 18:16:19 +0000
> 
> I have already attempted to contact assign@fsf.org to file my papers and was asked on Reddit to contribute
> this to a branch, which I am willing to do once the paperwork is done.

Thank you for working on this.

I can send you the forms to fill for the assignment, so if
assign@fsf.org doesn't respond quickly enough, I can be the fallback.

Re: Emacs Lisp JIT Compiler

[Daniel Colascione]

Thanks for doing this work.

On 12/05/2016 10:16 AM, Burton Samograd wrote:
> Hello,
>
> I’ve published my Emacs Lisp JIT compiler for comments and review:
>
>     https://github.com/burtonsamograd/emacs-jit
>
> The JIT compiler implements a strategy of turning the byte code
> execution loop into a series of function calls, moving the overhead of
> the loop into the CPU execution unit.  I call this ‘compiling down the
> spine’ of the byte code vector.  No other changes have been done to the
> byte code instructions other than to map them to the new execution strategy.
>
> This is work in progress and about ~90% complete and was done about 4
> years ago, so it’s quite a bit off of HEAD right now.  It ‘works’ to the
> point of being able to JIT compile and run my included ray-tracer with a
> 25% speed improvement.  Enabling full JIT during compilation shows bugs
> and will fail; I haven’t been able to track down the cause of these
> failures yet.

Let's benchmark it after making sure it's correct.

> By default, this build will provide the Lisp function 'jit-compile’
> which takes a lambda expression or a symbol.
>
> A new byte code instruction has been added Bjitcall.  When a function is
> JIT compiled, it’s code vector is replaced by the single Bjitcall
> instruction followed by the JIT compiled code block.

I'm hesitant to call this work a "JIT compiler", since it's not doing 
any "compilation" --- CFG construction, register allocation, 
machine-code generation. we're still executing the same bits of the 
interpreter code ---- just reaching them more efficiency. (It's a step 
in that direction though.) Since each function pointer (four or eight 
bytes) is much larger than the corresponding bytecode instruction, for 
cache efficiency reasons, I'd apply this optimization only to hot functions.

Four years ago, GCC's JIT API was unavailable. I suggest taking a close 
look at it. It will deliver far greater speedups to computation than the 
techniques in this work can, and it's much lower-maintenance to boot.

BTW: we don't use C99 dynamic arrays in Emacs.

Re: Emacs Lisp JIT Compiler

[Burton Samograd]

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


On Dec 5, 2016, at 12:32 PM, Daniel Colascione <dancol@dancol.org<mailto:dancol@dancol.org>> wrote:

Thanks for doing this work.

On 12/05/2016 10:16 AM, Burton Samograd wrote:
Hello,

I’ve published my Emacs Lisp JIT compiler for comments and review:

   https://github.com/burtonsamograd/emacs-jit

The JIT compiler implements a strategy of turning the byte code
execution loop into a series of function calls, moving the overhead of
the loop into the CPU execution unit.  I call this ‘compiling down the
spine’ of the byte code vector.  No other changes have been done to the
byte code instructions other than to map them to the new execution strategy.

This is work in progress and about ~90% complete and was done about 4
years ago, so it’s quite a bit off of HEAD right now.  It ‘works’ to the
point of being able to JIT compile and run my included ray-tracer with a
25% speed improvement.  Enabling full JIT during compilation shows bugs
and will fail; I haven’t been able to track down the cause of these
failures yet.

Let's benchmark it after making sure it's correct.

Understandable.


By default, this build will provide the Lisp function 'jit-compile’
which takes a lambda expression or a symbol.

A new byte code instruction has been added Bjitcall.  When a function is
JIT compiled, it’s code vector is replaced by the single Bjitcall
instruction followed by the JIT compiled code block.

I'm hesitant to call this work a "JIT compiler", since it's not doing any "compilation" --- CFG construction, register allocation, machine-code generation.

Technically, there is compilation into a linear series of function calls to the byte code interpreter code. That part is handled by libjit.  No, I didn’t write the entire JIT compiler that it uses, but it does compile the interpreter loop into a more efficient dispatch structure, giving the speed improvemet.  It’s a simple technique and easy to see where the improvement comes from, but yes, this implementation does cause maintenance problems by duplicating the code from the original interpreter loop.


we're still executing the same bits of the interpreter code ---- just reaching them more efficiency. (It's a step in that direction though.) Since each function pointer (four or eight bytes) is much larger than the corresponding bytecode instruction, for cache efficiency reasons, I'd apply this optimization only to hot functions.

That’s the intention with the stub jit_hotspot_compile, but of course, getting this correct is obviously more important first.

Four years ago, GCC's JIT API was unavailable. I suggest taking a close look at it. It will deliver far greater speedups to computation than the techniques in this work can, and it's much lower-maintenance to boot.

I didn’t realize GCC had a JIT API now.  Is that also linked in


BTW: we don't use C99 dynamic arrays in Emacs.

Noted, thanks.

By showing this ida/work I’m hoping not to get it included in emacs proper, but to show a relatively simple way to speed things up.  I’m sure there are better/alternate implementations that would both be cleaner and give better speedups, but this was as far as this POC went so far.


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

Re: Emacs Lisp JIT Compiler

[Lluís]

Burton Samograd writes:
[...]
> I didn’t realize GCC had a JIT API now. Is that also linked in 

Relevant links:

  https://gcc.gnu.org/wiki/JIT
  https://www.gnu.org/software/lightning/ (an alternative library)

Guile (which might fully support ELisp one day) also has an experimental
(tracing) JIT branch:

  https://github.com/8c6794b6/guile-tjit-documentation/blob/master/nash.pdf
  https://github.com/8c6794b6/guile-tjit


Cheers,
  Lluis