-
Notifications
You must be signed in to change notification settings - Fork 440
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Customization point for for_each, etc #83
Comments
After some more reading: |
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? |
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 |
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:
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 |
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 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. |
May I ask why? To me it feels like algorithms/functionals, such as
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). 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 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!
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. |
In case anyone wants to try this out, a commit to my private fork is now done, where it works: |
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. |
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 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. 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
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 |
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 asfor_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.
The text was updated successfully, but these errors were encountered: