RE: Performance Issue with ForEach loop
- From: Jon Skeet [C# MVP] <skeet@xxxxxxxxx>
- Date: Wed, 9 Nov 2005 17:51:41 -0000
Marek Suchenek <MarekSuchenek@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
> MS needs to fix it.
Fix what, exactly? What is the reproducible problem with foreach which
you believe has been identified?
> My guess is that whoever implemented the code that is used in processing of
> list-type structures followed the watered-down LIST scheme without current
> position. Then the access time to n-th element is always Big Theta(n) even if
> the elements are accessed conscutively!
That's a bad guess, and one which isn't borne out by evidence
elsewhere, or indeed the following program:
using System;
using System.Collections;
public class Test
{
const int Size = 100000000;
static void Main(string[] args)
{
ArrayList list = new ArrayList(Size);
for (int i=0; i < Size; i++)
{
list.Add("x"); // Just an arbitrary reference
}
DateTime start = DateTime.Now;
DateTime end = DateTime.Now;
int totalLength = 0;
foreach (string x in list)
{
totalLength += x.Length;
}
Console.WriteLine ("Iterating took {0}", end-start);
Console.WriteLine ("Total length={0}", totalLength);
}
}
On my laptop, that iterates through all 100,000,000 elements in under a
second. If the total cost of the whole operation were O(n^2), then even
if a single iteration only took a single instruction when JITted, that
would still indicate over 10^16 instructions being performed in under a
second.
I don't know what the OP's problem actually was, but I don't believe it
has anything to do with the performance of foreach itself. Far more
likely is that the operation he was performing within each chunk
depended on the chunk size.
> That's the price we all pay for watering down of CS curricula (and
> textbooks).
In this case, this post is the price we pay for you making wild guesses
without doing any testing.
> Those who graduated recently may not know how to do this kind of
> things efficiently. For instance, over last 15 years I was teaching Data
> Structures upper division or graduate courses, I noticed that elegant and
> efficient implemantation of LIST (e.g. the one outlined in Aho, Hopcroft,
> Ullman classic text) slowly disappeared.
Did the testing of hypotheses before saying that a company "needs to
fix" a problem which hasn't been proven to exist also disappear?
> I am betting $20 that people who implemented the mentioned above pieces for
> MS are recent graduates who were not taught how to implement LIST-type
> structures efficiently.
Good job you didn't bet your money on the implementation itself, isn't
it?
--
Jon Skeet - <skeet@xxxxxxxxx>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
.
- References:
- RE: Performance Issue with ForEach loop
- From: Marek Suchenek
- RE: Performance Issue with ForEach loop
- Prev by Date: RE: Threads: waiting and context switches
- Next by Date: Re: Measuring Performance
- Previous by thread: Re: Performance Issue with ForEach loop
- Next by thread: Re: What's a good % Increase in performance
- Index(es):
Relevant Pages
|
