Optimising Elisp code

classic Classic list List threaded Threaded
91 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

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)

Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Davin Pearson
On Friday, October 5, 2018 at 3:15:32 PM UTC+13, Davin Pearson 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)

Please could you admise me about whether or not such as function is part of Gnu Emacs or otherwise available as a third party tool.

If not then my code will be reinventing the wheel :-(
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
Davin Pearson wrote:

> Please could you admise me about whether or
> not such as function is part of Gnu Emacs or
> otherwise available as a third party tool.

Hm, perhaps it will be more educational as for
the purpose and advantages of your tool if you
posted a more live or in-world example of how
you have made use of it?

> If not then my code will be reinventing the
> wheel :-(

Reinventing the wheel is not easy. If you have
done that, cred to you, and it will be
interesting to have a look at it!

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Tomas Zerolo
In reply to this post by Davin Pearson
On Thu, Oct 04, 2018 at 07:15:30PM -0700, Davin Pearson 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)
Have you already looked at the code produced by the elisp compiler? As
in doing "compile-function" and "disassemble-function"?

Have you had a look at eval-and-compile and friends?

Perhaps elisp is already doing (parts of) what you have in mind?

Cheers
-- tomás

signature.asc (205 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Noam Postavsky
In reply to this post by Davin Pearson
On Thu, 4 Oct 2018 at 22:20, Davin Pearson <[hidden email]> wrote:

>
> On Friday, October 5, 2018 at 3:15:32 PM UTC+13, Davin Pearson 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)
>
> Please could you admise me about whether or not such as function is part of Gnu Emacs or otherwise available as a third party tool.

Not exactly, but if you use defsubst to define bar (defsubst bar ()
123), then the result of byte-compiling foo will be equivalent to your
optimized version.

Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Barry Margolin
In reply to this post by Davin Pearson
In article <[hidden email]>,
 Davin Pearson <[hidden email]> 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, [hidden email]
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
Barry Margolin wrote:

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

This rings a bell from the C++ days when/where
you could define a member function as "inline".
That's all I remember, but maybe it was
something similar to this? I think it amounted
to, instead of making a call, that function was
coded into the object itself, and for this
reason it was suited for really short,
simple functions.

Yes, what does it mean that "the function's
definition is open-coded into the caller"?

If the caller is a function, does this mean
instead of calling the other function, the
other function's code is put into the first
function so there isn't a second call but
everything is executed in the first function?

> Making a function inline makes explicit calls
> run faster.

Well, yeah, obviously since there is no second
invocation with just the original function put
onto the stack!

What are "explicit calls"? Regular calls,
right? But then what are implicit calls?
Anonymous functions? Or is an inline function
being executed an implicit call to
that function?

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

Another good point, but that's obvious as well.

(Hey, for a person who doesn't understand this,
I sure sound confident enough :))

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
> This rings a bell from the C++ days
> when/where you could define a member function
> as "inline". That's all I remember, but maybe
> it was something similar to this? I think it
> amounted to, instead of making a call, that
> function was coded into the object itself,
> and for this reason it was suited for really
> short, simple functions. [...]
>
> If the caller is a function, does this mean
> instead of calling the other function, the
> other function's code is put into the first
> function so there isn't a second call but
> everything is executed in the first function?

OK, in C++ it works like this:

If a member function is defined within the
class definition (not recommended), or if it is
defined outside of it (recommended) with the
word "inline" preceding the return type, then
the function becomes an inline function.

What this means is that when the code is
compiled into machine code, instead of having
one place for the function, and jumping back
and forth every time that function is called,
the machine code for the inline function is
placed, duplicated wherever it is used.

So you get longer machine code, but faster,
since there is just constant execution for the
inline functions, without jumping back
and forth.

When should it be used? If the function is very
short, say 1-3 lines, the jumping back and
forth requires more machine instructions than
the function itself. Then the organizational
gain of having it neatly at one place is
diminished by the speed advantage of not having
to jump back and forth to that place all
the time.

"Make the common case fast, and the complicated
case work" -- M. Yoda

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Óscar Fuentes
Emanuel Berg <[hidden email]> writes:

> OK, in C++ it works like this:
>
> If a member function is defined within the
> class definition (not recommended), or if it is
> defined outside of it (recommended) with the
> word "inline" preceding the return type, then
> the function becomes an inline function.
>
> What this means is that when the code is
> compiled into machine code, instead of having
> one place for the function, and jumping back
> and forth every time that function is called,
> the machine code for the inline function is
> placed, duplicated wherever it is used.
>
> So you get longer machine code, but faster,
> since there is just constant execution for the
> inline functions, without jumping back
> and forth.
>
> When should it be used? If the function is very
> short, say 1-3 lines, the jumping back and
> forth requires more machine instructions than
> the function itself. Then the organizational
> gain of having it neatly at one place is
> diminished by the speed advantage of not having
> to jump back and forth to that place all
> the time.

