Array Performance very similar to LinkedList - What gives?

Question

So the title is somewhat misleading... I'll keep this simple: I'm comparing these two data structures:

1. An array, whereby it starts at size 1, and for each subsequent addition, there is a realloc() call to expand the memory, and then append the new (malloced) element to the n-1 position.
2. A linked list, whereby I keep track of the head, tail, and size. And addition involves mallocing for a new element and updating the tail pointer and size.

Don't worry about any of the other details of these data structures. This is the only functionality I'm concerned with for this testing.

In theory, the LL should be performing better. However, they're near identical in time tests involving 10, 100, 1000... up to 5,000,000 elements.

My gut feeling is that the heap is large. I think the data segment defaults to 10 MB on Redhat? I could be wrong. Anyway, realloc() is first checking to see if space is available at the end of the already-allocated contiguous memory location (0-[n-1]). If the n-th position is available, there is not a relocation of the elements. Instead, realloc() just reserves the old space + the immediately following space. I'm having a hard time finding evidence of this, and I'm having a harder time proving that this array should, in practice, perform worse than the LL.

Here is some further analysis, after reading posts below:

[Update #1] I've modified the code to have a separate list that mallocs memory every 50th iteration for both the LL and the Array. For 1 million additions to the array, there are almost consistently 18 moves. There's no concept of moving for the LL. I've done a time comparison, they're still nearly identical. Here's some output for 10 million additions:

(Array)
time ./a.out a 10,000,000
real    0m31.266s
user    0m4.482s
sys     0m1.493s
(LL)
time ./a.out l 10,000,000
real    0m31.057s
user    0m4.696s
sys     0m1.297s

I would expect the times to be drastically different with 18 moves. The array addition is requiring 1 more assignment and 1 more comparison to get and check the return value of realloc to ensure a move occurred.

[Update #2] I ran an ltrace on the testing that I posted above, and I think this is an interesting result... It looks like realloc (or some memory manager) is preemptively moving the array to larger contiguous locations based on the current size. For 500 iterations, a memory move was triggered on iterations: 1, 2, 4, 7, 11, 18, 28, 43, 66, 101, 154, 235, 358 Which is pretty close to a summation sequence. I find this to be pretty interesting - thought I'd post it.

Answer 1

You're right, realloc will just increase the size of the allocated block unless it is prevented from doing so. In a real world scenario you will most likely have other objects allocated on the heap in between subsequent additions to the list? In that case realloc will have to allocate a completely new chunk of memory and copy the elements already in the list.

Try allocating another object on the heap using malloc for every ten insertions or so, and see if they still perform the same.

Answer 2

So you're testing how quickly you can expand an array verses a linked list?

In both cases you're calling a memory allocation function. Generally memory allocation functions grab a chunk of memory (perhaps a page) from the operating system, then divide that up into smaller pieces as required by your application.

The other assumption is that, from time to time, realloc() will spit the dummy and allocate a large chunk of memory elsewhere because it could not get contiguous chunks within the currently allocated page. If you're not making any other calls to memory allocation functions in between your list expand then this won't happen. And perhaps your operating system's use of virtual memory means that your program heap is expanding contiguously regardless of where the physical pages are coming from. In which case the performance will be identical to a bunch of malloc() calls.

Expect performance to change where you mix up malloc() and realloc() calls.