[boost] [GSoC] Boost.Matrix RFC

Subject: [boost] [GSoC] Boost.Matrix RFC
From: Kornel Kisielewicz (kornel.kisielewicz_at_[hidden])
Date: 2010-04-06 07:14:03

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/