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

["Garreau\, Alexandre" <galex-713@galex-713.eu>]

Le 06/10/2018 à 22h27, tomas@tuxteam.de a écrit :
> On Sat, Oct 06, 2018 at 09:55:09PM +0200, Garreau, Alexandre wrote:
>> 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.
>
> Then I didn't get you right: I gather we both mean the "context" where
> the function was "inlined into".

Yes.

> If you're lucky, no optimization has happened *after" you've inlined.

Lucky? Why? if it didn’t happen, will you really be able to extract the
inlined part to patch it? won’t recompiling it be simplier?

I like the idea of inline optimization precisely because if done
recursively even on a reasonable level it could sometimes lead to great
expansion/reduction and simplification, not only of one function call.

> Otherwise, you'll have to recompile the whole context (i.e. parts of
> the caller).

How do you recompile only a part? you can do this (I’m pretty ignorant
of elisp’s byte-compiler capabilities)?

>> > and do some magic there.
>> 
>> What other kind of magic than (maybe recursively)
>> reevaluating/recompiling could be needed there?
>
> In the case of a redefinition of the inlined function you'll have to
> find all call sites and do something.

that is, recursively recompiling, as I said, right? “do something” is no
more precise than “do some magic”, and “there” (in both messages)
already meant “at the call sites”.

>> > Perhaps doable, but not trivial.
>> 
>> I have really no precise idea of where and how is stored the place where
>> each function was defined
>
> Which functions you mean by "each function"? You mean the sites at which
> the inlined function is "called" (i.e. inlined), I guess.

Not really, including this, but I was speaking about the find-definition
feature of emacs specifically, since afterwards I talk about a symmetric
feature, that is, store the list of symbols refered by each function, even (or
rather, especially) if it is compiled, in a place linked to each
function definition: so if the functions `f', `g' and `h' refer to `a',
having in something linked to the `a' symbol (an alist, a plist,
anything) a list of these.  So the same way you can find-definition of
`a' and see how and where it was defined (like with C-h f, C-h v… and
xref generally), you could see where it has been used: that’s at the
same time a good way of see the use/meaning of `a' by examples rather
than by definition (if the definition didn’t suffice), and that would
allow to recursively draw some dependency graph showing what needs to be
recompiled if `a' is changed.

Maybe even someone could try some experimental optimizations features
such as, let this `a' be a variable, not a thunk, recompile everything
referring to `a' when you change it (thus leading to the same behavior
of a thunk, without side-effects, and with statical optimization)

> Well, I haven't a precise idea either, but for a pretty lucid description
> (in the context of Guile, but with pointers to other implementations),
> cf
>
>   https://wingolog.org/archives/2018/02/07/design-notes-on-inline-caches-in-guile

I was speaking of something more static, not at eval-time, but at
compile-time.  The idea was to keep a big but exhaustive list of usages
(that would be filled at each definition, I guess the same way as
load-history already is), growing with time (possibly directly linked to
the symbol).

>> >> Why “undo”? [...]
>
> [...]
>
>> So, except maybe wrt debugging (which there should imply reevaluation,
>
> you mean "recompile"

Afaik edebug-defun works by reevaluation everywhere, even for
not-compiled functions.  So I meant reevaluation.  Except, you, indeed,
were speaking about the case I was saying I wasn’t speaking about, that
is debugging an already existing (possibly compiled) function, without
reusing its definition (that is reevaluating, or recompiling if
necessary (because it was already compiled)).

>> like with edebug-defun), reevaluating (or rather recompiling indeed,
>> since afaiu then, simple evaluation will never optimize anything, unlike
>> byte-compiling (right?)).
>
> 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),

That’s why I’m talking about recompiling.

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

In wingo’s article he speaks about a cache put *inside* a function,
that’s updated *while* evaluation, depending on it.  I’m speaking of the
statical, pre-compilation case.  With this same information, not
guessed, but exhaustive, and not stored *inside* the function, but in
some place related, be it a global dictionary (hashtable, alist or
plist), or in something related to the symbol (its plist? some modified
symbol?): so you can programatically use this list of locations
typically in xref/help buffers, in some experimental paradigm of
programming, etc.  IC is only an optimization, is VM/evaluation-side, is
non-exhaustive/guessed by nature, and is, afaiu, hidden from the user
point-of-view.