Hello all, Last year I submitted a proposal for Boost.Matrix as a GSoC project, that provoked quite a bit discussion. Considering the fact that it wasn't unanimously rejected, and that a few things have changed since then (Boost.Geometry acceptance) as did my skills, I'd like to take the liberty of resubmitting my proposal to the list, with a request for comments. The proposal follows: == Boost.Matrix == uBLAS is Boost's general linear algebra library, and it is a fine library indeed. However, in some cases it's design decisions, while quite rational for the general use case, are restrictive. This proposal is about a new library that would address some of these issues in the specific situation of vector and matrix operations on fixed sized structures. Suggested is a new library boost::matrix. The library would introduce a single container class that allows representation of fixed size vectors and matrices, and their respective standard operations. The library would define the following template template<typename T, std::size_t Rows, std::size_t Cols, class Traits> matrix and standard operations on it. The class would make heavy use of template specialization to allow efficient vector operations (matrices with size 1xN ), and provide efficient operations for the common sizes (2-4). The class will provide the interface of STL containers with the exact concept depending on the Traits used. Care will be taken to allow transparent usage within STL and other boost libraries. In general, this library would be similary scoped as Boost.Quaternion. Recently a new library has been accepted into boost -- Geometry. As the library is deeply about matrices and vectors, and has much in common with this proposal, I'd like to take a deep focus on providing maximum interopeability between Geometry and Matrix. == Rationale == Boost.Matrix aims to be for uBLAS, what Boost.Array is for vectors - a fixed size version to remove the overhead. The need is however greater, because while uBLAS provides a template for a fixed-sized version of it's arrays, the template is just a cover for the original uBLAS matrices. While the performance is comparable, the size includes a unnecessary field size. In cases that make heavy use of fixed sized matrices and vectors ( like real-time computer graphics ), such a tradeoff is unacceptable - due to increased memory consumption as well as effective vectorized math operations, and alignment of structures passed ( a single 4D vector should effectively fit a 128 bit register, and a single 128 bit move operation ). Also, knowing the dimensions of a matrix/vector at compile time, allows for a more efficient operation implementation, both from the programmers side ( better algorithms ), as well as from the compilers side (optimization). Finally, the uBLAS introduces a lot of unneccessary bloat for users wanting only a 2,3,4 vector and 3,4 matrix classes. == Primary deliverables == Boost.Matrix library, with the following features: * a boost::matrix base container class for 2-dimensional matrices, with the proper behavious and semantics of a container, written following the boost coding guidelines, and with full portability in mind * specializations for efficient vector (1xN matrix) handling * operators for readable but efficient vector/matrix math * operator specializations for matrices and vectors of the most common size (2-4) for most efficient implementation * efficient implementation of interoperability of Boost.Matrix with other boost libraries (uBLAS, Quaternion and upcoming Boost.Geometry in particular) == Secondary deliverables == * performance test suite, for testing optimizations * unit tests for the whole library providing full operation coverage and code-coverage * documentation for the whole library in the BoostBook format, as well as doxygen markup for all the code == Bonus deliverables == ( if time allows these will be delivered during program timeline, if not, they will be implemented afterwards ) * performance tests on different compilers/architectures, further optimizations * support for further boost libraries ( Boost.Assign, sandbox libraries, etc. ) == Design issues == * compile-time concept checking to only generare functions that make sense for the given type ( no floating point operations for integral types ) * usage of template expressions to unroll the operations at compile-time to allow the compiler to optimize them ( needs to be tested case by case with the performance test suite ) and elimination temporaries * care to keep most useful memory alignment ( to provide ease of use with direct usage in architecture dependent pipelines ) -- possibly an alignment trait * design with architecture-dependent optimizations in mind ( ease of expansion ) * keeping all the standard boost practices, including workarounds for non-conformant compilers == Research == Several existing implementations were studied and evaluated before the repeated submission of this idea. I intend to encompass most of the good things I found in the following implementations into a small but very useful library: * Boost.uBLAS (obviously) * Eigen - http://eigen.tuxfamily.org/ (heavyweight) * CGAL - http://www.cgal.org/ (license issues) * Matrix Template Library - http://osl.iu.edu/research/mtl/ (similar issues to uBLAS) * VCGLib - http://vcg.sourceforge.net/ (GPL) * nVidia's vector and matrix classes (found in nVidia examples) -- regards, Kornel Kisielewicz http://chaosforge.org/
Last year I submitted a proposal for Boost.Matrix as a GSoC project, that provoked quite a bit discussion. Considering the fact that it wasn't unanimously rejected, and that a few things have changed since then (Boost.Geometry acceptance) as did my skills, I'd like to take the liberty of resubmitting my proposal to the list, with a request for comments. The proposal follows:
Hi Kornel, I think this is a fine idea for a SoC project. It's certainly much more focused than the patterns proposal from your previous post :) I would encourage you to develop this proposal ahead of the other. This already seems very clear and would probably make a good submission as is. That said, this will probably (hopefully) generate a lot of feedback again this year. I realize that the proposal will not satisfy everybody's needs, nor will it compete with some of the more mature LA libraries out there, but I think it would provide a nice starting point for a larger, more feature rich matrix library. Andrew Sutton andrew.n.sutton@gmail.com
Kornel Kisielewicz wrote:
== Research ==
Several existing implementations were studied and evaluated before the repeated submission of this idea. I intend to encompass most of the good things I found in the following implementations into a small but very useful library:
* Boost.uBLAS (obviously) * Eigen - http://eigen.tuxfamily.org/ (heavyweight) * CGAL - http://www.cgal.org/ (license issues) * Matrix Template Library - http://osl.iu.edu/research/mtl/ (similar issues to uBLAS) * VCGLib - http://vcg.sourceforge.net/ (GPL) * nVidia's vector and matrix classes (found in nVidia examples)
The last entry in <http://www.boost.org/community/review_schedule.html> is Static Size Linear Algebra Emil Dotchevski http://www.revergestudios.com/boost-la/ Needed - Regards, Thomas
* Boost.uBLAS (obviously) * Eigen - http://eigen.tuxfamily.org/ (heavyweight) * CGAL - http://www.cgal.org/ (license issues) * Matrix Template Library - http://osl.iu.edu/research/mtl/ (similar issues to uBLAS) * VCGLib - http://vcg.sourceforge.net/ (GPL) * nVidia's vector and matrix classes (found in nVidia examples)
The last entry in <http://www.boost.org/community/review_schedule.html> is
Static Size Linear Algebra Emil Dotchevski http://www.revergestudios.com/boost-la/ Needed
Ah... good catch. Your proposal should definitely address how you plan to adapt your matrix class(es) to the Boost.LA library in the review queue. Fortunately, there doesn't seem to be much overlap in functionality. Andrew Sutton andrew.n.sutton@gmail.com
On Tue, Apr 6, 2010 at 4:08 PM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
* Boost.uBLAS (obviously) * Eigen - http://eigen.tuxfamily.org/ (heavyweight) * CGAL - http://www.cgal.org/ (license issues) * Matrix Template Library - http://osl.iu.edu/research/mtl/ (similar issues to uBLAS) * VCGLib - http://vcg.sourceforge.net/ (GPL) * nVidia's vector and matrix classes (found in nVidia examples)
The last entry in <http://www.boost.org/community/review_schedule.html> is
Static Size Linear Algebra Emil Dotchevski http://www.revergestudios.com/boost-la/ Needed
Ah... good catch. Your proposal should definitely address how you plan to adapt your matrix class(es) to the Boost.LA library in the review queue. Fortunately, there doesn't seem to be much overlap in functionality.
Actually there is almost exact overlap looking at the documentation: http://www.revergestudios.com/boost-la/matrix_and_vector_types.html This is... kind of sad, considering that the same person mercilessly bashed my proposal as useless last year... -- regards, Kornel Kisielewicz
Kornel Kisielewicz wrote:
On Tue, Apr 6, 2010 at 4:08 PM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
* Boost.uBLAS (obviously) * Eigen - http://eigen.tuxfamily.org/ (heavyweight) * CGAL - http://www.cgal.org/ (license issues) * Matrix Template Library - http://osl.iu.edu/research/mtl/ (similar issues to uBLAS) * VCGLib - http://vcg.sourceforge.net/ (GPL) * nVidia's vector and matrix classes (found in nVidia examples)
The last entry in <http://www.boost.org/community/review_schedule.html> is
Static Size Linear Algebra Emil Dotchevski http://www.revergestudios.com/boost-la/ Needed
Ah... good catch. Your proposal should definitely address how you plan to adapt your matrix class(es) to the Boost.LA library in the review queue. Fortunately, there doesn't seem to be much overlap in functionality.
Actually there is almost exact overlap looking at the documentation: http://www.revergestudios.com/boost-la/matrix_and_vector_types.html
This is... kind of sad, considering that the same person mercilessly bashed my proposal as useless last year...
What you mean exactly? Would you have any references to this bashing handy? Best regards, -- Mateusz Loskot, http://mateusz.loskot.net
Andrew Sutton wrote:
The last entry in <http://www.boost.org/community/review_schedule.html> is
Static Size Linear Algebra Emil Dotchevski http://www.revergestudios.com/boost-la/ Needed
Ah... good catch. Your proposal should definitely address how you plan to adapt your matrix class(es) to the Boost.LA library in the review queue. Fortunately, there doesn't seem to be much overlap in functionality.
How is a static-sized matrix class not a subset of a static size linear algebra library? Even if it is designed like boost.geometry with non-intrusive traits for interoperability, the library still provides classes for matrices and vectors. I doubt there is anything to gain by adapting another matrix class to it. Due to the genericity of its design, the library doesn't seem to support SIMD. This might lead to quite some heated discussion during its review... (hey, shouldn't the compiler take care of that? ;))
Ah... good catch. Your proposal should definitely address how you plan to adapt your matrix class(es) to the Boost.LA library in the review queue. Fortunately, there doesn't seem to be much overlap in functionality.
How is a static-sized matrix class not a subset of a static size linear algebra library?
They are -- in fact, the library provides mat and vec classes that trivially wrap C-arrays (but do so in a not particularly thorough way). I actually missed those in my 1st glance over of the docs. Obviously there would be overlap if the proposed matrix data structure was wrapping static arrays. If the underlying matrix data was dynamically allocated, you now have a very different (i.e., moveable) matrix data structure. I doubt there is anything to gain by adapting another matrix class to it.
I think that there is value in this proposal.
Due to the genericity of its design, the library doesn't seem to support SIMD. This might lead to quite some heated discussion during its review... (hey, shouldn't the compiler take care of that? ;))
Andrew Sutton andrew.n.sutton@gmail.com
On Tue, Apr 6, 2010 at 4:28 PM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
Ah... good catch. Your proposal should definitely address how you plan to adapt your matrix class(es) to the Boost.LA library in the review queue. Fortunately, there doesn't seem to be much overlap in functionality.
How is a static-sized matrix class not a subset of a static size linear algebra library?
They are -- in fact, the library provides mat and vec classes that trivially wrap C-arrays (but do so in a not particularly thorough way). I actually missed those in my 1st glance over of the docs. Obviously there would be overlap if the proposed matrix data structure was wrapping static arrays. If the underlying matrix data was dynamically allocated, you now have a very different (i.e., moveable) matrix data structure.
Actually I'm forced to retract my proposal. The whole idea was to wrap static sized data in matrix and vector adapters, to allow efficient usage in computer graphics applications (e.g. games) for allowing ease of optimization and things like SIMD. In cases of dynamically allocated arrays, there's no reason not to use uBLAS, for the gain in simplicity is not worth a new library. However, this idea was violently rejected by some last year, including by Emil Dotchevski (author of the submitted Boost.LA) -- up to the point that he wrote a blog post about it : http://www.revergestudios.com/reblog/index.php?n=ReCode.MathLibrary ( ref http://thread.gmane.org/gmane.comp.lib.boost.devel/187988, http://article.gmane.org/gmane.comp.lib.boost.devel/187963 and http://article.gmane.org/gmane.comp.lib.boost.devel/188155 ) However, later, after GSoC ended (with my proposal obviously rejected) he changed his mind and implemented a library that basically implements almost every single statement of my proposal: http://www.revergestudios.com/reblog/index.php?n=ReCode.BoostLA Rounding things up, the Boost.Matrix proposal is no longer valid, as it is now known as Boost.LA and already implemented (I don't see anything else I'd like to see in Boost.LA, cause all the things I wrote about in my proposal in 2009 are already taken care of). The question of whether it's nice or not, I leave up to the reader, I'm just happy that my proposal... inspired the library to finally be taken care of. -- regards, Kornel Kisielewicz http://chaosforge.org/
On Tue, Apr 6, 2010 at 7:55 AM, Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:
However, this idea was violently rejected by some last year, including by Emil Dotchevski (author of the submitted Boost.LA) -- up to the point that he wrote a blog post about it : http://www.revergestudios.com/reblog/index.php?n=ReCode.MathLibrary
Yes, that discussion did prompt my blog post, though it does not critique or even mention your proposal, it critiques the game development community. I do not think that that community will ever use a Boost matrix/vector lib; they won't even use the matrix/vector library they wrote last year. :) If you read my proposal you'll see that I'm using a radically different approach to yours. Both proposals have merit. One way to move forward is to have the two libraries reviewed, the end result might be that none is accepted, only one is, or both are. Alternatively, we can work together to merge the two proposals, I am not against that. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
How is a static-sized matrix class not a subset of a static size linear algebra library?
They are -- in fact, the library provides mat and vec classes that trivially wrap C-arrays (but do so in a not particularly thorough way). I actually missed those in my 1st glance over of the docs. Obviously there would be overlap if the proposed matrix data structure was wrapping static arrays. If the underlying matrix data was dynamically allocated, you now have a very different (i.e., moveable) matrix data structure.
Actually I'm forced to retract my proposal. The whole idea was to wrap static sized data in matrix and vector adapters, to allow efficient usage in computer graphics applications (e.g. games) for allowing ease of optimization and things like SIMD.
That's too bad. I was hoping you would be able to adapt the proposal to implement a dynamically allocated matrix. I should hope you can still take advantage of SIMD optimizations with dynamically allocated memory. Plus, move-friendly data structures are (or can be) a Good Thing. I stand by my statement that there's value in that effort. It may be unlikely to see review for another year or so, but it shouldn't invalidate the work. Andrew Sutton andrew.n.sutton@gmail.com
Mathias Gaunard wrote:
Due to the genericity of its design, the library doesn't seem to support SIMD. This might lead to quite some heated discussion during its review... (hey, shouldn't the compiler take care of that? ;))
dum dum i was about to say that. Seems I'll have to unveil my talk at boost'con in advance then ...
----- Original Message ----- From: "Kornel Kisielewicz" <kornel.kisielewicz@gmail.com> To: <boost@lists.boost.org> Sent: Tuesday, April 06, 2010 1:14 PM Subject: [boost] [GSoC] Boost.Matrix RFC
== Primary deliverables ==
Boost.Matrix library, with the following features:
* a boost::matrix base container class for 2-dimensional matrices, with the proper behavious and semantics of a container, written following the boost coding guidelines, and with full portability in mind * specializations for efficient vector (1xN matrix) handling * operators for readable but efficient vector/matrix math * operator specializations for matrices and vectors of the most common size (2-4) for most efficient implementation * efficient implementation of interoperability of Boost.Matrix with other boost libraries (uBLAS, Quaternion and upcoming Boost.Geometry in particular)
Hi, I like the idea of an alternative proposal to Boost.LA. Please, could you clarify which kind of matrix and which operations do you intend to provide? Best, _____________________ Vicente Juan Botet Escribá http://viboes.blogspot.com/
On Mon, Apr 12, 2010 at 1:04 AM, vicente.botet <vicente.botet@wanadoo.fr> wrote:
== Primary deliverables ==
Boost.Matrix library, with the following features:
* a boost::matrix base container class for 2-dimensional matrices, with the proper behavious and semantics of a container, written following the boost coding guidelines, and with full portability in mind * specializations for efficient vector (1xN matrix) handling * operators for readable but efficient vector/matrix math * operator specializations for matrices and vectors of the most common size (2-4) for most efficient implementation * efficient implementation of interoperability of Boost.Matrix with other boost libraries (uBLAS, Quaternion and upcoming Boost.Geometry in particular)
Hi,
I like the idea of an alternative proposal to Boost.LA. Please, could you clarify which kind of matrix and which operations do you intend to provide?
Sorry for the late reply, Following the idea of a library geared for real-time operation the library would be focused on dense matrices, supporting all standard arithmetic operations for both vector and matrix as well as between them, common vector operations (dot, length, lengthsq, norm, cross, projection, etc...), common matrix operations (transposition, determinant, adjoint, inverse, etc) as well as interoperability with the quaternion library. If need be, this list could be expanded. -- regards, Kornel Kisielewicz
Following the idea of a library geared for real-time operation the library would be focused on dense matrices, supporting all standard arithmetic operations for both vector and matrix as well as between them, common vector operations (dot, length, lengthsq, norm, cross, projection, etc...), common matrix operations (transposition, determinant, adjoint, inverse, etc) as well as interoperability with the quaternion library. If need be, this list could be expanded.
For interorperabiltiy, better have interoperabiltiy with any UDT than just quaternion. w/r to other function implementation, any SIMD love ? -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
On Tue, Apr 13, 2010 at 9:47 PM, joel falcou <joel.falcou@lri.fr> wrote:
Following the idea of a library geared for real-time operation the library would be focused on dense matrices, supporting all standard arithmetic operations for both vector and matrix as well as between them, common vector operations (dot, length, lengthsq, norm, cross, projection, etc...), common matrix operations (transposition, determinant, adjoint, inverse, etc) as well as interoperability with the quaternion library. If need be, this list could be expanded.
For interorperabiltiy, better have interoperabiltiy with any UDT than just quaternion.
Interoperability with uBLAS and any qualified boost library (e.g. geometry) is one of the top priorities.
w/r to other function implementation, any SIMD love ?
SIMD would be planned for, but full support is probably out of scope for a GSoC project, and I'd have to add it later. -- regards, Kornel Kisielewicz
On Tue, Apr 13, 2010 at 12:40 PM, Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:
... as well as interoperability with the quaternion library.
In my opinion interoperability shouldn't target a particular library, and instead should be based on a concepts-style definition of all operations. Since C++ doesn't and AFAIK won't for the foreseeable future have concepts, the only option for such interoperability is to use type traits and boost::enable_if, so users can easily integrate other libraries' types and their own custom types. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
participants (9)
-
Andrew Sutton -
Emil Dotchevski -
joel falcou -
Joel Falcou
-
Kornel Kisielewicz -
Mateusz Loskot -
Mathias Gaunard -
Thomas Klimpel -
vicente.botet