Re: Optimising Elisp code [again]

Re: Optimising Elisp code [again]

[Garreau, Alexandre]

On 2018-10-07 at 17:59, Emanuel Berg wrote:
> Stefan Monnier wrote:
> So there is no gain as to the number of machine instructions. So where
> is the gain? The `call' instruction specifically, or the implied
> funcall overhead not visible in the disassembly?

A smarter compiler could have optimized the discarded value (since we
don’t use its return value, and the inlined function don’t have any
side-effects (which otherwise would have been preserved)), or could have
simplified the result (I checked and with + 2 then - 2 it seems elisp
compiler don’t do this, while I’m sure gcc can) if something was going
to be done with it.

However, inlining is not an optimization made to gain space or reduce
the number of instruction (even worse: normally it could *increase* the
total amount of instruction and therefore use more memory), it’s here to
gain *speed*.  Not by executing less instructions, but by removing a
jump (the funcall), as in today’s computers, jumps (like function calls,
or conditionals) can increase execution time.  So at the end,
duplicating instructions can lead to faster execution, albeit increased
memory usage.

I kind of forgot why jumps are slow, but afair, either because the cache
being little it’s faster to execute nearby code, either because as
modern cpus try to do as much as possible in the same time (pipeline
instructions optimization, found in today’s superscalar cpu, iirc), they
need to know what will be executed next, and they stop searching what’s
next after a jump…  but that (+ loop unrolling) might be mitigated by
the fact that if you use too much memory at same time, it might not fit
in the smaller and faster cache, and then get slower…  so I guess here
it gets complex and architecture dependant, and becomes the job of
complex and native compilers to guess what is best to do.

Re: Optimising Elisp code [again]

[Emanuel Berg]

Garreau, Alexandre wrote:

> I kind of forgot why jumps are slow

Isn't it as simple as all the overhead of
placing the new function on the stack with
return pointers and stuff?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: Optimising Elisp code [again]

[tomas]

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

On Mon, Oct 08, 2018 at 04:11:14PM +0200, Emanuel Berg wrote:
> Garreau, Alexandre wrote:
> 
> > I kind of forgot why jumps are slow
> 
> Isn't it as simple as all the overhead of
> placing the new function on the stack with
> return pointers and stuff?

And cold caches, and pipeline stalls and...

Modern processors are quite complex beasts, and much of it has to
do with the sad fact that RAM is much, much, MUCH slower than the
CPU, and they try to lie to you about it...

Cheers
-- tomás

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Optimising Elisp code [again]

[Barry Margolin]

In article <mailman.1852.1539009893.1284.help-gnu-emacs@gnu.org>,
 <tomas@tuxteam.de> wrote:

> On Mon, Oct 08, 2018 at 04:11:14PM +0200, Emanuel Berg wrote:
> > Garreau, Alexandre wrote:
> > 
> > > I kind of forgot why jumps are slow
> > 
> > Isn't it as simple as all the overhead of
> > placing the new function on the stack with
> > return pointers and stuff?
> 
> And cold caches, and pipeline stalls and...
> 
> Modern processors are quite complex beasts, and much of it has to
> do with the sad fact that RAM is much, much, MUCH slower than the
> CPU, and they try to lie to you about it...

Since we're talking about a byte-code interpreter, not machine code, the 
pipeline is probably not relevant.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: Optimising Elisp code [again]

[Emanuel Berg]

Barry Margolin wrote:

> Since we're talking about a byte-code
> interpreter, not machine code, the pipeline
> is probably not relevant.

Cannot one have a three-layer architecture, C,
compiled Lisp, interpretated Lisp?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: Optimising Elisp code [again]

[Garreau, Alexandre]

On 2018-10-09 at 08:26, Emanuel Berg wrote:
> Barry Margolin wrote:
>
>> Since we're talking about a byte-code interpreter, not machine code,
>> the pipeline is probably not relevant.
>
> Cannot one have a three-layer architecture, C, compiled Lisp,
> interpretated Lisp?

It’s already like this… or what are you talking about otherwise?  We got
C, which interprets directly both byte-compiled and interpreted lisp,
which is all the high-level stuff.

Re: Optimising Elisp code [again]

[Emanuel Berg]

Garreau, Alexandre wrote:

>> Cannot one have a three-layer architecture,
>> C, compiled Lisp, interpretated Lisp?
>
> It’s already like this… or what are you
> talking about otherwise? We got C, which
> interprets directly both byte-compiled and
> interpreted lisp, which is all the
> high-level stuff.

Isn't there an FOSS CL compiler around one can
duplicate/modify?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: Optimising Elisp code [again]

[Garreau, Alexandre]

On 2018-10-09 at 15:28, Emanuel Berg wrote:
> Garreau, Alexandre wrote:
>>> Cannot one have a three-layer architecture,
>>> C, compiled Lisp, interpretated Lisp?
>>
>> It’s already like this… or what are you
>> talking about otherwise? We got C, which
>> interprets directly both byte-compiled and
>> interpreted lisp, which is all the
>> high-level stuff.
>
> Isn't there an FOSS CL compiler around one can
> duplicate/modify?

gcl. It’s GNU, it uses gcc (for now it generates C and compile that with
gcc, but it was planned to make it a gcc frontend a long time ago, but
iso support comes first afair).  The only other compiler I know is the
most used/popular (afaik), sbcl, but it’s not GNU (so it would be less
meaningful since there are a bunch of GNU lisp implementations)… and
clisp has a *VM* too (and its byte-compiler), but I guess it’s better
than emacs’ one.

However if you’re talking about using a cl compiler to host emacs,
*iirc*, rms said cl was too big for emacs which he wanted not too big
(and indeed, unless some modifications are maid, afaiu, it might imply
to make gcc a mandatory dependency of emacs, which is pretty big)…

Interestingly, on my (debian stable) system, gcl [0] appears to be 7,8M
(but there is a 15M gcl static library [3]), emacs [1] 11M, and libguile
[2] 1,6M… so is gcl smaller than emacs (also maybe it is the static that
contain all gcl, and maybe gcl should be bigger when everything is
complete and standard?)? I can’t measure clisp as I didn’t attempted
(yet) to recompile here, and it’s not packaged for the current debian
stable.

Btw, what would it change to make emacs hosted by gcl, compared to by
guile (modulo the obvious facilities of having elisp and cl more near
than elisp and scheme)? would the gcc runtime dep hard to remove? would
that be so big? would that be easier to get buffer-local variables,
dynamic scoping, et al?

[0] resolves to /usr/lib/gcl-2.6.12/unixport/saved_gcl 
[1] /usr/bin/emacs25-x
[2] /usr/lib/i386-linux-gnu/libguile-2.0.so.22.8.1
[3] /usr/lib/gcl-2.6.12/unixport/libgcl.a

Re: Optimising Elisp code [again]

[Emanuel Berg]

Garreau, Alexandre wrote:

> Btw, what would it change to make emacs
> hosted by gcl

I mean, compile the Lisp that isn't user
defined and unlikely to change - compile for
real, not byte-compile for
sped-up interpretation.

I.e.: fun-and-play Elisp on the top
      compiled Elisp in the middle
      C downmost

?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: Optimising Elisp code [again]

[Garreau, Alexandre]

On 2018-10-09 at 17:26, Emanuel Berg wrote:
> Garreau, Alexandre wrote:
>
>> Btw, what would it change to make emacs
>> hosted by gcl
>
> I mean, compile the Lisp that isn't user
> defined and unlikely to change - compile for
> real, not byte-compile for
> sped-up interpretation.
>
> I.e.: fun-and-play Elisp on the top
>       compiled Elisp in the middle
>       C downmost
>
> ?

We’d get the same problems as mentioned before about loss of dynamism
(you’ll need to recompile everything if changing a core thing, which you
currently don’t need).  Yet the opposite would also be there: some core
functions might be reimplemented in lisp, and then these could be easier
to hack for beginners, or any people uncomfortable with C.

But beside that you would get awesome performances I guess.  Not
*always* like C, because, I guess there are still mallocs and garbage
collection all the way around, types may not be determined as you’d
like, etc.  but especially as elisp is quite imperative (but potentially
less well used, sometimes), you may get quite near performances (I did
hear about 1,2/1,5 more slow than C for compiled elisp).

I’d like to see how the performances of libjit (native jit compiler I
guess) emacs, as previously mentioned, I’ll try it I think.

Re: Optimising Elisp code [again]

[Barry Margolin]

In article <86ftxfm98q.fsf@zoho.com>, Emanuel Berg <moasen@zoho.com> 
wrote:

> Garreau, Alexandre wrote:
> 
> > Btw, what would it change to make emacs
> > hosted by gcl
> 
> I mean, compile the Lisp that isn't user
> defined and unlikely to change - compile for
> real, not byte-compile for
> sped-up interpretation.
> 
> I.e.: fun-and-play Elisp on the top
>       compiled Elisp in the middle
>       C downmost
> 
> ?

The Elisp interpreter is probably tightly intertwined with the Emacs 
editor code. Disentangling them so you can compile Elisp to machine code 
would be a big project, and probably not worth it.

Byte-code interpretation is common in many modern languages, it makes it 
easier for the languages to be portable. Python and PHP both compile to 
byte code rather than machine code. It's generally fast enough for 
interactive applications. For computationally-intensive applications, 
there are often libraries that can be linked in, like Numpy for Python.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: Optimising Elisp code [again]

[Óscar Fuentes]

Barry Margolin <barmar@alum.mit.edu> writes:

> The Elisp interpreter is probably tightly intertwined with the Emacs 
> editor code. Disentangling them so you can compile Elisp to machine code 
> would be a big project, and probably not worth it.

http://git.savannah.gnu.org/cgit/emacs.git/log/?h=feature/libjit

https://github.com/tromey/el-compilador

Re: Optimising Elisp code [again]

[Garreau, Alexandre]

On 2018-10-10 at 12:18, Barry Margolin wrote:
> In article <86ftxfm98q.fsf@zoho.com>, Emanuel Berg <moasen@zoho.com> 
> wrote:
>> I mean, compile the Lisp that isn't user
>> defined and unlikely to change - compile for
>> real, not byte-compile for
>> sped-up interpretation.
>> 
>> I.e.: fun-and-play Elisp on the top
>>       compiled Elisp in the middle
>>       C downmost
>> 
>> ?
>
> The Elisp interpreter is probably tightly intertwined with the Emacs 
> editor code. Disentangling them so you can compile Elisp to machine code 
> would be a big project, and probably not worth it.

Why would that need distangling?  Couldn’t editor code be compiled as
well?  I understand things need to stay dynamic and redefinable, but a
large portion would remain unchanged anyway for most of time and the
things that would most likely be changed would be less stable and
less low-level things that wouldn’t break other stuff wouldn’t it?

Re: Optimising Elisp code [again]

[Emanuel Berg]

Óscar Fuentes wrote:

>> The Elisp interpreter is probably tightly
>> intertwined with the Emacs editor code.
>> Disentangling them so you can compile Elisp
>> to machine code would be a big project, and
>> probably not worth it.
>
> http://git.savannah.gnu.org/cgit/emacs.git/log/?h=feature/libjit
>
> https://github.com/tromey/el-compilador

Wonderful! But how does one integrate the
compiled code with the rest of Emacs?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: Optimising Elisp code [again]

[Robert Thorpe]

Emanuel Berg <moasen@zoho.com> writes:

> Óscar Fuentes wrote:
>
>>> The Elisp interpreter is probably tightly
>>> intertwined with the Emacs editor code.
>>> Disentangling them so you can compile Elisp
>>> to machine code would be a big project, and
>>> probably not worth it.
>>
>> http://git.savannah.gnu.org/cgit/emacs.git/log/?h=feature/libjit
>>
>> https://github.com/tromey/el-compilador
>
> Wonderful! But how does one integrate the
> compiled code with the rest of Emacs?

Firstly, I think it's worth clarifying how things work now.  Emacs has
two interpreters.  There's the interactive interpreter, that's what's run
when you type elisp straight into Emacs.  It is used to interpret files
ending in ".el".  Then there's the bytecode interpreter.  To use that
you have to compile a program to bytecode first.  It's the bytecode
interpreter that deals with ".elc" files.  The bytecode interpreter is
much faster than the interactive interpreter.  (I expect you know all
this Emanuel, I'm just writing it here for others who are reading who
might not).

The libjit branch works by compiling bytecode into native code.  As I
understand it, this is done at runtime, so the user doesn't have to do
anything.  I think there was another project that did something similar
at compile time.  Compiling bytecode sounds a bit strange, but it makes
sense.  In many cases what the JIT does is emit the same code that
is inside the bytecode interpreter.  In a very simplified sense, it
works like this....  So, the bytecode interpreter is a big switch/case
statement.  Somewhere there is instruction FOO.  When the JIT compiler
sees FOO it inserts into it's output buffer the code that was in the
bytecoding interpreter to deal with that opcode.  There are some
optimizations beyond that.

I think it's a good idea and I hope it will be merged into mainline
Emacs one day.

BR,
Robert Thorpe

Re: Optimising Elisp code [again]

[Emanuel Berg]

Robert Thorpe wrote:

> The libjit branch works by compiling bytecode
> into native code. As I understand it, this is
> done at runtime, so the user doesn't have to
> do anything. I think there was another
> project that did something similar at compile
> time. Compiling bytecode sounds a bit
> strange, but it makes sense. In many cases
> what the JIT does is emit the same code that
> is inside the bytecode interpreter. In a very
> simplified sense, it works like this.... So,
> the bytecode interpreter is a big switch/case
> statement. Somewhere there is instruction
> FOO. When the JIT compiler sees FOO it
> inserts into it's output buffer the code that
> was in the bytecoding interpreter to deal
> with that opcode. There are some
> optimizations beyond that.

So it is a JIT native compiler of bytecode.

> I think it's a good idea and I hope it will
> be merged into mainline Emacs one day.

Thanks for a great post and also cred to the
people who have been, are, and/or in the future
will work on the libjit project!

-- 
underground experts united
http://user.it.uu.se/~embe8573