By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,905 Members | 902 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,905 IT Pros & Developers. It's quick & easy.

'new'd memeroy is contiguous?

P: n/a
No pun intended in the subject :)

Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.
warm regards,
Divya Rathore
(remove underscores for email ID)

Dec 19 '05 #1
Share this Question
Share on Google+
22 Replies


P: n/a
di************@gmail.com wrote:
No pun intended in the subject :)
memeroy?
Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.


Yes, it is. What details do you expect?
Dec 19 '05 #2

P: n/a
On 19 Dec 2005 09:04:23 -0800, "di************@gmail.com"
<di**********@gmail.com> wrote:
Is dynamically allocated memory contiguous in C++? In C? Details would
be appreciated.


C questions are off-topic here unless they are somehow also relevant
to C++ (comp.lang.c is the place to ask), so I'll limit myself to the
question concerning "new".

Do you mean, contiguous across different calls to new? If so, the
answer is: not necessarily, because it is implementation-defined how
new obtains and utilizes its raw memory. I would say, no, because
unused blocks of memory released by calling delete are normally
recycled within the total memory used by the process taken from its
free store (i.e. heap memory) provided by the operating system. Often,
the memory is only returned to the operating system when the process
ends, but that is also an implementation-specific detail which can be
quite different on another compiler and operating system.

A class can also overload new and delete to use a different memory
allocation scheme.

Otherwise, I don't really understand your question. Allocations
performed by new allocate a single object of a given type. Allocations
performed by new[] allocate arrays of objects of the same type.
Although the memory occupied by the array is guaranteed to be
contiguous, and the memory occupied by any given object is contiguous,
it is implementation-defined how the compiler lays out the individual
members of the object in that memory. The implementation (i.e. your
compiler) is free to add padding bytes between the individual members
for purposes of alignment and can be influenced by different
optimization and alignment settings at compile-time (e.g., see the
documentation for "#pragma pack" if your compiler supports it).

Consider the following:

struct X {
short a;
char b;
int c;
};

What is sizeof X here? Depending on the compiler settings, you will
most likely get an additional byte of padding thrown in after the char
member. However, it is also possible that there are two extra bytes
after the short member as well. Switch around the order of the members
and see if you get different results.

Of course, an instance of a class can allocate additional memory and
store just the pointer to that memory. When querying the size of such
an object with sizeof(), only the memory occupied by the pointer would
count towards the total size of the object.

If you want more details, I suggest you get a copy of the C++ standard
at: http://www.ansi.org

--
Bob Hairgrove
No**********@Home.com
Dec 19 '05 #3

P: n/a
On Mon, 19 Dec 2005 12:26:41 -0500, Victor Bazarov
<v.********@comAcast.net> wrote:
di************@gmail.com wrote:
No pun intended in the subject :)


memeroy?


Just a typo or misspelling.
I think the pun was with "new'd" and "nude" (groan...)

--
Bob Hairgrove
No**********@Home.com
Dec 19 '05 #4

P: n/a
Bob Hairgrove wrote:
On Mon, 19 Dec 2005 12:26:41 -0500, Victor Bazarov
<v.********@comAcast.net> wrote:

di************@gmail.com wrote:
No pun intended in the subject :)


memeroy?

Just a typo or misspelling.
I think the pun was with "new'd" and "nude" (groan...)


Ah... OK. I was thinking of "hemorrhoids".
Dec 19 '05 #5

P: n/a
di************@gmail.com wrote:
No pun intended in the subject :)

Is dynamically allocated memory contiguous in C++?
Yes.
In C?
Yes.
Deails would be appreciated.


What details do you want? It's contiguous, that's how you have dynamic
arrays.
Brian

--
Please quote enough of the previous message for context. To do so from
Google, click "show options" and use the Reply shown in the expanded
header.
Dec 19 '05 #6

P: n/a
Thank you all..
so, in:
int* x;
x = new int[MAX];

memory allocated is contiguous for how-so-ever-large MAX (till system
supports)?

Dec 19 '05 #7

P: n/a
>> Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.

Yes, it is. What details do you expect?


As someone pointed, asking about malloc/calloc is out of scope of this
newsgroup, so I will restrain myself.
Thanks anyways.

Dec 19 '05 #8

P: n/a
di************@gmail.com wrote:
Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.

Yes, it is. What details do you expect?

As someone pointed, asking about malloc/calloc is out of scope of this
newsgroup, so I will restrain myself.


Actually, since C Standard Library circa 1990 is part of C++ Standard
Library, it's not out of scope to talk about malloc or calloc. Please
ask your library questions as you wish, it's absolutely _in_ the scope
of this newsgroup. C _language_ questions are better asked in
comp.lang.c, however.

V
Dec 19 '05 #9

