Re: 3.3 Wishlist : [Fwd: Re: treelayout and spaugment procedures]

[Jaroslav Hajek]

On Wed, Aug 27, 2008 at 4:23 PM, David Bateman
<address@hidden> wrote:
> John,
>
> While responding to Ivana offline, I speculated on a 3.3 Wishlist. The
> wishlist I came up with was
>
> * Write a tree walker evaluator class
>  - Implement the current evaluation code in terms of this tree walker
>  - Write an instrumented version of the same evaluator to implement the
> profile command
>  - Write an Octave to C++ filter based on this class
>  - Write an Octave to Matlab (ie remove Octave specific code) filter based
> on this class
>  - Include a LLVM based JIT in this tree walker class based on work in
> FreeMat and use it in the first three of the above evaluators.
>

Nobody ever convinced me that mimicking Matlab-style JIT compiling is
a good way to go. In fact, when I was going through a JIT "demo" in
Matlab, I was plainly disappointed. Optimization, IMHO, is usually
something you do on purpose.
But Matlab, AFAIK, provides no real means to support optimization. As
John already pointed out, the key problem for the JIT optimization is
the type inference. If Matlab would be serious about optimizing
m-files, I would expect it to introduce some directives or other means
for the programmer to inform the interpreter/compiler that "R is
always real scalar" and "M is an integer matrix". Similarly, I would
expect a means to inform the compiler that there will be no
out-of-bounds assignment, etc.
With such means (e.g. directives), I believe that implementing the JIT
optimization would be much simpler. Serious optimization is always
about providing the compiler with extra information.

To put it in another way: I don't think that the real problem for
users is that their Octave m-code is running slow. The real problem is
that they have no way to make it run fast, unless they are willing to
step over to C++. I wouldn't mind having to decorate the for loops in
m-code with some directives,  if it was possible. In fact, I would
rather have a tool to explicitly optimize a piece of code than just
relying on the interpreter to pick up the particular section that *I
know* is the bottleneck.


> * Implement the saving of anonymous function handles (with their associated
> workspace) to Matlab file formats. This is complex as the file format for
> this case is not documented. Octave includes a first attempt at the loading
> of anonymous function handles previously saved by Matlab and might be used
> as a basis for this work.
>
> * Allow newer versions of HDF5 to be used with Octave without special
> compilation flags given to the compilation of HDF5. Write the autoconf magic
> necessary to recognize the different APIs
>
> * Write a Matlab v7.4 file format based on the HDF5 format to allow transfer
> of large variables to be transfered between Octave and Matlab
>
> * Rewrite the ftp package functions in octave-forge based on the CURL
> library and import these in to Octave itself
>
> * Write single precision version of the lsode, etc functions
>
> * Move some of the methods in the classes like Matrix upto the Array<T> to
> simplify these classes (based on previous discussion when introducing the
> single precision type)
>
> I was originally hoping to get the last two done for Octave 3.2, but will
> see how far I get. I'm not sure how realistic the tree walker evaluator
> class is as its a lot of work and I'm probably not the best placed to
> address this point. However, it was goal 14 (after the cutoff) for the 3.1
> goals and its important to address the two major missing Octave features in
> my mind (ie the profiler and simplify the inclusion of LLVM support for JIT)
> so I'd hope it will be seen as needed for 3.3
>
> The other 3.1 goals that were after the cutoff were
>
> <quote>
> 12. Implement nested functions
>
> 13. Eliminate explicit dispatch on type in various functions (for
> example, the NATIVE_REDUCTION macro in data.cc, the if/else mess
> in sort, or any other similar constructs) in favor of dispatch
> via virtual functions in the octave_value class.
>
> 15. BLAS/LAPACK:
> -- Stop distributing Fortran sources? If we do this, should
> we make it possible to compile Octave without any
> BLAS/LAPACK library, or should BLAS/LAPACK be required?

I'm not sure this is a good idea. BLAS and LAPACK are a vital part of
Octave; it would not even compile without them (and if it would, it
would be hardly usable). It's not that easy to compile BLAS and
LAPACK, IMHO. I'm often told that one thing that discourages people
from compiling software is solving such dependencies.

> -- Use cblas interface?

If you think about including cblas in Octave, that's certainly
possible, but I don't see much of an advantage over calling the F77
interface directly.
If you think about just relying that every BLAS has a cblas interface,
then that's a bad idea IMO - for instance, my favorite GotoBLAS does
not, though it's written in mixed C & assembler.
Like it or not, BLAS and LAPACK are established as Fortran libraries
(or Fortran-callable at least), and it seems that Fortran simply
failed to die out. LAPACK is now unlikely to be ever rewritten to C
(or at least in the several decades ahead), so there will still be
need for Fortran interfacing, if we want to make full use of LAPACK.

> 16. Update the configure script and make checks for header files and
> libraries more consistent (maybe we could recruit an autoconf
> expert to help with this job).
> </quote>
>
> though I believe I've at least partially addressed goal 13 (ie in sort and
> some of the sparse function now don't use dispatch). With this and the fact
> we are getting close to a 3.2 release, maybe its time to start looking at a
> 3.3 goals list.
>

Citing John, the future of Octave is whatever the community of users
and developers of Octave want it to be. I'm adding my targets for 3.3
(or later):

1. implement the nonlinear equations & least squares solvers in core Octave.
I recall someone posting a list of top 100 (or perhaps other number)
Matlab's most used functions and, I think fzero and fminbnd made the
list. fsolve is also important for many, and lsqnonlin completes the
list (nonlinear least squares are algorithmically & numerically very
close to nonlinear equations)..

2. improve the safe integer arithmetic in Octave. This is handled by
octave_int and is currently done via converting to double, doing the
operation, converting back, doing a cutoff and setting flags if
appropriate. It is possible to achieve significant speed-ups by doing
the operations in integer arithmetic if possible, though it requires
some care. (I have contributed a simple integer arithmetic benchmark
to OctaveForge's benchmark package for this purpose)
Also, I would like to make int64 arithmetic available in the
interpreter (though Matlab does not have it) and provide a means to
enter 64-bit numbers larger than 2**52 in the interpreter.

2a. Many Octave functions return real data where integers are more
appropriate, particularly for index vectors. Think about sort, lookup,
set functions, voronoi & delaunay... Perhaps there is a way to make
these functions work with integers without breaking (too much)
compatibility? I think that this is basically all about Matlab's
heritage from the times when it didn't support handling integers.

3.  rewrite parts of liboctave that use macros or code duplication
using templates.

4. maybe improve some string functions


regards,


-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz