are arrays contiguous in memory?

[Peteroid]

I looked at the addresses in an 'array<>' during debug and noticed that the
addresses were contiguous. Is this guaranteed, or just something it does if
it can?

[==P==]

PS = VS C++.NET 2005 Express using clr:/pure syntax

 

[Laurent Lequenne]

I guess that if you lock the array, the array will be contiguous to use a
pointer as it is the only safe way you can access the array through a
pointer

 

[Willy Denoyette [MVP]]

I looked at the addresses in an 'array<>' during debug and noticed that the
addresses were contiguous. Is this guaranteed, or just something it does if
it can?

[==P==]

PS = VS C++.NET 2005 Express using clr:/pure syntax

Yes.

Willy.

 

[Carl Daniel [VC++ MVP]]

I looked at the addresses in an 'array<>' during debug and noticed
that the addresses were contiguous. Is this guaranteed, or just
something it does if it can?

Managed arrays are always contiguous, but you can only observe/take
advantange of that fact by getting a pinning pointer into the array.
Naturally, if it's an array of reference type, then the contiguous array
will contain only pointers to the contained objects, which in all likelihood
will not be contiguous.

-cd

 

[Willy Denoyette [MVP]]

Managed arrays are always contiguous, but you can only observe/take
advantange of that fact by getting a pinning pointer into the array.
Naturally, if it's an array of reference type, then the contiguous array
will contain only pointers to the contained objects, which in all
likelihood will not be contiguous.

-cd

Not sure what you mean with "take/advantage", in managed code there is no
need to pin pointers unless you need to pass the array or one of its
elements to unmanaged code. But pinned or not, managed array's are always
contigious, just like non managed array's.

Willy.

 

[Carl Daniel [VC++ MVP]]

Not sure what you mean with "take/advantage", in managed code there
is no need to pin pointers unless you need to pass the array or one
of its elements to unmanaged code. But pinned or not, managed array's
are always contigious, just like non managed array's.

take-advantage-of as in use pointer arithmetic to access array elements.
Not of much (any?) value unless you're writing unmanaged code.

--cd

 

[Rodrigo Corral [MVP]]

It could be very useful to use pointer arithmetic, for performance reasons,
in managed code, at least in C#. I guest that is the same in managed
C++/CLI.
For example:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dncscol/html/csharp11152001.asp


--
Un saludo
Rodrigo Corral González [MVP]

FAQ de microsoft.public.es.vc++
http://rcorral.mvps.org

 

[Nishant Sivakumar]

Yes, arrays are ref types and the GC always allocates memory in contiguous
blocks.

 

[Nishant Sivakumar]

Managed arrays are always contiguous, but you can only observe/take
advantange of that fact by getting a pinning pointer into the array. <<

An interior pointer would suffice too, Carl.

 

[Willy Denoyette [MVP]]

It could be very useful to use pointer arithmetic, for performance
reasons, in managed code, at least in C#. I guest that is the same in
managed C++/CLI.
For example:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dncscol/html/csharp11152001.asp


--
Un saludo
Rodrigo Corral González [MVP]

FAQ de microsoft.public.es.vc++
http://rcorral.mvps.org

Beware that the sample in the article uses pointer arithmetic (C# unsafe
code) to directly access an unmanaged array (a bitmap is unmanaged data!!),
there is no need to pin here.
I see no reason whatsoever to use this to access managed arrays.

Willy.

 

[Willy Denoyette [MVP]]

Do you guy's know any "arrays" that aren't contigious?

Willy.

Yes, arrays are ref types and the GC always allocates memory in contiguous
blocks.

--
Regards,
Nish [VC++ MVP]

I looked at the addresses in an 'array<>' during debug and noticed that
the addresses were contiguous. Is this guaranteed, or just something it
does if it can?

[==P==]

PS = VS C++.NET 2005 Express using clr:/pure syntax

 

[Willy Denoyette [MVP]]

take-advantage-of as in use pointer arithmetic to access array elements.
Not of much (any?) value unless you're writing unmanaged code.

--cd

Carl,

Sorry to be dense, but when talking about advantage, you mean advantage in
terms of what and compared to what? I don't see any advantage to use pointer
arithmetic to access "managed" array elements over let's say indexed access,
I'm I missing something?

Willy.

 

[Carl Daniel [VC++ MVP]]

Carl,

Sorry to be dense, but when talking about advantage, you mean
advantage in terms of what and compared to what? I don't see any
advantage to use pointer arithmetic to access "managed" array
elements over let's say indexed access, I'm I missing something?

It's a figure of speach - don't put too much weight in it!