P: n/a
On 19 Dec 2005 12:18:29 -0800, "di************@gmail.com"
<di**********@gmail.com> wrote:
Thank you all..
so, in:
int* x;
x = new int[MAX];

memory allocated is contiguous for how-so-ever-large MAX (till system
supports)?


The limit on the array size (MAX) is not specified by the C++
standard. If the call to new succeeds, x will be a valid pointer to
that memory. Otherwise, an exception (std::bad_alloc) is thrown.

If you need to allocate very large sections of RAM, e.g. for image
processing, you can also do it with operating-system specific means
and use placement new.

--
Bob Hairgrove
No**********@Home.com
Dec 19 '05 #10

P: n/a
di************@gmail.com wrote:
Thank you all..
so, in:
int* x;
x = new int[MAX];
Why not write them in the same statement?
memory allocated is contiguous for how-so-ever-large MAX (till system
supports)?


"how-so-ever-large"? Google only has three links with that text in them
(and without hyphens, mind you). I have to admit, I'd never seen it
before reading your post. Some new English every day -- that's my goal.

The default allocation mechanism (if that's the one you're asking about)
will attempt to locate a contiguous segment of memory large enough to
accommodate the array. If it fails, an exception will be thrown. You can
overload 'new[]' and do whatever you would like...

V
Dec 19 '05 #11

P: n/a

di************@gmail.com wrote:
No pun intended in the subject :)

Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.
warm regards,
Divya Rathore
(remove underscores for email ID)


Dynamically allocated memory is contiguous. Don't confuse that with a
dynamically allocated object is contiguous.

class MyObj {
public:
MyObj()
: blockA( new char [12] )
, blockB( new int [12] )
{}
~MyObj()
{ delete [] blockA;
delete [] blockB;
}
private:
char *blockA;
int*blockB;
};

MyObj *p = new MyObj();

MyObj is contiguous. blockA is contiguous. blockB is contiguous. But
MyObj, blockA and blockB as a group might not be contiguous.

Dec 19 '05 #12

P: n/a
js****@cox.net wrote:
di************@gmail.com wrote:
No pun intended in the subject :)

Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.
warm regards,
Divya Rathore
(remove underscores for email ID)

Dynamically allocated memory is contiguous. Don't confuse that with a
dynamically allocated object is contiguous.


Every object occupies a contiguous block of memory, so I am not sure
where your second sentence is coming from.

class MyObj {
public:
MyObj()
: blockA( new char [12] )
, blockB( new int [12] )
{}
~MyObj()
{ delete [] blockA;
delete [] blockB;
}
private:
char *blockA;
int*blockB;
};

MyObj *p = new MyObj();

MyObj is contiguous. blockA is contiguous. blockB is contiguous. But
MyObj, blockA and blockB as a group might not be contiguous.


Why are they suddenly "a group"?

V
Dec 19 '05 #13

P: n/a
di************@gmail.com wrote:
No pun intended in the subject :)

Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.


Suppose it wasn't contiguous. You get one pointer out of the allocator,
which points to uninitialized storage. How would your program find the
other pieces? With what information?

Dec 19 '05 #14

P: n/a
Kaz Kylheku wrote:
di************@gmail.com wrote:
No pun intended in the subject :)

Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.

Suppose it wasn't contiguous. You get one pointer out of the allocator,
which points to uninitialized storage. How would your program find the
other pieces? With what information?


Somehow (in an implementation-defined manner) the pointer to a dynamic
array would be different from a pointer to any other array and any pointer
arithmetic on it would be performed using some magic (implementation-
specific magic, mind you). So, indexing, increments, pointer difference,
would be done for a pointer from 'new[]' somehow differently than for
a pointer to an element of an automatic or static array. Possible?

V
Dec 19 '05 #15

P: n/a
Victor Bazarov wrote:
Bob Hairgrove wrote:
On Mon, 19 Dec 2005 12:26:41 -0500, Victor Bazarov
<v.********@comAcast.net> wrote:

di************@gmail.com wrote:

No pun intended in the subject :)
memeroy?


Just a typo or misspelling.
I think the pun was with "new'd" and "nude" (groan...)

Ah... OK. I was thinking of "hemorrhoids".


Well, what can I say in my C++'d state, I'd never have C'n it coming.
Oh, the joys of a symbiotic relationship with yeast, alcohol being
derived from yeast etc, etc.

JB
Dec 20 '05 #16

P: n/a

Victor Bazarov wrote:
Kaz Kylheku wrote:
di************@gmail.com wrote:
No pun intended in the subject :)

Is dynamically allocated memory contiguous in C++? In C? Deails would
be appreciated.

Suppose it wasn't contiguous. You get one pointer out of the allocator,
which points to uninitialized storage. How would your program find the
other pieces? With what information?


