Customization point for for_each, etc

anders-sjogren commented 9 years ago

For certain classes of Ranges/Iterables, there may be ways to implement for_each that are easier to optimize (and auto-vectorize) for the compiler and thus gives faster code. My use-case is a chunked_vector, being a vector of vectors, where for_each(chunked_vector<T>& d,F f) is essentially implemented as for_each(d.chunks_,[f&](vector<T>& chunk){for_each(chunk,f);}). The inner loop here probably becomes easier to auto-vectorize than one based on somewhat complicated iterators.

So, the question is: is there a customization point in ranges that make it possible to add such specializations? Otherwise, this is a feature request for such customization points.

anders-sjogren commented 9 years ago

After some more reading: I guess I mean something like what's done for beginand end in begin_end.hpp, which is neatly explained in Eric's blogpost on the subject.

anders-sjogren commented 9 years ago

When comparing begin_end.hpp and the code in the blogpost above, it seems some steps are missing in begin_end.hpp (the steps commented with "To avoid ODR violations" in the blogpost). Is there a reason for this?

ericniebler commented 9 years ago

What you're asking for is support for segmented iterators. I understand why you want this, but you don't know the scope of what you're asking for. To fully support segmented iterators requires hierarchical versions of every algorithm. And they're not all as easy as for_each.

anders-sjogren commented 9 years ago

Eric,

Thanks for the reference to segmented iterators!

To be precise, I didn't ask for a segmented iterator algorithm to be implemented for me, I asked for a way to plug-in such an algorithm of my own.

More precisely: My use-case is that I want to create such a customization. Is there currently a way of doing so?

Or does for_each being an object rather than a function hinder the usual method of:

using namespace ranges;
for_each(d,f);

In the section "Function Objects and Customization Points" of your excellent blog-post, it is stated "But argument-dependent lookup is only done for free functions, and my std::begin is a function object.".

Does that mean that if the library chooses the path of function objects (such as is done with for_each_fn), then the library has to implement customization points according to the blog-post or no customization point is available at all?

ericniebler commented 9 years ago

If you want to turn all the algorithms into customization points, I like that idea less than proper support for segmented data structures. There has to be some limits on the fungibility of the library. Let's reserve customization points for the primitive operations like swap, begin and end that have very basic semantics.

I haven't yet talked with the guys from the concurrency study group to find out what is necessary from the algorithms and views to best support concurrency and parallelization. I'd rather wait to see what comes from that discussion.

anders-sjogren commented 9 years ago

If you want to turn all the algorithms into customization points, I like that idea less than proper support for segmented data structures.

May I ask why? To me it feels like algorithms/functionals, such as for_each, is really the basic operations and core of data centric programming, and could be a glue that connects the libraries for data structures and problem-specific code. Basically, the role of the ranges library could be:

Provide a set of declared range based operations.
Provide default definitions/implementation of those operations.
Provide customization points for data-structure specific improved implementations of those operations, to be implemented by implementors of custom data-structures when more space of time efficient versions exist.

If this route is taken, then the casual user of a custom data-structure library will be able to get access to custom high-performance implementation of the operations to be used on those data structures, but can do that by using a well described framework (ranges). This also makes it easy to switch data structures, from one to another (potentially coming from different libraries). The ranges library with its customization point becomes something of an extended interface for the class, but with a default implementation, and thus a well-defined glue between the libraries for data structures and problem-specific code.

If this route is not taken, then when using a custom data structure (such as segmented vector) from a library, users of a library must learn the specifics of that library and change the code to the specifics of that library. In addition to learning overhead, it also means that generic code that work with all ranges will not to tap into the power of these custom implementations, and will thus have decreased performance. Since C++ is main advantage is lean- and mean-ness this seams like a bad thing.

Since the functions of today in the standard library are functions, one can customize them using ADL and the using std::f; f(x); pattern. By having the functions as function objects and not regular functions, this no longer works (as pointed out in the previously mentioned blog-post, and double-checked here).

The suggested solution of implementing built-in support for customized data structures, in this case segmented data structures, seems non-sufficient for a standard library. There is no way to know what custom data structure will exist that have improved ways of performing some of the operations in the ranges library (not least basic ones such as for_each), nor is it possible to cover all existing data-structures even if one wanted to.

To summarize: Providing customization points for most or all operations allows the ranges library to focus on the core aspect of defining useful operations and giving reasonable default implementations, and facilitates and delegates writing customized operations for custom data structures (current and future ones) to the authors of those data structures.

