Can ZWC be optimized, for lesser depths of recursive exec* calls?

Can ZWC be optimized, for lesser depths of recursive exec* calls?

[Sebastian Gniazdowski]

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

Hello,
I've occurred a comment in exec.c, from year 2000:

 * Pipelines like the one above are executed by the functions in this file
 * which call each other (and sometimes recursively). The one above, for
 * example would lead to a function call stack roughly like:
 *
 *  execlist->execpline->execcmd->execwhile->execlist->execpline

This casts some light on attached profiling-stack-traces (OS X tool Instruments; images compressed by pngcrunch). The stack traces are very deep. I am pretty sure that the test script (ran by the Zsh controled by the profiler) doesn't do pipes.

So a conclusion can be made:

- Zsh code execution is emerging from from rich number of calls to exec.c functions,
- general-purpose or not-final calls are done, equilibrium is established, each Zsh script part finds its (convoluted) way to execsimple, prefork, addvars,
- like in Prolog (but maybe in reversed direction), where each theorem finds its top truths in many stages.

CPU time is dissipated over exec.c calls, profiling confirms this.

I'm trying to alter custom zcompile to limit the depth in case where there are no pipes. Can someone help with this? I can only state that execsimple() and Z_SIMPLE, WC_SUBLIST_SIMPLE are related. However, following comment:

 * Lists and sublists may also be simplified, indicated by the presence
 * of the Z_SIMPLE or WC_SUBLIST_SIMPLE flags. In this case they are only
 * followed by a slot containing the line number, not by a WC_SUBLIST or
 * WC_PIPE, respectively.

and some exec.c-reading hints, that the "not-following by WC_SUBLIST" means no-argumets for executed function, builtin, etc. So, if an entity has arguments, it will require to invoke another recursive execpline2, because execsimple() cannot be used. Is something possible here?

--  
Sebastian Gniazdowski
psprint /at/ zdharma.org

