CODEWITHSUNDEEP
c#.netperformancedata-structures
tau
tau

Reputation: 6749

LinkedList faster iteration than List?

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;
            }
        }
    }
}

Upvotes: 1

Views: 670

Answers (2)

Matt
Matt

Reputation: 6050

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.

Upvotes: 1

pbalaga
pbalaga

Reputation: 2068

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.

Upvotes: 4

Related Questions