Re: segmented fusion - a-ha!

Joel de Guzman <joel@xxxxxxxxxxxxxxxxxxxx> writes:

> Eric Niebler wrote:
>> I just had an a-ha! moment. Segmentation in Fusion is *so* much
>> simpler than I was making it. Fusion doesn't need segmented
>> iterators, it needs segmented sequences! Fusion's algorithms don't
>> take iterators like the std algorithms do -- they take sequences. I
>> was trying to shoe-horn Matt Austern's formulation into Fusion, but
>> that's the wrong approach.
>> Consider the joint_view. It should advertise itself as a segmented
>> view. Then, the only thing it needs to provide is a way to step
>> through the internal segments -- which are Fusion sequences that may
>> or may not be segmented. What you get, essentially, is:
>
> Yeah! This is "make it as simple as possible" thing that I was
> looking for. Essentially, segmented sequences are sequences with
> child sequences (segments). I see:
>
>     traits::is_segmented<Seq>::type // --> mpl::true_/false_
>
> Then for segmented sequences:
>
>     segments(seq) // --> a sequence of sequences
>     result_of::segments<Seq>::type // --> a sequence of sequences type
>
> Now, a joint_view can hold and return a vector2<Sequence1, Sequence2>&
> when its intrinsic "segments" is called (via tag-dispatch).

Hmm, this is interesting.  There's some inherent complexity in
segmented iterators that this seems to be either masking, or
eliminating.  It has to do with subranges.  To tell which it is, you
have to think about doing something like two finds in a hierarchical
sequence, using the resulting iterators to delimit a subrange, and
doing something like fill on the result.  

                             +---+---+
                             | A | B |
                             +-|-+-|-+
                    +----------+   +-----------+
                    |                          |
                    V                          V
              +---+---+---+              +---+---+---+ 
              | 1 | 2 | 3 |              | 4 | 5 | 6 | 
              +-|-+-|-+-|-+              +-|-+-|-+-|-+ 
        +-------+   |   +---+          +---+   |   +-------+
        |         +-+       |          |       +-+         |
        |         |         |          |         |         |
        V         V         V          V         V         V
    +---+---+ +---+---+ +---+---+  +---+---+ +---+---+ +---+---+
    | a | b | | c | d | | e | f |  | g | h | | i | j | | k | l |
    +---+---+ +---+---+ +---+---+  +---+---+ +---+---+ +---+---+

So what happens when we find, in separate steps, d and j, then use the
resulting subrange [d,j) to do a fill with x?
  
I think you have to see some kind of segmented iterator at some point:
the new hierarchical range is [ <A,2,d>, <B,5,j> ).

Now, you can build a sequence out of those two endpoints, but it's not
as simple as it looks, because above the leaves you don't have
half-open ranges anymore.  That is, the range doesn't include j, but
it does include 5.

Well there's more to think about here but I'll leave you guys with
that head start.  I'm pretty sure that doing this in terms of
sequences can't make all the complexity disappear.

> Now, if for_each was an object (ala Fusion1), then segmented for_each
> will simply be:
>
>     for_each(segments(seq), for_each);
>
> (Strike 1 for object algorithms, Dave?)

I think you mean "score 1."  Normally strikes are "against" ;-)

> Effectively, each segment is unrolled for us by the mechanism
> that already exists in fusion!

That's what happens with this hierarchical stuff.

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



-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642