Nick Gravelyn

So after the mess of my last post (see the comments for how it all plays out) it seems that while LINQ is really efficient for small data sets, ordering appears to happen at an O(n^2) rate (or close) of speed. Try sticking a list with a few million items in it through that and it bogs right down.

I decided to play with LINQ tonight and see if I can make things more efficient, with or without maintaining the readability. First I wrote up this method which I believe is about the most efficient it can get. It can turn through a 375,000 item list of Vector3s in about 0.012 seconds, i.e. fast enough to happen in a 60fps game (though just barely):

float d = float.PositiveInfinity;
Vector3 closest = testPoint;
foreach (var v in vectors)
{
	float dt =
		(testPoint.X - v.X) * (testPoint.X - v.X) +
		(testPoint.Y - v.Y) * (testPoint.Y - v.Y) +
		(testPoint.Z - v.Z) * (testPoint.Z - v.Z);
	if (dt < d)
	{
		closest = v;
		d = dt;
	}
}

With that as my benchmark I decided to compare that with a naive LINQ implementation:

var closest =
	(from v in vectors
	 let d = Vector3.DistanceSquared(testPoint, v)
	 orderby d
	 select v).First();

This LINQ method took .351 seconds to get through the same list of vectors. The problem is that we’re sorting the entire list which gets pretty slow with that many entries.

Next up is a really ugly LINQ query that aims to use a local variable to try and cut down on the time.

float e = float.PositiveInfinity;
var closest =
	(from v in vectors
	 let d = Vector3.DistanceSquared(testPoint, v)
	 where (d < e && ((e = d) != float.NegativeInfinity))
	 orderby d
	 select v).First();

This time we throw in a where clause that compares the distance to our local variable so that we never add an item to our intermediate list unless it is closer to us than the previous point. The ugly hacky stuff in there is one of the methods I’ve found for assigning a local variable inside a LINQ query. I just assign the value to the local variable and then compare that against a value I know it will never be (in this case a negative value since DistanceSquared cannot be negative).

By doing this test, the resulting list we wind up sorting tends to only have around 13 or 14 items in it. This method manages to get me my result in about 0.081 seconds. Not quite fast enough but it’s about 75% faster than our previous method.

I think that’s about the best I can come up with for now. LINQ definitely isn’t something you want to tear through giant lists with, but then when are you really going through 375,000 points comparing them to a position? At that point you’d use some spatial partitioning to narrow that down. As some food for thought, once we have a list with just 375 items in it, our results turn to this:

foreach: 0.0007573 seconds
LINQ (naive): 0.0104185 seconds
LINQ (with where clause hackery): 0.001516 seconds

In this case you can actually get away with the naive LINQ query as long as you don’t have too much else to do (it’s burned up 10 of the 16 milliseconds the frame gets), but the LINQ with the hackery actually is down to a point of being quick enough to use. But then you realize that the foreach loop is probably easier to understand and still kicks its butt in performance.

All in all I’d say use LINQ if you don’t mind the overhead. It’s a great way to simplify some of your code where garbage and performance aren’t issues.