Skip to main content

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.

Comments

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu