JIT: Support object stack allocation

Question

JIT: Support object stack allocation

erozenfeld opened this issue 7 years ago · 21 comments

This issue will track work on supporting object stack allocation in the jit. See dotnet/coreclr#20251 for the document describing the work.

The initial goal is to be able to remove heap allocation in a simple example like this:

class Foo
{
    public int f1;
    public int f2;
    public Foo(int f1, int f2)
    {
        this.f1 = f1;
        this.f2 = f2;
    }
}

class Test
{
    static int f1;
    static int f2;
    public static int Main()
    {
         Foo foo = new Foo(f1, f2);
         return foo.f1 + foo.f2;
    }
}

and then in a similar example where the class has gc fields.

Proposed initial steps are:

I will be modifying and extending this list as the work progresses.

cc @dotnet/jit-contrib

category:cq
theme:object-stack-allocation
skill-level:expert
cost:extra-large
impact:large

Answer 1 · 2018-10-04T15:23:53.000Z

add getObjHeaderSize jit interface method and its implementations

Why is this needed?

Answer 2 · 2018-10-04T17:41:40.000Z

We'll have to allocate space for ObjHeader before the stack-allocated object unless we can prove that it won't be needed for synchronization or hash code storage.

Answer 3 · 2018-10-04T17:52:39.000Z

needed for synchronization or hash code storage

I think using sychronization, etc. should prohibit stack allocation, for the initial iteration at least. Otherwise, you would also need a helper call to clear these objects from the synchronization tables and teach the synchronization tables to allow references to objects that do not live on the GC heap.

Answer 4 · 2018-10-04T17:54:26.000Z

modify lvaSetStruct to allow creating locals corresponding to stack-allocated classes
modify gc writebarrier logic to apply appropriate barriers when assigning to fields of (possibly) stack-allocated objects

How would stack allocated object fields would be accessed? Would existing FIELD/IND nodes be replaced with LCL_FLD/LCL_VAR nodes? Are writer barriers still needed if the object is allocated on stack?

Answer 5 · 2018-10-04T17:56:50.000Z

What would be the point of trying to synchronize on a stackallocated object? If it's considered for stack allocation then it means it doesn't escape which means no other thread can attempt to synchronize on it so any attempts to do so should be a no-op. The hash code could be derived from it's stack address as the object won't move until its deallocated.

Answer 6 · 2018-10-04T18:00:06.000Z

We'll need to detect calls to RuntimeHelpers.GetHashCode on the stackallocated object. They will be problematic if we don't allocate ObjHeader before the object.

Answer 7 · 2018-10-04T18:01:41.000Z

modify lvaSetStruct to allow creating locals corresponding to stack-allocated classes
modify gc writebarrier logic to apply appropriate barriers when assigning to fields of (possibly) stack-allocated objects

How would stack allocated object fields would be accessed? Would existing FIELD/IND nodes be replaced with LCL_FLD/LCL_VAR nodes? Are writer barriers still needed if the object is allocated on stack?

Stack allocated object will be treated like a struct and its fields may be promoted. No write barriers are needed if we are assigning to a field of a stack-allocated object.

Answer 8 · 2018-10-04T18:04:06.000Z

We will have cases where we are assigning to a field of an object that may live on the stack or on the heap (e.g., at joins or when passing a stack allocated object to another method). We'll have to detect these cases and use checked write barriers.

Answer 9 · 2018-10-04T18:10:11.000Z

I suppose calls to RuntimeHelpers.GetHashCode will look like calls to native code so we will consider the object escaping and won't stack-allocate, so we don't need ObjHeader for that.

Answer 10 · 2018-11-21T00:27:58.000Z

dotnet/coreclr#20814 implemented an initial version of object stack allocation. I updated the items in the description of this issue to mark what's done and added more items to the road map.

Answer 11 · 2019-01-15T07:53:58.000Z

dotnet/coreclr#21950 added several improvements:
objects with gc fields can be stack allocated;
optimization is enabled on x86;
gc pointer reporting is less conservative when the method has stack-allocated objects.

Answer 12 · 2019-02-27T01:23:59.000Z

What would be the point of trying to synchronize on a stackallocated object? If it's considered for stack allocation then it means it doesn't escape which means no other thread can attempt to synchronize on it so any attempts to do so should be a no-op.

