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
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@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@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
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.
Yeah, I now believe my suspicions to be correct, at least as of a year and half ago. Maybe there have been some advances as CLISP seems to support the needed feature and I'd bet the C friendly ECL and GCL both do as well, still no idea on SBCL.
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).
Hmmm... that sounds good, still not sure how Tamas' FFAs would work. I was preparing to suggest the *other* route that Tamas mentions on his page, basically using the GSL data structures thinly wrapped in a Lisp object (to tie it into the GC). I guess both have their pros and cons.
BTW, I have one question, purely out of curiosity. Even if you use an FFA, GSL is going to expect data in the format the GSL developers designed, e.g.:
00 01 02 03 XX XX XX XX 10 11 12 13 XX XX XX XX 20 21 22 23 XX XX XX XX
Which means that either the Lisp array will have extra junk to carry around, and hence new matrix operations will need to be defined, or some C side trickery must be performed to translate it, which is what we are trying to avoid, right? How do you deal with this (or plan to)?
Best, Zach
On Wed, Apr 9, 2008 at 5:45 PM, Zach elzacho@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@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
On Wed, Apr 9, 2008 at 10:13 PM, Zach elzacho@gmail.com wrote:
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.
Yeah, I now believe my suspicions to be correct, at least as of a year and half ago. Maybe there have been some advances as CLISP seems to support the needed feature and I'd bet the C friendly ECL and GCL both do as well, still no idea on SBCL.
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).
Hmmm... that sounds good, still not sure how Tamas' FFAs would work. I was preparing to suggest the *other* route that Tamas mentions on his page, basically using the GSL data structures thinly wrapped in a Lisp object (to tie it into the GC). I guess both have their pros and cons.
I'm not sure what that is, I guess I'll have to re-read his page. I do remember him mentioning another approach used by rif for blapack, and that is don't-copy-unless-necessary. I think my design will be the best of both worlds: on SBCL it will use the native array, but the usage is such that on non-SBCL platforms, there won't be any copying unless necessary. So chained foreign calculations will stay on the foreign side. This will be much like it is now with the #'cl-invalidate function that merely marks the CL copy to be bad but doesn't copy it back until #'data requests the data on the CL side.
BTW, I have one question, purely out of curiosity. Even if you use an FFA, GSL is going to expect data in the format the GSL developers designed, e.g.: 00 01 02 03 XX XX XX XX 10 11 12 13 XX XX XX XX 20 21 22 23 XX XX XX XX Which means that either the Lisp array will have extra junk to carry around, and hence new matrix operations will need to be defined, or some C side trickery must be performed to translate it, which is what we are trying to avoid, right? How do you deal with this (or plan to)?
I use the necessary GSL structures currently (see e.g. gsl-vector-c). These have a data pointer. Currently, that points to space allocated by GSL through the generic function #'alloc (which ultimately calls something like gsl_vector_alloc). The use of the GSL structure will continue, but FFA will assign the pointer to the C array. If using SBCL, that pointer will actually be to the Lisp data but it will work as the C array due to the foresight of the SBCL designers.
(I'm assuming by "extra junk" here you mean the parts of the GSL structs that aren't the array itself.)
Liam
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@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@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
Gsll-devel mailing list Gsll-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
Liam, Tamas,
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.
This afternoon I spent a bit writing GSL's matrix data types in terms of Lisp functions and data. Agreed, it is much easier/faster/more natural to do this 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.
This would be very handy.
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,
One would hope that this isn't too big of a loss. Different data types have different interfaces right. Are you referring to the inability to use other peoples tools?
also, I found
displaced arrays general enough.
You mean in conjunction with the affine parameters? You cannot encode the affine map in terms of :displaced-to and :displaced-index-offset, right?
But the above is easy to do, I have
some code lying around if you are interested.
I am interested, could you post it?
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).
Okay, so I guess I get it. Given the data structure the GSL docs describe, even with FFAs we cannot use AREF to access the data in the array. This is because we may be looking at a submatrix. However, since matrix views are perhaps the only time that a GSL function returns a submatrix (and we don't use that), we are always dealing with full matrices (tda = width). Thus nothing to worry about and we can use AREF.
Basically we are porting the functions like gsl_matrix_alloc to the Lisp side. Of course this means that we are sensitive to changes in the underlying GSL data type, even when C programs are not. You are right Liam, this does seem like a good compromise.
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?
Of course this all came about from my naive attempt to create a GSL binding without understanding what is happening underneath. Hence there is no application in mind. However, there is something to be said for elegance and fluidity in code. Then again, one must accept that this is out the window when using C.
Thanks, Zach
On Thu, Apr 10, 2008 at 10:46:17PM -0600, Zach wrote:
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,
One would hope that this isn't too big of a loss. Different data types have different interfaces right. Are you referring to the inability to use other peoples tools?
Yes.
You mean in conjunction with the affine parameters? You cannot encode the affine map in terms of :displaced-to and :displaced-index-offset, right?
I am not using the affine indexing code at the moment, I meant that displaced arrays are general enough for my needs.
But the above is easy to do, I have some code lying around if you are interested.
I am interested, could you post it?
I made it available at
http://www.princeton.edu/~tpapp/software/foreign-friendly-array.archived.tar...
Note that the code is not optimized, it was experimental. Quite a few design choices were refined in FFA, so just look at index-mapping.lisp to get the idea, the actual foreign interface code is not that good here.
Generally, I found that thinking a bit about my matrix/array layout always allows me to implement what I want using CL's displaced arrays. When R was my primary language, I found a lot of indexing magic nice, but later realized that it is a pain in the rear end when you try to optimize your applications. Displaced arrays are a compromise, but I found that they are general enough for my needs. For example, with row-major matrices, you can select a submatrix that contains all columns of the original, or with columns dropped from the left, using displaced arrays.
Tamas
On Fri, Apr 11, 2008 at 08:19:03AM -0400, Tamas K Papp wrote:
found that they are general enough for my needs. For example, with row-major matrices, you can select a submatrix that contains all columns of the original, or with columns dropped from the left, using displaced arrays.
I just realized this is incorrect. I meant "all columns, rows dropped from the top and/or the bottom."
Tamas
Tamas,
I like your ideas on general array views, it seems very standard; I think what we're all talking about is array slicing http://en.wikipedia.org/wiki/Array_slicing. I understand and support the desire to take advantage of everything Lisp has to offer, however, I would like to maintain compatibility with GSL and other foreign code to the extent possible where there is an analogous concept implemented, so we can take advantage of their functions (that's the idea behind GSLL after all). It seems to me that FFA should work just fine. Perhaps Zach can confirm that GSL's views work the way I expect in matching your general array views description, then your scheme should map into GSL's views. I think your general array views will give CL access to an underlying "full" array, and GSL's view can be made to match, and FFA can provide the option that the underlying full array is one and the same (on SBCL) or properly copied (everywhere else).
As far as the aref issue goes, I don't see it as a problem. I currently define #'maref which could be used as is, or #'aref could be shadowed out of the CL package if the user desires. You could even do this in CL code written by someone else by putting the shadow in the package definition.
Does this make sense?
Liam
On Fri, Apr 11, 2008 at 10:26:41AM -0400, Liam Healy wrote:
Tamas,
I like your ideas on general array views, it seems very standard; I think what we're all talking about is array slicing http://en.wikipedia.org/wiki/Array_slicing. I understand and support
Liam,
It seems that my idea is more general. With affine maps, you can do index rearrangements (eg reorder rows/columns in reverse order) and lot of other fancy stuff.
the desire to take advantage of everything Lisp has to offer, however, I would like to maintain compatibility with GSL and other foreign code to the extent possible where there is an analogous concept implemented, so we can take advantage of their functions (that's the idea behind GSLL after all). It seems to me that FFA should work just fine. Perhaps Zach can confirm that GSL's views work the way I expect in matching your general array views description, then your scheme should map into GSL's views. I think your general array views will give CL access to an underlying "full" array, and GSL's view can be made to match, and FFA can provide the option that the underlying full array is one and the same (on SBCL) or properly copied (everywhere else).
Currently, the affine maps are not in FFA, but it appears that views in GSL need them. If you need affine maps, let me know, I can whip up something on top of the current FFA (so even with these very general arrays, one could always access the underlying Lisp array if needed, I consider that an advantage).
As far as the aref issue goes, I don't see it as a problem. I currently define #'maref which could be used as is, or #'aref could be shadowed out of the CL package if the user desires. You could even do this in CL code written by someone else by putting the shadow in the package definition.
Indeed you can shadow aref. But code that assumes that some variable is a Lisp array when it is not could get into trouble by other ways, eg using row-major-aref, displacing it, etc. I would prefer if the fancy array type with affine mapping were kept separate.
I understand to desire to provide the whole interface to GSL, but in my opinion, implementing views is not central for Lisp users and leads to more confusion than it is worth. For the moment, I would suggest that we think about views more carefully, write a toy implementation that on top of ffa and try to see what the issues are.
Because Lisp arrays and affine mapping arrays are separate things, what GSLL functions accept and return is also an issue. I could have a matrix that is a Lisp array, or a matrix that is a slice from the middle of another matrix. But to me it is just a matrix, so I would expect to call the same function to deal with it. I think some OO glue could deal with this, but I don't know what functions are involved.
Tamas
On Fri, Apr 11, 2008 at 10:56 AM, Tamas K Papp tpapp@princeton.edu wrote:
On Fri, Apr 11, 2008 at 10:26:41AM -0400, Liam Healy wrote:
Tamas,
I like your ideas on general array views, it seems very standard; I think what we're all talking about is array slicing http://en.wikipedia.org/wiki/Array_slicing. I understand and support
Liam,
It seems that my idea is more general. With affine maps, you can do index rearrangements (eg reorder rows/columns in reverse order) and lot of other fancy stuff.
Ah, OK. That seems like it would indeed be easy to implement, and e.g. makes a transpose trivial.
the desire to take advantage of everything Lisp has to offer, however, I would like to maintain compatibility with GSL and other foreign code to the extent possible where there is an analogous concept implemented, so we can take advantage of their functions (that's the idea behind GSLL after all). It seems to me that FFA should work just fine. Perhaps Zach can confirm that GSL's views work the way I expect in matching your general array views description, then your scheme should map into GSL's views. I think your general array views will give CL access to an underlying "full" array, and GSL's view can be made to match, and FFA can provide the option that the underlying full array is one and the same (on SBCL) or properly copied (everywhere else).
Currently, the affine maps are not in FFA, but it appears that views in GSL need them. If you need affine maps, let me know, I can whip up something on top of the current FFA (so even with these very general arrays, one could always access the underlying Lisp array if needed, I consider that an advantage).
For the type of affine map that GSL views support, would it be straightforward to support those views through FFA? If so, go ahead and whip it up.
As far as the aref issue goes, I don't see it as a problem. I currently define #'maref which could be used as is, or #'aref could be shadowed out of the CL package if the user desires. You could even do this in CL code written by someone else by putting the shadow in the package definition.
Indeed you can shadow aref. But code that assumes that some variable is a Lisp array when it is not could get into trouble by other ways, eg using row-major-aref, displacing it, etc. I would prefer if the fancy array type with affine mapping were kept separate.
OK. I would probably not shadow this symbol, but it can be done for code that avoid the troublesome spots you mention.
I understand to desire to provide the whole interface to GSL, but in my opinion, implementing views is not central for Lisp users and leads to more confusion than it is worth. For the moment, I would suggest that we think about views more carefully, write a toy implementation that on top of ffa and try to see what the issues are.
Right, this was my motivation for skipping over them in the first place. As I said before, I didn't even bother to figure out if they would work. They just seemed unimportant. I think native arrays via SBCL are more important, so that's what I've been focusing on (to the extent that I've had time to work on GSLL).
Because Lisp arrays and affine mapping arrays are separate things, what GSLL functions accept and return is also an issue. I could have a matrix that is a Lisp array, or a matrix that is a slice from the middle of another matrix. But to me it is just a matrix, so I would expect to call the same function to deal with it. I think some OO glue could deal with this, but I don't know what functions are involved.
Tamas
Liam
On Sat, Apr 12, 2008 at 12:18:11PM -0400, Liam Healy wrote:
Currently, the affine maps are not in FFA, but it appears that views in GSL need them. If you need affine maps, let me know, I can whip up something on top of the current FFA (so even with these very general arrays, one could always access the underlying Lisp array if needed, I consider that an advantage).
For the type of affine map that GSL views support, would it be straightforward to support those views through FFA? If so, go ahead and whip it up.
It would be straightforward to support them with a _layer_ over FFA, but not inside FFA (because they would no longer be Lisp arrays).
To be honest, I don't really need views right now, and I have other higher-priority things I am working on, so I am not interested in writing something quick and dirty at the moment.
Right, this was my motivation for skipping over them in the first place. As I said before, I didn't even bother to figure out if they would work. They just seemed unimportant. I think native arrays via SBCL are more important, so that's what I've been focusing on (to the extent that I've had time to work on GSLL).
I agree with your original evaluation - views are not that important, a pain in the ass to integrate, so we should be focusing on other stuff first. I would not mind ignoring views altogether (ie simply not implementing those functions that need views) for the short or medium run.
But I am probably biased. I am using GSLL for the functions/algorithms which are a pain in the ass to implement and debug in any language, so I just want to use versions somebody else wrote. For example, special functions like erf of the gamma function, splines, multivariate optimization, etc.
I think views are used because of optimization, to avoid copying. My experience is that copying is fast and is generally not a hot spot in the programs I write. So I am not interested in implementing something that would lead to a 0.1% speed improvement in my programs, but would entail the loss of the ability to use native Lisp arrays seamlessly and also a huge amount of unnecessary debugging and scaffolding code.
I also understand that other users may need views in GSLL. But before embarking on a project to integrate them, I would like to see some real-world application where the profiling says that views would save a lot (at least 10%) of runtime, and it is not possible to do it by other means (reorganizing data structures, displaced arrays, etc).
Tamas
Tamas,
Agreed completely. Let's put aside views for the day when we're convinced they're worth it. I'm still not sure why they're in GSL; one day I might post this question to the GSL mailing list, and perhaps ask if anybody actually uses them.
Liam
-
Liam Healy -
Tamas K Papp -
Zach