[Gsll-devel] What is needed to fix matrix views?

[Tamas K Papp]

Hi everyone,

I have been also thinking about general array views for quite a while.
My abtraction for a view is 

- a dimension n
- ranges a_1, ..., a_n
- an affine map from [0,a_1) x ... [0,a_n) -> N, where intervals
  contain integers only and N is the set of natural numbers

The idea is that array-like data is just a flat vector.  What makes it
a vector, array or matrix (or any kind of view) is the way you map
n-tuples of integer indexes into indexes of this vector.  Affine maps
are a very general way to do this.

Affine maps can be implemented superfast, with a constant b_0 and a
set of coefficients b_1, ..., b_n.  For example, for n=2, the mapping
is b_0+i*b_1+j*b_2.  Row major matrices are just 0+i*nrow+j*1, column
major matrices are 0+i*1+j*ncol.  You can easily set up affine maps
for transposing matrices (or in general, "permuting" arrays), views on
a Cartesian product of contiguous indices, etc.  Or strides, you want
every 3rd element of a vector, 0+i*3.  For a 3-dimensional row-major
array, 0+i*(a_2*a1)+j*a1+k*1 (so the affine map would be
(0,a_2*a_1,a_1,1)).

Note that in this notation, a "view" is not something that is more
special than a plain vanilla matrix (0,nrow,1) or vector (0,1).

IMO this idea is easy to implement (and optimize to death, with
compiler macros) in Lisp.  I see no need for special glue to GSL's
views, which are less general (matrices only, specialized view types
etc) and reflect the limitations of C.  GSL is a great library, but I
don't think we should take pains to implement glue to stuff that is
much easier and faster to write in Lisp.

What do you gain?  A general affine map for indexing you can use for
multidimensional arrays and any kind of view you can imagine.

What do you lose?  You can no longer use aref and array functions.
That is actually a big loss, that's why I didn't do it, also, I found
displaced arrays general enough.  But the above is easy to do, I have
some code lying around if you are interested.  The advantage is that
everything is done in Lisp.

When I wrote FFA, I did it because I decided that for my applications,
putting the data in foreign memory is not worth it.  The idea behind
FFA is that we want to interoperate with foreign libraries, but still
want to do most of our calculations in Lisp, so setting up a data type
that resides in foreign memory is unwarranted (you lose a lot of nice
stuff that way, incl painless memory management).

Also understand that copying is very cheap, cheaper than most people
realize.  So if you just want a submatrix from a matrix, it is not
that expensive to simply copy it into another matrix.  Do you have
some application where you think views would be of huge importance?

My 2 cents,

Tamas


On Wed, Apr 09, 2008 at 07:19:00PM -0400, Liam Healy wrote:
> Zach,
> 
> To tell you the truth, I never looked closely enough at views to
> figure what it would take to make them work.  It may be trivial, or it
> may be impossible.
> 
> >From what you say, it sounds like it might be possible to write an
> implementation-specific layer that would support views, for some
> implementation.  One thing to keep in mind is that I am rewriting what
> I call "data" (matrix, vectors, etc.) to use Tamas Papp's
> foreign-friendly arrays.  On SBCL, this will mean that the CL array
> and the C array will be one and the same (no copying).   So it may be
> worth holding off implementing any plan for enabling views, though
> certainly researching it and thinking about it is worthwhile.
> 
> Liam
> 
> 
> On Wed, Apr 9, 2008 at 5:45 PM, Zach <elzacho at gmail.com> wrote:
> > Liam et. al.,
> >
> > OK, tell me if I am wrong.  Matrix/vector views are not supported in GSLL.
> > This is due to the fact that we need to recieve a structure by value.  This
> > cannot be done due to a weakness of the underlying CFFI.  Which in turn
> > (according to their mailing list) is actually a weakness of most Lisp
> > implementations.  In order to get this to work there is some C language glue
> > that needs to be written.  Is this a correct assessment of the situation?
> >
> > Zach
> >
> >
> > _______________________________________________
> >  Gsll-devel mailing list
> >  Gsll-devel at common-lisp.net
> >  http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
> >
> >
> _______________________________________________
> Gsll-devel mailing list
> Gsll-devel at common-lisp.net
> http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel