efficient fixed size vector/matrix represenation+operations

Discussion of Common Lisp
Post Reply
Sternmull
Posts: 2
Joined: Sun Feb 07, 2010 5:03 am

efficient fixed size vector/matrix represenation+operations

Post by Sternmull » Sun Feb 07, 2010 6:32 am

Hello,

at first I have to say that i am programming in C++ for about 10 years and are now trying to do my first steps with Lisp. I also use Python for a lot of stuff, so dynamic typing and some other non-C++-like concepts of Lisp are not completely new to me. I use SBCL with Emacs + Slime and use Practical Common Lisp as my primary guide to learn Lisp.

As my first toy projects i want to write small OpenGL programs. This way i can use an API i am already familiar with and will have some visible results that hopefully keep up my motivation. So far i have a small program that uses lispbuilder-sdl to show an OpenGL window. All runs fine.

But now to my problem: To do some 3D-stuff i need at least 3D-vectors, matrices and quaternions. All have the same size and the same type of elements (usually single-float). Sometimes 2D and 4D variants are also useful, maybe even with other element types. There will be a lot of instances of this data structures either as parts of other lightweight structures (for example to represent position and extend of a bounding box in an octree) or in arrays to represent geometry. Also there are operations like dotproduct, crossproduct and transformations that should be as efficient as possible. An operation does the same thing regardless of dimension and type of the used operands (the steps to calculate a dot product are always the same, no matter what dimension or element-type the operands have). Now i wonder how to express this with Lisp.

I actually have two questions:
1. How do i efficiently represent the vectors, matrices etc. ? Internally they should be stored as "C-arrays" in memory so i can pass vertex arrays to OpenGL without any conversion.
2. How do i implement the operations to be "generic" (for example one name "dot-product" that implements a dot product for all vector types)?

For the first problem I looked at "defstruct" and "vector". I would expect that "defstruct" gives me the compact memory representation that i aspire. Unfortunately i dont know if i can access structure-elements by index. The "vector" on the other hand allows access by index but i suspect it to also store the length even in situations where i know it will always be a fixed number. This way the length-informations will pollute anything that could be a vertex array.

I think the second problem could easily be implemented with CLOS. But that would conflict with the first problem: I dont want the vertices to have any runtime type information attached to them, i want "pure" data. Also I would expect that the overhead of CLOS would be pretty high when it is used for every single vector operation (the operations are simple and called very frequently).

In C++ the first problem is trivially solved by putting elements in a class/struct as a member that is a fixed size array. The second problem is also easy to solve: The operations can be implemented as templates. For every call of such an operation the correct implementation is chosen at compiletime. See for example GMTL.

I see that in Lisp I could write macros that implement the variants of all the different operations. But then i still have to call the right variant explicitly: Something like (dot3f a b) for 3D single-float vectors, dot3d for double-float, dot2f for 2D and so on. I would like to be less explicit. What i want to say is (dot a b) and Lisp figuring out at compiletime what specific function should be used.

I understand that this requires something like static type information. But it may be possible to implement some macros that extract type information out of "declare" expressions and insert the right function (and maybe instantiating the function out of some kind of template if necessary). I also found this other thread that is about static typing.

While i am interested to find a solution to my problem it would also be nice if someone could point me out a 3D-math library that fits my needs. So far all math libraries i found for Lisp offered more scientific functionality than the lightweight 3D stuff i need. Every 3D-graphics code i saw so far used the standard vector.

Btw. this is not intended to be a C++ vs. Lisp topic! I mentioned the C++ way to solve my problem only to clarify my intention.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: efficient fixed size vector/matrix represenation+operations

Post by gugamilare » Sun Feb 07, 2010 7:45 am

If you want to easily pass the arrays to C functions without any conversion, I know only about two possible choices
  • Stick to CMUCL or SBCL. You then should use arrays with a declared type, e.g. like this:

    Code: Select all

    (declare (type (array (signed-byte 32) *) my-array))
    (declare (type (array fixnum *) my-array))
    These implementation are able to pass arrays to C functions without "translation".
  • Implement arrays on top of CFFI, manually allocating an space for your data and manipulating it, like you would do in C.
