Dictionary.Keys.ElementAt method is slow (C# fun)

So, we were extending one the earlier implementations and required to loop through the Keys of a dictionary and perform operations that could be run in parallel. The code was added like following:

sw.Reset();
            sw.Start();
            Parallel.For(0, dictA.Keys.Count, (i) => {
                int x = dictA.Keys.ElementAt(i);
            });
            sw.Stop();
            Console.WriteLine("Time elapsed:" + sw.ElapsedMilliseconds);

On the surface this does not look all that bad. If you run this against a dictionary that has 100000 keys, this takes about 6-7 seconds on my machine. Clearly, something is amiss.

Looking through the implementation of ElementAt provides insight into why it is slow.

If you change the method to following, you can see why I say ElementAt is slow in this case.

sw.Reset();
            sw.Start();
            Parallel.ForEach(dictA.Keys.ToList(), (i) => {
                int x = i;
            });

            sw.Stop();
            Console.WriteLine("Time elapsed:" + sw.ElapsedMilliseconds);

Here are the results.

Time elapsed:6218
Time elapsed:6