a new GC API for large array allocation

To give users with high perf scenarios more flexibility for array allocations I propose to add a new API in the GC class.

Rationale

Below are mechanisms we would like to support for high perf scenarios

coreclr dotnet/runtime#20704;
choose whether you want to allocate the object as a gen0 object or in the old generation;
choose whether you want to pin the object you are requesting to allocate;

I am also thinking of exposing the large object size threshold as a config to users and this API along with that config should help a lot with solving the LOH perf issues folks have been seen.

Proposed APIs

class GC
{
    // generation: -1 means to let GC decide (equivalent to regular new T[])
    // 0 means to allocate in gen0
    // GC.MaxGeneration means to allocate in the oldest generation
    //
    // pinned: true means you want to pin this object that you are allocating
    // otherwise it's not pinned.
    //
    // alignment: only supported if pinned is true.
    // -1 means you don't care which means it'll use the default alignment.
    // otherwise specify a power of 2 value that's >= pointer size
    // the beginning of the payload of the object (&array[0]) will be aligned with this alignment.
    static T[] AllocateArray<T>(int length, int generation=-1, bool pinned=false, int alignment=-1)
    {
        // calls the new AllocateNewArray fcall.
        return AllocateNewArray(typeof(T).TypeHandle.Value, length, generation, pinned, clearMemory: true);
    }

    // Skips zero-initialization of the array if possible. If T contains object references, 
    // the array is always zero-initialized.
    static T[] AllocateUninitializedArray<T>(int length, int generation=-1, bool pinned=false, int alignment=-1)
    {
        return AllocateNewArray(typeof(T).TypeHandle.Value, length, generation, pinned, clearMemory: false);
     }
}

Restrictions

Only array allocations are supported via this API

Note that I am returing a T[] because this only supports allocating large arrays. it's difficult to support allocating a non array object since you'd need to pass in args for constructors and it's rare for a non array object to be large anyway. I have seen large strings but these are unlikely used in high perf scenarios. and strings also have multiple constructors...we can revisit if string is proven to be necessary.

Minimal size supported

Even though the size is no longer restricted to >= LOH threshold, I might still have some sort of size limit so it doesn't get too small. I will update this when I have that exact size figured out.

Perf consideration

Cost of getting the type

The cost of "typeof(T).TypeHandle.Value" should be dwarfed by the allocation cost of a large object; however in the case of allocating a large object without clearing memory, the cost may show up (we need to do some profiling). If that's proven to be a problem we can implement coreclr dotnet/corefx#5329 to speed it up.

Pinning

We'll provide a pinned heap that are only for objects pinned via this API. So this is for scenarios where you

have control over the allocation of the object you want to pin and
want to pin it as long as it's alive

Since we will not be compacting this heap fragmentation may be a problem so as with normal pinning, it should be use it with caution.

I would like to limit T for the pinning case to contain no references. But I am open to discussion on whether it's warranted to allow types with references.

@jkotas

Edited proposal to match naming guidelines

@jkotas supportive of this going to api review?

@jkotas

Nit: The method should be static.

@jkotas supportive of this going to api review?

Yes.

return AllocateNewArray(typeof(T).TypeHandle.Value, length, generation, clearMemory);

I think this should rather be return AllocateNewArray(typeof(T[]), length, generation, clearMemory) ... but that's an implementation detail we can figure out later.

IMO it would be good place to add alignment control for GC allocations. Additional parameter or additional overload would serve purpose very well.

class GC
{
    // generation: -1 means to let GC decide
    // 0 means to allocate in gen0
    // GC.MaxGeneration means to allocate in the oldest generation
    T[] AllocateLargeArray<T>(int length, int generation=-1, int alignment = -1, bool clearMemory=true)
    {
        // calls the new AllocateNewArray fcall.
        return AllocateNewArray(typeof(T).TypeHandle.Value, length, generation, clearMemory);
    }
}

