Optimization

.NET volatile write performance degradation in x86

Szymon Kulec 'Scooletz' C#, Optimization , , ,

TL;DR

This is a summary of my investigation about writing a fast and well designed concurrent queue for akka.net which performance was drastically low for 32bit application. Take a look at PR here. If you’re interested in writing a well performing no-alloc applications with mechanical symapthy in mind or you’re simply interested in good .NET concurrency this post is for you.

Akka.NET

Akka.NET is an actor system’s implementation for .NET platform. It has been ported from Java. Recently I spent some time playing with it and reading through the codebase. One of the classes that I took a look into was UnboundedMailboxQueue using a general purpose .NET BCL’s concurrent queue. It looked strange to me, as knowing a structure Envelope that is passed through this queue one could implement a better queue. I did it in this PR lowering number of allocations by 10% and speeding up the queue by ~8%. Taking into consideration that queues are foundations of akka actors, this result was quite promising. I used the benchmark tests provided with the platform and it looked good. Fortunately Jeff Cyr run some tests on x86 providing results that were disturbing. On x86 the new queue was underperforming. Finally I closed the PR without providing this change.

The queue design

The custom queue provided by use a similar design to the original concurrent queue. The difference was using Envelope fields (there are two: message & sender) to mark message as published without using the concurrent queue state array. Again, knowing the structure you want to passed to the other side via a concurrent queue was vital for this design. You can’t make a universal general collection. Note ‘general’, not ‘generic’.

Volatile

To make the change finally visible to a queue’s consumer, Volatile.Write was used. The only difference was the type being written. In the BCL’s concurrent queue that was bool in an array. In my case it was an object. Both used different overloads of Volatile.Write(ref ….). For sake of reference, Volatile.Write ensures release barrier so if a queue’s consumer reads status with Volatile.Read (the aquire barrier), it will finally see the written value.

Some kind of reproduction

To know how .net is performing this operations I’ve used two types and run a sample application with x64 and x86. Let’s take a look at the code first.

struct VolatileInt
{
int _value;

public void Write(int value)
{
_value = value;
}

public void WriteVolatile(int value)
{
Volatile.Write(ref _value, value);
}
}

struct VolatileObject
{
object _value;

public void Write(object value)
{
_value = value;
}

public void WriteVolatile(object value)
{
Volatile.Write(ref _value, value);
}
}

It’s really nothing fancy. These two either write the value ensuring release fence or just write the value.

Windbg for x86

The methods had been prepared using RuntimeHelpers.PrepareMethod(). A Windbg instance was attached to the process. I loaded sos clr and took a look at method tables of these two types. Because methods had been prepared, they were jitted so I could easily take a look at the jitted assembler. Because x64 was performing well, let’s take a look at x86. At the beginning let’s check the non-object method, VolatileInt.VolatileWrite

cmp     byte ptr [ecx],al
mov     dword ptr [ecx],edx
ret

Nothing heavy here. Effectively, just move a memory and return. Let’s take a look at writing the object with VolatileObject.VolatileWrite

cmp     byte ptr [ecx],al
lea     edx,[ecx]
call    clr!JIT_CheckedWriteBarrierEAX

Wow! Beside moving some data an additional method is called. The method name is JIT_CheckedWriteBarrierEAX (you probably this now that there may be a group of JIT_CheckedWriteBarrier methods). What is it and why does it appear only in x86?

CoreCLR to the rescue

Take a look at the following snippet and compare blocks for x86 and non-x86? What can you see? For x86 there are additional fragments, including the one mentioned before JIT_CheckedWriteBarrierEAX. What does it do? Let’s take a look at another piece of CoreCLR here. Let’s not dive into this implementation right now and what is checked during this call, but just taking a look at first instructions of this method one can tell that it’ll cost more than the simple int operation

cmp edx,dword ptr [clr!g_lowest_address]
jb      clr!JIT_CheckedWriteBarrierEAX+0x35
cmp     edx,dword ptr [clr!g_highest_address]
jae     clr!JIT_CheckedWriteBarrierEAX+0x35
mov     dword ptr [edx],eax
cmp     eax,dword ptr [clr!g_ephemeral_low]
jb      clr!JIT_CheckedWriteBarrierEAX+0x37
cmp     eax,dword ptr [clr!g_ephemeral_high]
jae     clr!JIT_CheckedWriteBarrierEAX+0x37
shr     edx,0Ah

Summing up
If you want to write well performing code and truly want to support AnyCPU, a proper benchmark tests run with different architectures should be provided.
Sometimes, a gain in one will cost you a lot in another. Even if for now this PR didn’t make it, this was an interesting journey and an extreme learning experience. There’s nothing better that to answer a childish ‘why?’ on your own.

Roslyn coding conventions applied

Szymon Kulec 'Scooletz' Optimization, RampUp , ,

