I was solving a programming task where we wanted to find a smallest integer not satisfying a given (monotone) property. This can be achieved via binary search. Using C++20, I decided to use std::partition_point together with std::iota_view. I had several types mixed up and my code was very slow for some reason. My code (simplified):
#include <ranges>
#include <iostream>
#include <algorithm>
#include <climits>
bool monotone(int n)
{
return n <= 1000000000;
}
long long MAX = INT_MAX; //weird?
int main()
{
using namespace std;
cout << *ranges::partition_point(ranges::iota_view(1,MAX), monotone) << endl;
}
by looking closer, it is weird that MAX is of type long long while it could be int. Running this on my machine yields a running time of approximately 12 seconds, which is too much, it should be logarithmic in MAX. I noticed that if i changed ranges::iota_view(1,MAX) to ranges::iota_view(1ll, MAX) or ranges::iota_view(1,(int)MAX) the code suddenly began to "work" fast as intended (completed in few milliseconds).
In both scenarios, i measured that the function monotone was called exactly 31 times (in this case), so the time complexity regarding number of calls of the predicate is ok.
Can someone explain to me what is going on under the hood and why mixing up types in the iota_view produced such slow code?
Edit: the issue seems to lie in calling ranges::distance inside ranges::partition_point which specializes itself to the variant where it computes distance of std::iota_view<int,long long>::_Iterator and std::iota_view<int,long long>::_Sentinel in linear time. Instead, when giving iota_view the same two types (either two ints or two long longs), the specialization chooses to compute distance between std::iota_view<int,int>::_Iterator and std::iota_view<int,int>::_Iterator which falls into the specialization where it is computed in O(1) simply as difference of two ints.
However, why such specialization occurs is still a mystery to me and would like a detailed explanation on why it behaves like this.
When iota_view receives different argument types, .end() returns a sentinel instead of an iterator.
A sentinel is a type that's ==-comparable with an iterator, and optionally subtractible from it (the latter makes it a sized sentinel).
If it happens to not be subtractible, ranges::partition_point can't know the range size in advance, and has to increment the iterator step by step (almost as if it wasn't random-access).
For some reason, for iota_view<A,B> this sentinel is specified to overload - only if std::sized_sentinel_for<B, A> == true, which is false, because neither is an iterator in this case (int and long long).