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.
> 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