Move segmented and histogram algorithms to <oneapi/dpl/numeric>

[akukanov]

Currently, all non-standard algorithms of oneDPL are defined in the <oneapi/dpl/algorithm> header. This is also described in the specification:

The parallel algorithms are defined in the <oneapi/dpl/algorithm> header, in namespace oneapi::dpl.

However some algorithms, namely, {inclusive,exclusive}_scan_by_segment, reduce_by_segment, and histogram, might better be defined in <oneapi/dpl/numeric> instead. The segmented algorithms would then reside in the same header as their non-segmented standard "ancestors". And histogram is currently defined to operate only with arithmetic types, so it is effectively a numeric algorithm.

The obvious downside is that this change would break existing codes that include only <...algorithm> but not <...numeric>. Perhaps the implementation would need to provide the definitions through both headers during a deprecation period. Not sure if the major version bump would be necessary for such a change.

Another concern is specific for histogram which, in principle, can be extended to non-numeric types with an extra overload taking a predicate for comparison with interval boundaries or a function to compute bin indexes for the input values. Such algorithms might also be considered as additions to the count family and reside in <...algorithm>.

Tagging @danhoeflinger @MikeDvorskiy

[danhoeflinger]

I have no strong preference of where histogram should be placed as you mention there are reasons to have it in each of numeric or algorithm. Since it is an extension beyond the std parallel APIs, we are not obligated to match an equivalent in the c++ standard specification from that perspective.

I don't see a problem to adding it to numeric in the specification and implementation. Do we see it as something which would need to be ultimately removed from algorithm in our implementation (after a deprecation)? I wouldn't think it would be a problem to keep it for backward compatibility. Of course, if we want to remove it then yes deprecation is the right move.

I realize I haven't added much to the conversation, but I don't have a strong opinion here for the outcome, other than if we do add / move it to numeric, we need to change the specification.

[akukanov]

Since it is an extension beyond the std parallel APIs, we are not obligated to match an equivalent in the c++ standard specification from that perspective.

True, we are not obligated. However, it makes sense to consider the spirit of the standard. At least from my perspective, histogram belongs to the same group as accumulate, partial_sum and iota rather than count, equal etc.

Do we see it as something which would need to be ultimately removed from algorithm in our implementation (after a deprecation)? I wouldn't think it would be a problem to keep it for backward compatibility.

Yes, I would remove it eventually if it's removed from the spec. It's not a problem to keep in the implementation, but it would be kind of an (undocumented?) extension to the spec, and I prefer to avoid extensions unless it's really a well-thought decision of not adding a feature to the specification.

[akukanov]

The specification update uxlfoundation/oneAPI-spec#657 proposes defining these algorithms in <oneapi/dpl/numeric> while also keeping in <oneapi/dpl/algorithm> for compatibility.

[akukanov]

Implemented in #2591