Call it a "lock elision" optimization and highlight it as a feature 😉 I think that's what Java does, unless I misunderstand what they do.

Equally could drop interlocked in objects that don't escape (where they operate on the object)?

Answer 13 · 2019-02-27T06:35:12.000Z

Call it a "lock elision" optimization and highlight it as a feature 😉 I think that's what Java does, unless I misunderstand what they do.

AFAIR the first Java collection classes were synchronized. Of course, they found out that this isn't such a great idea and their implementation of escape analysis was also trying to help by removing synchronization when the collection object wasn't escaping the stack.

Answer 14 · 2021-08-17T09:50:57.000Z

I've got very promising result in my simple test code, but it still has a gap from structs (majorly because the lack of work item enable promotion of fields of stack-allocated objects):

[Benchmark]
public int PointClassTest()
{
    var p1 = new PointClass(4, 5);
    var p2 = new PointClass(3, 7);
    var result = AddClass(p1, p2);
    return result.X + result.Y;
}

[Benchmark]
public int PointStructTest()
{
    var p1 = new PointStruct(4, 5);
    var p2 = new PointStruct(3, 7);
    var result = AddStruct(p1, p2);
    return result.X + result.Y;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
PointClass AddClass(PointClass x, PointClass y)
{
    return new PointClass(x.X + y.X, x.Y + y.Y);
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
PointStruct AddStruct(PointStruct x, PointStruct y)
{
    return new PointStruct(x.X + y.X, x.Y + y.Y);
}

record class PointClass(int X, int Y);
record struct PointStruct(int X, int Y);

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000
Intel Core i7-7660U CPU 2.50GHz (Kaby Lake), 1 CPU, 4 logical and 2 physical cores
.NET SDK=6.0.100-preview.7.21379.14
  [Host]      : .NET 6.0.0 (6.0.21.37719), X64 RyuJIT
  PGO + EA    : .NET 6.0.0 (6.0.21.37719), X64 RyuJIT, TieredPgo + TieredCompilation + TC_QuickJit + TC_QuickJitForLoops + JitObjectStackAllocation
  PGO + No EA : .NET 6.0.0 (6.0.21.37719), X64 RyuJIT, TieredPgo + TieredCompilation + TC_QuickJit + TC_QuickJitForLoops

Runtime=.NET 6.0

Method	Job	Mean	Error	StdDev	Median	Code Size	Gen 0	Allocated
PointClassTest	PGO + EA	0.7836 ns	0.0415 ns	0.0857 ns	0.7720 ns	157 B	-	-
PointStructTest	PGO + EA	0.0045 ns	0.0100 ns	0.0083 ns	0.0000 ns	6 B	-	-
PointClassTest	PGO + No EA (Baseline)	12.2350 ns	0.5015 ns	1.4548 ns	11.5586 ns	120 B	0.0344	72 B
PointStructTest	PGO + No EA	0.0000 ns	0.0000 ns	0.0000 ns	0.0000 ns	6 B	-	-

Codegen:

.NET 6.0.0 (6.0.21.37719), X64 RyuJIT, Config: PGO + EA

; DevirtualizationTest.PointClassTest()
       sub       rsp,38
       xor       eax,eax
       mov       [rsp+8],rax
       vxorps    xmm4,xmm4,xmm4
       vmovdqa   xmmword ptr [rsp+10],xmm4
       vmovdqa   xmmword ptr [rsp+20],xmm4
       mov       [rsp+30],rax
       mov       rax,offset MT_DevirtualizationTest+PointClass
       mov       [rsp+28],rax
       mov       dword ptr [rsp+30],4
       mov       dword ptr [rsp+34],5
       lea       rax,[rsp+28]
       mov       rdx,offset MT_DevirtualizationTest+PointClass
       mov       [rsp+18],rdx
       mov       dword ptr [rsp+20],3
       mov       dword ptr [rsp+24],7
       lea       rdx,[rsp+18]
       mov       ecx,[rax+8]
       add       ecx,[rdx+8]
       mov       eax,[rax+0C]
       mov       r8,offset MT_DevirtualizationTest+PointClass
       mov       [rsp+8],r8
       add       eax,[rdx+0C]
       mov       [rsp+10],ecx
       mov       [rsp+14],eax
       lea       rax,[rsp+8]
       mov       edx,[rax+8]
       add       edx,[rax+0C]
       mov       eax,edx
       add       rsp,38
       ret
; Total bytes of code 157
; DevirtualizationTest.PointStructTest()
       mov       eax,13
       ret
; Total bytes of code 6

.NET 6.0.0 (6.0.21.37719), X64 RyuJIT, Config: PGO + No EA

; DevirtualizationTest.PointClassTest()
       push      rdi
       push      rsi
       push      rbx
       sub       rsp,20
       mov       rcx,offset MT_DevirtualizationTest+PointClass
       call      CORINFO_HELP_NEWSFAST
       mov       rsi,rax
       mov       dword ptr [rsi+8],4
       mov       dword ptr [rsi+0C],5
       mov       rcx,offset MT_DevirtualizationTest+PointClass
       call      CORINFO_HELP_NEWSFAST
       mov       rdi,rax
       mov       dword ptr [rdi+8],3
       mov       dword ptr [rdi+0C],7
       mov       ebx,[rsi+8]
       add       ebx,[rdi+8]
       mov       esi,[rsi+0C]
       mov       rcx,offset MT_DevirtualizationTest+PointClass
       call      CORINFO_HELP_NEWSFAST
       add       esi,[rdi+0C]
       mov       [rax+8],ebx
       mov       [rax+0C],esi
       mov       edx,[rax+8]
       add       edx,[rax+0C]
       mov       eax,edx
       add       rsp,20
       pop       rbx
       pop       rsi
       pop       rdi
       ret
; Total bytes of code 120
; DevirtualizationTest.PointStructTest()
       mov       eax,13
       ret
; Total bytes of code 6

Is there any roadmap to make further progress on this?

Answer 15 · 2022-07-15T18:18:02.000Z

Is this actively being worked on?

Answer 16 · 2022-07-15T18:26:19.000Z

@TonyValenti no, see #1661 (comment)

Answer 17 · 2022-07-15T19:46:36.000Z

We will shortly be working on our post 7.0 plans and this is definitely in the mix. In particular I would like to see us working towards stack allocation of some boxes, since:

these were not accounted for in the initial (somewhat discouraging) scouting for opportunities and may be relatively abundant.
struct methods with gc type fields already use checked write barriers) so stack allocating them is pay for play. That's not the case for ref classes.
we can trivially rely on many struct methods not to capture the struct address in any way (so they can't make the struct escape) so we may not need to uplevel inlining or do some kind of interprocedural analysis to find viable candidates.
we may be able to optimize away unboxing stubs and (in some cases) not require the stack allocation to represent the full boxed object, just its payload (or sometimes even, just its type).
in conjunction with GDV driven loop test cloning and increasing use of struct enumerators we may be able to de-abstract some IEnumerator<T> uses and avoid heap allocation of the enumerator in the "happy path" case.

Answer 18 · 2024-07-01T16:39:27.000Z

Fixed by #103361.

Answer 19 · 2024-07-01T16:45:07.000Z

Fixed by #103361.

btw there're still some unfinished items like:

make the analysis more sophisticated to handle increasingly more complex examples (eg fields of value classes, or fields of unescaped ref classes
enable stack allocation of constant-sized arrays
enable stack allocation of strings
R2R/NAOT support

Answer 20 · 2024-07-20T15:43:16.000Z

@hez2010 But if you guys could get the point in the list finished: enable stack allocation of constant-sized arrays , wouldn't that also not get rid off automatically of enable stack allocation of strings , since strings are constant sized arrays of char or not, with some more hidden meta-data stuff backed up, or not?

Answer 21 · 2024-07-20T17:22:12.000Z

@hez2010 But if you guys could get the point in the list finished: enable stack allocation of constant-sized arrays , wouldn't that also not get rid off automatically of enable stack allocation of strings , since strings are constant sized arrays of char or not, with some more hidden meta-data stuff backed up, or not?

No. string is completely different and unlike any other types, allocations of string are done by calling to either FastAllocateString or String:.ctor, where both of them are internal methods implemented in unmanaged code. To support string stack allocation, we would need to add specific support.