Linq SelectMany causes memory allocations for each internal set?

Question

I've got a simple list of hashsets:

List<HashSet<TestObj>> listOfSets = new List<HashSet<TestObj>>();

When I iterate it manually, there is no additional memory allocation:

foreach(var childSet in listOfSets) {
    foreach (var neighbor in childSet) {
        // do something with neighbor
    }
}

However, if I do the same using Linq's SelectMany, it allocates memory on the Heap, once per childSet:

foreach(TestObj neighbor in listOfSets.SelectMany(x => x)) {
    // do something with neighbor
}

Any idea why it does that? Is there a way around it? Otherwise, is there another way to return an IEnumerable<TestObj> from a list of sets, so that it won't allocate any memory when iterating it?

Edit: It appears to have something to do with boxing. When I convert it to IEnumerable<IEnumerable<TestObj>> then direct iteration also triggers memory allocations. Any ideas what exactly is happening?

// This code triggers malloc for every set in listOfSets
IEnumerable<IEnumerable<TestObj>> enumOfEnum = listOfSets;
foreach(var childSet in enumOfEnum) {
    foreach (var neighbor in childSet) {
        // do something with neighbor
    }
}

Edit: Ok, so because SelectMany is an extention for IEnumerable<IEnumerable<T>>. When I call SelectMany on List<HashSet<T>>, it implicitly casts to IEnumerable<IEnumerable<T>>, and because HashSet<T>.Enumerator is a struct, every one of the HashSets is boxed (which is normal behavior when casting a struct to an interface).

Unless I'm looking at the wrong code, the way `SelectMany` works doesn't look too much different: https://github.com/microsoft/referencesource/blob/5697c29004a34d80acdaf5742d7e699022c64ecd/System.Core/System/Linq/Enumerable.cs#L535-L541 — gunr2171, Feb 09 '21 at 15:05
No they are the same : https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,535 . and Select many do returns `IEnumerable` https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.selectmany?view=net-5.0 — Drag and Drop, Feb 09 '21 at 15:07
I'm using Unity3D, and the profiler there counts memory allocations calls. If I try to implement an IEnumerator manually, like in the Linq, it still generates memory allocations. However if I just do the two fors directly, it doesn't... — tbkn23, Feb 09 '21 at 15:17
Update - It appears to have something to do with boxing. When I convert it to IEnumerable> then direct iteration also triggers memory allocations. See edit at bottom of quesiton. — tbkn23, Feb 09 '21 at 15:44
Hum, do you have code in the inner block or nothing? It's possible that the emptyness get better execution in foreach where compiler optimise it away. — Drag and Drop, Feb 09 '21 at 16:09

Linq SelectMany causes memory allocations for each internal set?

0 Answers0