Enumerable.Chunk throws OutOfMemoryException for very large chunk sizes.

[madelson]

Description

The exception is thrown even if the actual size of the enumerable is very small and the operation could (in theory) complete.

Reproduction Steps

new[] { 1 }.Chunk(int.MaxValue).ToArray();

Expected behavior

Returns a single element enumerable with a single chunk array of length 1.

Actual behavior

Throws OutOfMemoryException due to attempting to allocate a large array.

Regression?

No response

Known Workarounds

No response

Configuration

.NET 6, VS2022, Windows 10 x64.

Other information

One could argue that this shouldn't be fixed because callers just shouldn't ask for chunks that large. However, this can come up when using int.MaxValue as a means of "disabling" chunking/batching, especially when said batching is performed deeper in the call stack.

A fix for this would be to special case the creation of the first chunk when size is above a certain threshold. For large sizes, we can assume that the chunk probably won't fill and therefore we can build up to the full size (as is done for ToArray() rather than starting by trying to allocate the final array).

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

Tagging subscribers to this area: @dotnet/area-system-linq
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

The exception is thrown even if the actual size of the enumerable is very small and the operation could (in theory) complete.

Reproduction Steps

new[] { 1 }.Chunk(int.MaxValue).ToArray();

Expected behavior

Returns a single element enumerable with a single chunk array of length 1.

Actual behavior

Throws OutOfMemoryException due to attempting to allocate a large array.

Regression?

No response

Known Workarounds

No response

Configuration

.NET 6, VS2022, Windows 10 x64.

Other information

One could argue that this shouldn't be fixed because callers just shouldn't ask for chunks that large. However, this can come up when using int.MaxValue as a means of "disabling" chunking/batching, especially when said batching is performed deeper in the call stack.

A fix for this would be to special case the creation of the first chunk when size is above a certain threshold. For large sizes, we can assume that the chunk probably won't fill and therefore we can build up to the full size (as is done for ToArray() rather than starting by trying to allocate the final array).

Author:	madelson
Assignees:	-
Labels:	area-System.Linq, untriaged
Milestone:	-

[EgorBo]

However, this can come up when using int.MaxValue as a means of "disabling" chunking/batching

Technically Chunk can operate on data longer than int.MaxValue, e.g. "infinite" iterator and we don't know input's Length in advance. The best that we can do is to check input IEnumerable whether it's some known type of array/list we can query Length/Count from

[madelson]

Technically Chunk can operate on data longer than int.MaxValue

True, hence the quotes around disabling. That said there are plenty of scenarios where you know that the upper bound is less than int max (e. g. if the original source was a collection).

The best that we can do is to check input IEnumerable whether it's some known type of array/list we can query Length/Count from

I agree that there's nothing we can do about the general case of > ArrayMax elements in source with size > ArrayMax. However, if it is desirable that Chunk() should succeed in scenarios where there are <= ArrayMax elements with size > ArrayMax that is achievable.

[EgorBo]

That said there are plenty of scenarios where you know that the upper bound is less than int max (e. g. if the original source was a collection).

Want to file a PR with this change? (If BCL folks aren't against this idea)

[eiriktsarpalis]

Is this a real problem one would encounter though? It sounds to me like we'd be making the method slower for everyone simply to make it better behaved in a pathological scenario. Throwing OOM seems like an appropriate behavior (since most likely it's caused by a user bug).

[eiriktsarpalis]

However, this can come up when using int.MaxValue as a means of "disabling" chunking/batching, especially when said batching is performed deeper in the call stack.

So you're suggesting we special-case int.MaxValue as infinity rather than checking if the source count is less than the size parameter in the special case? Is there precedent for that in other APIs?

[EgorBo]

we'd be making the method slower for everyone simply to make it better behaved in a pathological scenario

I think it's not a pathological scenario, e.g. new int[] {1,2,3}.Chunk(1000) where it will allocate an int[1000] while it could just pay a little of perf for casts and allocate only int[3].

[Tornhoof]

You could always use the fancy new TryGetNonEnumeratedCount to see if you can optimize the chunk before allocating the full size in the fallback.

[eiriktsarpalis]

I think it's not a pathological scenario, e.g. new int[] {1,2,3}.Chunk(1000) where it will allocate an int[1000] while it could just pay a little of perf for casts and allocate only int[3].

Sure, but it's not pay for play. Now you're forcing every call to invoke TryGetNonEnumeratedCount even though this method is mostly used in Rx-style streaming applications where source is typically not a collection and size is typically a constant parameter.

it will allocate an int[1000] while it could just pay a little of perf for casts and allocate only int[3].

