[gsoc] Proposal - Boost.Matrix - DRAFT RFC
Hello all, Following the discussion in the threads: "[boost][gsoc] Interest check for 3d geometry proposal" "[boost] [gsoc] fixed size matrix class?" I post a draft of my proposal with a request for comments. Following the suggestions I decided to scale down the proposal to a polished and production-quality fixed-size Boost.Matrix library, with a big emphasis on correctness and performance. The application follows: Abstract ========= 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 N, std::size_t M, 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. 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 ). Primary deliverables ===================== Boost.Matrix library, with the following features: a) 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 b) specializations for efficient vector (1xN matrix) handling c) operators for readable but efficient vector/matrix math d) operator specializations for matrices and vectors of the most common size (2-4) for most efficient implementation Secondary deliverables ======================= a) performance test suite, for testing optimizations b) unit tests for the whole library providing full operation coverage and code-coverage c) documentation for the whole library in the BoostBook format d) efficient implementation of interoperability of Boost.Matrix with other boost libraries (uBLAS in particular) Bonus deliverables =================== ( if time allows these will be delivered during program timeline, if not, they will be implemented afterwards ) a) optional (compile-time controlled) integration with Boost.SIMD to boost (no pun intended) performance b) performance tests on different compilers/architectures, further optimizations c) support for further boost libraries ( Boost.Assign, sandbox libraries, etc. ) Design issues ============== a) compile-time concept checking to only generare functions that make sense for the given type ( no floating point operations for integral types ) b) usage of templates 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 ) c) usage of expression templates to eliminate temporaries in expressions d) care to keep most useful memory alignment ( to provide ease of use with direct usage in architecture dependent pipelines ) e) design with architecture-dependent optimizations in mind ( ease of expansion ) f) keeping all the standard boost practices, including workarounds for non-conformant compilers Project schedule ================= I plan to do at least weekly progress reports with emphasised design decisions (however well designed in the first phase, reality will probably change the design afterwards at least a little). Progress reports will be directed to the medium established with the mentor (blog, list or only direct communication). This will be my only job once summer starts, and will be treated as such during program coding timeline ( full-time schedule ) -- a week may fall out for a short vacation. Preplanning (April 20 - May 23) -------------------------------- Most of the major design decisions need to be done before the program starts. A end-user interface for the library should be established before the program starts. This will be summed up in a report that will be sent to boost-dev with a request for comments. Phase 1 (Correctness) - (May 24 - June 14) ------------------------------------------- A working basic (non-optimized) implementation, and a full test suite for the basic operations will be created. Goal for this phase is to provide a correct and working implementation. Basic usage document. Phase 2 (Functionality) - (June 14 - July 5) --------------------------------------------- Performance test suite. Compiler-level optimizations ( expression templates, unrolling, etc ). Basic library compatibility ( STL container, uBLAS ). Concept checking. Phase 3 (Optimization) - (July 6 - July 26) -------------------------------------------- Optimizations for vectors, optimizations for specific vector and matrix sizes, optimization checking through performance test suite. Code review for eventual optional architecture optimization ( Boost.SIMD for example ). General optimization of code. Update of documentation. Phase 4 (Finalization and bonuses) - (July 27 - August 10+) ------------------------------------------------------------ Testing on as many architectures as possible ( probably will need some help here ). Fixes. Cleanup of the code where needed. A report of the implementation that again will be posted to boost-dev with a request for comments. Here is included also buffer time if there will be delays in one of the former phases. If not, work will continue with the Bonus deliverables. Brief resume ============= I'm a Computer Science PhD student (2nd year) at the University of Wroclaw (Poland), in the field of Computer Graphics. My interests lie in Game Programming and Design, with a special hunch for Real-time Proceduraly Generated Content. I actively run self-designed courses and lectures at the University ( 3ds MAX course last year, Game Programming lecture this semester, and probably an Advanced C++ course next semester ). Currently, until the end of the semester, I'm working full-time at Tieto corporation, doing a large scale project for Nokia. Previously I worked at a smaller computer game company working on a massive multiplayer game. I've successfully taken part in two last GSoC's creating a Procedural City Generator for the BZFlag project. I consider myself a fairly competent C++ programmer, although I only recently discovered its true strengths ( learned to properly use and write in the style of STL, started reading Boost sources, and got hooked into C++0x ). I'm currently using the language both at work and for my own projects. The latter include a 3D game engine (in progress), and an unannounced space combat/trading game. I am a big fan of roguelike (ASCII) games, and managed to write several roguelikes up to date, the most famous one of them being DoomRL ( http://doom.chaosforge.org ) that did even get mentions in contemporary gaming magazines. Homepage : http://chaosforge.org/ IRC nick : Epyon E-mail : kornel.kisielewicz at gmail.com / epyon at cs.uni.wroc.pl -- regards, Kornel Kisielewicz
On Tue, Mar 31, 2009 at 6:17 PM, Kornel Kisielewicz <kornel.kisielewicz@gmail.com> wrote:
template<typename T, std::size_t N, std::size_t M, class Traits> matrix
I'd suggest using Rows and Cols as arguments of the template instead of M and N.
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 ).
IMO the abstraction provided by a template <typename T,size_t Rows,size_t Cols> class matrix is unnecessary and will only get in the way for computer graphics applications. I've seen several attempts like this at generalizing matrices for game engine use getting scrapped and refactored to a more traditional set of types (not templates) and functions (this doesn't mean that such generalizations are not appropriate in general.) Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
I'd suggest using Rows and Cols as arguments of the template instead of M and N.
I agree.
IMO the abstraction provided by a template <typename T,size_t Rows,size_t Cols> class matrix is unnecessary and will only get in the way for computer graphics applications. I've seen several attempts like this at generalizing matrices for game engine use getting scrapped and refactored to a more traditional set of types (not templates) and functions (this doesn't mean that such generalizations are not appropriate in general.)
And maybe it's not surprising that these attempts failed. It's not that easy to get the generalization exactly right. In a production environment it makes sense to just write some ad-hoc types rather than spend months on the perfect matrix class; but I do expect this sort of care in a Boost library. Anyway I personally could care less about computer graphics, fixed-size matrices are also useful in computer vision, robotics, and no doubt other domains. Kornel's application looks quite good to me; it would be terrific to see some real review-ready code come out of this. -Patrick
On Tue, Mar 31, 2009 at 10:25 PM, Patrick Mihelich <patrick.mihelich@gmail.com> wrote:
IMO the abstraction provided by a template <typename T,size_t Rows,size_t Cols> class matrix is unnecessary and will only get in the way for computer graphics applications. I've seen several attempts like this at generalizing matrices for game engine use getting scrapped and refactored to a more traditional set of types (not templates) and functions (this doesn't mean that such generalizations are not appropriate in general.)
And maybe it's not surprising that these attempts failed. It's not that easy to get the generalization exactly right. In a production environment it makes sense to just write some ad-hoc types rather than spend months on the perfect matrix class;
There is no such thing as the perfect matrix class. Also, there is no such thing as the perfect fixed size matrix class. Matrices are great generalization in mathematics; for programming, you need to start with the intended application.
Anyway I personally could care less about computer graphics, fixed-size matrices are also useful in computer vision, robotics, and no doubt other domains.
Maybe so, I don't have that much experience in those fields. What prompted my response was that realtime computer graphics was stated as one of the intended applications. In my opinion a different, less abstract interface would be more appropriate there. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
Emil Dotchevski a écrit :
There is no such thing as the perfect matrix class. Also, there is no such thing as the perfect fixed size matrix class. Matrices are great generalization in mathematics; for programming, you need to start with the intended application.
I could do nothing but agree with Emil. matrix is one of the abstraction which inner complexity is the most underestiamted. Took me a PHd and a half to get something decent in a generic-enough way (types support, policies, performances optimisations , etc) for exactly that. I think that something akin to a multi-dimensional boost::array is already aplenty for the 3 months of GSoC and may provide valuable outcome.
Joel Falcou wrote: [snip]
I think that something akin to a multi-dimensional boost::array is already aplenty for the 3 months of GSoC and may provide valuable outcome.
E.g., something like Boost.MultiArray [1]? Kind regards, Rutger ter Borg [1] http://tinyurl.com/d2dg2j
Rutger ter Borg a écrit :
Joel Falcou wrote:
[snip]
I think that something akin to a multi-dimensional boost::array is already aplenty for the 3 months of GSoC and may provide valuable outcome.
E.g., something like Boost.MultiArray [1]?
except multiarray is dynamically allocated contrary to array ? -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
Joel Falcou wrote:
I think that something akin to a multi-dimensional boost::array is already aplenty for the 3 months of GSoC and may provide valuable outcome. E.g., something like Boost.MultiArray [1]?
except multiarray is dynamically allocated contrary to array ?
Yes, I agree that would already be plenty for 3 months -- a library named "matrix" could imply that it would cover all kind of matrices and associated concepts (triangular, banded, packed, etc., etc.). Kind regards, Rutger ter Borg
Rutger ter Borg a écrit :
Yes, I agree that would already be plenty for 3 months -- a library named "matrix" could imply that it would cover all kind of matrices and associated concepts (triangular, banded, packed, etc., etc.).
Ah, sorry for the misundersatnding. I was thinking of statically allcoated multi-dimensionnal *array* of course. -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
On Wed, Apr 1, 2009 at 4:36 PM, Rutger ter Borg <rutger@terborg.net> wrote:
Joel Falcou wrote:
I think that something akin to a multi-dimensional boost::array is already aplenty for the 3 months of GSoC and may provide valuable outcome. E.g., something like Boost.MultiArray [1]?
except multiarray is dynamically allocated contrary to array ?
Yes, I agree that would already be plenty for 3 months -- a library named "matrix" could imply that it would cover all kind of matrices and associated concepts (triangular, banded, packed, etc., etc.).
Just as array implies all kinds of arrays (dynamic, multidimensional, sparse, etc...) ? -- regards, Kornel Kisielewicz
This looks a lot better, but I would err on the side of even more caution and build the tests and the documentation as you go along, so the docs and tests are also your primary deliverables for boost::matrix base container class for 2-dimensional matrices. But I can see that you will need things like operator<< to do testing. The reason for this is that getting the idiosyncratic Boost test and doc system will cause you some (much?) trouble to get going, but without them, the code itself will be very much less valuable because it won't be reviewable, or even not usable. I would strongly encourage you to use Quickbook to generate Boostbook and Doxygen with auto-doc, and John Maddock's indexing system too. This is hard work to set up and get going, but IMO the results are well worth it. (I am working on a 'boilerplate' to help ease this painful process - ask when you are starting?) Paul PS I would suggest NOT wasting your very limited time worrying about obsolete compilers - concentrate ton recent gcc and MSVC 9 SP1 - and ask for help from the Boost list with other recent less-popular compilers (unless you are already using them). --- Paul A. Bristow Prizet Farmhouse Kendal, UK LA8 8AB +44 1539 561830, mobile +44 7714330204 pbristow@hetp.u-net.com
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Kornel Kisielewicz Sent: 01 April 2009 02:17 To: boost@lists.boost.org Subject: [boost] [gsoc] Proposal - Boost.Matrix - DRAFT RFC
Hello all,
Following the discussion in the threads: "[boost][gsoc] Interest check for 3d geometry proposal" "[boost] [gsoc] fixed size matrix class?"
I post a draft of my proposal with a request for comments. Following the suggestions I decided to scale down the proposal to a polished and production-quality fixed-size Boost.Matrix library, with a big emphasis on correctness and performance.
The application follows:
Abstract =========
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 N, std::size_t M, 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.
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 ).
Primary deliverables =====================
Boost.Matrix library, with the following features:
a) 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 b) specializations for efficient vector (1xN matrix) handling c) operators for readable but efficient vector/matrix math d) operator specializations for matrices and vectors of the most common size (2-4) for most efficient implementation
Secondary deliverables =======================
a) performance test suite, for testing optimizations b) unit tests for the whole library providing full operation coverage and code-coverage c) documentation for the whole library in the BoostBook format d) efficient implementation of interoperability of Boost.Matrix with other boost libraries (uBLAS in particular)
Bonus deliverables ===================
( if time allows these will be delivered during program timeline, if not, they will be implemented afterwards )
a) optional (compile-time controlled) integration with Boost.SIMD to boost (no pun intended) performance b) performance tests on different compilers/architectures, further optimizations c) support for further boost libraries ( Boost.Assign, sandbox libraries, etc. )
Design issues ==============
a) compile-time concept checking to only generare functions that make sense for the given type ( no floating point operations for integral types ) b) usage of templates 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 ) c) usage of expression templates to eliminate temporaries in expressions d) care to keep most useful memory alignment ( to provide ease of use with direct usage in architecture dependent pipelines ) e) design with architecture-dependent optimizations in mind ( ease of expansion ) f) keeping all the standard boost practices, including workarounds for non-conformant compilers
Project schedule =================
I plan to do at least weekly progress reports with emphasised design decisions (however well designed in the first phase, reality will probably change the design afterwards at least a little). Progress reports will be directed to the medium established with the mentor (blog, list or only direct communication). This will be my only job once summer starts, and will be treated as such during program coding timeline ( full-time schedule ) -- a week may fall out for a short vacation.
Preplanning (April 20 - May 23) -------------------------------- Most of the major design decisions need to be done before the program starts. A end-user interface for the library should be established before the program starts. This will be summed up in a report that will be sent to boost-dev with a request for comments.
Phase 1 (Correctness) - (May 24 - June 14) ------------------------------------------- A working basic (non-optimized) implementation, and a full test suite for the basic operations will be created. Goal for this phase is to provide a correct and working implementation. Basic usage document.
Phase 2 (Functionality) - (June 14 - July 5) --------------------------------------------- Performance test suite. Compiler-level optimizations ( expression templates, unrolling, etc ). Basic library compatibility ( STL container, uBLAS ). Concept checking.
Phase 3 (Optimization) - (July 6 - July 26) -------------------------------------------- Optimizations for vectors, optimizations for specific vector and matrix sizes, optimization checking through performance test suite. Code review for eventual optional architecture optimization ( Boost.SIMD for example ). General optimization of code. Update of documentation.
Phase 4 (Finalization and bonuses) - (July 27 - August 10+) ------------------------------------------------------------ Testing on as many architectures as possible ( probably will need some help here ). Fixes. Cleanup of the code where needed. A report of the implementation that again will be posted to boost-dev with a request for comments. Here is included also buffer time if there will be delays in one of the former phases. If not, work will continue with the Bonus deliverables.
Brief resume =============
I'm a Computer Science PhD student (2nd year) at the University of Wroclaw (Poland), in the field of Computer Graphics. My interests lie in Game Programming and Design, with a special hunch for Real-time Proceduraly Generated Content. I actively run self-designed courses and lectures at the University ( 3ds MAX course last year, Game Programming lecture this semester, and probably an Advanced C++ course next semester ).
Currently, until the end of the semester, I'm working full-time at Tieto corporation, doing a large scale project for Nokia. Previously I worked at a smaller computer game company working on a massive multiplayer game.
I've successfully taken part in two last GSoC's creating a Procedural City Generator for the BZFlag project.
I consider myself a fairly competent C++ programmer, although I only recently discovered its true strengths ( learned to properly use and write in the style of STL, started reading Boost sources, and got hooked into C++0x ). I'm currently using the language both at work and for my own projects. The latter include a 3D game engine (in progress), and an unannounced space combat/trading game. I am a big fan of roguelike (ASCII) games, and managed to write several roguelikes up to date, the most famous one of them being DoomRL ( http://doom.chaosforge.org ) that did even get mentions in contemporary gaming magazines.
Homepage : http://chaosforge.org/ IRC nick : Epyon E-mail : kornel.kisielewicz at gmail.com / epyon at cs.uni.wroc.pl -- regards, Kornel Kisielewicz _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Apr 1, 2009 at 3:43 PM, Paul A. Bristow <pbristow@hetp.u-net.com> wrote:
This looks a lot better, but I would err on the side of even more caution and build the tests and the documentation as you go along, so the docs and tests are also your primary deliverables for boost::matrix base container class for 2-dimensional matrices.
I have a habbit of writing unit tests after interface but before implementation. As for documentation it will generally be written on the go.
But I can see that you will need things like operator<< to do testing.
I see no problem here :)
The reason for this is that getting the idiosyncratic Boost test and doc system will cause you some (much?) trouble to get going, but without them, the code itself will be very much less valuable because it won't be reviewable, or even not usable.
I don't see what problem is there with Boost.Test -- I used it a lot recently for unit testing my own project. As far as documentation goes, I only know the basics of QuickBook though.
I would strongly encourage you to use Quickbook to generate Boostbook and Doxygen with auto-doc, and John Maddock's indexing system too. This is hard work to set up and get going, but IMO the results are well worth it.
I'm a big fan of doxygen, and usually comment before coding. As for the rest of the tools I'll need to take a look.
(I am working on a 'boilerplate' to help ease this painful process - ask when you are starting?)
That doesn't depend on me :).
PS I would suggest NOT wasting your very limited time worrying about obsolete compilers - concentrate ton recent gcc and MSVC 9 SP1 - and ask for help from the Boost list with other recent less-popular compilers (unless you are already using them).
I 'd really count on that. As for compilers I have immidate access only to GCC 4.4 and 4.3 on Linux, and GCC 4.3, MSVC 8 & 9 on Windows. -- regards, Kornel Kisielewicz
I'm going to repost this as it seemed to get lost at the end of a dead thread...
Date: Mon, 30 Mar 2009 10:15:34 -0400 (EDT) From: Mike Tegtmeyer <tegtmeye@eecis.udel.edu> Reply-To: boost@lists.boost.org To: boost@lists.boost.org Subject: Re: [boost] [gsoc] fixed size matrix class?
I apologize for being late to the thread but I'd like to invite folks to take a look at cvalarray in the boost vault. I wrote this a few years ago and has been in active use in our organization for years now and I've seen it around the net-mostly in raytracing circles. (Actually, I've seen it referenced as boost::cvalarray because they obtained it from the vault) I basically accomplishes the "small fixed sized numeric array" requirement and can be used as base for small matrix class as well. There is an internal version here that also uses SIMD (intel) for the underlying operations. I asked for an interest check on the list many moons ago but I only seemed to get a lukewarm reception. In any case, it is complete, uses expression templates to eliminate temporaries, requires nothing outside of the language, is self-contained in one file, and is well tested. Unless there is heartburn with the interface or underlying implementation, It basically just needs to be boostified and integrated into the build system. Take a look and see if it either meets your needs or could be used as a jumping off point.
Mike
I'd like to add that in most of my experience, the needs of folks looking for a small numeric vector class are vastly different from folks who need complex matrix operations. Likewise, those needs end up driving how each can be implemented. For example, vector-oriented folks expect two vectors of size 4 to end up as one SIMD instruction and could really care less about some of the more complex matrix operations (most which cannot be done with SIMD ops). Sparse matrices and swizzling of vector elements are examples of conflicting usage patterns. So my .02 is that vectors and matrices need to be two different things. Having them as a single entity is not a good idea because: - unnecessarily complicates implementation as there are many operations that make sense on a vector but not on a matrix and vice versa - vectors and matrices are _really_ disjoint when it comes to common usage patterns. (in my world anyway) - Vector operations are much more likely to take advantage of SIMD than matrix operations - no point attempting to unify the un-unifiable - What a perfect interface for a matrix is much more controversial than a vector (again in my world) Having written a pretty complete numeric vector class (which I _really_ think folks should take a look at BTW) I would have this to say about your proposal: It is too ambitious for a summer. You will find a few major issues that will dominate your time and how what your proposal is implemented. -These things really _can't_ be STL container as the requirements pose requirements that limit how you can write an optimized implementation (aliasing is a good example. See 26.1 of the standard for intro). -Minor implementation details have _major_ performance implications. Again when I wrote cvalarray, I initially was using array references as the underlying thing that was passed around in the expression templates, even though they are basically the same thing, switching to pointers, there was a ~20%-30% performance improvement for certain operations (at least on gcc) due to how gcc was interpreting what was going on and how the SIMD register would get loaded. You will likely spend a lot of time trying to understand this kind of compiler behavior and getting a decent common implementation across compilers takes time. The underlying SIMD aspect will dominate the implementation. When I wrote cvalarray, I used my own SIMD base, (mostly because there was nothing else). If boost.simd ever finalizes/gets approved, it's integration will most certainly require almost a complete rewrite. In short, I wouldn't get too wrapped up about the SIMD nuances over a summer project, just keep it in the back of your head -it is a moving target unless you plan to write your own. I would focus on getting an interface that the majority of people will like the majority of the time. Again, my .02 Mike On Wed, 1 Apr 2009, Kornel Kisielewicz wrote:
Hello all,
Following the discussion in the threads: "[boost][gsoc] Interest check for 3d geometry proposal" "[boost] [gsoc] fixed size matrix class?"
I post a draft of my proposal with a request for comments. Following the suggestions I decided to scale down the proposal to a polished and production-quality fixed-size Boost.Matrix library, with a big emphasis on correctness and performance.
The application follows:
Abstract =========
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 N, std::size_t M, 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.
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 ).
Primary deliverables =====================
Boost.Matrix library, with the following features:
a) 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 b) specializations for efficient vector (1xN matrix) handling c) operators for readable but efficient vector/matrix math d) operator specializations for matrices and vectors of the most common size (2-4) for most efficient implementation
Secondary deliverables =======================
a) performance test suite, for testing optimizations b) unit tests for the whole library providing full operation coverage and code-coverage c) documentation for the whole library in the BoostBook format d) efficient implementation of interoperability of Boost.Matrix with other boost libraries (uBLAS in particular)
Bonus deliverables ===================
( if time allows these will be delivered during program timeline, if not, they will be implemented afterwards )
a) optional (compile-time controlled) integration with Boost.SIMD to boost (no pun intended) performance b) performance tests on different compilers/architectures, further optimizations c) support for further boost libraries ( Boost.Assign, sandbox libraries, etc. )
Design issues ==============
a) compile-time concept checking to only generare functions that make sense for the given type ( no floating point operations for integral types ) b) usage of templates 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 ) c) usage of expression templates to eliminate temporaries in expressions d) care to keep most useful memory alignment ( to provide ease of use with direct usage in architecture dependent pipelines ) e) design with architecture-dependent optimizations in mind ( ease of expansion ) f) keeping all the standard boost practices, including workarounds for non-conformant compilers
Project schedule =================
I plan to do at least weekly progress reports with emphasised design decisions (however well designed in the first phase, reality will probably change the design afterwards at least a little). Progress reports will be directed to the medium established with the mentor (blog, list or only direct communication). This will be my only job once summer starts, and will be treated as such during program coding timeline ( full-time schedule ) -- a week may fall out for a short vacation.
Preplanning (April 20 - May 23) -------------------------------- Most of the major design decisions need to be done before the program starts. A end-user interface for the library should be established before the program starts. This will be summed up in a report that will be sent to boost-dev with a request for comments.
Phase 1 (Correctness) - (May 24 - June 14) ------------------------------------------- A working basic (non-optimized) implementation, and a full test suite for the basic operations will be created. Goal for this phase is to provide a correct and working implementation. Basic usage document.
Phase 2 (Functionality) - (June 14 - July 5) --------------------------------------------- Performance test suite. Compiler-level optimizations ( expression templates, unrolling, etc ). Basic library compatibility ( STL container, uBLAS ). Concept checking.
Phase 3 (Optimization) - (July 6 - July 26) -------------------------------------------- Optimizations for vectors, optimizations for specific vector and matrix sizes, optimization checking through performance test suite. Code review for eventual optional architecture optimization ( Boost.SIMD for example ). General optimization of code. Update of documentation.
Phase 4 (Finalization and bonuses) - (July 27 - August 10+) ------------------------------------------------------------ Testing on as many architectures as possible ( probably will need some help here ). Fixes. Cleanup of the code where needed. A report of the implementation that again will be posted to boost-dev with a request for comments. Here is included also buffer time if there will be delays in one of the former phases. If not, work will continue with the Bonus deliverables.
Brief resume =============
I'm a Computer Science PhD student (2nd year) at the University of Wroclaw (Poland), in the field of Computer Graphics. My interests lie in Game Programming and Design, with a special hunch for Real-time Proceduraly Generated Content. I actively run self-designed courses and lectures at the University ( 3ds MAX course last year, Game Programming lecture this semester, and probably an Advanced C++ course next semester ).
Currently, until the end of the semester, I'm working full-time at Tieto corporation, doing a large scale project for Nokia. Previously I worked at a smaller computer game company working on a massive multiplayer game.
I've successfully taken part in two last GSoC's creating a Procedural City Generator for the BZFlag project.
I consider myself a fairly competent C++ programmer, although I only recently discovered its true strengths ( learned to properly use and write in the style of STL, started reading Boost sources, and got hooked into C++0x ). I'm currently using the language both at work and for my own projects. The latter include a 3D game engine (in progress), and an unannounced space combat/trading game. I am a big fan of roguelike (ASCII) games, and managed to write several roguelikes up to date, the most famous one of them being DoomRL ( http://doom.chaosforge.org ) that did even get mentions in contemporary gaming magazines.
Homepage : http://chaosforge.org/ IRC nick : Epyon E-mail : kornel.kisielewicz at gmail.com / epyon at cs.uni.wroc.pl -- regards, Kornel Kisielewicz _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Apr 1, 2009 at 4:59 PM, Mike Tegtmeyer <tegtmeye@eecis.udel.edu> wrote:
So my .02 is that vectors and matrices need to be two different things. Having them as a single entity is not a good idea because:
- unnecessarily complicates implementation as there are many operations that make sense on a vector but not on a matrix and vice versa
Well thought out implementation will just branch into two at a given point.
- vectors and matrices are _really_ disjoint when it comes to common usage patterns. (in my world anyway)
In CG it's multiplying vectors and matrices all the time, what do you suggest by disjoint?
- Vector operations are much more likely to take advantage of SIMD than matrix operations - no point attempting to unify the un-unifiable
That's where specializations enter.
- What a perfect interface for a matrix is much more controversial than a vector (again in my world)
That I have to agree with.
Having written a pretty complete numeric vector class (which I _really_ think folks should take a look at BTW) I would have this to say about your proposal:
It is too ambitious for a summer. You will find a few major issues that will dominate your time and how what your proposal is implemented.
It's not the first and not the second time I would be writing such classes, the main difference would be compatibility, a higher level of genericness and the need of implementing some more obscure operations that I never bothered with. I still think it's in scope, as long as I focus on what's important, and not week-long tries of reducing the constant of an algorithms complexity.
-Minor implementation details have _major_ performance implications. Again when I wrote cvalarray, I initially was using array references as the underlying thing that was passed around in the expression templates, even though they are basically the same thing, switching to pointers, there was a ~20%-30% performance improvement for certain operations (at least on gcc) due to how gcc was interpreting what was going on and how the SIMD register would get loaded. You will likely spend a lot of time trying to understand this kind of compiler behavior and getting a decent common implementation across compilers takes time.
The across compilers thing here is the major problem, however that is to be addressed with the performance suite. Also, the goal for this SoC is not to write *the optimal* implementation. It's to write an implementation that will be optimal enough to be optimized without full rewriting.
I would focus on getting an interface that the majority of people will like the majority of the time.
I agree. -- regards, Kornel Kisielewicz
On Wed, Apr 1, 2009 at 4:59 PM, Mike Tegtmeyer <tegtmeye@eecis.udel.edu> wrote:
So my .02 is that vectors and matrices need to be two different things. Having them as a single entity is not a good idea because:
- unnecessarily complicates implementation as there are many operations
make sense on a vector but not on a matrix and vice versa
Well thought out implementation will just branch into two at a given
On Wed, 1 Apr 2009, Kornel Kisielewicz wrote: that point. Just because it can, doesn't necessarily mean that it should. If the implementation branches for 1D matrix and "everything else", then the unification is in name only. There are too many operations are only meaningful for 1D matrices and vice versa. I'm having a hard time justifying to myself why they should fall under a common abstraction. To me, an analogy is std::vector and std::list, even though they have similar operations, then have different usage patterns. I think it makes much more sense that they are top-level entities instead of having a common std::sequence with a template argument that specifies the underlying memory layout and branching the two implementations under the hood.
- vectors and matrices are _really_ disjoint when it comes to common
usage
patterns. (in my world anyway)
In CG it's multiplying vectors and matrices all the time, what do you suggest by disjoint?
I'm not saying that you couldn't, for example, multiply a vector and matrix. I'm speculating that one of the reasons that a matrix interface is more controversial than a vector is because how the intended audience uses them is much more varied. Someone who uses matrices for transforms in graphics is usually (broad brush here) different from folks who care about triangle matrices, what makes a good triangle matrix implementation, and how a useful matrix library to them would have compile-time enforcement of symmetric matrices etc. I guess my 'disjoint' comment: that this disparity (er religious wars??) typically don't come up in 1D vectors.
- Vector operations are much more likely to take advantage of SIMD than matrix operations - no point attempting to unify the un-unifiable
That's where specializations enter.
Again my comment about being in name only.
It's not the first and not the second time I would be writing such classes, the main difference would be compatibility, a higher level of genericness and the need of implementing some more obscure operations that I never bothered with. I still think it's in scope, as long as I focus on what's important, and not week-long tries of reducing the constant of an algorithms complexity.
Sorry, I wasn't suggesting that you weren't up for the task. If you could pull it off, fantastic. I just would caution that if your library gains some interest, it is likely that you will get bogged down by the same stylistic, "I could do better", and "this isn't elegant for _my_ usage pattern" clashes that have plagued every other attempt to have a unified matrix library.
The across compilers thing here is the major problem, however that is to be addressed with the performance suite. Also, the goal for this SoC is not to write *the optimal* implementation. It's to write an implementation that will be optimal enough to be optimized without full rewriting.
Absolutely. I just have run into the same issues. In general, we really have to justify any abstraction penalty to the community you are attempting to target. And that abstraction penalty can very much be compile-time and learning curve. I'll argue most of this community knows how to write explicit SIMD instructions and need convincing to use a complex abstraction and having faith that it will 'do the right thing' and doing it fast enough as hand rolled code when speed it paramount. In short, because of what this is, and who the target audience is-simple and concise is probably better then clever and complicated. Again, just my .02, Mike
participants (7)
-
Emil Dotchevski -
Joel Falcou -
Kornel Kisielewicz -
Mike Tegtmeyer -
Patrick Mihelich -
Paul A. Bristow -
Rutger ter Borg