Messagepack-csharp: [Circular-Serialization] / -> Can we change IMessagePackFormatter<T> definition so it allows creating new objects and writing to them?

[rikimaru0345]

I want to add support for circular serialization.
My idea is simple: We only need to support for circular references for a few types, not all types.

So why not just write 0 for new object; and id for known objects?
It is as easy as it sounds, but there is one small problem...

Serialization works!

_(Deserialization is missing a small feature)_

using System.Collections.Generic;
using MessagePack;
using MessagePack.Formatters;
using MessagePack.Resolvers;

namespace MsgPackTestCyclicRef
{
    [MessagePackObject]
    public class Person
    {
        [Key(0)]
        public string Name;
        [Key(1)]
        public Pet Pet;
    }

    [MessagePackObject]
    public class Pet
    {
        [Key(0)]
        public string Name;
        [Key(1)]
        public Person Owner;
    }


    class Program
    {
        static void Main(string[] args)
        {
            var p = new Person { Name = "Riki" };
            var c = new Pet { Name = "Dr. Cat" };
            c.Owner = p;
            p.Pet = c;

            var myResolver = new MyResolver<Person>();

            var bytes = MessagePackSerializer.Serialize(p, myResolver);
            var reconstructed = MessagePackSerializer.Deserialize<Person>(bytes, myResolver);

        }
    }

    class MyResolver<T> : IFormatterResolver
    {
        public CircularFormatter<T> CircularFormatter = new CircularFormatter<T>();

        public IMessagePackFormatter<TRequested> GetFormatter<TRequested>()
        {
            // Maybe we can do a circular resolver before falling back to the default
            if (typeof(T) == typeof(TRequested))
                return (IMessagePackFormatter<TRequested>)CircularFormatter;

            return StandardResolver.Instance.GetFormatter<TRequested>();
        }
    }

    class CircularFormatter<T> : IMessagePackFormatter<T>
    {
        int _serializingId = 1;
        int _deserializingId = 1;
        Dictionary<int, T> _idToObj = new Dictionary<int, T>();
        Dictionary<T, int> _objToId = new Dictionary<T, int>();

        IMessagePackFormatter<T> _defaultFormatter = StandardResolver.Instance.GetFormatter<T>();
        IMessagePackFormatter<int> _intFormatter = StandardResolver.Instance.GetFormatter<int>();

        public int Serialize(ref byte[] bytes, int offset, T value, IFormatterResolver formatterResolver)
        {
            // How do we serialize? Will we write the object? Or just the ID?
            int writtenBytes = 0;
            if (!_objToId.TryGetValue(value, out int existingId))
            {
                // First encounter! Assign an ID to the object, then serialize it normally
                _objToId[value] = _serializingId++;

                // Write 0, meaning "this is a new object"
                writtenBytes += _intFormatter.Serialize(ref bytes, offset, 0, formatterResolver);

                // Write object itself
                writtenBytes += _defaultFormatter.Serialize(ref bytes, offset + writtenBytes, value, formatterResolver);
            }
            else
            {
                // It is a known object, only write the ID
                writtenBytes += _intFormatter.Serialize(ref bytes, offset, existingId, formatterResolver);
            }

            return writtenBytes;
        }

        public T Deserialize(byte[] bytes, int offset, IFormatterResolver formatterResolver, out int readSize)
        {
            int totalRead = 0;
            int read = 0;

            var id = _intFormatter.Deserialize(bytes, offset, formatterResolver, out read);

            totalRead += read;
            offset += read;
            read = 0;

            if (id == 0)
            {
                // We're getting a new object
                // Let's deserialize it using the default formatter (DynamicObject, ...)
                var obj = _defaultFormatter.Deserialize(bytes, offset, formatterResolver, out read);

                totalRead += read;
                offset += read;
                read = 0;

                readSize = totalRead;

                // This object might be referenced later on. We save it along with its id
                _idToObj[_deserializingId++] = obj;
                return obj;
            }
            else
            {
                // It is an already known object!
                readSize = totalRead;

                var obj = _idToObj[id];

                return obj;
            }
        }

        // todo: need to reset the formatter after every full serialization
        public void Reset()
        {
            _serializingId = 1;
            _deserializingId = 1;

            _idToObj.Clear();
            _objToId.Clear();
        }
    }
}

In Deserialize there is this line:

var obj = _defaultFormatter.Deserialize(bytes, offset, formatterResolver, out read);

The problem is, it will recursively read objects, while it has not finished reading the current / root object.
Serialization is depth-first, so it will try to resolve objects before they are fully read, and I don't have access to the object that I am currently reading (no "parent" object).

So that is why it will not find the object in the dictionary, and crash.

How it could be solved

Let us create the object manually, give us a reference, and we will manually populate all fields.
That way we can work with objects we're still in the process of reading.

@neuecc
1) Is the approach feasible? If CircularFormatter<T> is used for only few types (manually) it should not impact performance much. Disadvantage: have to manually determine what types to serialize by reference/id. It might be a problem for noob/beginner users, if they don't understand what they are doing. (Could get duplicated objects that are missing reference equality for some objects, even when reference equality is expected).

2) Can we get the object that was created for deserialization somehow, populate fields instead?
My suggestion, instead of:

var obj = _defaultFormatter.Deserialize(bytes, offset, formatterResolver, out read);

give us:

var obj = _defaultFormatter.CreateNewObject();
 // ---> Can enter obj into dictionary already, before it has finished reading!
_defaultFormatter.DeserializeInto(ref obj, ...);

This feature feels closely related to OverwriteFormatting https://github.com/neuecc/MessagePack-CSharp/pull/110

3) Maybe later we can write a smart algorithm that will "break" a object-graph at strategic positions. Only using CircularFormatter<T> to break loops in the circular graph when needed.
Or maybe we can add an attribute [KeepReferenceEquality] or [UseCircularFormatter] ...
Automatic way can not ensure that the result is what the user expects (maybe it decides that some object can be serialized the normal way, while still not having loops in the graph).
But doing it for every object seems wasteful, lots of dictionary lookups.
Maybe there is some way to "pre-process" a object-graph before serializing, setting the references/fields/properties to null, and then adding another section into the serialized data that tells us what properties to set where, so we can restore the original graph.

What are your thoughts?

[rikimaru0345]

In Deserialize we can remove the dictionary and use a list instead.

We know that the index will be simply increasing, so we can use a list directly.
That should be faster than using a dictionary.

I will try to find some time soon to see if I can make the necessary changes to DynamicObjectFormatter.
Either finishing OverwriteFormatter if that solves it, or changing how serialization is done.

[rikimaru0345]

