LinkedList faster iteration than List?

Question

For some reason it seems like my LinkedList is outperforming my List. I have a LinkedList because there is part of the code where I have to rearrange the children a lot. Everything after that bit of rearranging is simply looping over the data and performing calculations. I was previously just iterating over the LinkedList using an Iterator, but then I thought that I should simultaneously store a List of the same elements so I can iterate over them faster. Somehow, adding the List and iterating over that was significantly slower for the exact same thing. Not sure how this could be, so any info is helpful.

Here is roughly the code that I would EXPECT to be faster:

class Program {
    public static void Main(string[] args) {
        var originalList = new List<Thing>();
        for (var i = 0; i < 1000; i++) {
            var t = new Thing();
            t.x = 0d;
            t.y = 0d;
            originalList.Add(t);
        }
        var something = new Something(originalList);

        for (var i = 0; i < 1000; i++) {
            var start = DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
            something.iterate();
            time += (DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond) - start;
            Console.Out.WriteLine(time / (i + 1));
        }
    }

    class Thing {
        public double x {get; set;}
        public double y {get; set;}
    }

    class Something {
                    private List<Thing> things;
        private LinkedList<Thing> things1 = new LinkedList<Thing>();
        private List<Thing> things2 = new List<Thing>();

        public Class(List<Thing> things) {
            this.things = things;

            for (var i = 0; i < things.Count; i++) {
                things1.AddLast(things[i]);
                things2.Add(things[i]);
            }
        }

        public void iterate() {
            //loops like this happen a few times, but the list is never changed, only the
            //objects properties in the list
            for (var i = 0; i < things2.Count; i++) {
                                    var thing = things2[i];
                thing.x += someDouble;
                thing.y += someOtherDouble;
            }
        }
    }
}

This was what I was doing first, which I think SHOULD be SLOWER:

class Program {
    public static void Main(string[] args) {
        var originalList = new List<Thing>();
        for (var i = 0; i < 1000; i++) {
            var t = new Thing();
            t.x = 0d;
            t.y = 0d;
            originalList.Add(t);
        }
        var something = new Something(originalList);

        for (var i = 0; i < 1000; i++) {
            var start = DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
            something.iterate();
            time += (DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond) - start;
            Console.Out.WriteLine(time / (i + 1));
        }
    }

    class Thing {
        public double x {get; set;}
        public double y {get; set;}
    }

    class Something {
        private List<Thing> things;
        private LinkedList<Thing> things1 = new LinkedList<Thing>();

        public Class(List<Thing> things) {
            this.things = things;

            for (var i = 0; i < things.Count; i++) {
                things1.AddLast(things[i]);
            }
        }

        public void iterate() {
            //loops like this happen a few times, but the list is never changed, only the
            //objects properties in the list
            var iterator = things1.First;
            while (iterator != null) {
                var value = iterator.Value;
                value.x += someDouble;
                value.y += someOtherDouble;
                iterator = iterator.Next;
            }
        }
    }
}

How exactly do you benchmark? Is the cost of the constructor included in your measurement, and how often is `iterate()` called per instance? — , Jan 23 '14 at 18:27
check this: List vs a LinkedList. http://stackoverflow.com/questions/169973/when-should-i-use-a-list-vs-a-linkedlist — Matt, Jan 23 '14 at 18:29
I cannot even get that to compile. Please help me out the the syntax public Class(List things). — paparazzo, Jan 23 '14 at 18:30
im timing immediately before and after the `iterate` function is called. the constructor is not included. `iterate` is a function called on a single instance. — tau, Jan 23 '14 at 18:30
@Blam sorry i didnt mean for that to be compile-able. ill update with a more complete example. — tau, Jan 23 '14 at 18:31
@tau: Be sure you attach benchmarking code, even if it appears trivial. *How* the benchmark is performed is no less important than its subject. — pbalaga, Jan 23 '14 at 18:33
@pbalaga yes, i updated my code so you could see how i was measuring. i was measuring the same way for both approaches so i imagine thats not influencing the results, but if it is, then that would help me to know. thanks! — tau, Jan 23 '14 at 18:38
So it's said: you're going to need far bigger lists (or time the whole loop in `Main`) in order for `DateTime.Now` to be at all useful. Its resolution is typically tied to the system timer, which in NT has a 10ms interval. And 10ms is a *very* long time, once the JITter gets involved. (There's a `Stopwatch` class that's allegedly better suited for benchmarks. Try that.) — cHao, Jan 23 '14 at 18:57
When timing code, you have to use `Stopwatch`, make sure you're running a Release build, and make sure that you're running without the debugger attached. Otherwise your timings are likely to be inaccurate. See Eric Lippert's 4-part series on performance benchmarking. First part is at http://tech.pro/blog/1293/c-performance-benchmark-mistakes-part-one — Jim Mischel, Jul 03 '14 at 13:29

score 4 · Accepted Answer · answered Jan 23 '14 at 19:01

It's difficult to verify anything since it doesn't compile, so I can't run it on my machine, but still there are some big problems:

You should not be using DateTime.Now to measure performance. Instead use Stopwatch, which is capable of high fidelity time measurements, e.g.:

var stopwatch = Stopwatch.StartNew();
//do stuff here
stopwatch.Stop();
double timeInSeconds = stopwatch.Elapsed.TotalSeconds;

Your arithmetic is fundametally flawed in the following line:

DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond

Ticks are represented as integral numbers (long here) and the result of division is not a real number, but is truncated. E.g. 55 / 7 = 7. Therefore it definitely not a stable way of benchmarking.

Additionally, run the benchmark with more elements and ensure you do it in the Release mode.

thanks a lot for the advice! ill be able to accurately measure performance now and figure out where it is specifically slow. — tau, Jan 23 '14 at 19:08

score 1 · Answer 2 · edited May 23 '17 at 11:49

1

Based on your code, the cause of slow performance is not the iteration, it is from the action of adding element to the List<T>.

This post does a very good job on comparing the List and the LinkedList. List<T> is based on array, it is allocated in one contiguous block, so when you add more elements to it, the array will be resized, which cause the slow performance in your code.

If you come from the C++ world, List<T> in C# is equivalent to vector<T> in STD, while LinkedList<T> is equivalent to list<T> in STD.

edited May 23 '17 at 11:49

Community

1
1

answered Jan 23 '14 at 19:02

Matt

6,010
25
36

But he's not timing construction of the lists. He's timing iteration of the lists. So, whereas you're correct in that re-allocation of the `List` could make it slower than building a `LinkedList`, that information is not relevant to question. – Jim Mischel Jul 03 '14 at 13:25

LinkedList faster iteration than List?

2 Answers2