Solved

problem with array memory allocation

Posted on 2003-11-11
11
493 Views
Last Modified: 2010-08-05
I'm using "new" to allocate a 4-dimensional array, however, when I checked the actual size of memory available, the memory consumed by the array allocation is not what I expected.

Here's the code:

...
MEMORYSTATUS stat;
GlobalMemoryStatus (&stat);
printf("beginning memory: %dBytes\n", stat.dwAvailPhys);

int calc_tbl = 13;
int** MaxVal = new int*[calc_tbl]; //collect attribute MaxVals
for (int i=0; i<calc_tbl; i++)
                MaxVal[i] = new int[2];
MaxVal[0][0] = MaxVal[0][1] = 8;
MaxVal[1][0] = MaxVal[1][1] = 52342;
MaxVal[2][0] = MaxVal[2][1] = 2646689;
MaxVal[3][0] = MaxVal[3][1] = 2971;
MaxVal[4][0] = MaxVal[4][1] = 2871;
MaxVal[5][0] = MaxVal[5][1] = 3;
MaxVal[6][0] = MaxVal[6][1] = 1636;
MaxVal[7][0] = MaxVal[7][1] = 1597;
MaxVal[8][0] = 817;
MaxVal[8][1] = 837;
MaxVal[9][0] = MaxVal[9][1] = 4;
MaxVal[10][0] = MaxVal[10][1] = 1273392;
MaxVal[11][0] = MaxVal[11][1] = 1557;
MaxVal[12][0] = MaxVal[12][1] = 6;

//initialize Freq[tblNo][branchNo][val][class]
float**** Freq = new float***[calc_tbl];
for (i=0; i<calc_tbl; i++)
{
    Freq[i] = new float**[2];
    for (int b=0; b<2; b++)
   {
        Freq[i][b] = new float*[MaxVal[i][b]];
        for (int tt=0; tt<MaxVal[i][b]; tt++)
      Freq[i][b][tt] = new float[3];
   }
   GlobalMemoryStatus (&stat);
   printf("after initial Freq[%d] memory: %dBytes\n", i, stat.dwAvailPhys);
}

...

The available memory after each allocation is much less than what I expected for my array allocation. Why? The problem is, my memory runs out when I thought I should still have enough memory.
0
Comment
Question by:sherong
  • 6
  • 4
11 Comments
 
LVL 49

Expert Comment

by:DanRollins
ID: 9721345
>> float**** Freq = new float***[calc_tbl];

Can you be serious about using a pointer to a pointer to a pointer to a pointer to a float?

The reason the table is taking up so much room is that for each float value, there are 24 bytes of pointers involved.

I suggest that you examine the needs of your program carefully.  It is very rare to actually need a 4-dimensional array.  A much more common situation would be a 2-D array of structures, but I can't really tell what your goal is from that code.

If you do actually need a 4-D array, then you can avoid all of the pointer-poiner-pointer-pointers by simply defining a simple list and calculating the correct array index, knowing the size of each dimension.  For instance, in a 2-D array,

float *pafTheFloats = new float[MAX_X * MAX_Y];

float GetValueFromArray( int x, int y )
{
       float fRet=  pafTheFloats[ (MAX_X*y) + c ];
       return (fRet );
}

Similar logic for a 3-D-Array:

float *pafTheFloats = new float[MAX_X * MAX_Y * MAX_Z];

float GetValueFromArray( int x, int y, int z )
{
       float fRet=  pafTheFloats[ (MAX_X*MAX_Y*z) +(MAX_Y*x) +z  ];
       return (fRet );
}

A 4D array is so seldom needed that I'll not bother to illustrate it unless you can convince me you actually need to use one.

If you use a scheme like this, your memory allocation will exactly match what you expect:  the total_number_of_floats * sizeof(float)

-- Dan
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 9721413
You are allocating a lot of little chunks of memory, which is challenging for the free store manager. You would improve the efficiency by allocating your memory in fewer hits.

The following approach does 13x2=26 calls to new and makes use of automatic variables for the MaxVal 2D array:
--------8<--------
const int tables = 13;
const int branches = 2;
const int classes = 3;

struct Classes {
float score[classes]; /* I'm guessing this contains scores?! */
};

int main()
{
        int MaxVal[tables][branches];

        MaxVal[0][0] = MaxVal[0][1] = 8;
        MaxVal[1][0] = MaxVal[1][1] = 52342;
        MaxVal[2][0] = MaxVal[2][1] = 2646689;
        MaxVal[3][0] = MaxVal[3][1] = 2971;
        MaxVal[4][0] = MaxVal[4][1] = 2871;
        MaxVal[5][0] = MaxVal[5][1] = 3;
        MaxVal[6][0] = MaxVal[6][1] = 1636;
        MaxVal[7][0] = MaxVal[7][1] = 1597;
        MaxVal[8][0] = 817;
        MaxVal[8][1] = 837;
        MaxVal[9][0] = MaxVal[9][1] = 4;
        MaxVal[10][0] = MaxVal[10][1] = 1273392;
        MaxVal[11][0] = MaxVal[11][1] = 1557;
        MaxVal[12][0] = MaxVal[12][1] = 6;

/* Allocate */

        Classes* Freq[tables][branches];
        for (int table = 0;table < tables;table++)
                for (int branch = 0;branch < branches;branch++)
                        Freq[table][branch] = new Classes[MaxVal[table][branch]];

/* .... */

/* Clean up */

        for (int table = 0;table < tables;table++)
                for (int branch = 0;branch < branches;branch++)
                        delete[] Freq[table][branch];

}
--------8<--------
0
 

Author Comment

