refactoring variable storage

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

refactoring variable storage

John W. Eaton
Administrator
 From the beginning, Octave has stored values in the symbol table.  This
simplistic model initially did not work correctly for recursive function
calls.  To properly handle recursion, each symbol_record (the object
corresponding to a single variable in the scope of a script or function)
was eventually augmented to maintain a stack of values.  This worked,
more or less, but was quite messy.  Accessing values in recursive
functions was cumbersome and required managing a "context" variable to
say which element of the stack to access.

To fix this problem, I recently began a significant refactoring to move
the storage of values from the symbol table to the call stack.  This
makes much more sense and is consistent with the way I understand other
interpreters and complied languages typically work.  With the new
approach for storing values, accessing data from non-local scopes
(nested functions accessing variables from parent functions) and data in
parent stack frames is much simpler.  Creating proper closures should be
much more manageable, and should allow bug #39257 (handles to nested
functions are not yet supported) to be fixed (finally!).

The patches for these changes are on the jwe-call-stack-refactor
bookmark in the mercurial archive publicly accessible here:
http://hg.octave.org/octave-jwe

There are approximately 80 smaller changesets that make up the complete
set of changes.  These changes are not all self-contained or rational as
many were made at temporary checkpoints during development.  If merged
together, the resulting diff is about 12,000 lines.  I'm inclined to
apply it as one large changeset since at this point I don't know how to
break it up into smaller chunks that make sense.

Some details about the implementation are included at the top of the
stack-frame.h file and before each class declaration in that file.

One way or another, I'd like to merge these changes with the default
branch soon so they can be thoroughly tested before Octave 6 is released
sometime later in 2019 or early 2020.

Comments and questions welcome.

jwe

Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

John W. Eaton
Administrator
I pushed a series of changesets to default to make the change described
in the quoted message below.

The largest part of the change moves storage of values from
symbol_record objects to stack_frame objects.  In the end, I was unable
to see a good way to split that change into small chunks.  So it is,
unfortunately, checked in as one massive commit.  I'll certainly try to
do better than that in the future.

Overall, I believe this set of changes represents a significant
improvement in the implementation of the interpreter.

The jwe-call-stack-refactor bookmark on my personal hg archive that is
mentioned below is now abandoned but I will leave it in the archive.

jwe


On 1/3/19 10:21 PM, John W. Eaton wrote:

>  From the beginning, Octave has stored values in the symbol table.  This
> simplistic model initially did not work correctly for recursive function
> calls.  To properly handle recursion, each symbol_record (the object
> corresponding to a single variable in the scope of a script or function)
> was eventually augmented to maintain a stack of values.  This worked,
> more or less, but was quite messy.  Accessing values in recursive
> functions was cumbersome and required managing a "context" variable to
> say which element of the stack to access.
>
> To fix this problem, I recently began a significant refactoring to move
> the storage of values from the symbol table to the call stack.  This
> makes much more sense and is consistent with the way I understand other
> interpreters and complied languages typically work.  With the new
> approach for storing values, accessing data from non-local scopes
> (nested functions accessing variables from parent functions) and data in
> parent stack frames is much simpler.  Creating proper closures should be
> much more manageable, and should allow bug #39257 (handles to nested
> functions are not yet supported) to be fixed (finally!).
>
> The patches for these changes are on the jwe-call-stack-refactor
> bookmark in the mercurial archive publicly accessible here:
> http://hg.octave.org/octave-jwe
>
> There are approximately 80 smaller changesets that make up the complete
> set of changes.  These changes are not all self-contained or rational as
> many were made at temporary checkpoints during development.  If merged
> together, the resulting diff is about 12,000 lines.  I'm inclined to
> apply it as one large changeset since at this point I don't know how to
> break it up into smaller chunks that make sense.
>
> Some details about the implementation are included at the top of the
> stack-frame.h file and before each class declaration in that file.
>
> One way or another, I'd like to merge these changes with the default
> branch soon so they can be thoroughly tested before Octave 6 is released
> sometime later in 2019 or early 2020.
>
> Comments and questions welcome.
>
> jwe


Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

Michael Godfrey
John,

I ran some tests using your update and all worked correctly.
I did not check timing but definitely not slower than before.

In any case this seems to be a major step forward.

Michael
Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

nrjank


On Fri, Feb 1, 2019 at 8:28 AM Michael D Godfrey <[hidden email]> wrote:


In any case this seems to be a major step forward.


agreed. if it indeed allows bug #39257 to get knocked out, what else does that enable that's been on hold?  Wasn't that a major stumbling block to implementing GUIDE compatibility? 

would it be close enough to have GUIDE compatibility on the GSOC topic list? or too soon to count on that?
Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

jbect
In reply to this post by John W. Eaton
Le 31/01/2019 à 23:44, John W. Eaton a écrit :
> I pushed a series of changesets to default to make the change
> described in the quoted message below.

Hi John,

I can no longer build with --enable-jit.  Here are the errors that I get :


libinterp/parse-tree/pt-jit.cc: In member function ‘virtual void
octave::jit_convert::visit_statement(octave::tree_statement&)’:
libinterp/parse-tree/pt-jit.cc:835:34: error: ‘class
octave::tree_identifier’ has no member named ‘is_variable’
              do_bind_ans = (! id->is_variable (m_scope.current_context
()));
                                   ^~~~~~~~~~~
libinterp/parse-tree/pt-jit.cc:835:55: error: ‘class
octave::symbol_scope’ has no member named ‘current_context’
              do_bind_ans = (! id->is_variable (m_scope.current_context
()));
^~~~~~~~~~~~~~~
libinterp/parse-tree/pt-jit.cc: In member function
‘octave::jit_variable* octave::jit_convert::get_variable(const string&)’:
libinterp/parse-tree/pt-jit.cc:1177:16: error: ‘class
octave::symbol_record’ has no member named ‘is_persistent’
      if (record.is_persistent () || record.is_global ())
                 ^~~~~~~~~~~~~
libinterp/parse-tree/pt-jit.cc:1177:43: error: ‘class
octave::symbol_record’ has no member named ‘is_global’; did you mean
‘is_local’?
      if (record.is_persistent () || record.is_global ())
                                            ^~~~~~~~~
libinterp/parse-tree/pt-jit.cc:1184:35: error: ‘class
octave::symbol_record’ has no member named ‘varval’; did you mean ‘formal’?
          octave_value val = record.varval (m_scope.current_context ());
                                    ^~~~~~
libinterp/parse-tree/pt-jit.cc:1184:51: error: ‘class
octave::symbol_scope’ has no member named ‘current_context’
          octave_value val = record.varval (m_scope.current_context ());
                                                    ^~~~~~~~~~~~~~~
libinterp/parse-tree/pt-jit.cc: In member function ‘bool
octave::jit_info::execute(const vmap&) const’:
libinterp/parse-tree/pt-jit.cc:2745:17: error: ‘class
octave::symbol_scope’ has no member named ‘assign’
            scope.assign (m_arguments[i].first, real_arguments[i]);
                  ^~~~~~
libinterp/parse-tree/pt-jit.cc: In member function ‘octave_value
octave::jit_info::find(const vmap&, const string&) const’:
libinterp/parse-tree/pt-jit.cc:2862:22: error: ‘class
octave::symbol_scope’ has no member named ‘varval’
          return scope.varval (vname);
                       ^~~~~~


@++
Julien

Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

John W. Eaton
Administrator
On 2/1/19 3:35 PM, Julien Bect wrote:
> Le 31/01/2019 à 23:44, John W. Eaton a écrit :
>> I pushed a series of changesets to default to make the change
>> described in the quoted message below.
>
> Hi John,
>
> I can no longer build with --enable-jit.  Here are the errors that I get :

I can probably help fix these, but I'm not sure that it matters.  As you
know, the current implementation doesn't do much of anything useful. Are
you working on making it do more?  If so, instead of working with the
current framework (and old versions of LLVM) maybe we should work toward
updating it to a more modern way of using LLVM?

jwe


Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

jbect
Le 01/02/2019 à 22:20, John W. Eaton a écrit :

> On 2/1/19 3:35 PM, Julien Bect wrote:
>> Le 31/01/2019 à 23:44, John W. Eaton a écrit :
>>> I pushed a series of changesets to default to make the change
>>> described in the quoted message below.
>>
>> Hi John,
>>
>> I can no longer build with --enable-jit.  Here are the errors that I
>> get :
>
> I can probably help fix these, but I'm not sure that it matters. As
> you know, the current implementation doesn't do much of anything
> useful. Are you working on making it do more?  If so, instead of
> working with the current framework (and old versions of LLVM) maybe we
> should work toward updating it to a more modern way of using LLVM?

