Re: [boost] [range] for_each and std::map of std::list

Subject: Re: [boost] [range] for_each and std::map of std::list
From: Neil Groves (neil_at_[hidden])
Date: 2011-04-09 13:06:02

On Thu, Apr 7, 2011 at 7:24 PM, Jeffrey Lee Hellrung, Jr. <
jeffrey.hellrung_at_[hidden]> wrote:

> On Thu, Apr 7, 2011 at 11:17 AM, Jeremy Maitin-Shepard
> <jeremy_at_[hidden]>wrote:
>
> > On 04/07/2011 04:39 AM, Mathias Gaunard wrote:
> >
> >> On 07/04/2011 12:56, Thorsten Ottosen wrote:
> >>
> >>  Well, that is only a problem if you want to avoid manually applying the
> >>> adaptor twice (or more), right?
> >>>
> >>> If so, I think that is a limitation we can live with. A simple solution
> >>> covers most cases IMO.
> >>>
>

I believe it is easy to come up with a simple adapter that covers most of
the cases. However I also believe that it would define an interface that if
not carefully considered may be limiting.

I wish to be able to solve the related segmented iteration with superior
performance than is afforded by segmented iterators. I perceive the
segmented iteration problem to be another special-case of the projection of
an N-dimensional structure to a linear sequence.

The classic flattening of segmented iterators causes additional overhead
since each iterator increment must check to see if the end of the local
range was reached in order to correctly move to the start of the next local
range. However, if we allow ourselves to develop a small number of
'enumeration' algorithms such as for_each, that are optimized for a newly
defined set of traits, and a projection policy, we can produce a nested loop
that is optimal for traversing this structure. This small set of enumeration
algorithms would have to be optimized for the several idioms, but it then
opens the way to better support not just segmented iteration, but
specialization of chunked contiguous blocks of memory such, and thereby
enables better compiler auto vectorization.

Clearly projection from high-dimensional spaces to linear sequences requires
parameterization, and hence the earlier questions with respect to picking
columns versus rows first for matrices is deferred to the client as they
decide the parameters to pick for the projection policy. The same technique
solves the various decisions that need to be made when projecting trees
either depth-first or breadth-first.

In summary I believe that I need to separate a set of primitive algorithms
that define highly optimized enumeration algorithms. The other Boost.Range
algorithms where appropriate should implemented in terms of these
enumeration primitives. A Concept or Concepts need to be clarified to define
projection as a distinct subset of adaptors, and appropriate Concepts need
to be defined for the projection policies.

My earlier discussion of tree containers and n-dimensional containers was
meant to invoke thoughts of containers not implemented by the STL that could
be leverage, at least some,  generic algorithms. From my own experience in
high performance mathematical computing, and from discussion with colleagues
in this field there are frequently special high-dimensional containers that
would benefit from access to these algorithms.

I have spent some time developing these ideas and solutions, and would
prefer to solidify these ideas rather than implement the simple flattened
adaptor that would, in my opinion, move the Boost.Range design in the wrong
long-term direction.

> >>
> >> Oh, the adaptor I wrote flattens recursively.
> >>
> >> I guess just flattening the top level could be fairly easy.
> >>
> >
> > You could also require that the user specify the number of levels of
> > recursion explicitly, as in many cases the final value_type you want to
> > iterate over may be a range itself.  Consider, for instance, that a
> string
> > is itself a range of characters, but in many cases the user would not
> want
> > to flatten a range of strings into a range of characters.
> >
>
> +1
>
>
I believe that the projection into the one dimensional space needs to be
parameterizable in many more ways than simply the number of levels. I have
many concrete use-cases where this is so.

> I don't think auto-detecting the flattening depth is the way to go.  The
> closest that makes sense to me is to create a mechanism to "flatten until
> value_type == whatever", but that can be built as a layer on top of
> explicitly specifying the flattening depth.
>
>
I will not implement auto-detecting flattening depth. The inherent
limitations and inflexibility of this design choice make it a non-starter.

> I've done this before, it's kind of a PITA and I currently don't like my
> current implementation and had plans at some point to rework it...
>
> - Jeff
>
>
Thank you all for your patience.

Regards,

Neil Groves