Roslyn is a ‘compiler as a service’ provided for both VisualBasic.NET & C#. It has a thriving community of people providing new features for .NET languages. One of the most important parts of this community is a guideline how to contribute, which defines basic rules for coding and issuing pull requests. The most important part, not only from Roslyn perspective, but as general .NET guidance are Coding Conventions.

Avoid allocations in hot paths

This is the rule, that should be close to every .NET developer heart, not only these that work on a compiler. It’s not about ‘premature optimization’. It’s about writing performant code that actually can sustain its performance when executing its hot paths in majority of the requests. Give it a try, and when writing some code next time (today?) have this rule in mind. Awareness of this kind, may result in having no need for profiling your production system or making a dump just to know that allocating a list for every cell of two dimensional array wasn’t the best approach.

What’s your hot path

That’s a good question that everyone should answer on their system basis. I asked this question a few months ago for my RampUp library:

what’s the hot path for a system using message passing?

The answer was surprisingly obvious: the message passing itself. EventStore, using a similar approach uses classes for message passing. This plus every other object creates some GC pressure. Back then, I asked myself a question, is it possible to use structs for internal process communication and come up with a good way of passing them? My reasoning was following: if I remove the GC pressure from messages, then I remove the hottest path of allocations and this can greatly improve stability of my system. Was it easy? No it wasn’t as I needed to emit a lot of code and discover some interesting properties of CLR. Did it work? Yes, it did.

Next time when you write a piece of code or design a system keep the hot path question in your mind and answer it. It’s worth it.

False sharing is dead, long live the Padded

Szymon Kulec 'Scooletz' Optimization, RampUp , , , ,

False sharing is a common problem of multithreaded applications in .NET. If you allocate objects in/for different threads, they may land on the same cache line impacting the performance, limiting gains from scaling your app on a single machine. Unfortunately, because of the multithreaded nature of the RampUp library it’s been suffering from the same condition. I’ve decided to address by providing a tooling rather than going through the whole codebase and apply LayoutKind.Explicit with plenty of FieldOffsets

Padded is born

The easiest and the best way of addressing cross cutting concerns in your .NET apps I’ve found so far is Fody. It’s a post compiler/weaver based on the mighty Mono.Cecil library. The tool has a decent documentation, allowing one to create a even quite complex plugin in a few hours. Because of this advantages I’ve used it already in RampUp but wanted to have something, which can live on its own. That how Padded was born.

Pad me please

Padded uses a very simple technique of adding a dozen of additional fields. According to the test cases provided, they are sufficient enough to provide enough of space to prohibit overlapping with another object in the same cache line. All you need is to:

  1. install Padded in your project (here you can find nuget) in a project that requires padding
  2. declare one attribute in your project: 
    namespace Padded.Fody
{
public sealed class PaddedAttribute : Attribute { }
}
  3. mark the classes that need padding with this attribute.

Summary

Marking a class/struct with one attribute is much easier than dealing with its layout using .NET attributes, especially, as they were created not for this purpose. Using a custom, small tool to get the needed result is the way to go. That’s how & why Padded was provided.

StructLayoutKind.Sequential not

Szymon Kulec 'Scooletz' Optimization, RampUp , , ,

If you want to write a performant multi threaded application which actually is an aim of RampUp, you have to deal with padding. The gains can be pretty big, considering that the whole work with threads mean, that you need to give them their own spaces to work in.

False sharing

False sharing is nothing more than two or more threads trying to use memory that’s mapped to a single line of cache. The best case for any thread is to have their own memory space separated & by separation I mean having enough of padding on the right and on the left, to keep the spaces of two threads without any overlapping. The easiest way is to add additional 64 bytes (the size of a cache line) at the end and at the beginning of the struct/class to ensure that no other thread will be able to allocate memory close enough. This mechanism is called padding.

Padding

The easiest way to apply padding is applying StructLayoutAttribute. If StructLayoutKind.Sequential is used, then adding 4 Guid fields at the beginning and 4 Guid fields at the end should work just fine. The size of Guid is 16 bytes which give us needed 64 bytes. A harder way of doing it is using StructLayoutKind.Explicit as it requires to add FieldOffsetAttribute to every field of the structure/class, explicitly stating the offset in the memory. With this approach, it’s easy to start with 64 and leave some space at the end of the class.

Problem

StructLayoutKind.Sequential works perfectly. Almost. Unfortunately if any field has type that is not Sequential or Explicit CLR will simply ignore the sequential requirement and silently apply automatic layout ruining the padding. This is a regular case, all classes use Auto by default. Unfortunately it leaves the developer with the need of applying the fields offsets manually.

Solution

As I need this padding behavior for RampUp, I’m creating a small Fody weaver plugin called Padded which will automatically calculate offsets (possibly with some memory overhead) for any class/struct marked with a proper attribute. Hopefully, it will be useful not only for RampUp but for more, performance oriented projects

Replacing a generic dictionary

Szymon Kulec 'Scooletz' Optimization, RampUp ,