Just in case any bystander finds this post: don't rely on anything that is
mentioned above, nor for C++ `inline' keyword nor for code inlining in
general.


Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
In reply to this post by Emanuel Berg-4
Óscar Fuentes wrote:

> Emanuel Berg <[hidden email]> writes:
>
>> OK, in C++ it works like this: If a member
>> function is defined within the class
>> definition (not recommended), or if it is
>> defined outside of it (recommended) with the
>> word "inline" preceding the return type,
>> then the function becomes an inline
>> function. What this means is that when the
>> code is compiled into machine code, instead
>> of having one place for the function, and
>> jumping back and forth every time that
>> function is called, the machine code for the
>> inline function is placed, duplicated
>> wherever it is used. So you get longer
>> machine code, but faster, since there is
>> just constant execution for the inline
>> functions, without jumping back and forth.
>> When should it be used? If the function is
>> very short, say 1-3 lines, the jumping back
>> and forth requires more machine instructions
>> than the function itself. Then the
>> organizational gain of having it neatly at
>> one place is diminished by the speed
>> advantage of not having to jump back and
>> forth to that place all the time.
>
> Just in case any bystander finds this post:
> don't rely on anything that is mentioned
> above, nor for C++ `inline' keyword nor for
> code inlining in general.

I read it in this book:

    @book{cpp-direkt,
      author     = {Jan Skansholm},
      ISBN       = {91-44-47931-X},
      publisher  = {Studentlitteratur},
      title      = {C++ direkt},
      year       = {1996}
    }

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Óscar Fuentes
Emanuel Berg <[hidden email]> writes:

>> Just in case any bystander finds this post:
>> don't rely on anything that is mentioned
>> above, nor for C++ `inline' keyword nor for
>> code inlining in general.
>
> I read it in this book:
>
>     @book{cpp-direkt,
>       author     = {Jan Skansholm},
>       ISBN       = {91-44-47931-X},
>       publisher  = {Studentlitteratur},
>       title      = {C++ direkt},
>       year       = {1996}
>     }

The key data point there is "1996". But even then things were not as
simple as you described.

Since long time ago C++ "inline" is really about the ODR ("One
Definition Rule"), not about how the compiler generates code.


Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

James K. Lowden
In reply to this post by Emanuel Berg-4
On Fri, 05 Oct 2018 17:04:17 +0200
Emanuel Berg <[hidden email]> wrote:

> "Make the common case fast, and the complicated
> case work" -- M. Yoda

        Complex solutions are slow for small N, and
        N is almost always small.  
        -- Rob Pike

--jkl

Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
In reply to this post by Emanuel Berg-4
Óscar Fuentes wrote:

>>> Just in case any bystander finds this post:
>>> don't rely on anything that is mentioned
>>> above, nor for C++ `inline' keyword nor for
>>> code inlining in general.
>>
>> I read it in this book:
>>
>>     @book{cpp-direkt,
>>       author     = {Jan Skansholm},
>>       ISBN       = {91-44-47931-X},
>>       publisher  = {Studentlitteratur},
>>       title      = {C++ direkt},
>>       year       = {1996}
>>     }
>
> The key data point there is "1996". But even
> then things were not as simple as
> you described.

It was basically a translation of what it says.

> Since long time ago C++ "inline" is really
> about the ODR ("One Definition Rule"), not
> about how the compiler generates code.

I have now look it up in another book, namely

    @book{c-programming-language,
      author     = {Bjarne Stroustrup},
      ISBN       = {0-201-53992-6},
      publisher  = {Addison Wesley},
      title      = {The C++ Programming Language},
      year       = 1992
    }

here it says much less, with no attempt to
explain what actually "inline" means, still, it
seems to contradict what you say, because it
says the keyword inline is a "hint to the
compiler" to generate the code inline rather
than have the function called the usual way
(page 124).

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
In reply to this post by James K. Lowden
James K. Lowden wrote:

> Complex solutions are slow for small N, and
> N is almost always small.  
> -- Rob Pike

    Advance too fast, you catch up with death.
    But advance too slow, death catches up with YOU!
    -- The Metabaron

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
In reply to this post by Emanuel Berg-4
> I have now look it up in another book, namely
>
>     @book{c-programming-language,
>       author     = {Bjarne Stroustrup},
>       ISBN       = {0-201-53992-6},
>       publisher  = {Addison Wesley},
>       title      = {The C++ Programming Language},
>       year       = 1992
>     }
>
> here it says much less, with no attempt to
> explain what actually "inline" means, still, it
> seems to contradict what you say, because it
> says the keyword inline is a "hint to the
> compiler" to generate the code inline rather
> than have the function called the usual way
> (page 124).

I was about to say "I can do this all night",
but then I'd be a lier because I'm running out
of C++ books. This is the last one

    @book{small-c-how-to-program,
      author     = {H M Deitel and P J Deitel},
      ISBN       = {0-13-185758-4},
      publisher  = {Pearson},
      title      = {Small C++ How to Program},
      year       = 2005
    }

and it says virtually the same thing: "inline"
advices the compiler to "generate a copy of the
function's code in place" rather than the usual
call. (It also says the compiler can choose not
to do this; page 246.)

