Skip to main content
GameDev.net gamedev.net
🔒 Locked

Array vs List very basic experimentation

Started by janta Feb 24, 2008 at 12:48 PM 6 replies 1.1k views
Original Post
janta
janta
Hey I got the idea from this year's GDC. Back at home I've done a little experiment, I thought I'd share it with you. Here's the code:

struct Test
{
	Test* next;
	int data[255];
};

// ------------------------------

int _tmain(int argc, _TCHAR* argv[])
{	
        // Allocate an array of Test and link them together
	int count = 1024 * 1024;
	Test* data = new Test[count];

	for (int i = 0 ; i < count ; i++)
		data.next = i < count - 1 ? &data[i+1] : NULL;	
	
        // Iterate data as an array
	DWORD startTimeArray = timeGetTime();
	Test* pCurrentArray = data;	
	while(pCurrentArray->next)	
		++pCurrentArray;
	DWORD totalTimeArray = timeGetTime() - startTimeArray;	

        // Iterate data as a list
	DWORD startTimeList = timeGetTime();
	Test* pCurrentList = data;	
	while(pCurrentList->next)
		pCurrentList = pCurrentList->next;
	DWORD totalTimeList = timeGetTime() - startTimeList;
	
	printf("Total times: %d ms Array vs. %d ms List\n", totalTimeArray, totalTimeList);

	delete [] data;

	return 0;
}



Results on my machine (with default "Release" configuration, VC++ 2005 Express): 16 ms vs 84 ms You may want to try it with different counts of "Test" and with different data sizes within "Test" What are your thoughts
outRider
outRider
Pointer chasing is slower than incrementing a register, is that the gist of it or is there more to talk about?

Edit: Hmm... actually there is a little more to it, isn't there. I'll take a peak at what the compiler spits out and then comment.
Antheus
Antheus
Is this the idea

It's kind of hard to determine the point you're making.

What is your implementation supposed to achieve? A special form of linked list?

The closest I can see is that you're using pointers as cursors.

What is the alternative you're comparing to? std::list? std::vector? If so, then the difference in running time is obvious.

But it's really hard to comment with so much missing information.

I was also under the impression that timeGetTime isn't most suited for such high-resolution timing.
janta
janta
Yeah I just wanted to collect your thoughts without biasing them with mine. I'm trying to see how the CPU is capable of executing instructions out of order and start fetching data from the memory sooner in the first case (since adresses to be read can be determined deterministically) than in the second one (where the next address to read is unknown until the content of the current address has been read.
outRider
outRider
That's pretty much it, pointer chasing is slower than constant-stride memory access. It's an example of loop carried dependency.
janta
janta
The interesting idea is that for a list that does not change too often, it is possible to build a array of pointers to the elements of the list and use the _mm_prefetch thing in order to speed things up.

I'll post a link to the AMD's presentation given at the GDC a few days ago, it contains interesting stuff.
bulgurmayo
bulgurmayo
If your list isn't going to change much and if you are ready to pay the price of building an array of pointers on top of it, aren't you better off using a vector from the start ?

[edit : typo]
ViperG
ViperG
Those are expected results.

But I wouldn't bother either way, i would just use a vector, or if a list better suits your situation then a list.
Black Sky A Star Control 2/Elite like game

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.