Re: [boost] [gsoc] Proposal - Boost.Matrix - DRAFT RFC

Subject: Re: [boost] [gsoc] Proposal - Boost.Matrix - DRAFT RFC
From: Mike Tegtmeyer (tegtmeye_at_[hidden])
Date: 2009-04-01 10:59:44

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_at_[hidden]>
> Reply-To: boost_at_[hidden]
> To: boost_at_[hidden]
> 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
>