The first option might be a problem if you use callbacks. If you create a Lisp callback (i.e. a Lisp function which is passed as a pointer to a C function) and if the garbage collector is called during the execution of the callback, the arrays might be reallocated and C would not know about it, probably causing data corruption or segmentation faults. More about it, take a look at this part of SBCL's manual.

I would stick to the second option. It is not hard to create a small API to handle those arrays and abstract away boring details like allocating and freeing, not to mention they are safe with respect to garbage collection. You would have to create a small wrapper structure or class and store the array size, perhaps its type and the array itself. Then, for every object you create, you would set a finalizer for it (i.e. a function intended to be run after the object has been garbage collected) to free the space allocated by the array. And then implement translate-to-foreign and translate-from-foreign methods to let you pass those structures to C functions, and expand-to-foreign and expand-from-foreign to optimize away the call to the first two generic functions.

CFFI's manual explain how to do those stuff I mentioned.

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

Re: efficient fixed size vector/matrix represenation+operations

Post by dmitry_vk » Sun Feb 07, 2010 7:52 am

I understand that this requires something like static type information. But it may be possible to implement some macros that extract type information out of "declare" expressions and insert the right function
Some implementations (e.g., SBCL) allow macros to query lexical environment for e.g. type declarations. I think that the right way would be have a function for the generic case that would dispatch to functions for specific types. Then the compiler-macro could be used to optimize the call to the function: as the compiler macro gets the lexical environment, it can check type declarations for variables that are used.
In SBCL, struct and array both have per-instance overhead.

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

Re: efficient fixed size vector/matrix represenation+operations

Post by dmitry_vk » Sun Feb 07, 2010 7:54 am

gugamilare wrote: I would stick to the second option. It is not hard to create a small API to handle those arrays and abstract away boring details like allocating and freeing, not to mention they are safe with respect to garbage collection. You would have to create a small wrapper structure or class and store the array size, perhaps its type and the array itself. Then, for every object you create, you would set a finalizer for it (i.e. a function intended to be run after the object has been garbage collected) to free the space allocated by the array. And then implement translate-to-foreign and translate-from-foreign methods to let you pass those structures to C functions, and expand-to-foreign and expand-from-foreign to optimize away the call to the first two generic functions.
There's a lisp-ffa (foreign-friendly arrays) project that implements such an API. On SBCL, this API has zero overhead: it can pass lisp vector (with specified type) directly to foreign code.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: efficient fixed size vector/matrix represenation+operations

Post by gugamilare » Sun Feb 07, 2010 8:20 am

dmitry_vk wrote:There's a lisp-ffa (foreign-friendly arrays) project that implements such an API. On SBCL, this API has zero overhead: it can pass lisp vector (with specified type) directly to foreign code.
It is nice to know about it :) Just to make things easier, here is its Cliki page. But it seems to rather implement the first approach, not the second:
using native CL arrays and either copying them to/from foreign memory on demand, or taking advantage of implementation-specific features (eg pinning arrays) for direct access where possible
And:
Currently, only SBCL-specific code is provided, for all other implementations, the macro defaults to copying/conversion.
So, the concerns regarding callbacks still exist. But you are safe if you do one of the workarounds suggested by SBCL's manual, or if you do not use callbacks at all.

A library which implements the second approach would be fnv, available for download here.

good project would be either fix fnv, implement a similar library, or help FFA to support more implementations.

Sternmull
Posts: 2
Joined: Sun Feb 07, 2010 5:03 am

Re: efficient fixed size vector/matrix represenation+operations

Post by Sternmull » Sun Feb 07, 2010 11:14 am

Thank you for your fast and helpful replies!

Unfortunately at the moment i feel more confused than before :) Maybe i was a bit naive by me to assume that a garbage collected runtime gives me the easy direct control over memory details that i am used to when writing C++ code. And maybe the optimal use of C-APIs is not the best starting point for a Lisp newbie like me.

