Re: profiling Octave

[John W. Eaton]

On 8/12/19 5:08 PM, Rik wrote:

> JWE has changed the parser from a pull parser to a push parser (or maybe
> the other way around?) over time.  My hunch is that it is not parsing (done
> by lex and bison--old, well-established tools), but evaluation that has slowed.

We currently ask bison to generate both push and pull parsers but 
currently only use the pull parser (the parser calls lex, which calls a 
function to gather input from the user or a file).  We would only use 
the push parser and lexer if we change the design of the GUI terminal 
widget as we have discussed previously.

Compared to evaluation, parsing is pretty fast and only happens once 
when a function or script is first loaded by the interpreter.  You can 
time required to parse a single function or script by doing

  tic, __parse_file__ ("bm_toeplitz.m"), toc

On my system, this reports a time of 0.000945091 seconds.

> This is a bit beyond me, but I think so.  I believe Octave constructs a
> tree of nodes from the source code and then proceeds to evaluate them.  So
> you are correct, if
>
> y = x + 1
>
> generates the same primitive actions
>  > 1) create temporary octave_value from scalar 1

The constant is already stored in the parse tree as an octave_value object.

> 2) fetch x

This should be fairly quick for variables since they are the first thing 
we look for when resolving symbols.

> 3) perform operator function plus (x, tmp_value)

Somewhat time consuming because we have to dispatch to the correct 
addition function based on the types of the values./

> 4) assign octave_value output to y

Simple assignment to a variable with no index should be the fastest, but 
there may still be a lot of room for improvement.

> between versions, but one version takes longer than another, then the
> conclusion must be that the individual steps are taking longer.

We may also be doing more work because we have to handle new features 
(for example, class dispatch or import declarations when looking for 
functions).  Maybe some of the things we are doing now are unnecessary 
in many cases but we are doing them always.  It's not always easy to see 
what operations can be skipped and still provide the correct behavior.

> I think so.  Idea is to do the parsing to intermediate form.  Then, instead
> of calling evaluate on the IR each time through the loop, continue further
> and actually compile the IR to true executable code that can just be run,
> not evaluated.

Yes, and the general idea is that compiling has to be done "just in 
time" because without type info you can't compile the language and type 
info is not known until a function is called with actual values.  Then 
you cache the compiled code along with the types of the arguments so 
that it can be reused if you encounter another call to the same function 
with the same argument types again.

A generic compiler that generates code that uses octave_value objects 
would be of almost no use because one of the most time consuming parts 
of evaluation is dispatching based on types.  Using octave_value objects 
means you still do all of that work.

jwe