search

ericniebler / stl2

LaTeX and Markdown source for the Ranges TS/STL2 and associated proposals
88 stars 8 forks source link

reverse_view probably shouldn't accept non-Common ranges #576

Open ericniebler opened 5 years ago

ericniebler commented 5 years ago

Presently, calling begin() on a reverse_view that adapts a Bidirectional-but-not-Common range will cause an O(N) probe for the end of the range, caching the result in the view. We have the following in a Remarks clause:

In order to provide the amortized constant time complexity required by the Range concept, this function caches the result within the reverse_view for use on subsequent calls.

This makes me uncomfortable. Do we really want this?

CaseyCarter commented 5 years ago

This makes me uncomfortable. Do we really want this?

While I'm fine with the caching of the underlying range's end iterator, I'm concerned about the performance impact of the probe. The O(N) probe cost is one-time, and "amortizes" across the iteration of the O(N) elements in the range well, resulting in "amortized"-O(1) complexity for begin as required. Unfortunately, this simple notion of complexity doesn't really reflect performance in a system with a modern memory hierarchy. Walking through the range to find the end iterator has both the up-front costs of accessing the range elements, and secondary costs due to reloading the useful cache contents that were evicted when filling caches with range elements.

I think the 1 in this O(1) is too big.

ericniebler commented 5 years ago

UPDATE from San Diego: we should also reconsider std::ranges::reverse and std::ranges::reverse_copy.

CaseyCarter commented 5 years ago

More generally: algorithms/views that necessarily must determine the size and/or end iterator of a range before processing the range should reconsider "hiding" an additional linear traversal to find that size/end iterator when passed differing iterator and sentinel types (e.g., std::ranges::sort, although it's hardly an egregious example).

Similarly, We need to audit algorithms/views which provide complexity guarantees when the iterator models Bidirectionalterator/RandomAccessIterator to determine if those guarantees require a hidden linear traversal when the iterator and sentinel types differ (std::ranges::partition).

In both cases, I think we want a note about potentially large constant factors even if we make no normative changes.