iterator dereferencing cost a huge time

Question

I solved a problem with Set operations like upperbound, iterator dereferencing etc. It solves in around 20 seconds. The general problem is I am iterating over group of numbers (i*(i-1)/2) until it is less than 2 * 10^5, and then complete a DP vector. So in my algorithm for each number "x" I get the upper_bound,"up", then starting from the beginning iterate over the numbers until reach to "up". The solution does the same but it does not run upper_bound and dereferencing, but instead it directly calculate the i*(i-1)/2, which i previously calculated and stored in vset. the number of operations for both algorithm is almost same, around 80*10^6, which is not super big number. But my code takes 20 seconds, solution needs 2 seconds.
Please look at my code and let me know if you need more information about this:

1- vset has 600 numbers, which is all numbers in the form of i*(i-1)/2; less than 2*10^5
2- vset is already sorted as it is increasing
3- the final vector "v" in both algorithm is exactly same
4- cnt, number of operation for both is almost same. 80,000,000
5- you can test the codes with n = 199977.
6- On my computer, corei7 32G RAM, it takes 20 seconds, on server accepted around 200 Mili seconds, this is very strange to me.

typedef long long int llint;
int n; cin >> n;
vector<llint> v(n+1, INT_MAX); 
llint p = 1;
llint node = 2;

llint cnt = 0;
for (int i = 1; i <= n; i++)
{
    if (v[i] == INT_MAX)
    {
        for (int s = 1; (s * (s - 1)) / 2 <= i; ++s)
            v[i] = min(v[i], v[i - (s * (s - 1)) / 2] + s) , cnt++;
    }
    else cnt ++ ;
}
cout << cnt << endl; // works in less than 2 seconds

The Second solution takes 20 seconds.

typedef long long int llint;
int n; cin >> n;
vector<llint> v(n+1, INT_MAX); 
llint p = 1;
llint node = 2;
vector<int> vset;
while (p <= n) // only 600 numbers 
{
    v[p] = node;
    vset.push_back(p);
    node++;
    p = node * (node - 1) / 2;
}
llint cnt = 0;
for (int i = 1; i <= n; i++)
  {
    if (v[i] == INT_MAX)
    {
        auto up = upper_bound(vset.begin(), vset.end(), i);
        for (auto it = vset.begin(); it != up; it++) // at most 600 iteration
        {
            cnt++;
            int j = *it;
            v[i] = min(v[j] + v[i - j], v[i]);
        }
    } 
    else cnt ++ ;
   }
cout << cnt << endl; // cnt for both is around 84,000,000

So the question is about something I cannot figure out: which operation(s) here is expensive? going through the iterator? dereferencing the iterator? there is no more difference here but the time is TEN TIMES MORE. thanks

Please [edit] your question to include a [mcve], which is a buildable runnable program anyone can try without editing. — n. m. could be an AI, Dec 25 '22 at 18:35
A first option to find out how long a prog really needs at a given code is to use a profiler. But in your case, the code has low number of functional blocks and each of the blocks is small. So I expect using a profiler will end up in modifying the run time more as the code itself :-) In such cases the only option is toinspect the assembly or run the code on a cpu simulator which give you really exact results on each assembly instruction vs input c++ code. I believe nobody of us will do this job for you... — Klaus, Dec 25 '22 at 18:47
Don't use competitive coding sites to teach yourself C++ (to be honest your code makes me sad, its a mix of bad practices, "C" and "C++" aproaches, and frankly unreadable). Use a [good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or https://www.learncpp.com/ and first teach yourself C++ before tackling more of those problems. In the end finding bottlenecks is all about measuring (and measuring again) on your own computer where you have control over what is using CPU time. — Pepijn Kramer, Dec 25 '22 at 18:47
the second loop in second algorithm iterate only 600 numbers at most, and i caounter the cnt, number of operations for both is almost same. that's why i am wondered. — Azzurro94, Dec 25 '22 at 18:48
I don't think the two pieces are doing the same thing. `v[i - (s * (s - 1)) / 2] + s` in the first is equivalent to `v[i-j] + j`, not to `v[i-j] + v[j]` — Igor Tandetnik, Dec 25 '22 at 18:49
Are you measuring performance of debug builds, by any chance? The standard library implementations often maintain additional diagnostic information in debug builds, making containers and iterators slow. Compare release builds. — Igor Tandetnik, Dec 25 '22 at 18:57
@PepijnKramer thanks, Could you tell me which parts are mix of C and C++. you are right I am not an expert, but I just wanted to know if the iterators operations here are expensive because there is not much difference, to me. I use iterators and it is the first time i see this problem. — Azzurro94, Dec 25 '22 at 18:59
`typedef long long int llint;` Is a bad practice. INT_MAX is "C", use https://en.cppreference.com/w/cpp/types/numeric_limits. Naming variables "p" is not helping readability. Name variables after WHAT the represent with full names. For looping over vectors, use https://en.cppreference.com/w/cpp/language/range-for (if you don't need the indices, and just the values). Replace `min` with `std::min_element`. And remove `using namespace std` from your code. — Pepijn Kramer, Dec 25 '22 at 19:07
Also watch this : [naming is hard lets do better](https://www.youtube.com/watch?v=MBRoCdtZOYg) from cppcon — Pepijn Kramer, Dec 25 '22 at 19:08
@PepijnKramer I do agree, but this naming is just for writing the faster code. As you realized it is a Code Force problem. by the way I Edited my question in my number 6. i realized this code accepted on server but on my machine takes long time. very strange to me. thanks though — Azzurro94, Dec 25 '22 at 19:15
Code will not be faster or slower by giving it bad or good names, the final compiled code doesn't care. But good naming will help readability and understandability. Good code reads like a story (or at least a cooking recipe). And naming should just be one of those habits to learn yourself. As said before : don't use code force to teach yourself C++. Just to have fun solving puzzles. — Pepijn Kramer, Dec 25 '22 at 19:25

score 1 · Accepted Answer · answered Dec 25 '22 at 19:27

Thanks to all guys that commented and helped me to figure out the issue. I realized that the reason that I have slow performance was Debug Mode. So I changed it to Release Mode and it works in less than 2 seconds. There is a similar question, may help you more. I used Visual Studio C++ on Windows 10

iterator dereferencing cost a huge time

1 Answers1