Discriminated Union GC Support

[HyperSphereStudio]

I have been reading through the dotnet runtime and decided to toy around with how to implement a memory efficient discriminated union deep into the .NET runtime. I have been having quite a bit of success!

Lets say we want to represent the following:

   union Union1{
         object c;
         int e;
   }

You could create a struct of nullables for each but this will quickly waste ALOT of memory the more fields you begin adding..... it will be exponential especially as the depth of nested unions increase.

What makes this so hard? Managed Structs

Managed Structs allow multiple inline reference to occur thus any reasonable efficient memory representation (that doesnt box) will need to somehow figure out what references are where depending on the type of the union.

Lets make the internal memory representation of the union be the following

struct Union1 {
    union {
        Object* c;
        int e;
    };
    UnionTypeType type;
};

So what do we have to do?

First lets define some parameters describing this union

enum Union1Type : UnionTypeType{
    U1_NULL = 0,
    U1_C_TYPE = 1,

    U1_MANAGED_CNT = U1_C_TYPE,

    U1_E_TYPE = 2
};

The union fields should be sorted in the following order: ref type, managed structures then last unmanaged structures with an increasing type index assigned to each one.

Note that we don't care about any type index greater than MANAGED_CNT or NULL types.

Size of the union = max size of all ref or struct fields

My current work has dealt with go_through_object (fields inside an object) which is the primary bottleneck in this implementation:

There is a lot of detail that I am going to exclude for now because this post would be massive, but the general memory layout for the GC for our above example is the following:

class MyU : Object {
   public:

   Object * a;
   int d;
   Object * b;
   Union1 u1;
};

static struct MyUTable_MT{
    CGCDescEntry m_u1_c_Desc_entries[1];    //Here are the branches the GC can take based on the unionType
    CGCDesc u1DescC;                                   //Descriptor for each entryTable

    CGCUnionDescOffset m_u1DescOffsets[1];  //Here are the offsets to the branch tables
    CGCUnionOffsetTable m_u1OffsetTable;      //Header for the offset tables

    CGCDescEntry m_entries[3];                       //GCEntries for MyU [a, b, u1]
    CGCDesc desc;                                            //GCDescriptor for MyU

    // The actual methodtable
    MethodTable m_MT;
}
pMT;

My current results (let union be a managed object):

public union Union1{
    object c;
    int e;
}

public class MyU {
   object a;
   int d;
   object b;
   Union1 u1;
};
 
   MyU v1 = new MyU();
   v1. a = new MyU();
   v1.b = new MyU();
   v1.u1.c = new MyU();

   //Print Info
   
   GC.Collect(); //FullGC

   //Print Info ... everything should be the ame

   v1 = default;

    GC.Collect(); //FullGC
   //Now everything should be destroyed.

   //Print info

Output:

My Object Size:56 Offset_a:16 Offset_b:32 offset_c:48
U1->C Desc Offset:56
U1 Real Offset:00007FF7E67B9818
HandlePtr:000002BA4E400028 DataPtr:000002BA4E400030
(o->a) 000002BA4E400038=000002BA4E400060 (o->b) 000002BA4E400048=000002BA4E400098
Union (o->u1.c) = 000002BA4E4000D0 = 000002BA4E4000D0

Pre GC With Handle 1:000002BA4E400060->3 2:000002BA4E400098->5
Union (o->u1.c) = 000002BA4E4000D0 = 000002BA4E4000D0



Enter Object:000002BA4E400028
Entry[2]: o:000002BA4E400028 000002BA4E400038->000002BA4E400060 Offset:16 Union:0
Entry[1]: o:000002BA4E400028 000002BA4E400048->000002BA4E400098 Offset:32 Union:0
Entry[0]: o:000002BA4E400028 000002BA4E400058->0000000000000001 Offset:48 Union:1
Union Type:1 UnionOffsetTableOffset:32
        UnionDescTableOffset:56
Entry[0]: o:000002BA4E400028 000002BA4E400050->000002BA4E4000D0 Offset:40 Union:0


Enter Object:000002BA4E400060
Entry[2]: o:000002BA4E400060 000002BA4E400070->0000000000000000 Offset:16 Union:0
Entry[1]: o:000002BA4E400060 000002BA4E400080->0000000000000000 Offset:32 Union:0
Entry[0]: o:000002BA4E400060 000002BA4E400090->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0


Enter Object:000002BA4E400098
Entry[2]: o:000002BA4E400098 000002BA4E4000A8->0000000000000000 Offset:16 Union:0
Entry[1]: o:000002BA4E400098 000002BA4E4000B8->0000000000000000 Offset:32 Union:0
Entry[0]: o:000002BA4E400098 000002BA4E4000C8->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0


Enter Object:000002BA4E4000D0
Entry[2]: o:000002BA4E4000D0 000002BA4E4000E0->0000000000000000 Offset:16 Union:0
Entry[1]: o:000002BA4E4000D0 000002BA4E4000F0->0000000000000000 Offset:32 Union:0
Entry[0]: o:000002BA4E4000D0 000002BA4E400100->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0


