Array question in C++

J

Josh_B

Supreme [H]ardness
Joined
Aug 15, 2000
Messages
6,954
Good day all,

I read in my textbook for my C++ class, that arrays place variables that are all of the same type, in sequential memory allocations.

My question is, why then are arrays so performance degrading (or so I've been told), when they are sequential. Sequential memory access is much faster than random access, is it not? Sequential access should make features like hardware prefetch, perform that much better.
 
I hadn't heard they degraded performance. Who said that?

They usually work fine in the programs I make. The C++ STL is slower than a simple array, and both work fast for me.

If anything's performance degrading, it would be anything graphics related. Make a program to count to 1 billion. On an average processor, it'll take 3 seconds at most. Now, put a line to print out the result on the screen every loop through. You'll notice that it's probably only going to be at 100,000 if you leave it there all night.
 
If you're going to be adding, subtracting, or moving elements, it'll bog down from having to re-allocate memory and re-order the array (this is assuming that you're using pointers to dynamically allocate arrays, not using fixed size arrays). A linked list can be faster in alot of cases.

Say you want to insert an element at index 2 of a 1000-element array. With a linked list, you'd probably have to update 4-8 pointers(depending on if it's doublely or singlely linked), allocate space for the element, and set it's value. With an array, you'd have to move almost 1000 elements up a few bytes in memory, and possibly reallocate the whole thing if you didn't have more space allocated than you needed. But a linked list would have a large penalty for random access, and there's more memory overhead for the list, since you need all those pointers.

If you're not doing these sorts of things, I can't see why someone would consider an array to be performance degrading. But if memory isn't an issue, and you're never doing random access, why not use a list? Especially in a language with a good standard library like C++, where you don't have to implement the list yourself.

edit: make that 2-4 pointers... I suck at adding.
 
Yeah, insertion and deletion of sequential memory is slow... every thing else is extremely fast. If you are going to be inserting and deleting elements often, then a linked list is a better choice.
 
Arrays are performance degrading because the memory address is calculated each time you access an element of the array. For example:

Code: 
int arr[10];
arr[8] = 7;

Roughly translates to

Code: 
int arr[10];
*(arr + 8) = 7;

Since this calculation (arr + 8) is performed every time you access an element in the array, if you are accessing the same element repeatedly, you are wasting cycles re-calculating the variable's address each time. Of course, another disadvantage to arrays is that the space is continous. So if you have a large array, and highly fragmented memory space, there may not be enough contiguous memory to allocate your array, even though there is enough free memory. Of course, this doesn't come into play very often. :D
 
Originally posted by Velox
Since this calculation (arr + 8) is performed every time you access an element in the array, if you are accessing the same element repeatedly, you are wasting cycles re-calculating the variable's address each time.
Click to expand...

I think this would depend on how well your compiler optimizes code, though. While some certainly wouldn't, it wouldn't surprise me if the compiler iterated a pointer directly instead of using a loop counter as an offset a fixed one, or stored an array offset's resulting address if it's accessed repeatedly.
 
... and remembering that a modern computer operates at up to 4,000,000,000 operations a second...

When programming ask yourself if the complexity and time taken in coding more complicated methods and the run time overhead of said method actually improves over the total cost of using arrays.

Unless you're using a very complicated algorithm and arrays are the bottleneck, or you're using very substantial amounts of data, arrays will work just fine for the most part where they are the suitable storage type for your data.

Ike, IO is always a bottleneck.
 
Stating that an array is performance degrading is just flat false.

Some operations are slower on array's is true. As mentioned, insertion being on of them. But they are much faster for some operations, as mentioned sequential access.

One note, the example given by Velox is not completely accurate. If an array element is accessed with a constant the address calculation is done at compile time. His statement would be accurate if he accessed by a variable and not a constant. Also the memory alloted to arrays is always contiguous.
 
Odds are that you, as somebody just learning programming, misunderstood what was being said.


...or the person you were listening to is full of shit.
 
depending the machine, etc... physical memory access time is not locality based... it should be uniform...
but since caches are typically based on at least partially on LOR you do get performance benefits on any machines with cache, if you have sequential memory accesses
 
[Josh_B]
> I read in my textbook for my C++ class, that arrays place variables that are all of
> the same type, in sequential memory allocations.

Correct. Arrays are contiguous.

> why then are arrays so performance degrading

They are not. Arrays are low-level C gunk, which means that they're fast, but dangerous.

> Sequential memory access

Sequential access is different from contiguous storage.

[Mike29936]
> The C++ STL is slower than a simple array

There is SOME abstraction penalty to using the STL. It is not significant in the vast majority of cases, sometimes you get an abstraction bonus, and in any event the safety and clarity benefits are overwhelming.

Always use STL containers and algorithms until profiling indicates that you must hand-hack things.

[FuzzyDonkey]
> But if memory isn't an issue, and you're never doing random access,
> why not use a list?

std::vector<T> should be the container you first consider using. It offers blazing fast insertions and deletions at the end. Applications that require std::list<T> are less common.

[Velox]
> Arrays are performance degrading because the memory address is calculated each time
> you access an element of the array.

Compilers optimize this out. Once upon a time in C, traversing by incrementing pointers was faster than incrementing indices. No longer.

> Of course, another disadvantage to arrays is that the space is continous.

This is usually an advantage.

[vinnie]
> When programming ask yourself if the complexity and time taken in coding more
> complicated methods and the run time overhead of said method actually improves over
> the total cost of using arrays.

No. Arrays suck. Do not use them unless you know exactly what you are doing and there is no better way.

[Tnadrev]
> depending the machine, etc... physical memory access time is not locality based...
> it should be uniform...

No. Locality is extremely important due to caching. My favorite algorithm walks all over main memory (absolutely no locality) and performance suffers as a result.
 
You must log in or register to reply here.
Back
Top