But I'm not saying you are wrong. I was once
~fluent in *writing* C++, but I didn't claim
then, and certainly do not claim now, to
understand what goes on under the hood.

To young, promising programmers, two pieces of
advice:

1) don't be a professional programmer; and

2) stay away from these books:

%%%% C++

@book{small-c-how-to-program,
  author     = {H M Deitel and P J Deitel},
  ISBN       = {0-13-185758-4},
  publisher  = {Pearson},
  title      = {Small C++ How to Program},
  year       = 2005
}

@book{c-programming-language,
  author     = {Bjarne Stroustrup},
  ISBN       = {0-201-53992-6},
  publisher  = {Addison Wesley},
  title      = {The C++ Programming Language},
  year       = 1992
}

@book{cpp-direkt,
    author     = {Jan Skansholm},
    ISBN       = {91-44-47931-X},
    publisher  = {Studentlitteratur},
    title      = {C++ direkt},
    year       = 1996
}

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
> C++ blah blah blah

For anyone reading this, don't be confused by
all the C++ talk, please carry on the Elisp
discussion if that is your desire!

As well as the C++ discussion for that matter.
Programming is NEVER off-topic on an
Emacs newsgroup!

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
In reply to this post by Emanuel Berg-4
> I was about to say "I can do this all night",
> but then I'd be a lier because I'm running
> out of C++ books. This is the last one

I was wrong, I have yet another one, but not on
C++, but on C, namely

    @book{vägen-till-c,
      author     = {Ulf Bilting and Jan Skansholm},
      ISBN       = {978-91-44-01468-5},
      publisher  = {Studentlitteratur},
      title      = {Vägen till C},
      year       = 2000
    }

it says, page 279, that into the "new" C99
standard, from C++, they have brought the
"inline" keyword. Then they just say the same
thing, instead of a call, the insertion of
code.

They also say the previous method of getting
somewhat the same stuff has been the use of
macros. By macros, they mean the #preprocessor
replacement of text! So they think the new
"inline" is really good! And one can
appreciate that :)

Now I really need to drink a couple of beers
and ride my bike (bicycle). I haven't written
this much on gnu.emacs.help in ages. Maybe I'm
not getting older after all! That, I'd
appreciate as well...

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Stefan Monnier
In reply to this post by Emanuel Berg-4
>>> function. What this means is that when the
>>> code is compiled into machine code, instead
[...]
>>> function is called, the machine code for the
>>> inline function is placed, duplicated
                    ^^
Maybe, maybe not: it's up to the compiler, because you won't be able to
tell the difference without looking under the hood.

And for the same reason the compiler can also decide to inline when you
*don't* say `inline`, as long as it doesn't affect the behavior of
the program.

Similarly, the compiler may decide to "outline" a chunk of code (take
a part of your function, move it to a new separate function, and
replace it with a call to that new function), or do all kinds of other
fun stuff, such as compile your C++ to Elisp code and combine it with an
Elisp interpreter.


        Stefan


Reply | Threaded
Open this post in threaded view
|

Re: Optimising Elisp code

Emanuel Berg-4
In reply to this post by Emanuel Berg-4
Stefan Monnier wrote:

> Similarly, the compiler may decide to
> "outline" a chunk of code (take a part of
> your function, move it to a new separate
> function, and replace it with a call to that
> new function), or do all kinds of other fun
> stuff, such as compile your C++ to Elisp code
> and combine it with an Elisp interpreter.

Can you explain what inline means in terms
of Elisp?

--
underground experts united
http://user.it.uu.se/~embe8573
Reply | Threaded
Open this post in threaded view
|

Knowing where a function has been used (e.g. for optimizing) [Was: Re: Optimising Elisp code]

Garreau, Alexandre
In reply to this post by Barry Margolin
On 2018-10-05 at 10:28, Barry Margolin wrote:
> You can define bar as a macro -- those HAVE to be expanded at compile
> time, since that's how they work.

But what’s the relationship since here, it’s not?

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

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

So aren’t there any dynamical system that would keep a track of
dependencies so that to allow inlining while recompiling the appropriate
functions when changing definitions of inlined stuff?

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

Doesn’t lexical scoping also lead to that behavior?

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

Does it automatically for lexically scoped function definitions?

Is it only because then the behavior would differ and because there’s
currently no way to, say, tell to defun, each time it redefines
something that has been inlined, to also recompile every functions which
included it?

There’s already, for each currently defined function, a handy way to get
back to where it was defined.  But I always noticed this relation is
one-way: there’s no way, for each currently defined function, to get
back to where it was called.  I always missed it because it would gives
a quick way to look at exemples of how a function is used (examples are
the other great way of learning: inherenthly more imperfect than a
definition but quicker and easier), but I feel like, there, if it
existed, it would also allow to generalize some optimizations that
already are handy for compiled, non-dynamic code (because afaik
recursively do this and other expansions, reducing, simplification,
could lead to making abstraction free of performance overhead, right?).

12345