Filtering a list of vertices that lie inside a cylinder, with and without LINQ

Question

Since I don't know how LINQ works under the hood, I can't decide what version is best to use in term of rapidity of execution. I've done some testing with my testing data (Point Cloud) but I can't see a clear difference between the two. The only thing I know is that the real life data will be a larger Point Cloud so my guess is that the LINQ would be faster but this is only if LINQ doesn't do a for each under the hood. If it's the case, the 2 functions would be the same. What is your advice?

By the way, cylindre is a 3D cylinder and I want to know which point are inside.

Version 1 without LINQ

for (int i = 0; i < fpc.Vertices.Length; i++)
{
    if (cylindre.IsPointInside(fpc.Vertices[i]))
        listPoint.Add(fpc.Vertices[i]);
}

Version 2, with LINQ

var insidePoint =
    from pt1 in fpc.Vertices
    where cylindre.IsPointInside(pt1)
    select pt1;

    foreach (Point3D pt2 in insidePoint)
    {
        listPoint.Add(pt2);
    }

Answer 1

Under the hood LINQ will iterate over the collection, just as foreach will. The difference between LINQ and foreach is that LINQ will defer execution until the iteration begins.

Performance wise take a look at this blog post.

Answer 2

As has been said, the for loop will most likely be more performant, but you can still clean the code up a bit more:

for (int i = 0; i < fpc.Vertices.Length; i++)
{
    if (cylindre.IsPointInside(fpc.Vertices[i]))
        listPoint.Add(fpc.Vertices[i]);
}

Can become:

foreach (var vertice in fpc.Vertices)
{
    if (cylindre.IsPointInside(vertice))
        listPoint.Add(vertice);
}

EDIT: As per the performance question. This code will run in LINQPad. I found that the foreach version performs a few milliseconds better than the for loop.

var elements = Enumerable.Range(0, 4000000).Select(x => true).ToArray();


var sw = new Stopwatch();
var result = new List<bool>();
int trueCount = 0;
sw.Start();
for(int i=0; i < elements.Length; ++i)
{
    if (elements[i])
    {
        ++trueCount;
        result.Add(elements[i]);
    }
}

sw.Stop();
sw.ElapsedMilliseconds.Dump();

sw.Reset();
trueCount = 0;
result = new List<bool>();
sw.Start();
foreach(var element in elements)
{
    if (element)
    {
        ++trueCount;
        result.Add(element);
    }
}
sw.Stop();
sw.ElapsedMilliseconds.Dump();

EDIT2 - Regarding the link that seems to indicate such drastically poor performance in a foreach loop

The link (http://www.schnieds.com/2009/03/linq-vs-foreach-vs-for-loop-performance.html) is dealing with removing elements from a list. In the case that you have a generic list, removing elements via a for loop is not normally the best approach. A better approach is to use the RemoveAll method. RemoveAll will remove all elements matching the predicate and then consolidate the list as opposed to RemoveAt which will require moving all elements above the removed element. For performance comparison of the removal please see the below code (once again, this can be run in LINQPad). In my testing the RemoveAll ran roughly 250x faster.

var elements = Enumerable.Range(0, 100000).Select(x => x % 2 == 0).ToArray();

var sw = new Stopwatch();
var source = new List<bool>(elements);
sw.Start();
for(int i=0; i < source.Count; ++i)
{
    if (!source[i])
    {
        source.RemoveAt(i);
        --i;
    }
}

sw.Stop();
sw.ElapsedMilliseconds.Dump();
int count = source.Count;

sw.Reset();
source = new List<bool>(elements);

sw.Start();
source.RemoveAll((bool x) => {return x;});
sw.Stop();
sw.ElapsedMilliseconds.Dump();

Answer 3

Update:

If you're targeting .net 4 or later, you could use:

Parallel.ForEach()

or

RemoveAll().Parallel();

They should be faster than other methods.

Answer 4

I don't think it will run faster on LINQ. The function cylindre.IsPointInside would still have to be called on each item of Vertices.