Introduction
Recently I’ve been optimizing the heck out of Noda Time. Most of the time this has been a case of the normal measurement, find bottlenecks, carefully analyse them, lather, rinse, repeat. Yesterday I had a hunch about a particular cost, and decided to experiment… leading to a surprising optimization.
Noda Time’s core types are mostly value types – date/time values are naturally value types, just as DateTime and DateTimeOffset are in the BCL. Noda Time’s types are a bit bigger than most value types, however – the largest being ZonedDateTime, weighing in at 40 bytes in an x64 CLR at the moment. (I can shrink it down to 32 bytes with a bit of messing around, although it’s not terribly pleasant to do so.) The main reason for the bulk is that we have two reference types involved (the time zone and the calendar system), and in Noda Time 2.0 we’re going to have nanosecond resolution instead of tick resolution (so we need 12 bytes just to store a point in time). While this goes against the Class Library Design Guidelines, it would be odd for the smaller types (LocalDate, LocalTime) to be value types and the larger ones to be reference types. Overall, these still feel like value types.
A lot of these value types are logically composed of each other:
- A LocalDate is a YearMonthDay and a CalendarSystem reference
- A LocalDateTime is a LocalDate and a LocalTime
- An OffsetDateTime is a LocalDateTime and an Offset
- A ZonedDateTime is an OffsetDateTime and a DateTimeZone reference
This leads to a lot of delegation, potentially – asking a ZonedDateTime for its Year could mean asking the OffsetDateTime, which would ask the LocalDateTime, which would ask the LocalDate, which would ask the YearMonthDay. Very nice from a code reuse point of view, but potentially inefficient due to copying data.
Why would there be data copying involved? Well, that’s where this blog post comes in.
Behaviour of value type member invocations
When an instance member (method or property) belonging to a value type is invoked, the exact behaviour depends on the kind of expression it is called on. From the C# 5 spec, section 7.5.5 (where E is the expression the member M is invoked on, and the type declaring M is a value type):
If E is not classified as a variable, then a temporary local variable of Eās type is created and the value of E is assigned to that variable. E is then reclassified as a reference to that temporary local variable. The temporary variable is accessible as this within M, but not in any other way. Thus, only when E is a true variable is it possible for the caller to observe the changes that M makes to this.
So when is a variable not a variable? When it’s readonly… from section 7.6.4 (emphasis mine) :
If T is a struct-type and I identifies an instance field of that class-type:
- If E is a value, or if the field is readonly and the reference occurs outside an instance constructor of the struct in which the field is declared, then the result is a value, namely the value of the field I in the struct instance given by E.
(There’s a very similar bullet for T being a class-type; the important part is that the field type is a value type
The upshot is that if you have a method call of:
then it’s effectively converted into this:
int result = tmp.Foo();
Now if the type of the field is quite a large value type, but Foo() doesn’t modify the value (which it never does within my value types), that’s performing a copy completely unnecessarily.
To see this in action outside Noda Time, I’ve built a little sample app.
Show me the code!
Our example is a simple 256-bit type, composed of 4 Int64 values. The type itself doesn’t do anything useful – it just holds the four values, and exposes them via properties. We then measure how long it takes to sum the four properties lots of times.
using System.Diagnostics;
public struct Int256
{
private readonly long bits0;
private readonly long bits1;
private readonly long bits2;
private readonly long bits3;
public Int256(long bits0, long bits1, long bits2, long bits3)
{
this.bits0 = bits0;
this.bits1 = bits1;
this.bits2 = bits2;
this.bits3 = bits3;
}
public long Bits0 { get { return bits0; } }
public long Bits1 { get { return bits1; } }
public long Bits2 { get { return bits2; } }
public long Bits3 { get { return bits3; } }
}
class Test
{
private readonly Int256 value;
public Test()
{
value = new Int256(1L, 5L, 10L, 100L);
}
public long TotalValue
{
get
{
return value.Bits0 + value.Bits1 + value.Bits2 + value.Bits3;
}
}
public void RunTest()
{
// Just make sure it’s JITted…
var sample = TotalValue;
Stopwatch sw = Stopwatch.StartNew();
long total = 0;
for (int i = 0; i < 1000000000; i++)
{
total += TotalValue;
}
sw.Stop();
Console.WriteLine("Total time: {0}ms", sw.ElapsedMilliseconds);
}
static void Main()
{
new Test().RunTest();
}
}
Building this from the command line with /o+ /debug- and running (in a 64-bit CLR, but no RyuJIT) this takes about 20 seconds to run on my laptop. We can make it much faster with just one small change:
{
private Int256 value;
// Code as before
}
The same test now takes about 4 seconds – a 5-fold speed improvement, just by making a field non-readonly. If we look at the IL for the TotalValue property, the copying becomes obvious. Here it is when the field is readonly:
get_TotalValue() cil managed
{
// Code size 60 (0x3c)
.maxstack 2
.locals init (valuetype Int256 V_0,
valuetype Int256 V_1,
valuetype Int256 V_2,
valuetype Int256 V_3)
IL_0000: ldarg.0
IL_0001: ldfld valuetype Int256 Test::’value’
IL_0006: stloc.0
IL_0007: ldloca.s V_0
IL_0009: call instance int64 Int256::get_Bits0()
IL_000e: ldarg.0
IL_000f: ldfld valuetype Int256 Test::’value’
IL_0014: stloc.1
IL_0015: ldloca.s V_1
IL_0017: call instance int64 Int256::get_Bits1()
IL_001c: add
IL_001d: ldarg.0
IL_001e: ldfld valuetype Int256 Test::’value’
IL_0023: stloc.2
IL_0024: ldloca.s V_2
IL_0026: call instance int64 Int256::get_Bits2()
IL_002b: add
IL_002c: ldarg.0
IL_002d: ldfld valuetype Int256 Test::’value’
IL_0032: stloc.3
IL_0033: ldloca.s V_3
IL_0035: call instance int64 Int256::get_Bits3()
IL_003a: add
IL_003b: ret
} // end of method Test::get_TotalValue
And here it is when the field’s not readonly:
get_TotalValue() cil managed
{
// Code size 48 (0x30)
.maxstack 8
IL_0000: ldarg.0
IL_0001: ldflda valuetype Int256 Test::’value’
IL_0006: call instance int64 Int256::get_Bits0()
IL_000b: ldarg.0
IL_000c: ldflda valuetype Int256 Test::’value’
IL_0011: call instance int64 Int256::get_Bits1()
IL_0016: add
IL_0017: ldarg.0
IL_0018: ldflda valuetype Int256 Test::’value’
IL_001d: call instance int64 Int256::get_Bits2()
IL_0022: add
IL_0023: ldarg.0
IL_0024: ldflda valuetype Int256 Test::’value’
IL_0029: call instance int64 Int256::get_Bits3()
IL_002e: add
IL_002f: ret
} // end of method Test::get_TotalValue
Note that it’s still loading the field address (ldflda) four times. You might expect that copying the field onto the stack once via a temporary variable would be faster, but that ends up at about 6.5 seconds on my machine.
There is an optimization which is even faster – moving the totalling property into Int256. That way (with the non-readonly field, still) the total time is less than a second – twenty times faster than the original code!
Conclusion
This isn’t an optimization I’d recommend in general. Most code really doesn’t need to be micro-optimized this hard, and most code doesn’t deal with large value types like the ones in Noda Time. However, I regard Noda Time as a sort of "system level" library, and I don’t ever want someone to decide not to use it on performance grounds. My benchmarks show that for potentially-frequently-called operations (such as the properties on ZonedDateTime) it really does make a difference, so I’m going to go for it.
I intend to apply a custom attribute to each of these "would normally be readonly" fields to document the intended behaviour of the field – and then when Roslyn is fully released, I’ll probably write a test to validate that all of these fields would still compile if the field were made readonly (e.g. that they’re never assigned to outside the constructor).
Aside from anything else, I find the subtle difference in behaviour between a readonly field and a read/write field fascinating… it’s something I’d been vaguely aware of in the past, but this is the first time that it’s had a practical impact on me. Maybe it’ll never make any difference to your code… but it’s probably worth being aware of anyway.
That’s interesting.
I’d be tempted to use #if around declarations in this instance:
#if(DEBUG)
private readonly int _x;
#else
private int _x;
#endif
Doesn’t have to be DEBUG, obviously, but means you can just run a compile with whatever flag you use set to check the readonly behaviour.
It would be interesting to see a performance comparison that a) uses a value type as large as the real-world one (i.e. 320 bits instead of 256), and b) considers the performance of the reference type equivalent.
Even more interesting would be to see a more realistic performance profile, one designed to show the real-world performance impact of using a 40-byte value type instead of a reference type.
I empathize with the goal to ensure no one eschews NodaTime on the basis of performance. But it’s not clear to me that a profile performed here does that.
The most useful result is having demonstrated that, just as one might suppose, putting the arithmetic inside the value type instead of repeatedly retrieving the value type’s internals provides the best performance. But at the end of the day, what if even that optimization provides only a fraction the performance that a reference type would?
@M
@Mark: That’s an interesting idea. I like the way I could easily switch between configurations to check that it would still compile. I have something similar for preconditions of internal methods. Hmm.
@pete.d: The fact that OffsetDateTime and ZonedDateTime are value types has more to do with consistency than the performance goal. They still *feel* like natural value types to me – and I’d find it hard to justify why (say) LocalDateTime would be a value type but OffsetDateTime would be a reference type.
I agree that the performance tests I’ve done don’t address that question – but I’m actually not sure how I *would* address that, as suddenly the frequency of different operations becomes more important… there’s more cost to construction due to allocation and GC, so I’d need to understand the relative frequency of “create new value” vs “interrogate existing value”. It’s a question which would be good to answer, but which I don’t have the data for at the moment.
Of course I could still *try* making ZonedDateTime a class and run the existing benchmarks, just for the sake of interest…
This seems to be a problem of JIT64, specifically; if you look at the generated machine code, there is lots of unnecessary copying going on in the readonly case. Although, the x86 JIT compiler produces less efficient code for the readonly case as well, the difference is much less severe (approx. +14% runtime compared to the “not-readonly” case on an Core i5-4570).
Re: value vs reference type
Are these values in NodaTime immutable? If not, well there’s a problem right there.
If they are immutable, then so too could be the reference type version of the objects.
And in that case I would be surprised if reference type overheads of allocation and GC were significant. As immutable reference types, new instances need be made only when new values are actually made, and allocation and GC is likely to be _less_ expensive than copying 40 bytes every time the value is passed from one place in the code to another (e.g. down a method call stack or across threads).
As I know you’re well aware, allocation in .NET is basically free. During the lifetime of the object, you win by a margin of 5x even on x64 (10x on x86…and that ignores the fact that register-sized pointers are cheaper even per byte to copy than strings of bytes) on passing/copying/etc. So the only real overhead is collection, but of course .NET is well-optimized for dealing with short-lived objects, and long-lived objects get to exercise their 5x copying advantage more often.
I admit, I am not fully versed in the design philosophies behind the C# distinction between value and reference types. But it’s my understanding that the main goal was to expose to the C# programmer more control over allocation strategies. I don’t see value vs reference as having any real semantic benefit, so the idea that a type “feels like” a value type is foreign to me. Or rather, to me the way to deal with a type that “feels like” a value is really that it feels like something that ought to be immutable. Which is as easily accomplished with reference types as with value types.
Back to the performance question then…the one place I can see an argument in favor of sticking with a value type is if you expect there to be very large arrays of these objects, where most or all of the value instances are unique. But even there, you’re talking only 20% overhead (10% on x86) for a specific scenario, where in other scenarios there may be no performance benefit.
Well, sorry for the rambling. The bottom line is that I believe that in truth, time is not such a central element of nearly any program that these types of decisions would have real performance impacts (i.e. ones a user would notice) in the vast majority of cases.
You’re also correct that doing a performance analysis that takes into account a reference type implementation would be much more complicated. But a performance analysis minus consideration of reference types isn’t a valid analysis.
I.e. it’s academically interesting to understand the impact of readonly versus read/write value type members, but inasmuch as it presupposes value types instead of reference types, it seems to miss the bigger picture.
I just think that inasmuch as anyone might worry about performance to this degree, that the basic choice of using value types in the first place seems questionable. š And if there are non-performance reasons to stick with value types, then I think the goal of “don’t _ever_ [emphasis pete.d] want someone to decide not to use it on performance grounds” is a distraction and should probably be abandoned. Because if using a value type for non-performance reasons results in less-than-optimal performance in any scenario, it’s practically certain at least one person will opt out of NodaTime for performance reasons.
(My apologies if this is a repeat submission…the server seems very slow and I have not gotten a confirmation of posting)
@Mark: Not sure if it’s a good idea or not, but you can avoid redeclaring (that is, repeating yourself) the variable:
private
#if(DEBUG)
readonly
#endif
int _x;
or
#if(DEBUG)
readonly
#endif
private int _x;
Might throw someone for a loop reading the code though.