Re: are arrays contiguous in memory?

One thing that is missing from this discussion is the importance of cache effects when iterating. If your vector accesses are distributed all over memory like they might be with a linked list that has been sorted, then your cache miss rate will be significantly higher than if you iterate over a contiguous block of memory. This effect is drastic because L1 cache can be well over 20 times faster than RAM.

Another thing here is the fact that modern compilers have extremely good optimizations for looping over contiguous arrays because the compiler knows that it is working with contiguous memory.

That said, depending on what you are doing, it is not always worth it to sacrifice an order of complexity on an algorithm just to get these benefits. The two things I describe above are only constant time improvements, while dispersed memory vectors (such as linked lists) can sometimes give you order N or greater improvements over contiguous arrays.

We kind of got off topic from the original question but this is a good discussion!


-----Original Message-----
From: Arnaud Debaene
Posted At: Monday, December 19, 2005 1:38 PM
Posted To:
Conversation: are arrays contiguous in memory?
Subject: Re: are arrays contiguous in memory?

Peter Oliphant wrote:
> 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.
And there is also in intermediate "mix" between the two : the deque.

> My opinion is this: with a faster computer and more memory it really
> doesn't matter which method is used! : )
This is of course basically wrong : processor speed has never changed
anything to algorithm complexity. When manipulating great number of elements
(several tens of thousands), the difference between logarithmic and linear
complexity is as important today as it was 10 years ago.