Enter Object:000002BA4E400028
Entry[2]: o:000002BA4E400028 000002BA4E400038->000002BA4E400060 Offset:16 Union:0
Entry[1]: o:000002BA4E400028 000002BA4E400048->000002BA4E400098 Offset:32 Union:0
Entry[0]: o:000002BA4E400028 000002BA4E400058->0000000000000001 Offset:48 Union:1
Union Type:1 UnionOffsetTableOffset:32
        UnionDescTableOffset:56
Entry[0]: o:000002BA4E400028 000002BA4E400050->000002BA4E4000D0 Offset:40 Union:0


Enter Object:000002BA4E400060
Entry[2]: o:000002BA4E400060 000002BA4E400070->0000000000000000 Offset:16 Union:0
Entry[1]: o:000002BA4E400060 000002BA4E400080->0000000000000000 Offset:32 Union:0
Entry[0]: o:000002BA4E400060 000002BA4E400090->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0


Enter Object:000002BA4E400098
Entry[2]: o:000002BA4E400098 000002BA4E4000A8->0000000000000000 Offset:16 Union:0
Entry[1]: o:000002BA4E400098 000002BA4E4000B8->0000000000000000 Offset:32 Union:0
Entry[0]: o:000002BA4E400098 000002BA4E4000C8->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0


Enter Object:000002BA4E4000D0
Entry[2]: o:000002BA4E4000D0 000002BA4E4000E0->0000000000000000 Offset:16 Union:0
Entry[1]: o:000002BA4E4000D0 000002BA4E4000F0->0000000000000000 Offset:32 Union:0
Entry[0]: o:000002BA4E4000D0 000002BA4E400100->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0
Post GC With Handle 1:000002BA4DC00078->3 2:000002BA4DC000B0->5
Union (o->u1.c) = 000002BA4DC000E8 = 000002BA4DC000E8

Post GC Without Handle p2:0000000000000000 p3:0000000000000000
Union p3= 0000000000000000

Perfect! This is following the behaviour that we want!!!

Lets try the union being an unmanaged value

   MyU v1 = new MyU();
   v1. a = new MyU();
   v1.b = new MyU();
   v1.u1.c = 5;

   //Print Info
   
   GC.Collect(); //FullGC

   //Print Info ... everything should be the ame

   v1 = default;

    GC.Collect(); //FullGC
   //Now everything should be destroyed.

   //Print info

Output

My Object Size:56 Offset_a:16 Offset_b:32 offset_c:48
U1->C Desc Offset:0
U1 Real Offset:00007FF620FC9818
HandlePtr:000001F65A800028 DataPtr:000001F65A800030
(o->a) 000001F65A800038=000001F65A800060 (o->b) 000001F65A800048=000001F65A800098
Union (o->u1.e) = 5

Pre GC With Handle 1:000001F65A800060->3 2:000001F65A800098->5
Union (o->u1.e) = 5



Enter Object:000001F65A800028
Entry[2]: o:000001F65A800028 000001F65A800038->000001F65A800060 Offset:16 Union:0
Entry[1]: o:000001F65A800028 000001F65A800048->000001F65A800098 Offset:32 Union:0
Entry[0]: o:000001F65A800028 000001F65A800058->0000000000000002 Offset:48 Union:1
Union Type:2 UnionOffsetTableOffset:32
        UnionDescTableOffset:0


Enter Object:000001F65A800060
Entry[2]: o:000001F65A800060 000001F65A800070->0000000000000000 Offset:16 Union:0
Entry[1]: o:000001F65A800060 000001F65A800080->0000000000000000 Offset:32 Union:0
Entry[0]: o:000001F65A800060 000001F65A800090->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0


Enter Object:000001F65A800098
Entry[2]: o:000001F65A800098 000001F65A8000A8->0000000000000000 Offset:16 Union:0
Entry[1]: o:000001F65A800098 000001F65A8000B8->0000000000000000 Offset:32 Union:0
Entry[0]: o:000001F65A800098 000001F65A8000C8->0000000000000000 Offset:48 Union:1
Union Type:0 UnionOffsetTableOffset:32
        UnionDescTableOffset:0
Post GC With Handle 1:000001F65A800060->3 2:000001F65A800098->5
Union (o->u1.e) = 5

Post GC Without Handle p2:0000000000000000 p3:0000000000000000

Awesome! The GC is not treating "5" like its a valid reference!

Anyhow this isnt meant to be super formal ... just wanted to make yall aware of this.

You can find all my work thus far in my personal fork of the runtime. All code above is in GCSample.cpp

Currently managed value type arrays dont work ... I havent reworked their memory format just yet.

Because of the new data structures I will have to redesign some AOT/JIT methodtablebuilders.

Thoughts?

