NetFabric.Hyperlinq: Experiencing Slow ArrayPool Performance with Enumerables

Awesome! Thank you for your efforts, @aalmada!

Today I was thinking a bit more about Contains() and realized I don’t need the source generator to fix the issue with your case.

Contains() is very confusing because it’s both a LINQ method and an ICollection<> method. I have to be very careful not to create infinite call loops. I have already written so many versions of it that I lost count. I sure hope this is the last time. 😉

Contains()

ToArray() performance is about the same with and without ArrayPool.

Much more acceptable

Sorry, I got lost in these details and forgot about the return type of ArrayPool.Rent().

Hah no worries there are only a million billion things going on with what we do here. 😃 I am amazed that I am able to keep as many details straight that I do, personally. It’s sort of the name of the game, TBH. And FWIW my intent is not to point out that a possible mistake was made (an attitude that seems to be rampant in dev culture) but to ensure my understanding and that I am following along correctly.

In any case, I am glad you are able to apply a fix. 👍

If the source implements ICollection, then CopyTo(T[], int) should be used instead

OK thank you for the investigation/explanation @aalmada … If I understand correctly, the CopyTo is what is occurring in Linq and not Hyperlinq, correct? Is this something you think will be done in the new source generator magic you’re working on?

Right, CopyTo is occurring in Linq but not Hyperlinq. It’s not related to the source generator. It’s only related to the limitation on the CopyTo destination parameter but read what’s next…

The ArrayPool.Rent() methods returns a Span<> not an array

To clarify here, I believe you meant the inverse. 😁 That is, ArrayPool.Rent() returns an array and not a Span. The rest does align with my understanding, there is no CopyTo(Span<>) and the closest that I know of is CollectionsMarshal.AsSpan which only deals with List<T>.

Damnit, you’re right once again. I feel so embarrassed… 😔

ArrayPool.Rent() does return an array. It’s my implementation of ValueMemoryOwner<> that returns Memory<>.

I implemented it this way because ArrayPool.Rent() may return an array larger than requested. That requires some more work by the caller of ToArray() if this larger array was returned. I slice it using a Memory<> to make it simpler. I implement IMemoryOwner<> to make it similar to MemoryPool.

Sorry, I got lost in these details and forgot about the return type of ArrayPool.Rent().

This means I can fix the issue. CopyTo can be applied on the unsliced array and then return the sliced one.

Thanks for insisting on this… 😞

I took another look at the Contains. I understand you are saying it can be boxed, but I guess I am confused on how Linq can be so much faster without any additional allocations. It almost suggests to do a check for IEnumerable and if so use Linq instead of Hyperlinq.

Yes, you’re right. That shouldn’t happen. I now understand that it’s an issue with how AsValueEnumerable() is implemented.

I’ve been working on a total refactor of the source generator that will fix this issue and many more. I hope to release this other version soon.

The issue is that, even if I calculate the sum for both, the dispose is still accounted for

I believe I am following with everything except this. You mean unaccounted for, correct? From my understanding Dispose is not being called, thus the disparity.

In any case, there is still a huge disparity with the HyperlinqEnumerable and everything else. It again makes me wonder if we can ascertain that it’s strictly IEnumerable (and not ICollection, etc) to use Linq and Hyperlinq for everything else.

Those 10x times slower can’t be the disposing. 🤪 I’m going to check what’s going on.

I now realized that I’m doing the benchmarking wrong.

The ToArray() with an ArrayPool parameter returns a ValueMemoryOwner<> that has to be disposed so that the rented memory is returned to the pool. To avoid dead code elimination and to make sure the dispose happens, just like you, I’m calculating the sum of the array items and disposing before returning the result of the sum.

For the other ToArray() benchmarks I was just returning the array because I’m only interested in benchmarking its creation. Not iterating on it.

The issue is that, even if I calculate the sum for both, the dispose is still accounted for. Making the benchmarks still not really comparable.

I noticed a long time ago about this limitation and I’ve been wanting to report an issue but ended up never doing it. I finally did it. https://github.com/dotnet/BenchmarkDotNet/issues/1788

Let’s see what they say but, for now, I’ll work with what we have now.

OK, that makes sense now, @aalmada. I appreciate your time in investigating this as well as the time taken to explain your findings. Hopefully, you can track down the ArrayPool bandit. 😃 🤞

For now, I run my benchmarks and got the following results:

ToArray()

Contains()

I now need to analyze the code to understand what’s going on with ToArray() with the ArrayPool parameter.

On the Contains(), notice that it only allocates when it’s an enumerable and the enumerator is a reference type. That’s expected. The only way to enumerate it is by calling GetEnumerator() which created the instance. Any other operation appended will not have this penalty as the first operation returns an IValueEnumerable<,> for which the GetEnumerator() returns a value type.

For the other enumerables, it calls the ICollection<>.Contains(). This will allocate if the enumerable (not the enumerator) is a value type, which will be boxed.

It will allocate an enumerator if it implements IReadOnlyCollection<> but not ICollection<>. Most collections implement both.

Sorry, I didn’t notice you reported an issue. 😦 I’ll have to check what’s going on. Thanks for reporting it.