speed of vector filling: Matlab vs C++

[roym]

Hello,

I recently (2 months ago) started learning C++. Before that, I always worked with Matlab (2-3 years). People always use to say that Matlab is slower than C++, because Matlab is interpreted and C++ compiled, which is (according to most people) almost by definition faster. Therefore, with the little knowledge I have now of C++, I did a test where I filled a vector of 1e9 (1 billion) elements in C++ and in Matlab, and measured the time it took for both Matlab and C++. The code for both is shown below:

C++

#include<iostream>
#include<vector>
#include<chrono>

using namespace std::chrono;

// fill vector
void vector_fill(std::vector<int>& somevector){

        for (int i=0; i<somevector.size(); i++){

                somevector[i] = i;

        }

}

int main(){

        // start clock
        auto start = high_resolution_clock::now();

        // pre-allocate vector
        std::vector<int> myvector(1000000000);
        vector_fill(myvector);

        // stop clock
        auto stop = high_resolution_clock::now();

        // calculate time
        auto duration = duration_cast<microseconds>(stop - start);

        // print time
        std::cout << duration.count() << std::endl;

}

The C++ code was compiled using: g++ -O3 vector_fill.cpp.

Matlab:

% pre-allocate vector
myvec = zeros(1,1e9);

% fill vector
tic
for i = 1:size(myvec,2);
   
    myvec(i) = i;
    
end
toc

This task takes Matlab 4.1 seconds (average over multiple runs). Whereas it takes C++ 4.6 seconds (average over multiple runs). It surpises me that C++ is "slower" than Matlab in filling this vector. I think the difference of 12% is also significant. How can this be explained? And is there a way to improve the speed in my C++ code?

Thanks!

Regards,
Roy

[keskiverto]

How does C++ Standard Library algorithm 'iota' run in your system?

std::vector<int> myvector( 1000000000 );
std::iota( myvector.begin(), myvector.end(), 0 );

See http://www.cplusplus.com/reference/numeric/iota/

Which part of time is used by memory allocation,and which by the fill?

[lastchance]

On my PC:
with no optimisation: 7.04 seconds
with -O3 optimisation: 1.38 seconds


If using iota instead:
with no optimisation: 9.60 seconds
with -O3 optimisation: 1.38 seconds


BUT ...

Note that your matlab code CREATED the vector BEFORE you started timing, whilst your c++ code created the vector AFTER you started timing. That's not a fair comparison, is it?

If I create the vector BEFORE I start timing, then I get
with -O3 optimisation: 0.47 seconds

It's the initial memory allocation that's taking the time here. See @Kesiverto's comment:

Which part of time is used by memory allocation,and which by the fill?

[Thomas1965]

In your for loop you should change i++ to ++i;
I tried with 100'000'000 ints since my PC didn't have enough RAM for your billion and the difference is amazing,

Time for i++: 2298337
Time for ++i: 1435584

[roym]

Thanks keskiverto for your fast response.

I ran the program again and it appears that 3.9 seconds are spend in pre-allocating memory for the vector, and less than 0.5 seconds for filling the vector. Is that normal that it takes so long for the std::vector to allocate space?

With the use of std::iota it takes just as long as with the simple for loop.

[roym]

Thanks everyone for responding.

@lastchance
You are right that I did not include the pre-allocation of the vector in Matlab. But Matlab does the pre-allocation in 0.01 seconds. So that is negligible. It appears that the time it takes to fill the vector in the loop is roughly 0.5 seconds for both of us. However, apperantly you pre-allocate the vector much faster than I do...

@Thomas1965
I changed i++ to ++i, but it does not make any difference. But that is since all time is spent in the pre-allocation of the memory for the vector.

So it appears that the for loop in C++ is much faster than in Matlab. Whereas the pre-allocation in C++ takes much more time compared to Matlab.

[lastchance]

I think Matlab grabs a lot of memory upfront. (The latest incarnation expects you to have at least 8GB RAM on your machine). Assuming the operating system was willing to yield that up, then sub-letting 4GB to one array (i.e. 10⁹ ints) isn't a problem.

On the other hand, asking for a vector to be constructed at run-time with 4GB of data is a pretty greedy request of the operating system and, depending on what else is running, might end up with paged memory.

roym wrote:

However, apperantly[sic] you pre-allocate the vector much faster than I do...

Did you have Matlab already running when you tested your C++ code? Not much memory left if you were.

[roym]

No, I closed everything when I ran the C++ code.

[jonnin]

Matlab's slowness is not in trivial operations. Its more of 'program wide'. When I wrote my "M to C" conversion, I was seeing a full multiplier faster (I forget exactly, 3-4 times faster from memory) in the C++ to do the same things, but that was over an entire program that did a lot of complicated things. And, we had the compiler, so we could compile the matlab to an executable.

Taking an honest look back on that work, I would chalk the speed I got up to a few key points:
1) I am a human. I knew where in my code that I needed high quality numerical approaches and where ignoring them was fine. Eg, my work was in controls, and I knew that my matrices were stable, well conditioned, whatever other words and didn't need all that pre-work to normalize and adjust them that is done by default in a generic matrix package.
2) I had a better memory manager. I wrote my own and apart from program start and program end, I did not create/destroy/copy anything unnecessary.
3) I frequently doctored the code to generate transposed results of intermediate values. This let me do an alternate multiply that could iterate sequentially (in memory) across the data, rather than page-faulting across rows. I did other tweaks on the intermediates as well, but don't recall much now...
4) My matrix data was one dimensional, and I exploited that every which way from memcpy to reshape. I think Matlab internally uses 2-d, but I don't know that for sure. I know it grows in either dimension without any complaint; mine allowed for a resize but I had coded it to avoid those at all costs.

Over the long haul it added up to massive time savings. This was many years ago, though. Matlab is constantly improving. All I know to tell you if you want to really compare it is to get the best matrix package you can find and write something significant in both. Or write your own matrix stuff, but that is a lot of work; I had over a year in my package and it could only do the things I needed, a tiny subset of what M can do.

[roym]

Thanks for your response jonnin.

"Matlab's slowness is not in trivial operations." Apperantly not :)

"All I know to tell you if you want to really compare it is to get the best matrix package you can find and write something significant in both". As soon as my C++ skills let me, I will write something "significant".

[jonnin]

^^ The actual c++ wrapper is pretty small -- its going to be 99% library code to call the matrix library stuff. hopefully in math terms, eg z = A*B using operator overloads, or simple math words like e = A.eigenvals(); etc.

Its a big assumption, but assuming matlab has kept up with the universe, its likely multi-threaded inside, so to beat it now (I was doing this work before multi-core cpus existed, and right on the edge of them coming out but they were not in our embedded systems so no point in growing into it) you will need to use threading well on top of the points I gave.

And test compiled matlab to compiled c++ is more fair. The interp interface is for messing around to do math like a calculator, not for real work.

Its probably been done already, so you can skip all that and look at some results online most likely. Just don't use any from the matlab site, get a neutral 3rd party study.

If you want to beat it by a large margin, the memory management is the key. Excess copying, creating, destroying large matrices is where so much time is buried. The algorithms to do the computations etc are all the same... everyone knows them. And matlab has the 'soft type' problem, it has to deal with that.