Re: Optimising Elisp code [again]

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

Optimising Elisp code

[Davin Pearson]

Suppose that you have a function:

(defun foo ()
   (bar))

And bar is a function that has no side effects and returns 123 then calling
the function code-optimize (the name of my optimisation routine)

M-x code-optimize on the function foo will result in the following defun 

(defun foo ()
    123)

Re: Optimising Elisp code

[Barry Margolin]

In article <638fb7dc-6fc5-4645-8793-97a00038a3a8@googlegroups.com>,
 Davin Pearson <davin.pearson@gmail.com> wrote:

> Suppose that you have a function:
> 
> (defun foo ()
>    (bar))
> 
> And bar is a function that has no side effects and returns 123 then calling
> the function code-optimize (the name of my optimisation routine)
> 
> M-x code-optimize on the function foo will result in the following defun 
> 
> (defun foo ()
>     123)

What you're describing is called inline expansion. AFAIK, the Elisp 
compiler doesn't do this automatically.

You can define bar as a macro -- those HAVE to be expanded at compile 
time, since that's how they work.

You can also define an inline function using defsubst. From the Elisp 
manual:

An inline function works just like an ordinary function except for one 
thing: when you compile a call to the function, the function's 
definition is open-coded into the caller.

Making a function inline makes explicit calls run faster. But it also 
has disadvantages. For one thing, it reduces flexibility; if you change 
the definition of the function, calls already inlined still use the old 
definition until you recompile them.

There are more caveats given in the documentation.

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

Re: Optimising Elisp code

[Stefan Monnier]

> What you're describing is called inline expansion.
> AFAIK, the Elisp compiler doesn't do this automatically.

Indeed, it doesn't do it automatically because it doesn't know how to
(automatically) undo it, and it has visible effects w.r.t advice,
debug-on-entry, etc...

> You can define bar as a macro -- those HAVE to be expanded at compile 
> time, since that's how they work.
>
> You can also define an inline function using defsubst. From the Elisp 
> manual:

And also with cl-defsubst, with (declare (compiler-macro ...))
and more recently with define-inline.


        Stefan

Re: Optimising Elisp code

[Garreau, Alexandre]

On 2018-10-06 at 10:40, Stefan Monnier wrote:
>> What you're describing is called inline expansion.
>> AFAIK, the Elisp compiler doesn't do this automatically.
>
> Indeed, it doesn't do it automatically because it doesn't know how to
> (automatically) undo it, and it has visible effects w.r.t advice,
> debug-on-entry, etc...

Why “undo”? do you mean take the byte-compiled form and programmatically
do on it something like find and extract the part that comes from
byte-compiling the inlined function?

Or would “reevaluate every function that where defined with the
(now-redefined) inlined function inside” work too?

Re: Optimising Elisp code

[tomas]

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

On Sat, Oct 06, 2018 at 06:55:54PM +0200, Garreau, Alexandre wrote:
> On 2018-10-06 at 10:40, Stefan Monnier wrote:
> >> What you're describing is called inline expansion.
> >> AFAIK, the Elisp compiler doesn't do this automatically.
> >
> > Indeed, it doesn't do it automatically because it doesn't know how to
> > (automatically) undo it, and it has visible effects w.r.t advice,
> > debug-on-entry, etc...
> 
> Why “undo”? [...]

because...

 - when debugging, you want to know that function "foo" is being
   called
 - you want, perhaps, to advice/instrument the function after its
   entrails have been spread across some other byte code
 - because you expect it to be possible to redefine the function
   at run time (the run time system would have to know how to
   excise the inlined and perhaps optimised bits and pieces and
   replace them by something else)

> Or would “reevaluate every function that where defined with the
> (now-redefined) inlined function inside” work too?

Hmm. Not reevaluate, but recompile, and not "inside", but rather
"outside" -- like finding all places where this function was
inlined and do some magic there. Perhaps doable, but not trivial.

Cheers
-- t

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

Knowing where a function has been used (bis) [Was: Re: Optimising Elisp code]

[Garreau, Alexandre]

Le 06/10/2018 à 21h24, tomas@tuxteam.de a écrit :
> On Sat, Oct 06, 2018 at 06:55:54PM +0200, Garreau, Alexandre wrote:
>> Or would “reevaluate every function that where defined with the
>> (now-redefined) inlined function inside” work too?
>
> Hmm. Not reevaluate, but recompile, and not "inside", but rather
> "outside" -- like finding all places where this function was
> inlined 

