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

Subject: [boost] [gsoc] Proposal - Boost.Matrix - DRAFT RFC
From: Kornel Kisielewicz (kornel.kisielewicz_at_[hidden])
Date: 2009-03-31 21:17:20

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