Proposal: Folding generic methods in NativeAOT #117564
Description
I was investigating the size of my NativeAOT app with View MichalStrehovsky's Sizoscope before and after doing anything in Main, and observed that a bit of space seems to be attributable to generic instantiations. e.g. System.Collections.Generic alone is 402.6 KB
Inspecting these instantiations in IDA Pro, I noticed a bit of a pattern.
The decompiled pseudocode GrowForInsertion for Int16 looks like this
__int64 __fastcall S_P_CoreLib_System_Collections_Generic_List_1_Int16___GrowForInsertion(
__int64 a1,
unsigned int a2,
int a3)
{
__int64 v6; // rdx
__int64 v7; // rbp
int v8; // ecx
__int64 v9; // rax
__int64 v10; // r14
v6 = (*(a1 + 16) + a3);
if ( __OFADD__(*(a1 + 16), a3) )
{
S_P_CoreLib_System_ThrowHelper__ThrowOverflowException(a1, v6);
__debugbreak();
}
v7 = *(a1 + 8);
if ( *(v7 + 8) )
v8 = 2 * *(v7 + 8);
else
v8 = 4;
if ( v8 > 0x7FFFFFC7 )
v8 = 2147483591;
if ( v8 < v6 )
v8 = v6;
v9 = RhpNewArray(&__Array_Int16_::`vftable', v8);
v10 = v9;
if ( a2 )
S_P_CoreLib_System_Array__Copy_1(v7, v9, a2);
if ( *(a1 + 16) != a2 )
S_P_CoreLib_System_Array__Copy_2(*(a1 + 8), a2, v10, a2 + a3, *(a1 + 16) - a2);
return RhpAssignRefAVLocation(a1 + 8, v10);
}whereas GrowForInsertion for Int32 looks like this
__int64 __fastcall S_P_CoreLib_System_Collections_Generic_List_1_Int32___GrowForInsertion(
__int64 a1,
unsigned int a2,
int a3)
{
__int64 v6; // rdx
__int64 v7; // rbp
int v8; // ecx
__int64 v9; // rax
__int64 v10; // r14
v6 = (*(a1 + 16) + a3);
if ( __OFADD__(*(a1 + 16), a3) )
{
S_P_CoreLib_System_ThrowHelper__ThrowOverflowException(a1, v6);
__debugbreak();
}
v7 = *(a1 + 8);
if ( *(v7 + 8) )
v8 = 2 * *(v7 + 8);
else
v8 = 4;
if ( v8 > 0x7FFFFFC7 )
v8 = 2147483591;
if ( v8 < v6 )
v8 = v6;
v9 = RhpNewArray(&__Array_Int32_::`vftable', v8);
v10 = v9;
if ( a2 )
S_P_CoreLib_System_Array__Copy_1(v7, v9, a2);
if ( *(a1 + 16) != a2 )
S_P_CoreLib_System_Array__Copy_2(*(a1 + 8), a2, v10, a2 + a3, *(a1 + 16) - a2);
return RhpAssignRefAVLocation(a1 + 8, v10);
}This code is completely identical, except for the following lines
&__Array_Int16_::`vftable'&__Array_Int32_::`vftable'This then has a trickle down effect; List<T>.Insert then also needs to be duplicated, because GrowForInsertion is duplicated. I do note that not all Insert methods appear to have the same implementation; I'm not exactly sure why that is.
In this particular scenario, the only notable difference is the vtable of the array that should be used when the array is grown. If that were to be stored as a field on this, that would eliminate the need to hardcode the reference to it within the method itself, allowing the method to be flagged as a duplicate and removed (albeit at the cost of needing to do a field lookup anytime you want to reference that vtable)
When it comes to how parameters are passed to generic methods, in the case of reference types I would expect the parameter is a fixed size (the size of a pointer). Essentially, I'm suggesting to just pretend it's a value of type object. I'm not sure if you'd be able to fold methods where the generic type is a struct, as you'd need to know how big the value in your register or in a memory location is to interact with it. Maybe folding based on the size of T? e.g. Int32 vs UInt32 are both 4 bytes? In the case of value types, you could still get a partial win: if generic type that is a struct is actually used in that method, we're free to fold it. So in the case of List<Int32>.GrowForInsertion, it doesn't actually use an Int32 in any variable, so as long as the array vtable type could be pulled from a field on the List, this method could be folded.
This proposal probably falls apart for any methods where you try and access a field on your generic type.
One big downside of this proposal is that stack traces won't make sense, so perhaps methods that get folded/shared should be renamed to indicate the fact they're being shared
I found an existing issue #88748 which discusses folding to some extent, however I am specifically talking about folding for generics. Certain scenarios may prohibit folding a given method, however I'm hoping that it would the common case that folding would be permitted and some good file size wins could be achieved