Boost logo

Glas :

Re: [glas] using (boost)range or STL style interface [was: dense and sparse vectors]

From: David Abrahams (dave_at_[hidden])
Date: 2005-08-04 09:44:11


Toon Knapen <toon.knapen_at_[hidden]> writes:

> David Abrahams wrote:
>> For what it's worth, the MTL4 project is using a Sequence interface:
>> (http://tinyurl.com/cdnlt or
>> http://boost-consulting.com/projects/mtl4/libs/sequence/doc/html/),
>> which is similar to the Boost.Range interface, but generalized along
>> several dimensions.
>>
>> - Instead of iterators, we use cursors and property maps:
>> http://tinyurl.com/7hcka
>> (http://boost-consulting.com/projects/mtl4/libs/sequence/doc/html/cursors_and_property_maps.html)
>
>
> Very interesting indeed. How would you compare the cursors and property
> maps approach with the n1531 proposal?

Everything below the bullet list at
http://tinyurl.com/7hcka#problems-with-c-03-iterators describes a
problem solved by cursors and property maps that's not solved by N1531.

(http://boost-consulting.com/projects/mtl4/libs/sequence/doc/html/cursors_and_property_maps.html#problems-with-c-03-iterators)

> Do you have a prototype lying around that I can use to get some
> hands on experience?

There are two incomplete prototypes:

  1. As part of the MTL4 project I have built an implementation of
     Sequence-based algorithm dispatching, where a Sequence is a
     property map and two cursors of possibly different types. The
     only thing it demonstrates is that I can correctly dispatch to an
     unrolled version of the copy algorithm when operating on
     fixed-sized arrays. You can browse it at
     http://boost-consulting.com/projects/mtl4/boost/sequence/ and
     http://boost-consulting.com/projects/mtl4/libs/sequence/. I'll
     be happy to provide an archive on request, but I warn you that
     there's a lot of framework there and not much computation, so you
     may find it hard to read.

  2. Dietmar Kuehl and I have been working on how to represent
     segmented cursors and property maps (that's the cursor/property
     map version of what's described in the Austern paper on segmented
     iterators that I mentioned). We have some prototype algorithms
     and tests that depend on using GCC >= 3.0. I've enclosed a
     .tar.gz archive of these. This prototype is not Sequence-based,
     in that cursors and property maps are passed to functions
     independently, without bundling them into Sequences. It also
     doesn't yet incorporate the generalizations that cursors
     delimiting a range may have different types. Also our
     conversation about how to operate within a segment has evolved
     somewhat since this code was written.

> Note: The motivation for my response on the range-style interface
> was mainly that from my experience numerics people (which are the
> (future) users of glas) need 'everything as simple as possible but
> not simpler' (to quote Einstein). Everybody is now familiar with
> the [begin,end[ iterators. Using an alternative style can therefore
> only be adopted IMHO if it clearly provides a lot of added
> value. C++ is already a complicated language (well if you compare it
> to fortran77) and numericists want to focus on getting their job
> done (without becoming a language-lawyer). This is from my
> experience but more important are actually the opinions of the
> numericists on this ml.

Sure. One great added value in a Sequence-based implementation, aside
from the simplicity of being able to pass containers directly to
algorithms, is composability. That is, you can pass the results of
one algorithm directly on to another one, without declaring
intermediate variables. That's important in a world with lots of
views. For example,

   some_algorithm(transpose_view(m))

as opposed to:

   some_algorithm(transpose_view(m).begin(), transpose_view(m).end())

> <snip>
>
>>
>> - We are supporting segmented cursors and property maps, per
>> http://lafstern.org/matt/segmented.pdf. Segmentation turns out to
>> be crucial for blocking, parallel decomposition, and efficient
>> operation on linearized CSR matrices.
>
> thanks for the link. Is there a practical|performance difference between
> the implementation as proposed by Matt Austern and the implementation in
> the cursors and property maps?

Since the difference is just that Austern uses segmented iterators and
we use segmented cursors and property maps,the answer is the same as I
gave earlier: everything below the bullet list at
http://tinyurl.com/7hcka#problems-with-c-03-iterators.

The performance advantage of handling segmentation is huge. You can
make time-segmented and run it to see some numbers.



-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com