Somehow (in an implementation-defined manner) the pointer to a dynamic
array would be different from a pointer to any other array and any pointer
arithmetic on it would be performed using some magic (implementation-
specific magic, mind you). So, indexing, increments, pointer difference,
would be done for a pointer from 'new[]' somehow differently than for
a pointer to an element of an automatic or static array. Possible?


The semantics of these pointer operations is what defines contiguity.
:)

Dec 20 '05 #17

P: n/a

Victor Bazarov wrote:
"how-so-ever-large"? Google only has three links with that text in them
(and without hyphens, mind you). I have to admit, I'd never seen it
before reading your post. Some new English every day -- that's my goal.
hyphens were to put stress. I, well, could have done with italisizing
the phrase had it been allowed (I am using web interface of google
groups). Yes.. English, being a flexible language, allows one to be
experimental.

The default allocation mechanism (if that's the one you're asking about)
will attempt to locate a contiguous segment of memory large enough to
accommodate the array. If it fails, an exception will be thrown. You can
overload 'new[]' and do whatever you would like...

V

Thanks! You and others have been very informative.

Dec 20 '05 #18

P: n/a

Kaz Kylheku wrote:
Suppose it wasn't contiguous. You get one pointer out of the allocator,
which points to uninitialized storage. How would your program find the
other pieces? With what information?

Yes, that's what I was worried about.
I, indeed, am working in a image processing application and was trying
to figure out if a 2D array is better for dynamic allocation or a big
1-dimensional one.

Case 1: 1D case will allocate it in one go. So contguity is there
indeed.
Case 2: 2D will involve memory to be new'd (again, grammatical usage is
casual here. This is *NOT* correct english.) once for the columns and
then itertively with in a 'for' loop so as to cover the rows.
int** array2D = new int*[height];
for (int i=0; i<height; i++)
{
array2D[i] = new int[width];
}

My querry is that whether this array2D is contiguous or not.

So far so good.. now which of these 2 cases will be faster to access?
Obviously the one which is contiguous. Hence this question on the
newsgroup.

Dec 20 '05 #19

P: n/a

di************@gmail.com wrote:
Case 1: 1D case will allocate it in one go. So contguity is there
indeed.
Yes, and you could use this allocated memory as a 2D array, if you
wanted to.

int** array2D = new int*[height];
int* temp = new int[height*width];
for (int i=0; i<height; ++i)
{
array2D[i] = &(temp[i*width]);
}
Case 2: 2D will involve memory to be new'd (again, grammatical usage is
casual here. This is *NOT* correct english.) once for the columns and
then itertively with in a 'for' loop so as to cover the rows.
int** array2D = new int*[height];
for (int i=0; i<height; i++)
{
array2D[i] = new int[width];
}

My querry is that whether this array2D is contiguous or not.
Not necessarily.
So far so good.. now which of these 2 cases will be faster to access?
Obviously the one which is contiguous. Hence this question on the
newsgroup.


The obvious is not necessarily the case. It could be that because of
cache hits/misses, the non-contiguous one is faster. You should just
try it and see.

Another thing that no one mentioned. Do you mean physically contiguous,
or virtually contiguous. It is a fact that the memory allocated will be
virtually contiguous. It is not a fact that the memory will be
physically contiguous.

Dec 20 '05 #20

P: n/a

di************@gmail.com wrote in message ...

I, indeed, am working in a image processing application and was trying
to figure out if a 2D array is better for dynamic allocation or a big
1-dimensional one.

Case 1: 1D case will allocate it in one go. So contguity is there
indeed.

Case 2: 2D will involve memory to be new'd (again, grammatical usage is
casual here. This is *NOT* correct english.) once for the columns and
then itertively with in a 'for' loop so as to cover the rows.
int** array2D = new int*[height];
for (int i=0; i<height; i++){
array2D[i] = new int[width];
}

My querry is that whether this array2D is contiguous or not.

So far so good.. now which of these 2 cases will be faster to access?
Obviously the one which is contiguous. Hence this question on the
newsgroup.


What do you have against std::vector? I use a vector of 3D points(double
x,y,z) to store a '3D rock' which animates smoothly, 30k+ triangle-mesh in
OpenGL running in wxWidgets.
Vector is contiguous.

#include <iostream> // 2D example
#include <vector>
// ........
size_t Rows( 480 );
size_t Columns( 640 );
std::vector<std::vector<double> > My2Darray( Rows, Columns );
std::cout<<"My2Darray.size() ="<<My2Darray.size()<<std::endl;
std::cout<<"My2Darray.at(0).size() ="<<My2Darray.at(0).size()<<std::endl;
std::cout<<"row 7 col 9 ="<<My2Darray.at(7).at(9)<<std::endl;