I will learn a bit more about the basic Lisp datatypes before i start to optimize the code. Using CFFI to manage vertex arrays sounds ok. But at the moment i fail to declare my vectors a way that allows full optimization (SBCL complains about type mismatches). So i conclude that i am simply far from qualified to do more advanced stuff. I looked at some raytracing stuff and they all used the ordinary vector type. I will stick with that until i have a better understanding of Lisp. For the first steps the performance is not so important anyway.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: efficient fixed size vector/matrix represenation+operations

Post by nuntius » Sun Feb 07, 2010 8:46 pm

BTW, here are a few bindings to OpenGL. The main difference is whether to use GLFW, GLUT, or SDL to open the window; but there are stylistic differences as well.
http://www.cliki.net/CL-GLFW
http://common-lisp.net/project/cl-opengl/
http://cl-sdl.sourceforge.net/

Destruct1
Posts: 20
Joined: Wed Jan 20, 2010 1:40 am

Re: efficient fixed size vector/matrix represenation+operations

Post by Destruct1 » Mon Feb 08, 2010 2:27 am

Sternmull wrote:Btw. this is not intended to be a C++ vs. Lisp topic!
Thats not gonna happen. :D

Here is the point: You learn Lisp by recreating C programms, caring about C problems, using the C interface and the C libraries
While I understand the reason I think it is wrong to learn Lisp by putting it on top of C. If you try to solve problems the C way and dont want to compromise on the efficiency that is not going to work very well. Instead I would try to learn Lisp with examples where Lisp is strong like high-level math/AI and basically everything not low-level (and probably not web-based).

First a rant: Of course C is good when you need to sqeeze every bit of efficiency out of your code. Of course C is good when you do pure numbercrunching like calculating the dot product of 3000 vectors by looping a pointer over a superdefined array, without security, without runtime checking.
But here is the point: If your program wastes 1 byte 1000 times and is running 24 hours on 1million computers, you just wasted 1GB of permanent memory. 1GB permanent RAM costs you 30€. If a programmer tries to find a bug which is introduced by C or if he writes totally pointless code just to get to the real deal, it will just you 10€ at least. And that is for a PHP script kiddie or in a thirdworld country.
And here is the list of specific C problems you will never have in Lisp:
pointer arithmetic;
new/delete memory allocation and the resulting pointless code, memory leaks;
silent array overflows;
silent number overflow;
the necessity to start every datatype from scratch and have no higher order datatype
pointer who point to something already freed;
checking if the memeory allocation suceeded;
the need to write a function for exactly (int int) input or exactly (int long) input or the necessaties to cast to that input;
the unability to write a function for a generic higher datatype like lists, instead C always expects mystruct or a very narrow input;
and of course you must declare the datatypes in a struct/class/whatever which makes it impossible to share data beyond simple types

Now to the constructive part:
I think arrays of the desired length (3 for 3D vectors, 3x3 for matrices etc.) are a good choice to store data. You can declare the types of these arrays and get a good memory efficiency. I wouldnt go into static type checking with Lisp. Because you basically have infinite computing power for single vectors I would just use a length method for runtime-type checking. If you need to compute LOTS of vector operations, you can write functions which only compute the length for the first element in a vector and use this typeinformation for the rest.


For example (everythin untested):
You create a basic function which takes an extra argument dimension:
(defun basicdotproduct (inpa inpb dimension)
(let ((sum 0))
(dotimes (e dimension)
;refernce array and calculate sum
)));return sum

Then you create a function which takes two arrays/lists of vectors, computes the length of one subvector and processes the rest without length checking.
(defun pipelinedot (firstlist secondlist)
(let ((dim (length (first firstlist))))
(mapcar #'(lambda (x y) (basicdotproduct x y dim)) firstlist secondlist)

Of course lists are 2 pointers which are 4 bytes each on most machines, so you might need to replace the lists with arrays.

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

Re: efficient fixed size vector/matrix represenation+operations

Post by dmitry_vk » Mon Feb 08, 2010 4:50 am

I would also add a point that high-performance numerical computational systems like matlab and octave also store matrices dimensions and generally have overhead for every number. But their performance is very good and they may be used for very large tasks. I think that you are looking into wrong direction for possible problems.

Post Reply