(If anyone is wondering how I deal with multiple nested union types without having stack overflow I built a special graph traverser to handle this)

[HyperSphereStudio]

My go_through_object macro looks like this: (Note that again, managed value type arrays are not supported just yet, but I think they wont cause to many extra hurdles)

#define go_through_object(mt,o,size,parm,start,start_useful,limit,exp){        \
    FastGraphWalker<GraphNode> walker;                                         \
    walker.parent.SetDesc(CGCDesc::GetCGCDescFromMT((MethodTable*)(mt)));      \
    walker.parentPushed();                                                     \
    GraphNode* n;                                                              \
    uint8_t** parm = 0;                                                        \
    printf("\n\nEnter Object:%p\n", o);                                        \
                                                                               \
    while((n = walker.currentNode()) != nullptr){                              \
         while(n->index > -1){                                                 \
              auto e = n->desc->GetEntry(n->index);                            \
              parm = (uint8_t**) ((uint8_t*)o + e->GetOffset());               \
              printf("Entry[%d]: o:%p %p->%p Offset:%d Union:%d\n", (size_t) n->index, o, parm, *parm, (int32_t) e->GetOffset(), e->IsUnionType()); \
              n->index--;                                                      \
              if (e->IsUnionType()) {                                          \
                  auto ot = walker.parent.desc->GetUnionOffsetTable(e->GetUnionOffsetTableOffset());\
                  printf("Union Type:%u UnionOffsetTableOffset:%d\n", *(UnionTypeType*) parm, e->GetUnionOffsetTableOffset()); \
                  auto dof = ot->GetUnionDescOffset(*(UnionTypeType*) parm);   \
                  printf("\tUnionDescTableOffset:%d\n", dof);                  \
                  if (dof != CGCUnionDescOffsetNull) {                         \
                       GraphNode gn;                                           \
                       gn.SetDesc(walker.parent.desc->GetUnionDesc(dof));      \
                       walker.pushNode(gn);                                    \
                       n = walker.currentNode();                               \
                       continue;                                               \
                  }                                                            \
              }                                                                \
              else {                                                           \
                 uint8_t** ppstop = parm + e->GetPointerSpanLength();          \
                 if (!start_useful || (uint8_t*)ppstop > (start)){             \
                     if (start_useful && (uint8_t*)parm < (start))             \
                         parm = (uint8_t**)(start);                            \
                     while (parm < ppstop){                                    \
                         {exp}                                                 \
                         parm++;                                               \
                     }                                                         \
                 }                                                             \
              }                                                                \
         }                                                                     \
         walker.popNode();                                                     \
    }                                                                          \
}                                                                             

The FastGraphWalker keeps an N-size inline stack to hopefully help speed up most cases where the depth of unions is shallow. It falls back to grabbing memory from a pool when needed (slower, but wont cause overflow).

[huoyaoyuan]

This can't really work. Not only the GC is treating GC references differently, but also JIT code (GC field require write barriers), managed BCL (non-GC field can be safely copied with SIMD register), etc.

[HyperSphereStudio]

But this again raises my question to where are the static field roots enumerated?

I presume they're enumerated down from root AppDomain object

Which would be an object ....

So I think that means my code should "allegedly" be able to support static struct fields at the moment since it probably emits it into a object that is referenced? I have to add support for the new structures to the methodtablebuilder but I am happy if this is how the CLR handles this :)

[EgorBo]

But what happends when we have multiple GC slots because a struct can have say 3 fields?

Fair. Do we expect such structs with GC fields to be common in DU types? It seems like this edge-case requires too much of efforts.

[EgorBo]

to support static struct fields at the moment since it probably emits it into a object that is referenced?

Yes, static fields of struct types are stored inside objects on the heap and are reachable from AppDomain - we call them "boxed statics", especially if they contain GC fields (if they don't, the often get allocated on the NonGC heap (aka Frozen) instead)

[HyperSphereStudio]

Im not sure how common this is

Is it worth the effort? Probably not :). But I am doing this for fun and education for myself ... not neccesarily to be added.

I am doing this mostly for fun ... I got really excited though when I got one of the big hurdles accomplished (being able to enumerate through an object graph containing unions effectively when it had a searchable root)!

I will put some effort towards making the unions searchable themselves in the roots ... but I just wanted the community to have this in case the collective where like, hell yeah we want this.

[333fred]

Do we expect such structs with GC fields to be common in DU types?

Yes, I expect it to be at least somewhat common. A union-like type I've used in multiple different projects now is OneOrMany<T>, which is backed by a simple T in one case, and an ImmutableArray<T> in the many case.

[HyperSphereStudio]

My current TODO list

• Test against cross generational object graphs

• Support gc roots (static struct fields & the stack)

• Support value type arrays

What have I accomplished? (We will see how this holds in further tests)

• Non root (inside object) discriminated union with conditional GC checking

If anyone has any particular questions about how I did the above, feel free to ask or play around with my repo!