There is a moment, when you profile your high-throughput system and you hit the wall. And it’s not your code but some BCL elements. That’s what happened in RampUp when I was profiling Write part of the buffer.

The writer is emitted, but as the very foundation it uses a dictionary of metadata stored per message type. The metadata are simple:

  • the message size
  • the offset of the message envelope

Before optimization it was using the generic Dictionary specified with the message type and the message metadata. It was horribly slow. As the set of messages does not change, you could easily provide a set of message types up-front. For each message type one can obtain RuntimeTypeHandle, which can be easily converted to long. With a set of longs, you could select minimal long and just subtract it from all the values. This would reduce the value to int. So here you are. You have a way of turning a type into int and ints are much easier to compare & to handle. One could even use a simple hash-map just to map between ints and metadata. This was the way to reduce the overhead of obtaining metadata with IntLookup<TValue>. After applying the change, write performance has increased by 10%.

Atomic* in RampUp

Szymon Kulec 'Scooletz' Optimization, RampUp , ,

In the two recent posts we’ve build strong/relaxed foundations to take a very first look at some parts of RampUp library.

Structs vs classes

The differences seem to be obvious. Structs are allocated on the stack (they are on heap when allocated in arrays), are passed by value unless passed by ref or out, should be small as they are copied by value as well. Instances of classes are allocated on the heap, are passed by reference. If we considered a proper wrapper for all the operations related to the value of a long, including operations related to the class Volatile, we’d need to use a class, as a struct would be copied, hence referring to the same address would be impossible, right? Not exactly

Hello pointer

Let’s take a look at the AtomicLong implementation now. It’s a struct. Why can it be a struct? Oh, wait a second. It doesn’t have a long field representing the value. It has a long* field, representing the address of the value! Now, when the AtomicLong is copied, it has the address copied, not the value, hence, it preserves the value and all the operations that were issued against it. How one can obtain a pointer to long which will be valid forever? It can be done in many ways, but one of them is to allocate an offheap, unmanaged memory using for instance Marshal.AllocHGlobal. RampUp does it in a different way (still, using unmanaged memory) but the result is the same. You have a nice wrapper around all the operations for a single long gathered in one place.

Ref vs pointer

The most interesting parts of this class struct are methods using ref. As you can see below to use Volatile.Read the pointer is first dereferenced and then, the reference to the value is taken. How does it work?

[Pure]
public int VolatileRead()
{
    return Volatile.Read(ref *_ptr);
}

To answer this question, you can compile RumpUp and use an IL viewer (DotPeek, ILSpy, Ildasm, whatever you want). You’ll see an interesting thing. The pointer is passed to the method without any modifications, in other words, dereferencing and then taking a reference to the obtained value negate each other resulting in the pointer being passed to the Volatile.Read.

Summing up

This simple wrapper around all the memory & memory barriers related operations for long is one of the pillars of RampUp. Now we can move forward with more advanced operations.

Memory models relaxed foundations

Szymon Kulec 'Scooletz' Optimization, RampUp , ,

In the previous post we’ve built up some basic foundations for total ordering of CPU instructions. It was mentioned that this total ordering is much too strict and if we want to use the hardware in the best possible way, there’s a need of relaxed barriers, that allow some reorderings, especially when considering high-througput libraries like RampUp.

2×2 = 4

From the CPU perspective there are only two operations that can be performed on a memory location. These are:

  • Store – a value is read from the memory
  • Load – a value is written to the memory

If you consider an order of two operations you can get following chains (pairs):

  • Load-Store
  • Load-Load
  • Store-Load
  • Store-Store

These for pairs are enough to consider different reorderings. One can easily imagine reordering elements in each of these pairs. Knowing these pairs and the definition of the full memory barrier, one can easily reason, that the full barrier prohibits all of the reorderings mentioned above.

Volatile this, volatile that

There’s a class in .NET, used very infrequently, called Volatile. It has only two methods, with many overloads. They’re Read and Write. Here’s their semantics:

  • Volatile.Read – is equal to the following sequence of operations:
    • read the value from the memory
    • issue a barrier prohibiting Load-Store & Load-Load reorderings
  • Volatile.Write – is equal to the following sequence of operations:
    • issue a barrier prohibiting Store-Store & Load-Store reorderings
    • write the value to the memory

These two methods should be thought of as siblings and should be used together. If one thread writes value with a Volatile.Write & the other reads with Volatile.Read, the value written by the first will be visible to the second after a while, in other words, reading the value in the loop finally will result in the value written by the first thread. This behavior connected with the barriers and disabling some of the reorderings may create an extremely performant approaches.

Summing up & RampUp implications

Now, the memory barriers, reorderings are known a bit better. You know, that an efficient & performant code is a code that lets a CPU for reorderings to optimize the pipeline. You know also, that beyond full memory barriers there are much less obstructive methods that can be used to apply partial ordering of instructions. As our knowledge about memory expands, we’re getting closer to analyze the very first element of the RampUp, AtomicLong & AtomicInt.