Foreword
If you read nothing else in this post, please at least read the
bit about params; thanks. I’m going to talk about a number of things that cause unforeseen allocations, and then discuss possible options for avoiding them. Some of the options presented are intentionally exotic and esoteric, and are
not intended to be used directly – they are for the purposes of discussion only.
Additional: Blogger and LiveWriter seem to be squabbling about the layout; my apologies for any spacing issues
Back story
Today I rant about allocations; “but objects are cheap!” I hear you cry – and indeed you’d be right. So is an individual coffee bean, but yet coffee is one of the most highly traded commodities in the world (next to crude oil, IIRC). Any Java joke in here is coincidental. You use something routinely, and it is amazing how it adds up. On 64 bit, even an empty object is pretty big.
.NET has a first class garbage collector, and it is constantly improving, but on
a busy system memory concerns can be very noticeable and very real. Adding more memory to the box
helps a bit, but then when garbage collection
does eventually happen, it can be even more noticeable.
So; I get very excited about allocations. Perhaps ridiculously so. I want to be very clear:
I don’t mind using objects, and I don’t mind using memory. Simply – I want to be using them for useful work. And a lot of things… just
aren’t. Collecting a few hundred generation-zero objects might be cheap, but do you know what is cheaper?
Not having to. Perhaps my perspective is also skewed a bit by the fact that I work on a lot of library / utility code, and have reached the conclusion that no library should ever be the cause of unexpected / unnecessary overhead. Application code is a bit different: in application code you should be writing domain logic
about your application – that is
useful work and is free to do whatever it wants.
Enough background; let’s look at an example; don’t worry, we’ll pick an easy one…
string prefix = // something variable
foreach (var line in File.ReadAllLines(somePath))
foreach (var token in line.Split(';').Where(s => s.StartsWith(prefix)))
{
Console.WriteLine(token);
}
Fairly innocent looking file processing; but let’s pull it apart for allocations – I’ll list them first, and discuss each in turn:
ReadAllLines creates a vector containing each line, all at once - We get an enumerator over the vector of lines
- We get a capture-context over
prefix
- Then for every line:
- We create and populate a new vector of characters, length 1 – for the
Split call
Split allocates a vector of the results - The first iteration only (in this case, but can vary) creates a delegate to the hoisted predicate on the capture-context (the lambda)
Where allocates an enumerable/iterator (some fancy details make the same object function as enumerable and iterator most of the time)
Which might not sound too bad at all, but if you know (by usage, profiling, memory dumps etc) that this code is used
all the time, then you really might want to think about how much of these are actually useful.
The obvious but uninteresting problems
There are no prizes for spotting these…
ReadAllLines
Yeah, not much to say here other than: use
ReadLines instead, which gives you a spooling iterator over the lines, rather than reading everything up front. Not what I want to focus on today, really.
foreach over a vector
You need to be a little careful over-interpreting
foreach on a vector – I suspect the JIT might do more than you might imagine here, so I’m not going to get too excited about this. If we
did still have a vector (see above), then a naked
for might be cheaper, but I wouldn’t rely on it – again, not my focus.
The capture-context and delegate
Did that lambda
really make the code easier to read than, say, an
if test (with either a nested block or a
continue)? LINQ is great, but can be over-used… and in non-trivial code the captures can be surprisingly nuanced, often requiring a new capture-context and delegate instance on every iteration.
The less obvious, but more interesting (IMO) problems
There are also no prizes for spotting these, but give yourself a quiet cheer if you did.
The params array to Split
This is one that often gets overlooked; the overload of
Split being used here takes a
params char[];
there is no overload that takes a single char. Most usages of
Split that I see only use a single
char parameter (or maybe two). Since .NET vectors are mutable, it doesn’t trust the code inside the method not to change the values, so the compiler explicitly
does not hoist this away onto a static field somewhere. It would be nice if it could, but there’s a lot of “const correctness” problems that would need to be resolved for that to work – so it needs to allocate a new vector
every single call – which is often inside loops within loops. In the interim, I posit that there are some sorely needed missing overloads here! I
strongly recommend that you do a search for “.Split(“ in your code and see how many times you use it – especially in loops. I tend to create a utility class (imaginately named
StringSplits), and use things like
line.Split(StringSplits.Semicolon), where that is defined as
static readonly char[] Semicolon = {';'};
This change is so staggeringly simple, but removes
so many allocations that are
entirely overhead. Imagine what your CPU could be doing instead of collecting all those vectors!
The result of Split
Yet another vector. But really… do we need that? A lot of uses of
Split are going to involve things like
foreach, so maybe an
IEnumerable<string> (presumably via an iterator block) would be more efficient. But, then we still need to allocate an enumerator etc. Or do we? A lot of people mistakenly think that
foreach is tied to the
IEnumerable[<T>]/
IEnumerator[<T>] interfaces. It is indeed true that the compiler
can use these, but actually the compiler looks first for a
duck-typed API:
- is there a method called
GetEnumerator() that returns some result…
- …that has a
bool MoveNext() method
- …and a
.Current property with a get accessor?
If so:
that is what it uses. Historically, this allowed for typed iterators that didn’t need to box their values, but it also allows the
iterator itself to be a value-type. This is actually very common –
List<T> and
Dictionary<TKey,TValue> use this approach – which means when you iterate a
List<T> directly, there are zero allocations. If, however, you use the
IEnumerable[<T>]/
IEnumerator[<T>] APIs, you force the iterator to become boxed. And keep in mind that LINQ uses the
IEnumerable[<T>]/
IEnumerator[<T>] APIs – so code like our lazy
Where shown above can multiple unexpected consequences.
If we wanted to, we could write a
Split2 (naming is hard) extension method that took a single char, and returned a value-typed enumerator / iterator; then this entire chunk would have zero
overhead allocations. It would still have the allocations for the substrings, but
that is useful data, not overhead. Unfortunately the compiler doesn’t help us at all here – if you want to write value-typed iterators you need to do it all by hand, which is quite tedious. I’ve tested it locally and it works great, but I’m not actually presenting this as a serious “thing to do” – the intent here is more to get people thinking about what is possible.
What about the substrings?
Another interesting feature of
Split is that everything it produces is
pure redundant duplication. If I split “abc,def,ghi” by commas, then I now have 4 strings, 3 of which are exact sub-substrings of the original. Since strings in .NET are immutable (at least, to the public), it is alarming how close this is to being ideal, while being so far away in reality. Imagine if there was a
Substring struct – a tuple consisting of a
string reference, the offset to the first character, and length – with equality and comparison support etc. Unfortunately, without direct support from the BCL by things like
StringBuilder,
TextWriter, etc (so that they could copy in values without creating a new
string) it wouldn’t be very useful. What would be even nicer is if we didn’t need such a thing in the first place, and could simply use
string itself to represent internal sub-strings – however, unfortunately the internal implementation details don’t really allow for that: it isn’t the case that the
string type contains a pointer to the actual data; rather, the
string instance is magically variable-sized, and is the data. Again, I don’t have a magic wand here, other than highlighting where hidden allocations can come from.
Why do I care about all of this?
Because often, memory profiling shows that vast amounts of our memory is swamped with silly, unnecessary allocations. Of particular note in some recent Stack Exchange memory dumps was
massive numbers of
string[] next to the same recurring set of
strings. After some digging, we recognised them from
[OutputCache] parameters. Some of these we could remove ourselves by tweaking our
GetVaryByCustomString; in our case, we were actually mainly interested in “does the tokenized string contain this token, under usual split logic“ – and of course you don’t
actually need to split the code
at all to do that – you can just check for containment, paying special attention to the previous/next characters. Some more of these allocations were coming from ASP.NET MVC (and I hope to send a pull-request over shortly); and yet more are coming from raw ASP.NET internals - (
Page, IIRC - which has the low-level output caching implementation). The overheads we were seeing is from
Split; and pretty much all of it is avoidable if the code is written with a view to allocations. Since we make extensive use of caching, we were perhaps paying disproportionately here.
But if your server’s memory is being dominated by unnecessary overhead: that is memory that can’t be used for
interesting data, like questions and answers.
Oh, and the final code
string prefix = // something variable
foreach (var line in File.ReadLines(somePath))
foreach (var token in line.Split2(';'))
{
if(token.StartsWith(prefix))
{
Console.WriteLine(token);
}
}