by:sherong
ID: 9721453
The code I pasted was just a test sample, in my real codes, I have to dynamically allocate the array, as 3 of the dimensions: "tblNo, branchNo, val" are all unknown and have to be calculated on the fly every time. That's why I used the "new" operator and whole bunch of pointers, or otherwise I could have used fixed size array declaration.

Thanks Dan for letting me know where the memory was consumed. I'll try to change everything to 1-d array and calculate indexes then. Yes I do need 4-dimensional array (the whole logic is quite complicated so I can't explain too much), I guess with converting this 4D array to 1D, then I won't have the problem of occupying extra memory then?
0
 

Author Comment

by:sherong
ID: 9721546
There's still problem. I can't change it to 1D array, as one of the dimensions has different values (there's no single MAX_X in this dimension), as you can see from my sample code, one of the dimensions is calculated by MaxVal[], which is different for each Freq[]. So I can't declare the array as [MAX_A*MAX_B*MAX_C*MAX_D].

What do I do then? Please help.
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 9721585
> I'll try to change everything to 1-d array and calculate indexes then

Unless I'm mistaken, you've got a jagged array, which means that you'll need something like this:

--------8<--------
/*const*/ int tables = 13; // Not const
/*const*/ int branches = 2; // Not const
const int classes = 3;

struct Classes {
float score[classes]; /* I'm guessing this contains scores?! */
float operator[] (int index) {return score[index];}
};

int main()
{

/* Need to allocate */

        int *MaxVal = new int[tables*branches];

/* Assign */

        MaxVal[0*branches+0] = MaxVal[0*branches+1] = 8;
        MaxVal[1*branches+0] = MaxVal[1*branches+1] = 52342;
        // ...etc...

/* Allocate */

        Classes* Freq[tables*branches];
        for (int table = 0;table < tables;table++)
                for (int branch = 0;branch < branches;branch++)
                        Freq[table*branches+branch] = new Classes[MaxVal[table*branches+branch]];

/* .... */

/* Clean up */

        for (int table = 0;table < tables;table++)
                for (int branch = 0;branch < branches;branch++)
                        delete[] Freq[table*branches+branch];
        delete[] MaxVal;

}
--------8<--------
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 17

Expert Comment

by:rstaveley
ID: 9721594
Oops... Freq also needs to be dynamically allocated of course
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 9721605
i.e.

            Classes** Freq = new *Classes[tables*branches];

            /* .... */

            delete[] Freq;
0
 

Author Comment

by:sherong
ID: 9721742
Thanx rstaveley, you're right, mine is a jagged array. Your code looks great. However, as you've also put in a operator [] in the struct Classes, it should be okay if I directly refer to Freq[x][y][z] now, right? Why is it giving me a compilation error, saying Freq[][][] is not a value?
0
 
LVL 17

Accepted Solution

by:
rstaveley earned 50 total points
ID: 9721822
There were two mistakes:

 (1) I needed to make the operator return a reference to make it a valid LHS for assignments
 (2) My allocation was a bit drunk:
        Classes** Freq = new Classes*[tables*branches];

This should work:
--------8<--------
/*const*/ int tables = 13; // Not const
/*const*/ int branches = 2; // Not const
const int classes = 3;

struct Classes {
float score[classes]; /* I'm guessing this contains scores?! */
float& operator[] (int index) {return score[index];}
};

int main()
{

/* Need to allocate */

        int *MaxVal = new int[tables*branches];

/* Assign */

        MaxVal[0*branches+0] = MaxVal[0*branches+1] = 8;
        MaxVal[1*branches+0] = MaxVal[1*branches+1] = 52342;
        // ...etc...

/* Allocate */

        Classes** Freq = new Classes*[tables*branches];
        for (int table = 0;table < tables;table++)
                for (int branch = 0;branch < branches;branch++)
                        Freq[table*branches+branch] = new Classes[MaxVal[table*branches+branch]];

/* .... */

        Freq[0*0+0][0][0] = 1;

/* Clean up */

        for (int table = 0;table < tables;table++)
                for (int branch = 0;branch < branches;branch++)
                        delete[] Freq[table*branches+branch];
        delete[] Freq;
        delete[] MaxVal;

}
--------8<--------
0
 

Author Comment

by:sherong
ID: 9721889
Thanx so much. You're great!
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 9721916
If you want to be able to write...

    Freq[0][0][0][0] = 1;

... you should be able to use the following approach.

--------8<--------
/*const*/ int tables = 13; // Not const
/*const*/ int branches = 2; // Not const
const int classes = 3;

struct Classes {
float score[classes]; /* I'm guessing this contains scores?! */
float& operator[] (int index) {return score[index];}
};

class A4 {

        Classes** Freq;
        int tables,branches;

public:
        A4(int tables,int branches,const int *MaxVal): tables(tables),branches(branches) {
                Freq = new Classes*[tables*branches];
                for (int table = 0;table < tables;table++)
                        for (int branch = 0;branch < branches;branch++)
                                Freq[table*branches+branch] = new Classes[MaxVal[table*branches+branch]];
        }
        ~A4() {
                for (int table = 0;table < tables;table++)
                        for (int branch = 0;branch < branches;branch++)
                                delete[] Freq[table*branches+branch];
                delete[] Freq;
        }
        Classes** operator[] (int index) {
                return &Freq[index*branches];
        }
};

int main()
{

/* Need to allocate */

        int *MaxVal = new int[tables*branches];

/* Assign */

        MaxVal[0*branches+0] = MaxVal[0*branches+1] = 8;
        MaxVal[1*branches+0] = MaxVal[1*branches+1] = 52342;
        // ...etc...

/* Instance of Freq - note that this is now an instance of a class */

        A4 Freq(tables,branches,MaxVal);

/* This indexing works using two different operator overloads */

        Freq[0][0][0][0] = 1;

        delete[] MaxVal;

}
--------8<--------
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now