how much does array size affect compiling speed?

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?

The program is in this message

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.

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? :confused:

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

Quote:

---

Originally Posted by 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.

---

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.

Quote:

---

Originally Posted by 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? :confused:

---

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.

Quote:

---

Originally Posted by GCDEF

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

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

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:

Code:

---

{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:

Code:

---

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):

Code:

---

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

Code:

---

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?

Quote:

---

Originally Posted by VladimirF

However, this makes NO SENSE at all:

Code:

---

{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):

Code:

---

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

Code:

---

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?

Quote:

---

Originally Posted by larry burns

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:

Code:

---

{
  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

Quote:

---

Originally Posted by Paul McKenzie

C++ has rules:

Code:

---

{
  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

Quote:

---

Originally Posted by larry burns

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

Quote:

---

Originally Posted by Paul McKenzie

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 ?

Quote:

---

Originally Posted by larry burns

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

---

You could post your most current code…

One more comment. This code fragment:

Code:

---

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):

Code:

---

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;
        }
    }
}

---

thanks again for the suggestion!!! Heres the current code. I think the problem may be solved! I was able to get 500 n_simulations in only 5 minutes, which is about 10 times the previous speed. I'll now include the rest of the program that I didn't include earlier and see if it still works

You still have a few

Code:

---

{
    int t = 1;
}

---

left in your code. I thought you said that you've fixed it...

Few more comments?
Your code has a LOT of levels of nestedness (is that a word?), so whatever you can do to reduce it – please do.
Your statement:

Code:

---

if( n_simulations != 0 )

---

is right after n_simulations is initialized with 1 – just remove it.

I should have stated earlier – never EVER modify loop counter inside the loop (other then for regular step). You are making it impossible to read your code.

Code:

---

for ( double f = 0; f < 1; f = f + .004 )
{
    if( (x_value) < f + .004 && (x_value) >= f )
    {
        x = -(n_size - (2 * n_size * f) - 1);
        f = 1;
    }
}

---

is the same as

Code:

---

for ( double f = 0; f < 1; f = f + .004 )
{
    if( (x_value) < f + .004 && (x_value) >= f )
    {
        x = -(n_size - (2 * n_size * f) - 1);
        break;
    }
}

---

without forcing a reader to follow the usage of variable f to see why it needs to be set to 1.

Now look at this loop:

Code:

---

for ( int j = 1; j < 500; j++ )
{
    for ( int e = 0; e < 250; e++ )
    {
        for ( int f = 0; f < 250; f++ )
        {
            if( island[e][f] == j )
            {
                IslandSize[j - 1]++;
            }
        }
    }
}

---

What do you need the outer loop for? You are running through you 250*250 matrix (it’s already 62,500 iterations) 500 times, without changing anything!
Isn’t it pretty much the same as:

Code:

---

for ( int e = 0; e < 250; e++ )
{
    for ( int f = 0; f < 250; f++ )
    {
        IslandSize[island[e][f] - 1]++;
    }
}

---

only 500 times slower?

In addition, this loop is indeterminate as to how many times it will execute:

Code:

---

for ( double f = 0; f < 1; f = f + .004 )

---

Never, never, never use doubles as loop counters!

The reason is that doubles are not exact. When you add 0.004, there is round-off error involved, since 0.004 cannot be represented exactly as a binary floating point number. So when you add 0.004, the value of f is not exact.

Now, how many times will the loop run? You don't know due to the round-off error.

Always use integers for loop counters. The loop should be rewritten:

Code:

---

double f;
for (int fInt = 0; fInt < 1000; fInt += 4)
{
  f = (double)fInt / 1000.0;
  // now do your calculations using f
//...
}

---

Regards,

Paul McKenzie