I don’t get how “outside” is the correct form here, as this is precisely
what I was meaning: I mentioned it in my other message titled “Knowing
where a function has been used (e.g. for optimizing)” (message-id: [0],
url: [1]), as I found a such functionality, symetrical to
find-definition, would be quite generally useful for lot of stuff.

> and do some magic there.

What other kind of magic than (maybe recursively)
reevaluating/recompiling could be needed there?

> Perhaps doable, but not trivial.

I have really no precise idea of where and how is stored the place where
each function was defined wrt the related function’s symbol (I tried to
search somewhere ago and found it must be linked with load-history, but,
because of the absence of a such feature ^^, I don’t know where and how
it is updated, without further searching (by grepping?)), but would it
be so hard storing a symbol at the right place (near the place where it
is said where that symbol is defined (and/or other informations about
this symbol)) for each function (why not also variable or even macro?
symbol generically) refered in the function body?

>> Why “undo”? [...]
>
> because...
>
>  - when debugging, you want to know that function "foo" is being
>    called
>  - you want, perhaps, to advice/instrument the function after its
>    entrails have been spread across some other byte code
>  - because you expect it to be possible to redefine the function
>    at run time (the run time system would have to know how to
>    excise the inlined and perhaps optimised bits and pieces and
>    replace them by something else)

So, except maybe wrt debugging (which there should imply reevaluation,
like with edebug-defun), reevaluating (or rather recompiling indeed,
since afaiu then, simple evaluation will never optimize anything, unlike
byte-compiling (right?)).

[0] <9oqtevzzzzzz.yga.xxuns.g6.gal_-_@portable.galex-713.eu>
[1] https://lists.gnu.org/archive/html/help-gnu-emacs/2018-10/msg00068.html

Re: Knowing where a function has been used (bis) [Was: Re: Optimising Elisp code]

[Emanuel Berg]

tomas wrote:

> Not only debugging, but any kind of
> redefinition. Emacs lisp is a dynamic
> language, and the users expect that when you
> redefine a function, the new definition is
> active; unless the magic is under user
> control (you've said "defmacro" or
> "def-inline", then you know you've to
> recompile the callers), the run system has to
> manage the mess, i.e. it has to remember all
> the sites where things have to be inlined,
> like in the "inline cache" from the
> reference above.

No one in this thread, unless I missed
something, has made an attempt at defining,
explaining, and showing with examples how
inlining is done and what it means in Elisp:

(defun add-two-digits (a b)
  (+ a b) )
  
(defsubst add-two-digits-inline (i j)
  (+ i j) )

(defun add-it ()
  (add-two-digits 5 10)
  (add-two-digits-inline 15 5) )

This byte-compiles with no warnings/errors.

So what happens then, and what happens when
"add-it" is called?

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

Re: Knowing where a function has been used (bis) [Was: Re: Optimising Elisp code]

[Emanuel Berg]

Stefan Monnier wrote:

> Try M-x disassemble RET add-it RET
> to see how the two calls where compiled.

OK, here goes:

(defsubst add-it-inline (i j)
  (+ i j) )

(defun add-it (a b)
  (+ a b) )

(defun test-normal ()
  (add-it 1 2) )
;; (test-normal)

;; byte code for test-normal:
;;   args: nil
;; 0       constant  add-it
;; 1       constant  1
;; 2       constant  2
;; 3       call      2
;; 4       return

(defun test-inline ()
  (add-it-inline 10 20) )
;; (test-inline)

;; byte code for test-inline:
;;   args: nil
;; 0       constant  10
;; 1       constant  20
;; 2       varbind   j
;; 3       dup
;; 4       varbind   i
;; 5       varref    j
;; 6       plus
;; 7       unbind    2
;; 8       return

OK, so there is no call, instead the code
is inserted. I suppose this is a glitch in the
Matrix, becuase what I can reCALL this is what
I've been saying this whole time...

But anyway, instead of dwelling on the past,
meditate on this:

;; byte code for add-it:
;;  args: (a b)
;; 0       varref    a
;; 1       varref    b
;; 2       plus      
;; 3       return

So as for machine instructions, the inline
version, "test-inline", has 9.
The "test-normal" has 5. The non-inlined
"add-it" has 4. 5 + 4 = 9. And I've saved the
best forst last: 9 = 9!

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?

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

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