2D Vectors Cause High Memory Problem - Why?
I'm C++ beginner and converting my Python code into C++. (calculation speed problems)
I use Visual Studio as C++ IDE.
The problem is that memory usage is diverging and rising insanely. Here is what the code looks like:
As you see, I create big 2d vectors and deal with multiplications of them. But memory usage is too high, even worse than Python.
I've searched C++ books and learned that I must destruct them. But I can't. I mean I need them at the and of my process(I'll write them on a .dat file). So how can I overcome this issue?
If I destruct them, how can I work with them? It sounds weird. My humble opinion is to create a big function and do my job in it, and therefore I would not deal with destructing variables.
Regards,
Ordinary
I use Visual Studio as C++ IDE.
The problem is that memory usage is diverging and rising insanely. Here is what the code looks like:
|
|
As you see, I create big 2d vectors and deal with multiplications of them. But memory usage is too high, even worse than Python.
I've searched C++ books and learned that I must destruct them. But I can't. I mean I need them at the and of my process(I'll write them on a .dat file). So how can I overcome this issue?
If I destruct them, how can I work with them? It sounds weird. My humble opinion is to create a big function and do my job in it, and therefore I would not deal with destructing variables.
Regards,
Ordinary
Last edited on
A vector of 250 double values shouldn't take up much more than (250 * size of double ) bytes, which would be about 2000 bytes (assuming an 8 byte double).
If you've got 250 of them, that'd be about 500000 bytes. Half a MB. This is not a lot of memory.
Some more memory will get eaten up when you're copying vectors around (push_back) , but still not much.
You can pre-reserve the memory you need when you create a vector, to make it the right size ( reserve function ) but when you say high memory, how much do you mean?
You're building them on the stack. They get destructed automatically at the point that they go out of scope. That's not something you need to worry about in the above code.
If you've got 250 of them, that'd be about 500000 bytes. Half a MB. This is not a lot of memory.
Some more memory will get eaten up when you're copying vectors around (push_back) , but still not much.
You can pre-reserve the memory you need when you create a vector, to make it the right size ( reserve function ) but when you say high memory, how much do you mean?
| I've searched C++ books and learned that I must destruct them. |
You're building them on the stack. They get destructed automatically at the point that they go out of scope. That's not something you need to worry about in the above code.
Last edited on
| ordinary wrote: |
|---|
| big 2d vectors and deal with multiplications of them |
Do you mean multiplication of matrices? Bare C++ does not have them.
You can, with some effort write your own based on containers, but making them work well is not really a beginner task, and there are plenty of popular matrix libraries for C++.
For example, http://www.boost.org/doc/libs/1_66_0/libs/numeric/ublas/doc/index.html
|
|
or http://eigen.tuxfamily.org
|
|
(if you were to write your own, you'd need a class that holds a 1D vector<double> or valarray<double>, with accessor functions that translate between (row,column) and the position in that 1D index, as in, row*columns_total+column)
did you compile in release mode?
push back can cause some mild memory issues (mostly performance related) if you did not reserve. I don't know the algorithm but it attempts to second guess you, so say it allocated 10k bytes and you needed 1 more, it does not allocate 1 more byte and the copy the data, it allocates maybe 1k (this amount is what I don't know, I think its a % of the current size?) more so you can grow for a while before it needs to do that big slow resize operation again. Could be that if you have 1/2 a MB almost and needed just a little more that it pulls down 2/3 or something, getting much more than it needs. Remember that to increase the size of a vector, the under the hood work is to allocate a new block of memory (more than doubles your memory in use for a moment) and then copy all the data to the new block before release the old block. Its slow and its ugly and its better if you don't do this very much.
Also because its a 2-d construct, the above effects may be multiplied somewhere.
I am a huge fan of keeping it 1-d; there are so many places this allows better performance, and 2-d has almost no advantages. You can transpose in place, resize, reshape, iterate directly (consider AX where X is a constant like 5.0 instead of a vector or matrix) for many algorithms, copy faster, and gain many other lifts using the 1-d approach.
so, to recap...
go 1-d
try using a reserve statement or just a declare
vector<double> m(maxrows*maxcols); //this reserves enough space right off.
be sure to compile in release mode
avoid push back; use it if necessary, but avoid it when it isnt necessary.
and, as you make functions and classes for this stuff, avoid copying the data and unnecessary temporary variables with all that data.
push back can cause some mild memory issues (mostly performance related) if you did not reserve. I don't know the algorithm but it attempts to second guess you, so say it allocated 10k bytes and you needed 1 more, it does not allocate 1 more byte and the copy the data, it allocates maybe 1k (this amount is what I don't know, I think its a % of the current size?) more so you can grow for a while before it needs to do that big slow resize operation again. Could be that if you have 1/2 a MB almost and needed just a little more that it pulls down 2/3 or something, getting much more than it needs. Remember that to increase the size of a vector, the under the hood work is to allocate a new block of memory (more than doubles your memory in use for a moment) and then copy all the data to the new block before release the old block. Its slow and its ugly and its better if you don't do this very much.
Also because its a 2-d construct, the above effects may be multiplied somewhere.
I am a huge fan of keeping it 1-d; there are so many places this allows better performance, and 2-d has almost no advantages. You can transpose in place, resize, reshape, iterate directly (consider AX where X is a constant like 5.0 instead of a vector or matrix) for many algorithms, copy faster, and gain many other lifts using the 1-d approach.
so, to recap...
go 1-d
try using a reserve statement or just a declare
vector<double> m(maxrows*maxcols); //this reserves enough space right off.
be sure to compile in release mode
avoid push back; use it if necessary, but avoid it when it isnt necessary.
and, as you make functions and classes for this stuff, avoid copying the data and unnecessary temporary variables with all that data.
Last edited on
> The problem is that memory usage is diverging and rising insanely
as Repeater said, that code takes about 0.5 MB, which doesn't seem too much.
¿how are you measuring memory usage? also, the culprit may be somewhere else.
as Repeater said, that code takes about 0.5 MB, which doesn't seem too much.
¿how are you measuring memory usage? also, the culprit may be somewhere else.
Thank you everyone. Your instant help is really something for me.
I made a mistake in the post. It's not 250. Nx and Ny's are 248*249.
@Repeater: I've just calculated as you said: Nx*Ny = 61752. So, total memory is 61752*61752*8 = 30505476032 bytes ≈ 30.5 Gigabytes which has just made me laugh.
@Cubbi: Yes I create big matrices and solve them. I can barely do it in Python but matrices are small. In Python Nx and Ny's are 78*79=6162 at maximum. It takes much time. So I decided to move C++. Thank you for your matrix libraries.
@jonnin:
I don't understand. I just install Visual Studio. Didn't change default installation settings. Maybe I just chose C++. I build code via Ctrl+Shift+B and, Debug x64 Local Windows Debugger. And there I see memory line chart goes insane. By the way, thank you for your 1D advice.
@ne555: Sorry for my mistake. I changed it in the first post.
I made a mistake in the post. It's not 250. Nx and Ny's are 248*249.
@Repeater: I've just calculated as you said: Nx*Ny = 61752. So, total memory is 61752*61752*8 = 30505476032 bytes ≈ 30.5 Gigabytes which has just made me laugh.
@Cubbi: Yes I create big matrices and solve them. I can barely do it in Python but matrices are small. In Python Nx and Ny's are 78*79=6162 at maximum. It takes much time. So I decided to move C++. Thank you for your matrix libraries.
@jonnin:
| did you compile in release mode? |
@ne555: Sorry for my mistake. I changed it in the first post.
c++ can be compiled in a debug mode, which is the default in visual studio for new projects. Debug compiles have optimizations turned off and burn extra memory for hidden items that allow you to step into and debug the code. Release compiles remove all this and turn on optimizations. Also, a lot of matrix processing, including multiplication, can be done in parallel with threading, which cuts the time significantly for larger problems. Somewhere there is a configuration that will let you compile in a default release build, its a drop down or it used to be... and you can hand-pick the settings to make it even better, but that takes some black magic and a lot of trial and error / experience to get right.
way back when I was coding seriously (I am not anymore) release mode could get multiples of speed faster for math type work (cpu and memory bound problems, but mostly cpu). For some code you can barely notice (a gui form that has a few text fields and buttons, you can't tell the difference).
after MB, by the way, use powers of 2 or its way off. Its actually less than 30GB, but more than 30 billion bytes, because 1 MB is actually 2^20 not 10^6. Here its not critical but you are off by more than 1GB.
there are better algorithms than the N^3 multiply by brute force. But if you want to use the brute force one (its easy to code), then I highly recommend you transpose so that both matrices iterate across rows, not columns. this will cut your page faults way down and generally improve performance. Ideally, generate one matrix as transposed to begin with, to save that effort. The up front cost of the transpose is more than earned back.
Of course, if you use a good library, it will do all the good stuff for you. But some of them do too much, checking condition numbers, normalizing, and more that may, or may not, be needed. IIRC for example the classic clapack required you to do a LU factor and normalize before a multiply... it took all day just to get in the format it wanted so it could shave a few ms off the multiple routine. I ended up writing my own multiply as we were in controls and our stuff was stable and well conditioned.
way back when I was coding seriously (I am not anymore) release mode could get multiples of speed faster for math type work (cpu and memory bound problems, but mostly cpu). For some code you can barely notice (a gui form that has a few text fields and buttons, you can't tell the difference).
after MB, by the way, use powers of 2 or its way off. Its actually less than 30GB, but more than 30 billion bytes, because 1 MB is actually 2^20 not 10^6. Here its not critical but you are off by more than 1GB.
there are better algorithms than the N^3 multiply by brute force. But if you want to use the brute force one (its easy to code), then I highly recommend you transpose so that both matrices iterate across rows, not columns. this will cut your page faults way down and generally improve performance. Ideally, generate one matrix as transposed to begin with, to save that effort. The up front cost of the transpose is more than earned back.
Of course, if you use a good library, it will do all the good stuff for you. But some of them do too much, checking condition numbers, normalizing, and more that may, or may not, be needed. IIRC for example the classic clapack required you to do a LU factor and normalize before a multiply... it took all day just to get in the format it wanted so it could shave a few ms off the multiple routine. I ended up writing my own multiply as we were in controls and our stuff was stable and well conditioned.
Last edited on
| ¿do you have sparse matrix? |
Yes, it's sparse. 5 diagonal matrix. I mean there are 5 diagonal bands.
@jonnin
Thank you for your valuable post. I turned debug mode off, then built in release mode. Still it consumes too much memory.
As far as I understand I need to convert my "HUGE" 5 banded sparse matrices into 1D vectors, and find some methods to solve them which I'm currently on it.
Thank you for your valuable post. I turned debug mode off, then built in release mode. Still it consumes too much memory.
As far as I understand I need to convert my "HUGE" 5 banded sparse matrices into 1D vectors, and find some methods to solve them which I'm currently on it.
Since they are sparse, you should create (or find) a class that will handle a sparse matrix. The fact that you have just 5 diagonal bands means that you might be able to write your own that's very efficient.
This problem illustrates why its important to do a back-of-the-envelope calculation on your data size when that size starts to get big.
This problem illustrates why its important to do a back-of-the-envelope calculation on your data size when that size starts to get big.
Topic archived. No new replies allowed.