To me, that seems like a good separation of responsibilities. But I may well have missed important aspects. Enlighten me!

I haven't yet talked with the guys from the concurrency study group to find out what is necessary from the algorithms and views to best support concurrency and parallelization. I'd rather wait to see what comes from that discussion.

A fair point. I'll just implement customization points for algorithms I need in a private fork in the mean-while. If you'd have time to keep the rest of us posted on the progress, it'd be greatly appreciated.

anders-sjogren commented 9 years ago

In case anyone wants to try this out, a commit to my private fork is now done, where it works: https://github.com/anders-sjogren/range-v3/commit/b9643cd9a532af79b7c39eca545ac874c58297e9 . The fork is certainly not intended as any kind of alternative to the main ericniebler/range-v3, it's just my private lab area.

ericniebler commented 9 years ago

If you want to turn all the algorithms into customization points, I like that idea less than proper support for segmented data structures.

May I ask why? To me it feels like algorithms/functionals, such as for_each, is really the basic operations and core of data centric programming, and could be a glue that connects the libraries for data structures and problem-specific code.

To be useful, there should be as few "primitive" operations and customization points as possible. That way, users can hook the core mechanisms with only one or two overloads or specializations. If every algorithm is a customization point, then the number of things a user has to do to hook the mechanism is potentially unbounded.

For parallelization, the only hook that is really needed is a "split" or "segments" API that takes a range and returns a range of ranges -- the internal segments of the segmented data structure. Or, if the data structure is not segmented (e.g. a vector), it returns subranges broken on, say, the size of the cache line. All parallel algorithm can be specified in terms of that one primitive. Waaaay easier than telling people that they need to reimplement a hundred or so standard algorithms for every one of their types.

anders-sjogren commented 9 years ago

To be useful, there should be as few "primitive" operations and customization points as possible.

I agree that reaping the rewards using just a few extension points is excellent. In the segmented array case, it's clearly possible to do so using a single customization point that provides the segments (or parts of them even, if they are big). This is also similar to the Intel TBB approach, where you provide a range of type R and a method for splitting it into two pieces of type R. I like the approach you propose where one does not give ranges of the same type back better, since the segments are clearly not of the same type as the segmented_array.

However, I bet there are important classes of structures and algorithms that do not let themselves be optimally expressed in this manner. Suppose you have a set class s implemented using a sorted array, which is iterated through in increasing value order. Suppose then that you call ranges::find(s,some_value). This could clearly be customized by s to be O(log(n)), while segmentation won't help (?) and will be O(n).

I agree that few extension points are good, but if there is not enough of them to express common functions, then the library writer will just need to implement it (e.g. find) in his own namespace lib_ns and the user will need to call lib_ns::find instead, which unnecessarily couples the implementation of a possibly generic method to the data structure used in it.

My case is that we do not know which operations are optimal for each data structure. All we can do is to default implement methods in terms of other methods as much as possible (if those methods, such as for_each, are customized), and to provide customization points for the algorithms we include.

Waaaay easier than telling people that they need to reimplement a hundred or so standard algorithms for every one of their types.

If the algorithms are implemented in terms of other algorithms/extension points, this will clearly not be needed (as you point out in the case with a few extension points). My suggestion is not either/or, it's more of a gradual scale. Let most algorithms be default implemented (in ranges) in terms of other algorithms/extension points, but leave the library writer freedom to provide a different implementation if needed!? This will make the algorithms in the ranges namespace be optimal for well written libraries, and the user won't need to look further. In a way, it standardizes the interface for a class, if the functions reachable from ADL is seen as part of the interface (which is a view taken in the wikipedia article of ADL and seems supported in e.g. http://www.gotw.ca/publications/mill08.htm).

To elaborate on "May I ask why?": Suppose we have your proposal where ranges provides some customization points (such as segmented access, begin, end, etc), and the implementations in ranges uses those extension points to the best of their ability. What is then the cost of adding additional customization points for the rest of the algorithms? If the 3:rd party library writer does not implement the customization points, the net result will be having the same functionality as if the customization points did not exist (that is the same as your current suggestion)? If the extension points are optimally implemented on the other hand (say for a set class), the user will get faster code. So, we have clear use-cases where we gain a clear benefit from adding further customization points. What are the downsides to it?

ericniebler / range-v3

Customization point for for_each, etc #83