Until recently it was only working with LLVM 3.8, but I made changes
recently that makes it work with 3.9 too (they have been pushed to
stable by Rik : see https://savannah.gnu.org/patch/?9741).

Of course, as you say it doesn't do much, but at least it can can
(could) be built and compiles some simple for loops.  I would like to
try to make it do more, but first I need to understand better what it
already does and how it does it...  (and fix existing problems with
complex numbers, exceptions, etc.)

It can (could) also be built with LLVM 4.0, but there is something wrong
with the memory manager (https://savannah.gnu.org/bugs/?55492), so it
doesn't really work.  This is what I was currently trying to solve.  I
also have patches that make it build with LLVM 5.0, but the same problem
exists there.

You're talking about "old versions" of LLVM, but LLVM 3.8 -- 4.0 are in
fact the version currently available in Debian stretch.  (I know, not in
fedora...)

Concerning more "modern ways of using LLVM", we already jumped from the
"old JIT" to MCJIT when I adapted the code to work with LLVM 3.8 almost
one year ago.  From what I have read, the most "modern" way would
prbably be to use the "ORC" framework, but since our current JIT
implementation is very limited, I am not sure that switching from MCJIT
to ORC is very important right now.

@++

Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

Mike Miller-4
On Fri, Feb 01, 2019 at 22:45:53 +0100, Julien Bect wrote:
> You're talking about "old versions" of LLVM, but LLVM 3.8 -- 4.0 are in fact
> the version currently available in Debian stretch.  (I know, not in
> fedora...)

IMHO, the development branch of Octave should try to target "current"
versions of LLVM, where "current" is 7.0 and 8.0-rc1 at the moment.
Targeting the Debian stable version of LLVM seems less than effective.

Please consider that by the time the current default branch becomes
Octave 6 (probably about a year from now), it would be most useful to
everyone if it worked with LLVM 9 and/or 10 (probably releasing
September 2019 and March 2020, respectively).

But obviously I am not the one doing the work, just offering a
perspective. And thank you for taking on this long-neglected task.

--
mike

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

Re: refactoring variable storage

jbect
Le 01/02/2019 à 23:25, Mike Miller a écrit :

> On Fri, Feb 01, 2019 at 22:45:53 +0100, Julien Bect wrote:
>> You're talking about "old versions" of LLVM, but LLVM 3.8 -- 4.0 are in fact
>> the version currently available in Debian stretch.  (I know, not in
>> fedora...)
> IMHO, the development branch of Octave should try to target "current"
> versions of LLVM, where "current" is 7.0 and 8.0-rc1 at the moment.
> Targeting the Debian stable version of LLVM seems less than effective.
>
> Please consider that by the time the current default branch becomes
> Octave 6 (probably about a year from now), it would be most useful to
> everyone if it worked with LLVM 9 and/or 10 (probably releasing
> September 2019 and March 2020, respectively).

Sure, I am not "targeting the Debian stable version".  Not at all.

I am just noting that : 3.8 -- 3.9 is the range of LLVM versions that we
currently can build with.  Then, I progressively try to extend this
range (as opposed to : making it work with 4.0 while breaking what
currently works with 3.8 - 3.9).

I believe that for 4.0 and 5.0 it will boil down to a few autoconfs
macros **once** the required change will have been determined... (By the
way, note that 4.0 and 5.0 are not *very* old, since they were releases
in March and September 2017, respectively.)

Then I will try to extend to 6.0 (March 2018) and 7.0 (September 2018)
but I have no idea about the kind of problem that I will meet then.

Proceeding like this, step by step, is easier for me than breaking
everything and trying to make it work wih LLVM 7.0 or 8.0-rc1 directly,
because my understanding of LLVM, JIT, etc. is very limited and I am
learning along the way...


Reply | Threaded
Open this post in threaded view
|

Re: refactoring variable storage

Michael Godfrey
This should work as long as you can at least at some point catch
up with the LLVM release schedule. At some point LLVM may settle
on a stable interface but that does not appear to be in their current
plans. Anyhow, good luck!

On 2/2/19 8:18 AM, Julien Bect wrote:
Le 01/02/2019 à 23:25, Mike Miller a écrit :
On Fri, Feb 01, 2019 at 22:45:53 +0100, Julien Bect wrote:
You're talking about "old versions" of LLVM, but LLVM 3.8 -- 4.0 are in fact
the version currently available in Debian stretch.  (I know, not in
fedora...)
IMHO, the development branch of Octave should try to target "current"
versions of LLVM, where "current" is 7.0 and 8.0-rc1 at the moment.
Targeting the Debian stable version of LLVM seems less than effective.

Please consider that by the time the current default branch becomes
Octave 6 (probably about a year from now), it would be most useful to
everyone if it worked with LLVM 9 and/or 10 (probably releasing
September 2019 and March 2020, respectively).

Sure, I am not "targeting the Debian stable version".  Not at all.

I am just noting that : 3.8 -- 3.9 is the range of LLVM versions that we currently can build with.  Then, I progressively try to extend this range (as opposed to : making it work with 4.0 while breaking what currently works with 3.8 - 3.9).

I believe that for 4.0 and 5.0 it will boil down to a few autoconfs macros **once** the required change will have been determined... (By the way, note that 4.0 and 5.0 are not *very* old, since they were releases in March and September 2017, respectively.)

Then I will try to extend to 6.0 (March 2018) and 7.0 (September 2018) but I have no idea about the kind of problem that I will meet then.

Proceeding like this, step by step, is easier for me than breaking everything and trying to make it work wih LLVM 7.0 or 8.0-rc1 directly, because my understanding of LLVM, JIT, etc. is very limited and I am learning along the way...