FWIW the same issue also applies to sources of length 1003 for the final chunk. That's by design though, it's an explicit trade-off to using List<T> for building the intermediate chunks.

[madelson]

Is this a real problem one would encounter though?

@eiriktsarpalis for context, we've have had this utility method in our internal utility for years and I was looking to replace it with Chunk(). Our version handles the "large size" use case because we found that developers expected to be able to "turn off" chunking inline by passing a large value and were surprised that the implementation would actually insist on pre-allocating arrays of the chunk size regardless of how large it was.

For example, imagine a function like this that uses Chunk internally:

void CreateRecords(IEnumerable<...> items, ..., int maxBatchSize);

Encountering an OutOfMemoryException when the application is not actually out of memory is somewhat confusing too (the message does clarify).

So you're suggesting we special-case int.MaxValue as infinity

I wouldn't propose special-casing int max. I think there is something to be said for the method returning successfully in cases where it can do so. Based on the description of what Chunk() does, calling it with Count() <= ArrayMax seems like it should always succeed (provided sufficient memory); the fact that it doesn't is due to the specifics of the implementation.

Is there precedent for that in other APIs?

Skip() and Take() both work as expected with int max and the code makes a point of supporting this (see https://source.dot.net/#System.Linq/System/Linq/Partition.SpeedOpt.cs,304 and https://source.dot.net/#System.Linq/System/Linq/Partition.SpeedOpt.cs,421). It's not exactly the same thing, just philosophically similar. I'd be willing to bet that 99% of people calling .Take(int.MaxValue) are doing it to "take everything" vs. actually working with more than int max elements.

It sounds to me like we'd be making the method slower ... it's not pay for play

I'm imagining that any special handling would come into play only when size is above a certain threshold. Anyone below the threshold wouldn't pay the cost other than the single integer comparison.

If the threshold were ArrayMax, then there is effectively no cost because the method always fails in that case currently.

Possibly there are lower thresholds where the cost of allocating memory upfront when it often won't all be used is worse than the cost of having to grow the array when the memory will be used.

Want to file a PR with this change? (If BCL folks aren't against this idea)

Sure, provided there is a path forward that all are happy with (doesn't seem like the case currently).

[stephentoub]

we found that developers expected to be able to "turn off" chunking inline by passing a large value

FWIW, I don't think this is a reasonable expectation the implementation needs to account for. If the shape of the method you exposed, the context in which you exposed it, etc. makes it more likely that developers would have such an expectation, your CreateRecords wrapper can simply skip the chunking and just ToArray above whatever threshold makes sense for your application. Enumerable.Chunk docs are explicit about creating arrays of the specified size; that's not the case with Enumerable.Take.

Sure, but it's not pay for play. Now you're forcing every call to invoke TryGetNonEnumeratedCount even though this method is mostly used in Rx-style streaming applications where source is typically not a collection and size is typically a constant parameter.

I agree it's not pay-for-play and that pay-for-play is in general the goal, but at the same time, the ship sailed on Enumerable.Chunk being concerned with top performance when we decided that every chunk would be a brand new array allocation. If we think there's a meaningful number of cases where the input's size can be determined up front and where it'd be smaller than the specified chunk size, adding a fast-path that just handles a single chunk seems ok. (It'd be good to validate the perf impact, though, regardless.)

[eiriktsarpalis]

If we think there's a meaningful number of cases where the input's size can be determined up front and where it'd be smaller than the specified chunk size, adding a fast-path that just handles a single chunk seems ok. (It'd be good to validate the perf impact, though, regardless.)

I have concerns about that, source.Chunk(int.MaxValue) will have different observable behaviour depending on whether source is countable or not (successfully returning a single chunk vs throwing OOM). That sounds like a violation of LSP to me.

We might want to consider solving the issue in the general case using List<T> to build the chunks. It would result in a few additional allocations/copying but like you said the ship has sailed when it comes to peformance. It might look like the following (NB this hasn't been tested):

private static IEnumerable<TSource[]> ChunkIterator<TSource>(IEnumerable<TSource> source, int size)
{
    using IEnumerator<TSource> e = source.GetEnumerator();

    if (e.MoveNext())
    {
        var chunkBuilder = new List<TSource>(Math.Min(size, 1024)); // some cutoff constant after which resizes are acceptable.

        do
        {
            chunkBuilder.Add(e.Current);

            int i = 1;
            for (; i < size && e.MoveNext(); i++)
            {
                chunkBuilder.Add(e.Current);
            }

            yield return chunkBuilder.ToArray();

            if (i == size)
            {
                chunkBuilder.Clear();
            }
            else
            {
                yield break;
            }
        }
        while (e.MoveNext());
    }
}