how much does array size affect compiling speed?

[larry burns]

so my current program uses two array variables, each of size 250x250, and I use the ofstream function to output the stuff on Notepad. When I first ran it with each array variable of size 50x50, I didn't have any problems and it didnt take too long to run. But when I increased the size of each of them to 250x250, I'm having all sorts of problems. When I ran the simulation (each simulation runs the program) too many times, the program crashed. I then tried eliminating one of the variables, and while the program runs, it takes ridiculously long to run. It would take 23 hours! to do the number of simulations I want, whereas I think it only took 10 minutes for the 50x50 case.

I attached the relevant part of the program in this message. The parts including:

if ((x_value)<0.25)
{x--;
LeftCount++;


For the left, right, down, and up cases are negligible since they don't affect the 'island[][]' array variable
So what can I possibly do to speed up the program? Do I have no choice but to use a smaller array size?

[larry burns]

The program is in this message

[OReubens]

it depends what it does...
Increasing the size of an array itself won't make much of a difference. but the amount of work done can increase dramatically.
If you have an N*M type problem, then increasing from 50x50 to 250x250 will mean 25times more work to be done, so you can expect at least a 25fold increase in time to execute.

if your problem is exponential in nature, it could be a lot worse.

But it gets worse... while 50x50 is fairly small it means you can probably still fit all of the data into the L2 CPU cache (maybe even the L1 cache), while with 250x250 this will no longer be the case.

[VictorN]

1. Your code cannot compile
2. You didn't show declarations/definitions of a lot of the variables
3. .txt file is not the best to post code snippets: you should either attach .cpp, .h files (or a whole project in zip archive) or post code snippets directly using Code tags around them
4. What do all these magic numbers (0.004, .5, 0.25, 0.75, ..., 10, 125, 124, ..., 116, ...) mean?

[GCDEF]

5. What does your problem have to do with compiling speed?

[larry burns]

it depends what it does...
Increasing the size of an array itself won't make much of a difference. but the amount of work done can increase dramatically.
If you have an N*M type problem, then increasing from 50x50 to 250x250 will mean 25times more work to be done, so you can expect at least a 25fold increase in time to execute.

if your problem is exponential in nature, it could be a lot worse.

But it gets worse... while 50x50 is fairly small it means you can probably still fit all of the data into the L2 CPU cache (maybe even the L1 cache), while with 250x250 this will no longer be the case.

whats the L2 CPU cache? The last time i took a c++ class was 2.5 years ago, and I don't think I learned about that.

1. Your code cannot compile
2. You didn't show declarations/definitions of a lot of the variables
3. .txt file is not the best to post code snippets: you should either attach .cpp, .h files (or a whole project in zip archive) or post code snippets directly using Code tags around them
4. What do all these magic numbers (0.004, .5, 0.25, 0.75, ..., 10, 125, 124, ..., 116, ...) mean?

the code does compile. It just crashes if I have two 250x250 array variables. I didn't list the entire code in that message, since I don't think you guys want to see all of it, but I'll attach it in this message anyways

.004 is 1/250 and .5, .25, .75, 1 are the the ranges used to assign the random movements based on the random number generator. They don't affect the array.

5. What does your problem have to do with compiling speed?

Thats what I want to know? I don't know much about arrays



I've noticed that the program runs significantly slower as the value of j, which is related to n_simulations, increases. It runs fast, as expected, for the first 10 values or so for j, then runs ALOT slower as j gets in the range of 50, but it may get slower before that, as i havent checked the speed for j between those values

[larry burns]

that previous attachment is wrong. the correct one is in this message. I fixed one of the if statements, as the previous one evaluated a few of them as 'if island[][250]', but island only goes from 0 to 249. But even with the corrections, it runs only a little faster, and would still take about 16 hours to have 11,250 n_simulations, as my professor wants

[VladimirF]

Your code formatting is very… hmmm… artistic?
None of the formatting styles I saw places an open bracket on the same line as the next statement.
I see how you can make an exception for a construct that fits nicely on one line (for compactness).
However, this makes NO SENSE at all:

{int t=1;}

You define a local variable t that goes out of scope right away. (This happens more than once in your code).
Here is another senseless line:

void close();

It declares a void function close(), which is not defined in your code, but that’s OK – it is never called either

Now one thing about efficiency. You have this nested loop (a few times):

for (int a=0; a<250; a++)
{    
	for (int b=0; b<250; b++)
	{ 
		if (island[125-y][x+124]>island[a][b])
		{t=0;}

	}
}

Note that inner part is executed 62,500 times.
Note also that after the very first time you set t to 0, the rest of those loops can’t possibly make any difference. See if you can break out of there.

This whole thing is triple-nested into

for(int i=0;i<n_walks;i++)// 'FOR' STATEMENT IS A TYPE OF LOOP
{
	for (int f=125; f>-116; f=f-10)
	{
		for (int g=125; g>-116; g=g-10)
		{

which produces 500,000 * 25 * 25 = 312,500,000 iterations of the previous fragment. No wonder it takes long time!

Could you please clean up you code and repost here for further analysis?

[larry burns]

However, this makes NO SENSE at all:

{int t=1;}

You define a local variable t that goes out of scope right away. (This happens more than once in your code).



Now one thing about efficiency. You have this nested loop (a few times):

for (int a=0; a<250; a++)
{    
	for (int b=0; b<250; b++)
	{ 
		if (island[125-y][x+124]>island[a][b])
		{t=0;}

	}
}

Note that inner part is executed 62,500 times.
Note also that after the very first time you set t to 0, the rest of those loops can’t possibly make any difference. See if you can break out of there.

This whole thing is triple-nested into

for(int i=0;i<n_walks;i++)// 'FOR' STATEMENT IS A TYPE OF LOOP
{
	for (int f=125; f>-116; f=f-10)
	{
		for (int g=125; g>-116; g=g-10)
		{

which produces 500,000 * 25 * 25 = 312,500,000 iterations of the previous fragment. No wonder it takes long time!

Could you please clean up you code and repost here for further analysis?

what do you mean the t=1 goes out of scope right away? I need it there so it can run through the if(t!=0) part

Thanks alot for that suggestion to break out of the loop after setting t to 0. My program now runs faster, but its still ridiculously slow. It would now take 23 hours or so to run 11,250 n_simulations

how can I clean up the code? Sorry for the mess, but isn't it easier to read if I skip a line for the 'for' statements?

[Paul McKenzie]

what do you mean the t=1 goes out of scope right away? I need it there so it can run through the if(t!=0) part

C++ has rules:

{
   int t=1;
}

You declared an integer inside that block { } and called it "t". As soon as that block is exited (the } is reached), that "t" no longer exists. This is called "variable lifetime" or "scope".

Regards,

Paul McKenzie

[larry burns]

C++ has rules:

{
   int t=1;
}

You declared an integer inside that block { } and called it "t". As soon as that block is exited (the } is reached), that "t" no longer exists. This is called "variable lifetime" or "scope".

Regards,

Paul McKenzie

I made those changes. Also, I noticed I opened the ofstream too much, and that I'm better off opening the file once, writing everything, then closing after all the data is written.

With all those changes, the program runs slightly faster, but would still take 20 hours to run. Theres gotta be other problems

[Paul McKenzie]

I made those changes. Also, I noticed I opened the ofstream too much, and that I'm better off opening the file once, writing everything, then closing after all the data is written.

With all those changes, the program runs slightly faster, but would still take 20 hours to run. Theres gotta be other problems

The "problem" is that you have nested loops inside of nested loops inside of nested loops, etc.. Multiply those iterations, and you have to be in the millions of iterations occurring. What were you expecting?

Secondly, I have to agree with others about your formatting -- your code is very hard to read. For the sake of the others here, I've attached is a more coherently formatted version of your code, which you should be using.

Third, the main() function returns int, not void.

And lastly, you don't need a loop to initialize those arrays to 0. See the updated source code I've attached. Also, please take what I posted, and change it to what you have now. In other words, keep the formatting that I have and change the program to your current version without the "t" mistakes you had.

Regards,

Paul McKenzie

[larry burns]

The "problem" is that you have nested loops inside of nested loops inside of nested loops, etc.. Multiply those iterations, and you have to be in the millions of iterations occurring. What were you expecting?

Secondly, I have to agree with others about your formatting -- your code is very hard to read. For the sake of the others here, I've attached is a more coherently formatted version of your code, which you should be using.

Third, the main() function returns int, not void.

And lastly, you don't need a loop to initialize those arrays to 0. See the updated source code I've attached. Also, please take what I posted, and change it to what you have now. In other words, keep the formatting that I have and change the program to your current version without the "t" mistakes you had.

Regards,

Paul McKenzie

thanks alot for the improved formatting version of my program. Anyways, is there anything else I can do to improve my nested loops ?

[VladimirF]

Anyways, is there anything else I can do to improve my nested loops ?

You could post your most current code…

[VladimirF]

One more comment. This code fragment:

int t = 1;
for ( int a = 0; a < 250; a++ )
{
    for ( int b = 0; b < 250; b++ )
    {
        if( island[125 - y][x + 124] > island[a][b] )
        {
            t = 0;
            b = 1000;
            a = 1000;
        }
    }
}

made me think for a second: why 1000? Then I realized that this is how you are breaking from the loop.
There is a MUCH better way to break out of nested loop (well, even a goto would be better that this):

int t = 1;
for ( int a = 0; a < 250 && t == 1; a++ )
{
    for ( int b = 0; b < 250 && t == 1; b++ )
    {
        if( island[125 - y][x + 124] > island[a][b] )
        {
            t = 0;
        }
    }
}