String.Where Comparatively Poor Performance

c#, linq, performance

Solution

If the source code of `ToArray` in Mono is any indication, your implementation wins because it performs fewer allocations (scroll down to line 2874 to see the method).

Like many methods of LINQ, the `ToArray` method contains separate code paths for collections and for other enumerables:

TSource[] array;
var collection = source as ICollection<TSource>;
if (collection != null) {
    ...
    return array;
}

In your case, this branch is not taken, so the code proceeds to this loop:

int pos = 0;
array = EmptyOf<TSource>.Instance;
foreach (var element in source) {
    if (pos == array.Length) {
        if (pos == 0)
            array = new TSource [4];
        else
            // If the number of returned character is significant,
            // this method will be called multiple times
            Array.Resize (ref array, pos * 2);
    }
    array[pos++] = element;
}

if (pos != array.Length)
    Array.Resize (ref array, pos);

return array;

As you can see, LINQ's version may allocate and re-allocate the array several times. Your implementation, on the other hand, does just two allocations - the upfront one of the max size, and the final one, where the data is copied. That's why your code is faster.

Problem

I have two methods that take a string and remove any 'invalid' characters (characters contained in a hashset). One method uses Linq.Where, another uses a loop w/ char array. The Linq method takes nearly twice as long (208756.9 ticks) as the loop (108688.2 ticks) Linq: ``` string Linq(string field) { var c = field.Where(p => !hashChar.Contains(p)); return new string(c.ToArray()); } ``` Loop: ``` string CharArray(string field) { char[] c = new char[field.Length]; int count = 0; for (int i = 0; i < field.Length; i++) if (!hashChar.Contains(field[i])) { c[count] = field[i]; count++; } if (count == 0) return field; char[] f = new char[count]; Buffer.BlockCopy(c, 0, f, 0, count * sizeof(char)); return new string(f); } ``` My expectation would be that LINQ would beat, or at least be comparable to, the loop method. The loop method isn't even optimized. I must be missing something here. How does Linq.Where work under the hood, and why does it lose to my method?

Original source