The only advantage would be to use it with existing code that does pointer
arithmetic when accessing an array.

In real terms, there is no advantage, since in C, a[n] is equivalent to
*(a+n) by definition.

-cd

 

[Carl Daniel [VC++ MVP]]

Do you guy's know any "arrays" that aren't contigious?

Matrix arithmetic libraries typically supply some kind of sparse array
that's not contiguous, but those are definitely special purpose things. It
would seem very silly to make a general purpose array non-contiguous.

-cd

 

[Willy Denoyette [MVP]]

Carl,

Sorry to be dense, but when talking about advantage, you mean
advantage in terms of what and compared to what? I don't see any
advantage to use pointer arithmetic to access "managed" array
elements over let's say indexed access, I'm I missing something?

It's a figure of speach - don't put too much weight in it!

The only advantage would be to use it with existing code that does pointer
arithmetic when accessing an array.

In real terms, there is no advantage, since in C, a[n] is equivalent to
*(a+n) by definition.

-cd

Carl,

Agreed, all I want is to make sure people don't start to believe that using
pointer arithmetic has performance advantages when accessing arrays
(elements). I know a lot of C# (and some C++) developers believe that there
is such advantage when using unsafe constructs, but it's most often not the
case, worse, they start to pin arrays for a long period of time, effectively
disturbing the GC activity which results in reduced overall performance.

Willy.

 

[Brandon Bray [MSFT]]

Agreed, all I want is to make sure people don't start to believe that
using pointer arithmetic has performance advantages when accessing
arrays (elements). I know a lot of C# (and some C++) developers believe
that there is such advantage when using unsafe constructs, but it's
most often not the case, worse, they start to pin arrays for a long
period of time, effectively disturbing the GC activity which results in
reduced overall performance.

There is one performance benefit for using pointers over indexing for CLR
arrays. When indexing a CLR array, there is a bounds check. That check is
eliminated when using a pointer to iterate over the array.

Of course, that's a trade off between safety and performance. One should be
very careful when making that decision. Because the JIT compiler has the
ability to eliminate bounds checks in some cases, switching to pointers is
not always a worthwhile exercise. Though, it is definitely useful in some
cases where bitmap manipulation is done. This is probably the only reason
why interior pointers exist in the new C++. If it wasn't for this case, I
probably would have succeeded at keeping them out of the language entirely.

 

[Arnaud Debaene]

Do you guy's know any "arrays" that aren't contigious?

A double-linked list?

Arnaud
MVP - VC

 

[Willy Denoyette [MVP]]

A double-linked list?

Arnaud
MVP - VC

Why a double linked list and not a linked list?
Anyway, it's not what I would call an array (or a vector).

Willy.

 

[Willy Denoyette [MVP]]

There is one performance benefit for using pointers over indexing for CLR
arrays. When indexing a CLR array, there is a bounds check. That check is
eliminated when using a pointer to iterate over the array.

That's true, though the overhead is real small (something like a cmp and a
jmp) and only important to consider for some operations on arrays.

Of course, that's a trade off between safety and performance. One should
be very careful when making that decision. Because the JIT compiler has
the ability to eliminate bounds checks in some cases, switching to
pointers is not always a worthwhile exercise. Though, it is definitely
useful in some cases where bitmap manipulation is done. This is probably
the only reason why interior pointers exist in the new C++. If it wasn't
for this case, I probably would have succeeded at keeping them out of the
language entirely.

Well, as I said in another message, a Bitmap (assumed we talk about
GDI/GDI+) is stored in unmanaged (GDI+ allocated) memory and accessing them
directly using pointers is a big perf. win, but that's because accessing
them using the GDI+ methods is extremely slow.

Willy.

 

[Peter Oliphant]

Wow, you ask a simple question..... : )

As I understand it, the 'old' STL containers make a distinction in this
regard. List's are linked lists, and so are not necessarily contiguous in
memory. Vector's are the STL equivalent of contiguous lists. The reason for
both is that vector's are better at lookup performance (randomly accessible
and therefore a fixed length of lookup time); but suffer when being deleted
from or resized, since this is often done by moving the entire end of the
list and allocating a bigger vector somewhere else and copying over,
respectively. List's are worse at lookup performance since they require
serial lookup (linking thorugh the list from the header, which is takes a
variable length of time based on 'distance' from header), but benefit when
it comes to deletion and resizing since an element can be removed without
moving anything else, and resizing just means finding a large enough memory
space anywhere for the added element.

My opinion is this: with a faster computer and more memory it really doesn't
matter which method is used! : )

[==P==]