zero.racetime.com.au - Version 6.2a

zero.racetime.com.au/

Zero

You must login to post new threads

Topic: Of course linked list is slow

I was having a discussion, with a friend at uni thisafternoon, who was trying to figure out why one of his utilities was slower than another when in theory it was faster. I suggested a few things, before he explained to me that in one version he was using a Linked List, whereas in the other version it was a Queue. Unfortunately, he was using the LinkedList in the version which he expected should have been faster, so he was not getting the results he expected.

Very quickly I realised that this would of course be the case, especially since he was running the implementation in C#/.NET - C# being an OO language being your serious problem here.

You see, in a queue, you put a value onto the queue, and dequeue it. This can be done with a simple array, and an integer to store your current working positions for the start and end of the queue. You could actually do it using a linked list as well, adding to the tail and head of the queue. In an ideal environment, the instructions to take an object off the queue look like this:
- Add the value in memory of the upper bounds counter to the address the array is located at.
- Decrease the upper bounds counter
- Return the value of the data at that memory address

3 instructions.

In an optimal LinkedList implementation, to pop the first element, you would go:
- Copy the reference of the head to a temporary location.
- Set temp.next.previous to null (3 instructions because you have to get the memory)
- Set the head to temp.next (2)
- Return temp

Even optimally this is 6 instructions, double the number of instructions. Where you really lose out is by the fact that in a .NET implementation, it ends up having to deal with the overhead of having a node to store your references to your data, adding more overhead.

Just to test my theory, and see how bad the difference actually was, I decided to write some quick tests on the trip home. The results were pretty straightforward:

Starting Int32 test.
Increment ints took 64793168 (64)
Starting Queue test.
Using Queue took 908806800 (908)
Starting LinkedList test.
Using LinkedList took 1316493024 (1316)

The number represent the number of ticks used, the tests were, in order, a simple for I = max to 0, the queue test was a queue/dequeue, and the linkedlist test a addfirst/removefirst.

Obviously I think this illustrates my point, the native .NET implementations of a Queue being 25% faster than a Linked List. Not to mention that their intended use is completely different.

Helix login

Pages

News categories

Affiliates

Links

News

Registered user

Unregistered user

105972 visits. 2645 news articles. 350 journal entries