Now you don't need to worry about 'new/delete[]'.

[ Sorry if this was all 'old hat' to you. Maybe it will help some newbie. ]
--
Bob R
POVrookie
Dec 20 '05 #21

P: n/a
"di************@gmail.com" <di**********@gmail.com> wrote in message
news:11**********************@g43g2000cwa.googlegr oups.com...

Kaz Kylheku wrote:
Suppose it wasn't contiguous. You get one pointer out of the allocator,
which points to uninitialized storage. How would your program find the
other pieces? With what information?

Yes, that's what I was worried about.
I, indeed, am working in a image processing application and was trying
to figure out if a 2D array is better for dynamic allocation or a big
1-dimensional one.

Case 1: 1D case will allocate it in one go. So contguity is there
indeed.
Case 2: 2D will involve memory to be new'd (again, grammatical usage is
casual here. This is *NOT* correct english.) once for the columns and
then itertively with in a 'for' loop so as to cover the rows.
int** array2D = new int*[height];
for (int i=0; i<height; i++)
{
array2D[i] = new int[width];
}

My querry is that whether this array2D is contiguous or not.


Most likely it will not be contiguous as a group.

That is, array2D + height will probably not point to array2D[1][0]. It
could, but probably wouldn't.

So in your specific case it would be better to allocate it in one go and do
the array math.

So far so good.. now which of these 2 cases will be faster to access?
Obviously the one which is contiguous. Hence this question on the
newsgroup.

Dec 20 '05 #22

P: n/a
di************@gmail.com wrote:
Case 2: 2D will involve memory to be new'd (again, grammatical usage is
casual here. This is *NOT* correct english.)
"newed" will do, patterned after "renewed", as in library books or a
club membership.

once for the columns and then itertively with in a 'for' loop so as to cover the rows.
int** array2D = new int*[height];
for (int i=0; i<height; i++)
{
array2D[i] = new int[width];
}

My querry is that whether this array2D is contiguous or not.
Your new query is whether this 2D array is contiguous or not. Your
original query doesn't ask anything like this.

In general, each call to the memory allocator is an independent
request, which is satisfied by finding a sufficiently large piece of
memory somewhere.

The memory will quite likely not be contiguous. Even if the rows are
allocated sequentially at the beginning of a large extent of memory,
there will possibly be separated by memory management information.

So far so good.. now which of these 2 cases will be faster to access?
Obviously the one which is contiguous. Hence this question on the
newsgroup.


The non-contiguous case gives you flexibility that doesn't exist in the
contiguous case, because when you make your 2D array one object, the
width of each row is a compile-time constant.

You could dynamically allocate a 2D array with a number of rows and
columns determined at run-time. It would actually be a 2D array
simulated within a 1D array. To access row R and column C, you would
use the expression:

array[width * R + C]

rather than

array[R][C]

The first method performs a multiplication, addition and one memory
access. The second method, assuming that array[] is a vector of
pointers to individually allocated rows, has to displace into the row
vector to retrieve a pointer, and then displace that pointer to fetch
the element. Two memory accesses.

What is faster? The answer to that depends entirely on the compiler,
machine, the size of the array, the access pattern to that array and so
forth.

It may happen that both of these "naive" representations for a 2D array
are inefficient for doing some kinds of operations on very large
arrays, such as high resolution graphical images.

Suppose you are writing an image manipulation program. With this
program, the user will do lots of editing operations that are clustered
in a small part of the image, and in fact he or she may zoom in, so as
to only see a small part of the image.

A naive, "linear" memory allocation strategy will have the effect that
two pixels that are right above one another (same column) will be in
different virtual memory pages. To retrieve a 100x100 square of the
image for some paintbrush operation or whatever will involve accesses
to 100 different pages! And 100x100 is barely larger than a modern
icon; it's tiny. With this representation of the image data, the
program will thrash the page translation cache, and also demonstrate
poor swapping behavior in low memory conditions.

Programs like this, such GIMP, use a "tile based" memory allocation.
The image is carved into small, square tiles, which are individual 2D
arrays that are contiguous. Thus a sub-rectangle of an image occupies
only a small number of pages.

So you see, optimization issues aren't always simple when you have
various different kinds of caches for instructions, data, and virtual
memory information, existing at various different levels.

A data representation scheme that involves burning a few memory and
machine cycles on chasing a few pointers may be faster than a naive one
that just uses address arithmetic, because it exhibits better caching
and paging behavior!

Some programs will exhibit different performance if you just switch
their arrays from row major to column major representation. In some
languages that actually have true multidimensional arrays, choosing
that representation is up to the compiler or language run-time, or
perhaps influenced by optimization hints from the programmer.

Dec 21 '05 #23

This discussion thread is closed

Replies have been disabled for this discussion.