where alignment value -1 means GC decides and any value > 0 asks for allocation alignment as specified by caller.

See dotnet/csharplang#1799 [Performance] Proposal - aligned new and stackalloc with alignas(x) for arrays of primitive types and less primitive as well

alignment control for GC allocations

This problem has been discussed in https://github.com/dotnet/corefx/issues/22790 and related issues.

Video

Should it just be AllocateArray? In the end, the developer controls the size.
What happens if the developer specifies gen-0 but wants to create a 50 MB array? Will the API fail or will it silently promote the object to, say, gen-1?
No clearing the memory is fine, but we want to make sure it shows up visibly on the call side (a plain false isn't good enough). We'd like this to be an overload, such a AllocateLargeArrayUninitialized? The other benefit of having an overload is that this could be constrained to only allow Ts with no references (unmanaged constraint).
Is LOH the same as MaxGeneration? If not, how can a developer explicitly allocate on the LOH?

We'd like to this be an overload, such a AllocateLargeArrayUninitialize

Agree. Did you mean AllocateUninitializedArray ?

The other benefit of having an overload is that this could be constrained to only allow Ts

I do not think we want the unmanaged constrain it. It would just make this API more pain to use in generic code for no good reason. GC should zero-initialize the array in this case. Note that the array will be zero-initialize in many cases anyway when the GC does not have a uninitialized block of memory around. The flag is just a hint to the GC that you do not care about the content of the array.

Should it just be AllocateArray? In the end, the developer controls the size.

this is only meant for large array allocation, ie, arrays larger than the LOH threshold.

What happens if the developer specifics gen-0 but wants to create a 50 MB array? Will the API fail or will be silently promote it to, say, gen-1?

that's something we need to decide. but if it fails to allocate anything in gen0 it would revert to the default behavior (ie, on LOH).

No clearing the memory is fine, but we want to make sure it shows up visibly on the call side

I am not sure why this needs to be an overload but not the other aspects. why wouldn't there be a AllocateLargeArrayInYoungGen overload too, then?

Is LOH the same as MaxGeneration? If not, how can a developer explicitly allocated on the LOH?

LOH is logically part of MaxGeneration.

I do not think we want the unmanaged constrain it. It would just make this API more pain to use in generic code for no good reason.

this API is not for generic code though. I would only expect people with very clear intentions for perf to use this. and if you specify to not clear, I think, if I were a user, it would be more desirable to indicate an error if that can't be done (ie, the type has references) instead of silently taking much longer.

after the discussion it seems like this API should perhaps take another parameter that indicates whether the operation succeeded or not, eg, AllocateLargeArrayError.TooBigForGen0, AllocateLargeArrayError.MustClearTypesContainsReferences. however I will leave this decision to API folks.

this API is not for generic code though

What makes you think that it is not? It is very natural to use these API to implement generic collections optimized for large number of elements.

I am not sure why this needs to be an overload but not the other aspects. why wouldn't there be a AllocateLargeArrayInYoungGen overload too, then?

The uninitialized memory has security ramifications so you want to have an easy way to search for it. Generation hint has no security ramifications.

What makes you think that it is not? It is very natural to use these API to implement generic collections optimized for large number of elements.

do you think the default is not good for "implementing generic collections with large number of elements" in general? I would think it is - you'd want the objects to be cleared so you don't deal with garbage; and most of the time if you have an object with large # of elements it should be on LOH, not gen0.

The uninitialized memory has security ramifications

ahh, yep, makes sense to single out APIs with security ramifications.

The default is fine for most cases. This API is workaround for cases where the default does not work well and turns into bottleneck.

Large arrays are used mostly for buffers and collections. I think it is important that this API works well for specialized generic collections.

For example, the email thread from a few months ago that both of us are on had this real-world code fragment:

class ListEx<T> : IList<T>
{
    private T[][] Memory = null;

    public T this[int index]
    {
        get
        {
            removed checking
            return Memory[index / blockSize][index % blockSize];
        }

This code artificially allocates number of smaller arrays to simulate large array. It does it to avoid landing short-lived large array in Gen2 heap. The double indirection has non-trivial cost (the element access is several times slower). Changing the implementation of this ListEx<T> to use these APIs and avoiding the double indirection should be straightforward. Also, when T does not contain object references, it is fine for the backing array to be uninitialized.

😆 I see what the confusion was...by "generic" I meant "general cases" and you meant "code that implements generics collections". what I meant was this is not an API used in general cases so it's a little harder to use I don't see that as a problem.

@Maoni0

this is only meant for large array allocation, ie, arrays larger than the LOH threshold

@Maoni0, what would be the proposed behavior if the user attempts to create an array smaller than the LOH threshold?

Or another option: Allocate all memory on the unmanaged side and if you want to "extend" a pointer, pass that pointer on to a special function on the managed side to the unmanaged side and it take care of the rest, then manipulate that data (write to it) like normally.

That would force the used data structures to be blittable and in this case that wouldn't be possible. The data isn't needed on the unmanaged side, its for the managed code, but the unmanaged code has to point where to get that data.

At the moment I'm just passing id (int) to unmanaged code and then use that to retrieve the managed object from a dictionary (could also be an array for better performance). This obviously works just fine but I would rather deal with raw pointers for simplicity and performance.

This is just one use case I have but there are certainly way more valid usage cases for references in the POH. Also as the POH already seems to support references, it would seem to make sense to allow that (?), unless there's some blocking issue.

Isn't it the use case for a normal gchandle instead of special convention to pass some index/pointer?

The problem with GCHandles is that it fragments the heap and has some overhead due to the internal table needed to keep those objects as roots. The POH solves this issue by having separate heap for those objects. So if you have hundreds of long lived objects that are kept pinned ultimately results to fragmented heap and increased memory usage, which isn't ideal.

there is probably some misconception here. as in I read you like you don't really need objects themselves pinned, but you need to pass them to unmanaged code so that they can then be passed back to managed code and used. GCHandle solves this, and does not require pinning. I don't mean using it for pinning.

Ah, right! You were speaking about normal GCHandle. That could also work for this, but as far as I remember, having a lot of GCHandles will causes problems by having long GC pauses. I could confirm this and see what happens.

having a lot of GCHandles will causes problems by having long GC pauses

The problem are GCHandles that point to Gen0 objects. They are scanned during stop-the-world pause in the current GC. It is no different from POH array slots pointing to Gen0 objects. They are scanned during stop-the-world pause as well. The exact algorithm is different between the two so the absolute numbers will vary and also depend on the usage pattern. But it is safe to say that having a lot of either one will contibute to GC pause times.

The problem are GCHandles that point to Gen0 objects

Why would only gen 0 objects be a problem? What about gen 1/2 objects? I couldn't find any differences between generations when doing some testing.

The exact algorithm is different between the two so the absolute numbers will vary and also depend on the usage pattern.

I was expecting the POH to be more lightweight and optimized for this and get the best performance.

Benchmarks

I'm not really sure what would be the most ideal way to benchmark the differences between these two and I'm unsure does my benchmark reflect anything relevant in the real world, but here are my findings. The N is the number of objects that were allocated and the benchmark code only does one call to GC.Collect() and the objects are created beforehand in the iteration setup.

On the first test I created an object[] array in the pinned heap and then assigned objects to it.

Method	N	Mean	Error	StdDev	Median
DoGcPOH	1000	129.6 us	11.78 us	33.61 us	116.8 us
DoGcPOH	10000	284.3 us	20.00 us	57.39 us	279.9 us
DoGcPOH	100000	1,667.7 us	127.67 us	368.37 us	1,535.8 us

On the second test I had a GCHandle[] array and then assigned the created GCHandles to it (so I can clean them up afterwards).

Method	N	Mean	Error	StdDev	Median
DoGcHandles	1000	230.8 us	14.71 us	41.50 us	233.1 us
DoGcHandles	10000	376.2 us	32.82 us	92.03 us	336.5 us
DoGcHandles	100000	2,691.3 us	167.84 us	489.59 us	2,493.8 us

So from the looks of it, the POH is scanned much faster than the GCHandles, as expected. These objects were in the generation 0 upon calling the GC.Collect, but promoting them beforehand does not reflect any differences in the numbers.

Benchmark code

The benchmarks are split to two separate classes for simplicity.

The POH benchmark:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Runtime.CompilerServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Diagnostics.Windows.Configs;

//[MemoryDiagnoser]
//[EtwProfiler(performExtraBenchmarksRun: false)]
//[SimpleJob(targetCount: 1000)]
public class PohBenchmarks
{
	[Params(1_000, 10_000, 100_000)]
	public int N;

	private object[] handles;

	[GlobalSetup]
	public void GlobalSetup()
	{
		this.handles = GCHelpers.AllocateArray<object>(this.N);
	}

	[IterationSetup]
	public void IterationSetup()
	{
		GC.Collect();

		for (int i = 0; i < this.N; i++)
		{
			this.handles[i] = new();
		}
	}

	[Benchmark]
	public void DoGcPOH()
	{
		GC.Collect();
	}

	[IterationCleanup]
	public void IterationCleanup()
	{
		this.handles.AsSpan().Clear();
	}
}

internal static class GCHelpers
{
	private enum GC_ALLOC_FLAGS
	{
		GC_ALLOC_NO_FLAGS = 0,
		GC_ALLOC_ZEROING_OPTIONAL = 16,
		GC_ALLOC_PINNED_OBJECT_HEAP = 64,
	};
	
	private static readonly Func<IntPtr, int, GC_ALLOC_FLAGS, Array> AllocateNewArray = typeof(GC).GetMethod("AllocateNewArray", BindingFlags.Static | BindingFlags.NonPublic).CreateDelegate<Func<IntPtr, int, GC_ALLOC_FLAGS, Array>>();

	internal static T[] AllocateArray<T>(int length)
	{
		return Unsafe.As<T[]>(GCHelpers.AllocateNewArray(typeof(T[]).TypeHandle.Value, length, GC_ALLOC_FLAGS.GC_ALLOC_PINNED_OBJECT_HEAP));
	}
}

The GCHandle benchmark:

using System;
using System.Runtime.InteropServices;
using System.Threading;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Diagnostics.Windows.Configs;

//[MemoryDiagnoser]
//[EtwProfiler(performExtraBenchmarksRun: false)]
//[SimpleJob(targetCount: 1000)]
public class GcHandleBenchmarks
{
	[Params(1_000, 10_000, 100_000)]
	public int N;

	private GCHandle[] handles;

	[GlobalSetup]
	public void GlobalSetup()
	{
		this.handles = new GCHandle[this.N];
	}

	[IterationSetup]
	public void IterationSetup()
	{
		GC.Collect();

		for (int i = 0; i < this.N; i++)
		{
			object instance = new();

			this.handles[i] = GCHandle.Alloc(instance, GCHandleType.Normal);
		}
	}

	[Benchmark]
	public void DoGcHandles()
	{
		GC.Collect();
	}
	
	[IterationCleanup]
	public void IterationCleanup()
	{
		int n = this.N;
		for (int i = 0; i < n; i++)
		{
			this.handles[i].Free();
			this.handles[i] = default;
		}
	}
}

Why would only gen 0 objects be a problem? What about gen 1/2 objects?

Gen2 -> Gen2 references are scanned in the background. The GC pause times are not affected by how many of them you have as long as the background GC works as expected).

Gen2 -> Gen0 references are scanned during the stop-to-world pauses. The GC pause times are always affected by how many of them you have.

POH is scanned much faster than the GCHandles,

The GC scanning of arrays is optimized for scanning of the whole array and it works well for the usage pattern in your micro-benchmark. It is what I meant "the exact algorithm is different between the two so the absolute numbers will vary and also depend on the usage pattern".

Gen2 -> Gen2 references are scanned in the background. The GC pause times are not affected by how many of them you have as long as the background GC works as expected).

And I'm gonna assume that the GC.Collect() forces the gen2 to be blocking even with the concurrent GC and thats why I never saw any differences? I did try the blocking: false parameter and got the same results, but the documentation mentions that its not guaranteed so 🤷.

Okay, this clears up my confusion as I had the impression that GCHandles always effected the pause time by forcing the rooted objects to be scanned during the pause (even if they were in gen2). Looking forward to moving my stuff to use GCHandles.

Well, back to the topic. The question still remains, would it make sense to now allow references in the POH as its supported by the GC?

the only reason why we allowed references is because of a usage in the runtime, not because there was a need for general usage. and it sounds like you are fine with using normal handles?

I can understand that, and I was already a bit skeptical about my use case. And looks like I forgot some details about my use case while doing the refactor while going through the implementation.

I forgot that I was actually pinning some data already in the Gen 0 which I moved to POH. What I have now is a blittable struct with normal GCHandle and some other variables needed on the unmanaged side. The variables are directly accessed by pointers on the unmanaged side and when the managed side is needed, the GCHandle is passed on.

Now, I could replace the GCHandle with managed reference to avoid the indirection needed to do the GC table lookup.

Would certainly be an interesting API for me.
Do we need major GC changes here or just C# changes and possibly minor GC changes?

Hey, my apology to revive this topic, but I have actually a question related to the existing API GC.AllocateArray<T> as the doc mentions:

If pinned is set to true, T must not be a reference type or a type that contains object references.

But I have tried with a reference type and it seems to work well (and quickly checking the C++ code behind I don't see a check), so can I assume that this is allowed to pin an array of reference types?

can I assume that this is allowed to pin an array of reference types?

Yes, this was relaxed in #89293. Submitted dotnet/dotnet-api-docs#10142 to update the docs.

Navigation Menu

Repository navigation

a new GC API for large array allocation #27146

Rationale

Proposed APIs

Restrictions

Only array allocations are supported via this API

Minimal size supported

Perf consideration

Cost of getting the type

Pinning

90 remaining items

Benchmarks

Benchmark code

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

a new GC API for large array allocation #27146

Description

Rationale

Proposed APIs

Restrictions

Only array allocations are supported via this API

Minimal size supported

Perf consideration

Cost of getting the type

Pinning

Activity

danmoseley commented on Aug 15, 2018

jkotas commented on Aug 15, 2018

jkotas commented on Aug 15, 2018

4creators commented on Aug 19, 2018

jkotas commented on Aug 20, 2018

terrajobst commented on Aug 28, 2018

jkotas commented on Aug 28, 2018

Maoni0 commented on Aug 29, 2018

jkotas commented on Aug 29, 2018

jkotas commented on Aug 29, 2018

Maoni0 commented on Aug 29, 2018

jkotas commented on Aug 29, 2018

Maoni0 commented on Aug 29, 2018

tannergooding commented on Aug 29, 2018

90 remaining items

AraHaan commented on Jun 12, 2021

aromaa commented on Jun 12, 2021

webczat commented on Jun 12, 2021

aromaa commented on Jun 12, 2021

webczat commented on Jun 12, 2021

aromaa commented on Jun 12, 2021

jkotas commented on Jun 12, 2021

aromaa commented on Jun 12, 2021

Benchmarks

Benchmark code

jkotas commented on Jun 12, 2021

aromaa commented on Jun 12, 2021

Maoni0 commented on Jun 15, 2021

aromaa commented on Jun 15, 2021

deeprobin commented on Aug 28, 2022

xoofx commented on Jul 23, 2024

jkotas commented on Jul 23, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions