Performance of Arrays vs. Lists

Question

Say you need to have a list/array of integers which you need iterate frequently, and I mean extremely often. The reasons may vary, but say it's in the heart of the inner most loop of a high volume processing.

In general, one would opt for using Lists (List) due to their flexibility in size. On top of that, msdn documentation claims Lists use an array internally and should perform just as fast (a quick look with Reflector confirms this). Neverless, there is some overhead involved.

Did anyone actually measure this? would iterating 6M times through a list take the same time as an array would?

Answer 1

I was worried that the Benchmarks posted in other answers would still leave room for the compiler to optimize, eliminate or merge loops so I wrote one that:

• Used unpredictable inputs (random)
• Runs a calculated with the result printed to the console
• Modifies the input data each repetition

The result as that a direct array has about 250% better performance than an access to an array wrapped in an IList:

• 1 billion array accesses: 4000 ms
• 1 billion list accesses: 10000 ms
• 100 million array accesses: 350 ms
• 100 million list accesses: 1000 ms

Here's the code:

static void Main(string[] args) {
  const int TestPointCount = 1000000;
  const int RepetitionCount = 1000;

  Stopwatch arrayTimer = new Stopwatch();
  Stopwatch listTimer = new Stopwatch();

  Point2[] points = new Point2[TestPointCount];
  var random = new Random();
  for (int index = 0; index < TestPointCount; ++index) {
    points[index].X = random.NextDouble();
    points[index].Y = random.NextDouble();
  }

  for (int repetition = 0; repetition <= RepetitionCount; ++repetition) {
    if (repetition > 0) { // first repetition is for cache warmup
      arrayTimer.Start();
    }
    doWorkOnArray(points);
    if (repetition > 0) { // first repetition is for cache warmup
      arrayTimer.Stop();
    }

    if (repetition > 0) { // first repetition is for cache warmup
      listTimer.Start();
    }
    doWorkOnList(points);
    if (repetition > 0) { // first repetition is for cache warmup
      listTimer.Stop();
    }
  }

  Console.WriteLine("Ignore this: " + points[0].X + points[0].Y);
  Console.WriteLine(
    string.Format(
      "{0} accesses on array took {1} ms",
      RepetitionCount * TestPointCount, arrayTimer.ElapsedMilliseconds
    )
  );
  Console.WriteLine(
    string.Format(
      "{0} accesses on list took {1} ms",
      RepetitionCount * TestPointCount, listTimer.ElapsedMilliseconds
    )
  );

}

private static void doWorkOnArray(Point2[] points) {
  var random = new Random();

  int pointCount = points.Length;

  Point2 accumulated = Point2.Zero;
  for (int index = 0; index < pointCount; ++index) {
    accumulated.X += points[index].X;
    accumulated.Y += points[index].Y;
  }

  accumulated /= pointCount;

  // make use of the result somewhere so the optimizer can't eliminate the loop
  // also modify the input collection so the optimizer can merge the repetition loop
  points[random.Next(0, pointCount)] = accumulated;
}

private static void doWorkOnList(IList<Point2> points) {
  var random = new Random();

  int pointCount = points.Count;

  Point2 accumulated = Point2.Zero;
  for (int index = 0; index < pointCount; ++index) {
    accumulated.X += points[index].X;
    accumulated.Y += points[index].Y;
  }

  accumulated /= pointCount;

  // make use of the result somewhere so the optimizer can't eliminate the loop
  // also modify the input collection so the optimizer can merge the repetition loop
  points[random.Next(0, pointCount)] = accumulated;
}