[-- Attachment #2: execpline2_a.png --]
[-- Type: image/png, Size: 121123 bytes --]

[-- Attachment #3: execpline2_b.png --]
[-- Type: image/png, Size: 101387 bytes --]

Re: Can ZWC be optimized, for lesser depths of recursive exec* calls?

[Bart Schaefer]

On Thu, Jul 20, 2017 at 8:41 AM, Sebastian Gniazdowski
<psprint@zdharma.org> wrote:
>
> - Zsh code execution is emerging from from rich number of calls to exec.c functions,
> - general-purpose or not-final calls are done, equilibrium is established, each Zsh script part finds its (convoluted) way to execsimple, prefork, addvars,
> - like in Prolog (but maybe in reversed direction), where each theorem finds its top truths in many stages.

To some extent you're having a deeper variation of the same confusion
that Ray Andrews sometimes has, namely, distinguishing characteristics
of an interpreted language from a compiled one.  With a true compiled
language, the syntax and semantics can both be analyzed at compile
time, but in an interpreted language the semantics aren't fully
expressed until run time.  In this case the chain of exec.c function
calls traces the semantics of the language -- reconstructing the parse
tree, traversing it, and executing it, all at the same time.

This is crucial for accurately reproducing the original script flow in
xtrace output.  Simplifying the ZWC would amount to rewriting the
script -- looking at xtrace output would be like stepping through an
optimized C program with a debugger:  the program counter would no
longer correspond to the source.

Even if you are willing to accept that, there are a number of
potential gotchas with any shortcutting of the process -- witness
issues found in the past several months with signal handling, job
control management, propagation of environment variables, etc., some
of which arose because of the optimizations that are already present.

> some exec.c-reading hints, that the "not-following by WC_SUBLIST" means no-argumets for executed function, builtin, etc.

I think that's a wrong interpretation -- WC_SUBLIST should mean a
construct like "command1 && command2", where SIMPLE means there is no
such conditional construct (only "command1" is present).

Re: Can ZWC be optimized, for lesser depths of recursive exec* calls?

[Sebastian Gniazdowski]

On 20.07.2017 at 19:40:33, Bart Schaefer (schaefer@brasslantern.com) wrote:
> To some extent you're having a deeper variation of the same confusion
> that Ray Andrews sometimes has, namely, distinguishing characteristics
> of an interpreted language from a compiled one. With a true compiled
> language, the syntax and semantics can both be analyzed at compile
> time, but in an interpreted language the semantics aren't fully
> expressed until run time. In this case the chain of exec.c function
> calls traces the semantics of the language -- reconstructing the parse
> tree, traversing it, and executing it, all at the same time.

Today instead of looking at large OS X Instruments call tree, I've added function-name-printing to each *exec* (plus addvars) function in exec.c. This way execution looks much more normal and exec.c code seems quite compact now, not so many such functions there. Basically following repeats for any execution-code item (not e.g. function-definition item):
  execlist -> execpline -> execpline2 -> execcmd_exec.

Function execsimple() can do assignment and function-definition (there's also some general-purpose else {} but it's rather not used, as control should go general-purpose earlier, before execsimple, if needed). Didn't track WC_SIMPLE yet.

I have a hard time establishing where CPU-time dissipates. It's a gradual process, and exec.c functions happen to be long. However I see that my requests to help in optimizing zwc have been rather asking for doing something with the 4 above typical calls, and yeah, they're typical, rather nothing to do with them.

> This is crucial for accurately reproducing the original script flow in
> xtrace output. Simplifying the ZWC would amount to rewriting the
> script -- looking at xtrace output would be like stepping through an
> optimized C program with a debugger: the program counter would no
> longer correspond to the source.

I have this automated. (z) flag and state tracking, and voila, automatic function extraction:

% zplg lexicon convert zdharma/fast-syntax-highlighting
Extracted  47-line function `_zsh_highlight'...
Extracted  21-line function `_zsh_highlight_apply_zle_highlight'...
Extracted  34-line function `_zsh_highlight_bind_widgets'...
Extracted   2-line function `_zsh_highlight_buffer_modified'...
Extracted   2-line function `_zsh_highlight_call_widget'...
Extracted   2-line function `_zsh_highlight_cursor_moved'...
Extracted   3-line function `_zsh_highlight_preexec_hook'...
Generated preamble ( 21 lines) # this is .plugin.zsh file stripped of funs

% pwd
/Users/sgniazdowski/.zplugin/lexicon

% ls
_zsh_highlight                     _zsh_highlight_call_widget
_zsh_highlight_apply_zle_highlight _zsh_highlight_cursor_moved
_zsh_highlight_bind_widgets        _zsh_highlight_preexec_hook
_zsh_highlight_buffer_modified

% file ../lexicon.zwc
../lexicon.zwc: data

So if user wants xtrace, he can revert to-lexicon-conversion and run plugin normally. The problem is that lexicon seems to be 2-3 ms slower. Not much, can treat this as the-same-speed, however, it should be faster to justify doing this. Or at least have some not-speed-related features. Seeing plugin's functions as files is cool, but I need something more.

--  
Sebastian Gniazdowski
psprint /at/ zdharma.org

Re: Can ZWC be optimized, for lesser depths of recursive exec* calls?

[Sebastian Gniazdowski]

On 20 lipca 2017 at 19:40:33, Bart Schaefer (schaefer@brasslantern.com) wrote:
> On Thu, Jul 20, 2017 at 8:41 AM, Sebastian Gniazdowski
> wrote:
> >
> > - Zsh code execution is emerging from from rich number of calls to exec.c functions,  
> > - general-purpose or not-final calls are done, equilibrium is established, each Zsh  
> script part finds its (convoluted) way to execsimple, prefork, addvars,
> > - like in Prolog (but maybe in reversed direction), where each theorem finds its top  
> truths in many stages.
>  
> To some extent you're having a deeper variation of the same confusion
> that Ray Andrews sometimes has, namely, distinguishing characteristics
> of an interpreted language from a compiled one. With a true compiled
> language, the syntax and semantics can both be analyzed at compile
> time, but in an interpreted language the semantics aren't fully
> expressed until run time. In this case the chain of exec.c function
> calls traces the semantics of the language -- reconstructing the parse
> tree, traversing it, and executing it, all at the same time.

It's just that I suspect "recurse and forget" tactics in exec.c. Like zle recursive-edit – surprisingly useful, implemented by running zlecore() second time. Having an opportunity to give kudos, I would give it to that person who decided to spend time on doing this very useful in the future, but in general slightly bizarre (running zlecore() again) feature.


The comment in exec.c (first line about suspending pipelines):

 * Some years ago, zsh either couldn't suspend such things at all, or
 * it got really messed up when users tried to do it. As a solution, we
 * implemented the list_pipe-stuff, which has since then become a reason
 * for many nightmares.
 * Pipelines like the one above are executed by the functions in this file
 * which call each other (and sometimes recursively). The one above, for
 * example would lead to a function call stack roughly like:
 *
 *  execlist->execpline->execcmd->execwhile->execlist->execpline

So it looks like getting away through recursion, which is a powerful technique, but if it's "recurse and forget", and CPU time dissipates, then well, no huge problem, shell doesn't have to be fast like python, but it is an obstacle sometimes (syntax highlighting large functions, for example, I was removing functions (inlining) and also simply removing code if only it was possible, gaining many milliseconds).

I have obstacles in working on Zsh recently, I would dive into exec.c and maybe find something. Side note – all this is to make Zplugin sophisticated, dreaming about automatic extraction of functions and "turbo" compilation of them into zwc digest. But "turbo" compiling of plugin file (with global code and functions) would also work, he he, so I would close this door for the users ;)

> > some exec.c-reading hints, that the "not-following by WC_SUBLIST" means no-argumets  
> for executed function, builtin, etc.
>  
> I think that's a wrong interpretation -- WC_SUBLIST should mean a
> construct like "command1 && command2", where SIMPLE means there is no
> such conditional construct (only "command1" is present).

Thanks. It's a better situation than no-arguments, if one thinks about short-cutting execution more early to execsimple(), etc.

--  
Sebastian Gniazdowski
psprint /at/ zdharma.org

Re: Can ZWC be optimized, for lesser depths of recursive exec* calls?

[Bart Schaefer]

On Mon, Jul 24, 2017 at 6:26 PM, Sebastian Gniazdowski
<psprint@zdharma.org> wrote:
>
> It's just that I suspect "recurse and forget" tactics in exec.c.

I don't know what you mean by this.

Re: Can ZWC be optimized, for lesser depths of recursive exec* calls?

[Sebastian Gniazdowski]

On 25 lipca 2017 at 07:04:07, Bart Schaefer (schaefer@brasslantern.com) wrote:
> On Mon, Jul 24, 2017 at 6:26 PM, Sebastian Gniazdowski
> wrote:
> >
> > It's just that I suspect "recurse and forget" tactics in exec.c.
>  
> I don't know what you mean by this.

The example in comment in exec.c is:

    cat foo | while read a; do grep $a bar; done

Expected calls are:

    execlist->execpline->execcmd->execwhile->execlist->execpline

This shows that grep is treated as a potential pipe. So what I mean is that the problem with pipes (the topic of the comment) is solved by having enough general execpline(), and then just recursing, always, and expect a positive outcome to be computed. Like the zlecore() example – main Zle works, so calling it again "should not cause problems", to simulate typical programmer thinking in such situation. So it's an opportunity to not write new code, just reuse what's there already, tested and working.

--  
Sebastian Gniazdowski
psprint /at/ zdharma.org