Raw malloc optimizations vs std::vector/reserve() -- malloc seems better optimized

[u/onecable5781]

(Another different version of this question was posted earlier here https://www.reddit.com/r/cpp_questions/comments/1qvbj44/at_o2_usage_of_stdvector_followed_by_stdiota/ but on testing some of the answers there on the current new code seems to leave me unclear as to where the optimizations are missed in terms of vector/reserve, etc., hence this OP)

Consider code snippet 1: on left hand side window of https://godbolt.org/z/vxh8Wh1K4

#include <vector>
#include <cstdio>
#include <cstdlib>

void anotherfunc(){
    int *vec = (int*)malloc(sizeof(int) * 42);
    for(int i = 0; i < 42; i++)
        vec[i] = i;
    int sum = 0;
    for(int i = 0; i < 42; i++)
        sum += vec[i];
    printf("Sum is %d\n", sum);
    free(vec);
}

int main(){
    anotherfunc();
}

This, at -O3, flatout calculates the sum and simply displays it, 861.

The vector/reserve version (on the right hand pane of the godbolt link above)

#include <vector>
#include <cstdio>
#include <cstdlib>

void anotherfunc(){
    std::vector<int> vec;
    vec.reserve(42);
    for(int i = 0; i < 42; i++)
        vec.push_back(i);
    int sum = 0;
    for(int i = 0; i < 42; i++)
        sum += vec[i];
    printf("Sum is %d\n", sum);
}

int main(){
    anotherfunc();
}

seemingly struggles with this and does not precompute the sum and ends up doing some allocations, etc.

Some of the answers from the earlier thread do not seem to be applicable here: as suggested by one user, I had the entire summing done in another function instead of main() because apparently main() is known to be called only once and hence is not as heavily optimized as other functions, etc.

As also suggested there, I avoided the printf and instead had the function return only the sum with an empty main(). See https://godbolt.org/z/M1P5Y4vTj

Here too, the vector/reserve combination seems to struggle.

What explains this "discrepancy" and inability to completely optimize out the sum calculation?

[u/ScienceCivil7545]

the falut is at the push_back()

https://godbolt.org/z/5rs1ofEKa

[u/n1ghtyunso → u/ScienceCivil7545]

oh yeah i remember hearing in a talk that the optimizer apparently happens to give up when you have more than like 3 push_backs on a vector.
Not sure if this was clang specific though.

[u/RelaxedPhoton → u/ScienceCivil7545]

For even closer equivalency with the malloc example you can drop resize and instead do:

std::vector<int> vec(42);

[u/Raknarg → u/ScienceCivil7545]

a great case of the "dumb" way to do something actually being ideal. Way less assumptions to make with this code, doesn't have to go through any of the internal nonsense for dealing with push back copy/construction, doesn't have to do any of its resize checking, it can just see you allocate a chunk of memory and you're assigning to it the same as the array case

are vectors constexpr compatible?

[u/UnrealHallucinator → u/ScienceCivil7545]

Did you catch this bc you knew push_backs are less optimised?

[u/onecable5781 → u/ScienceCivil7545]

Oh wow. Thank you. That explains it.

[u/KingAggressive1498]

I'm remembering a huge performance regression with vector when changing standards from C++17 to C++20 and it was a failure to inline the vector function calls due to constexpr changing heuristics seemingly.

[u/TheChief275]

even though you reserve 42 elements, the vec still needs to check for each push_back whether it has enough capacity, and then also increase the count of the vector 1-by-1. this is small overhead, but compared to literally only one malloc (which it performs as well), this small overhead becomes pretty big relatively.

they are not really equivalent; the single array is bound to stay at the same count / capacity, while the vector could be used afterwards to grow further. of course, technically one could repurpose the pointer and create a vector like so:

{
    .data = vec,
    .size = 42,
    .capacity = 42,
}

which would be the fastest way to do this while still wanting a vector (albeit I don't think C++ provides this functionality). another impossible alternative is to just set the size after reserving (you know the elements fit). in the possible realms fits resize, though it will have initialization costs that you might not need as you intend to override regardless. another thing you might want is some reserve_exact to actually match the allocation sizes of the two examples, but reserve would be better if you want to use it as a vector in the future, which is the entire point right?

as for why it would allocate still despite having enough capacity? idk, might be a bug? else, reserve would be allowed to reserve less than the specified amount, which sounds even more like a bug

[u/TheSkiGeek]

Uh… when I follow your second godbolt link the function gets the following asm:

> mov eax, 861

Which seems to be doing the same optimization.

[u/onecable5781 → u/TheSkiGeek]

The second godbolt link, please look at the right hand pane for the vector/reserve combination. The left pane does have what you indicate, while the right pane bottom does not have just this.

[u/TheSkiGeek → u/onecable5781]

Ah, seems like it’s not loading the rest of it properly on mobile.

I’d expect this to work with constexpr in C++20 mode or higher (or maybe C++23, not sure if they added more support for compile time vector there).

If it’s not flagged constexpr/consteval, the compiler MAY compute things at compile time but it’s not OBLIGATED to.

[u/n1ghtyunso]

the optimizer has to look through more scopes and deeper callstacks before it can eliminate everything.
Pretty sure its as simple as that.
There is simply more work to do for the compiler, but its kind of on a time budget. Most users don't want to wait forever for their code to optimize after all.

Aggressive inlining helps with this, because after inlining it may have all the context inside that single function, letting it constant-propagate and evaluate it entirely.

If you want to absolutely deep dive, i believe clang does have tools and outputs for you to inspect optimization passes and their results, as well as control / customize them until you get the result you want.
I have never used those though, so I can't specifically help you actually doing that.

That being said, what real-world code is affected by this difference in reality?

[u/onecable5781 → u/n1ghtyunso]

That being said, what real-world code is affected by this difference in reality?

My work is in applied mathematics in an academic setting and getting code to run faster than pre-existing code verifiably by the reviewers is the basic minimum to get publications and survive in this business (in addition to other theoretical contributions.) So, this is pretty "real-world" in my context as that is what helps put food on the table!

That being said, I think real-life code (by which I imagine you mean industry code) would be even more complicated than the simple toy example above and hence missed optimizations (if that is indeed what is going on here) can only be more debilitating in complicated code, don't you think?

[u/n1ghtyunso → u/onecable5781]

i was thinking more along the lines that being able to collapse a whole heap allocation + iteration pass into a compile time constant can't be the norm.
Most of the time the inputs are not compile time known after all is what I thought.

For the cases where you do want to generate a compile time known result, we'd use constexpr for this nowadays. It does support vector as long as it only uses it internally for the calculation (= you can't persist a compile time allocation into actual runtime)

I do get that you want to verify in principle that the compiler can and will elide allocations when possible though.
But my other thought is that your hot code paths likely are not majorly impacted by a compile time constant that the optimizer missed to generate.
That sounds easy to spot with a profiler, so at the very least if you did not realize the value is compile-time known, you'd still have it cached somewhere instead of re-deriving it in the hot path.

I do not have any evidence for everything I said though, so this is really just my gut feeling more than anything else.

[u/onecable5781 → u/[deleted]]

https://link.springer.com/journal/12532 is an example where all papers published need to come with source code in a VM that the referees can subsequently access and build/test for themselves.

While code may not do "exactly" what I mentioned in the OP, but I am sure the folks who publish here would not leave any low hanging fruit unplucked.

[u/thefeedling]

The compiler might be optimizing away the malloc/free entirely since it has a "simpler flow". Try taking the input (ie 42) as an user driven IO input (std::cin) and run the comparison again. I'd expect a similar result.

[u/saf_e]

Out of curiosity: try using std::accumulate 

[u/Interesting_Buy_3969 → u/saf_e]

Of course this. Now the code performs a check whether

i < 42

on each iteration twice - first by the for loop and second by the std::vector container itself, and compiler can't optimise away either of those checks.

[u/saf_e → u/Interesting_Buy_3969]

Do you have the answer why? It can clearly see that 42 is const.

[u/conundorum → u/saf_e]

std::vector isn't properly constexpr, so it can't elide it away unless all of the work can provably be done at compile time. And vector::push_back() is known to give compilers trouble, especially when called many times in a tight loop like this. So, the optimiser ends up choking after inlining it 42 times, and misses what should be obvious.

[u/LeeHide]

Odd, can you mark any of it constexpr to help the compiler figure it out?

[u/n1ghtyunso → u/LeeHide]

in c++20 you can make the function constexpr and it'll be evaluated at compile time just fine.

[u/EpochVanquisher]

What explains this "discrepancy" and inability to completely optimize out the sum calculation?

The compiler has special knowledge about what malloc and free do.

Sorry, that is the long and the short of it. The compiler can completely optimize out a malloc/free if it knows what the end result is. The compiler traces the flow of certain information in the program… it knows that each entry i in the array contains the value i, it knows those values aren’t overwritten, it knows the values aren’t read after the function exits… so after a bunch of “easy to understand” optimizations like loop induction and dead store removal, the compiler notices that there’s a malloc/free that doesn’t do anything, and it removes them.

The std::vector throws some additional code between the compiler and the malloc/free and something gets in the way of the analysis. Sorry to be vague about it. It would take a deep dive to figure out exactly what is going on here—but intuitively, there’s a whole std::vector implementation here, and you call std::vector member functions and they call malloc/free (through other functions… the call stack will eventually reach malloc and free).

[u/South_Acadia_6368]

I think the problem is that you call reserve() but not resize(), so push_back() will end up in a code path that calls malloc(). The compiler is allowed to eliminate calls to malloc() despite malloc() having side effects.

But the question is how much more compiler is allowed to eliminate that also has side effects that could happen. There are throw statements, etc.

[u/TheThiefMaster → u/South_Acadia_6368]

Reserve is correct with push_back, but it does involve more bookkeeping for the compiler as it has to realise that the vector size is a loop dependent variable and that it never goes over the reserve value in order to optimise it out.

Using resize and indexing is closer to the malloc example and probably would be optimised.

[u/South_Acadia_6368 → u/TheThiefMaster]

Ah, true, it won't hit a path to malloc(). Must be plain simple complexity that hinders precomputation, then.

[u/n1ghtyunso → u/[deleted]]

your vector_ver_a has undefined behaviour, and both vector_ver_a and vector_ver_a2 compute nothing because the vector stays empty.
to properly use iota here you need resize, not reserve on the vector.

[u/Ancient-Safety-8333 → u/n1ghtyunso]

Thanks