I have started writing my own proof of concept serializer, since the design of MessagePack-CSharp is not really suitable to support object overwriting easily (in the current PR it is implemented as a second interface and method void DeserializeTo(ref T to, ...).

I'm getting similar performance to MessagePack-CSharp, using only Linq.Expressions instead of direct ILGen.

If my ideas regarding object "caching" (simply saving an ID for references that were written previously like explained in my first post) pan out as intended, then I'll either try to implement that into MessagePack-CSharp, or I might release my own serialization library.

My own library will be completely incompatible to the MessagePack binary format though and also has much weaker guarantees regarding binary-versioning. It will not support things like the Typeless* formatters, and will generally break if you change classes/fields. I can most likely fix that later by adding attributes similar to those that MessagePack-CSharp has.

It will also support even the most complex object hierarchies; supporting all cases even the ones were MessagePack-CSharp crashes with InvalidProgram / InvalidOperation / StackOverflow

[oruchreis]

This issue is a blocker to use this awesome library in our framework. The circular references might occur in a big framework, and we can't control the models for circular references in a large group of developers.

[rikimaru0345]

Good news! I finished my serializer.

If there is interest, I think I'll publish it on github. And if neuecc is willing, I'd even try to see if it is possible to backport the ideas in my new serializer to MessagePack-CSharp. (Unfortunately that is unlikely though as the binary format is completely different from the established MessagePack protocol).

Obviously it takes quite a bit of time to properly release something on github (along with nuget packages...). And seeing as the serializer I wrote belongs at least partially into a niche category, I decided to just post what I have and then see if there would even be any substantial interest in the library.

Right now it is only supposed to fulfill the needs I and my team have, so even though it has massive advantages compared to MessagePack-CSharp, it also has massive disadvantages. Just like with any library or tool you have to know exactly what you need from it and what features you can totally live without / sacrifice for other things, like performance.

While developing I made a list of the most important differences and similarities, roughly ordered by importance to us:

• Performance. Mostly very similar to MsgPack-CSharp. Sometimes faster, sometimes slower, it much depends on what actual types are present in the given object-graph, and what formatters get used; and even in the "worst case" it is still comparable to MessagePack-CSharp in speed (details further down in the post)

• No allocations! :raised_hands: This one is really huge for us since few serializers support it and we have a dire need for it. Avoiding useless allocations also gives a notable performance boost even if you don't care about garbage-collection-pressure.

  • Both serialization _and_ deserialization will never allocate if you do it right!! :tada:
  • For serialization you simply give it a byte[] buffer to use! If it's too small, it will obviously have to allocate/resize. If all your object-graphs are either relatively small (E.g. network messages), or you keep re-using a large buffer, there won't be any allocations.
  • If it becomes a concern for us eventually I might add a delegate to call when the serializer is out of space, so you can recycle the old / too small byte[] buffers manually for other things.
  • Deserialization is always "populate or create", the deserialize methods signature is Deserialize(byte[] buffer, int offset, ref T obj);. You can pass in null for obj, but then the serializer will of course allocate a T for you (unless the given data says the object is _supposed to be_ null of course)
  • Collections will be cleared when the serialized data says "null" or "empty" (so it won't null collections even if the data wants to assign null, which is important to avoid GC-pressure)
  • If one of your object fields is null (or of the wrong type) and the serialized data says there is an object, you can provide a delegate (a factory), so you can give the deserializer an instance from your object pool (very important for UnityEngine as well as networking, _zero_ GC pressure, which is awesome!). If you don't provide a delegate/factory it will simply fall-back to new(), which allocates, but that's obviously not the serializers fault then :P
  • Obviously the "bootstrapping" has to allocate, but it's needed an not garbage/disposed. Bootstrapping is the initial code-generation, compiling, finding fields, first serialization of a new type to build caches, ...
  • All objects internal to the serializer are reused. That includes Dictionary and List caches, instanced Formatters, temporary storage to find fields, ...

• Besides primitives it of course supports arbitrary user objects. Same technique as MessagePack-CSharp uses, dynamic code generation to generate an optimized serializer at runtime for each specific object. MessagePack-CSharp calls it "DynamicObjectFormatter", same here. However instead of ILGen I'm using Linq.Expressions.Expression which does essentially the same thing. This adds a limitation though: a hard-dependency on Expression.Block(), meaning at no support for very old runtimes like .NET 3.5 or earlier. Only .NET 4.0 or higher, or any version of Standard/Core. That is probably the only reason why neuecc went the "hard" way of using ILGenerator, which is available since .NET 1.1. Unless someone makes a convincing argument I have no plans to add support for those older runtimes, since even Unity now supports .NET 4.x.

• "CacheFormatting". The magic ingredient that enables:

  • Serialization of _any_ object graph. Circular references, indirect circular, many references to a single object, ... no problem!
  • Depending on the situation, it can massively increase performance if your object-graph contains many references the same object(s), because only the lookup ID has to be written instead of a full object each time.
  • Does reference handling correctly! No "dangling" references. (Only a thing in serializers that try to implement reference handling in a bad/half-assed way as in some lesser known serializers we've tried in the past. They just handled directly circular references, while indirectly circular (like 3 objects pointing to each other in a circle) was "instantiated" multiple times, which works but the references are then obviously wrong as you get duplicate objects / duplicate loops!)
  • Even in the worst case, you only pay a minor (~12%) performance hit. The worst case being serializing a graph that contains a lot of non-sealed-type references, because every reference object needs to be put into a dictionary.
  • No measurable performance impact for deserialization in any case (simple and complex graphs)! Since we know the reference IDs are monotonically increasing while reading through the data, the deserialization CacheFormatter can use a simple List<> per type (so referenceId is simply the index in the list), instead of having to do Dictionary lookups.
  • Works not just for objects, but strings as well; and thus by extension also for Type (since that has to write as string), and thus also for MemberInfo/FieldInfo/PropertyInfo/MethodBase, ...
  • How that works is explained in the notes at the end.
  • The dictionarys/lists are cleared after every full Serialize()/Deserialize() call. But it could be very interesting to disable that. See note (*4)

• An important and major disadvantage to keep in mind (at least for now) is: No "binary-versioning" support of any kind! Opposite to MessagePack-CSharp, it does not use field indices ([Key(...)]), and it does not serialize field-names (as Contractless* formatters do in MessagePack-CSharp).

  • It uses the combination of "Field-TypeName" + "FieldName" to order fields! Which means the binary is very brittle, and any change to field or class names will break previously serialized data. It can however deal with the reordering of fields.
  • This limitation can easily be removed in the future, if there is any need for it, by optionally adding all needed meta information such as field-names, field-types into the serialized data as well. (Which would still be very efficient because of special type formatting and caching). That way it would be possible to either have some simple attributes that could be named like this:
    
    
    
    • [PreviouslyNamed("OldFieldName")], [PreviousType(typeof(IList<>))], [PreviousTypeName("TypeNameOfTypeBeforeTheUpdate")]
    
    
    • Or even dispatching the migration of seemingly completely incompatible fields to a user provided class, like [MigrationConverter(typeof(MyOldMemberToNewMemberConverterType))] for fields, or [ObjectMigrationConverter(typeof(...))] for whole objects... or something like that for automatic migration of older serialized data.
    
    
    • Note that to maintain performance here, the user would probably need to know the version of some serialized data, otherwise the serializer would have to do an expensive lookup of all the source and target types, and check if there is any sort of converter for this object or field... However that could be as simple as just adding a "version int" at the very beginning of the data, or some sort of hash that contains all the types and field names that have participated in the serialized data or so...
    
    

• Fully polymorphic serialization; even crazy large inheritance-chains and edge caes of polymorphism are supported! No need to annotate anything with [Union] like in MessagePack-CSharp, no crashes with InvalidProgramException, InvalidOpeartionException, or StackOverflowException when specifically complicated type hierarchies are encountered.

  • This is enabled by very efficient serialization of the Type type.
  • Every non-primitive, non-sealed Object is written with full type information. The serializer will still maintain performance because it makes use of the combination of efficient Type formatting and CachingFormatters! (See note *2 at the end)
  • Zero performance cost for serializing fields of primitive or fully sealed types!
  • Fully sealed means that the _EXACT_ type is known. So no, List<int> is not eligible, and still has to have type information, because the actual value in that field could still possibly be a user-class that inherits from List<>! But a field of type sealed class MyClass {...} won't need any type information!
  • Primitives (bool, int, string, ...) are written as they are, no need for any type information.

• Side effect of full support for arbitrary inheritance means it supports very efficient serialization of the "System.Type" type itself. Non-generic (normal, int), open-generic (List< >), half-open-generic (Dictionary< , int>), closed-generic types (List<int>), and every possible combination of "semi-open" generics (when nesting generics with more than 1 generic parameter) are supported.

  • Those are serialized very efficiently. See note *2 at the end for more information.

• Collections: Right now it only supports ICollection<T> (which is basically just IEnumerable+Clear+Add methods). Everything implementing that interface is automatically supported! That means List<>, Dictionary<>, ... are all automatically supported.

• Built-in efficient serialization of KeyValuePair<,> and ICollections containing them (like Dictionary)

• Built-in support types that serializers usually rarely support like: FieldInfo, ConstructorInfo, PropertyInfo, MethodInfo, and Type, simply because we have a need for that.

• Classic arrays (T[]) are not supported at the moment. Why? Simply because we try to use List<> (or similar) wherever possible because those can be cleared and reused while deserializing, whereas arrays can not be reused! They need to be of the exact right size and System.Array.Resize<> simply allocates a new array, and thus causes GC pressure. If there is interest, and you don't care about allocating arrays while deserializing, then that would be very easy to add (literally <20min).

• Right now it only serializes public fields. And there's only one attribute it supports ([IgnoreField]).

• No support for private fields (trivial to add however)
• No support for "deserialization constructors"
• No support for properties. Should however be relatively easy to add.

• No support to ignore fields of types you don't control (if you can't add [IgnoreField]), but adding a way to do that should be easy if there is interest.

• No support for the "MessagePack" format binary format or any sort of interoperability with other serializers. Nothing planned in that direction either.

• For now, no support for primitives except those few: int byte bool (all as zigzag encoded VarInt), float, string.

  • Currently not supported: literally any other primitive like uint, char, long, double, DateTime, Guid, decimal, short, ...
  • Adding support probably takes ~20-60 minutes per missing type, so not a big deal if people really need those.

(*1)
That is because I simply don't have any need for binary versioning. If we'd ever have to do something like that (for example upgrade a savegame from a previous version to a newer patch of the game), then we'd keep the old class hierarchy around in a "deprecated" namespace, and then do a very easy, simple and of course slow way to migrate the data: Use the serializer to load the old data using the old types/classes, then serialize that instance to JObject using Newtonsoft.Json, then do all the needed changes to the JObject, then deserialize that into the new type-structure. Sounds complicated but it is actually very easy. The only downside is that it is obviously really slow. But it is doubtful that this is ever needed for us anyway, and if so, it will be a one-time thing, and maybe take 200ms instead of <2ms. Should there be interest in the serializer and the community wants "versioning support", then simply adding fieldnames+field types and even "ordering ids" (as in [Key(...)] from MessagePack-CSharp), would not be a big problem. But that obviously costs some binary space then...

(*2)
To see how writing types and CachingFormatters work together, lets look at a quick example.
Let's assume you have an interface IMyObj { }, class MyObjA : IMyObj { public int Num; } and class MyObjB : IMyObj { public string Str; }.
Then you want to serialize an object containing a field of type IEnumerable<object> which right now contains a List<object>, and the list contains some crazy example content like this:
[new object(), myObjAInstance, myObjBInstance, 123.45f]

Since, at deserializationtime, it would not be clear from just the field type (IEnumerable<object>) what to instantiate, the first thing that gets written is actual type of the collection. In this case the type is List<object>, so it actually writes two separate types. The open generic System.Collections.Generic.List<> and then its argument: System.Object. After that it just writes the number of elements (here 4), and then each object.

Next the elements themselves. To serialize new object() we'd normally write the type System.Object directly again, but since that was already written once only the ID of that type (here 1, List being 0) has to be emitted, and that's it (Since object itself actually has no public fields).
Serialization continues like this, writing the type for each item, and then uses the specific DynamicFormatter to write out the content (fields) of the object. For myObjAInstance, myObjBInstance that'd just be the concrete type name + whatever value (int or string).
The float at the end has to have its type written as well as it would otherwise not be clear what formatter to use for reading (you only know object at this point). If the container would have been a List<float> no type information would have been written per element, as the collection type itself already tells us the item type!

All reference and type IDs are written as int, which is ZigZag encoded and written into the binary as a VarInt (so small numbers only consume 1 byte, using more bytes the larger the number gets, up to 5).

As shown in the example type information for generic types is not written in the usual "mangled form" as that would take up a ton of space and be very redundant.
Example: Serializing an instance of class C { public object A = (int)5; public List<int> B; }
Lets just look at how the types for A and B are written and ignore C and the actual values.
Normally the final binary data would have to contain the very long "mangled type names", which are not only long, but also full of redundant/useless information, like this:

System.Collections.Generic.List1[[System.Int32, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]], mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089`

Instead of doing that, all types are written as combinations of "open type + generic arguments", enabling massive space-savings while serializing types.
In our example we _could_ write
System.Int32 for the type of A and System.Collections.Generic.List<> + System.Int32 for the type of B, but there's still one more optimization to do, and that is again caching.
We've already written System.Int32, so the type definition of B can make use of that.
It can now simply write System.Collections.Generic.List<0> the 0 being the reference to the first written type (int).
In this example the savings are small, but with more realistic hierarchies and generic type definitions it makes a massive difference!

(*3) How reference serialization works
While serializing, if the object was encountered before, it simply writes a lookup ID. If not, it writes out -1 + the new object. While deserializing it reads the ID, if its's -1 the object is added to the known objects list. Note that deserialization uses a list, not a dictionary, so no performance cost while deserializing. This also works for self-referencing objects, and indirectly self-referencing objects (for example an object that references itself through an object-typed field)

(4*) Keeping the reference cache!
Normally that wouldn't make sense, because every serialized object is probably unique in its type-setup (maybe there's a SpecificTypeA at index 5 of some list at one time, and the other time it is a SpecificTypeB there ...).
But think about networking!
Having a two pairs of serializers at each endpoint (one Serializer/Deserializer-pair for sending, and one for receiving) would allow the networking protocol to be self-optimizing. Instead of having to give each object a pre-defined "NetworkMessageId" or something, the serializer would simply write out the type name in full once, and after that everytime the type is to be written, the CachingFormatters would just emit a single byte (or more if actually needed) for the type. Network-Messages that are sent rarely could be marked as "no type caching", to save ID-space for things that get sent more often (for example you wouldn't want to "allocate" a type-ID for something like LoginPacket, which is only ever sent once anyway). It's even possible to let the CachingFormatters decide what should get cached by keeping a count of how often something was encountered! That way Messages that often get sent by the server to the client, but never sent from client to server, get an ID assigned to them in the receiving direction, but not in the sending direction, extremely efficient!

[AshIceLoky]

Hi rikimaru0345,

I'm very interested by your serializer .... do you think create a repository?

thanks

[rikimaru0345]

I'll probably create a repo for it over the coming week.

[rikimaru0345]

The repository is here:
https://github.com/rikimaru0345/Ceras

The code will be added after I finished most of the guides and examples. (probably tomorrow)