Saturday, April 20, 2013

Fast Deep Copies in C# using Sasa.Dynamics

I've briefly discussed Sasa.Dynamics in my first announcement for the upcoming Sasa v0.9.4 release. There was some confusion about what Sasa.Dynamics really is though, since the post didn't go into much detail, or wasn't explained clearly enough. In short, Sasa.Dynamics is a framework for type-safe, blazingly fast reflection.

It's useful for writing all sorts of algorithms that compute results based on the structure of types. For instance, as mentioned in the above article, Sasa.Dynamics ships with two such algorithms by default: an immutable type test, and a deep copier. Both of these algorithms are fully generic and apply to any type, and they're faster than anything you can do with standard reflection. Here's how you perform a deep copy on an object:

var copy = Type<T>.Copy(originalValue);

If you don't know anything about the type you're copying, you can just supply T = object. The more specific the static type information you provide to the copier, the faster it will be. As a small proof, here are a few benchmarks I just added to Sasa's test suite:

= Type: Int32[] =
Binary formatter:            626608 ticks
Type<object>.Copy:           152474 ticks
Type<Int32[]>.Copy:          128127 ticks

= Type: List<Int32> =
Binary formatter:           1209692 ticks
Type<object>.Copy:           767455 ticks
Type<List`1>.Copy:           739828 ticks

= Type: Bar =
Binary formatter:           1066745 ticks
Type<object>.Copy:           549021 ticks
Type<Bar>.Copy:              500552 ticks

= List<Lazy<Int32>> =
Binary formatter:          22065369 ticks
Type<object>.Copy:         21339976 ticks
Type<List`1>.Copy:         21090640 ticks

= Type: Int32 =
Binary formatter:            428022 ticks
Type<object>.Copy:             7050 ticks
Type<Int32>.Copy:              1435 ticks

= Type: String =
Binary formatter:            222462 ticks
Type<object>.Copy:             4895 ticks
Type<String>.Copy:             1547 ticks

= Type: String[] =
Binary formatter:          25201559 ticks
Type<object>.Copy:           234653 ticks
Type<String[]>.Copy:         185214 ticks

You can clearly see that Type<T>.Copy is sometimes many orders of magnitude faster than a roundtrip through BinaryFormatter. The benchmarks for immutable types will be particularly fast, as you can see from entries for String and Int32. This is because immutability of a type is automatically detected (via Type<T>.MaybeMutable), and such values are never copied, just returned as-is.

Of course, it's not exactly hard to beat framework serialization, but what's notable here is that I'm doing it with fully general reflection and very little optimization effort. The more type information you can provide to Type<T>, the faster it is. For instance, there's a 3x-5x difference in Int32 and String copying when we provide the statically known type T rather than object.

I've also barely scratched the surface of the optimizations that can be done. The structural induction inherent to Sasa.Dynamics means I can also easily build a trace of the operations performed for a given type T, generate a function to do it all in one step, and cache that somewhere for when I need to rerun it. Basically, it would be a small tracing JIT for any reflection-based operation.

There are still a few cases I haven't fully optimized for deep copies, but it seems to work pretty well so far.

Sasa's binary serializer is also based on Sasa.Dynamics, but that hasn't received any review or optimization effort, so while it passes many correctness tests, the performance isn't all that great. Still, if you're interested to see what a serializer based on structural induction looks like, it's a good reference.

No comments: