High-performance code design patterns in C#

class: center, middle

# High-performance code design patterns in `C#`
### Konrad Kokosa
#### @konradkokosa
https://prodotnetmemory.com

---
class: center, middle

.center[![:scale 100%](images\aboutme.png)]

---
class: center, middle

## .red[High-performance] code design patterns in `C#`

---
class: center, middle

## High-performance in `C#`?!

---
### High-performance in `C#`

Having said that, this talk is...

--
* not about APM

--
* not about frontend & architecture (like horizontal scaling)

--
* not about caching (like Redis), DB

--
* about C# **code-level** performance

---
class: center, middle

## High-performance code .red[design patterns] in `C#`

---
## Design Pattern

A design pattern:

--
- is **a common solution to a problem** that occurs in many different contexts

--
- contains expert knowledge about "best practices"

--
- allows us to avoid "reinventing the wheel"

--
- is based on more general, underlying .red[principles]

--
 - like in case of OOP design patterns (SOLID, modularity, loose coupling, ...)

---
exclude: true
class: center, middle

# Principles

--
exclude: true
#### Those principles/rules are valuable by their own, feel free to use them (like SOLID, clean code,. ...)

---
exclude: true
class: center, middle

### Principle 0 - Memory/cpu disrepancy

#### The Mother Of All Principles

---
exclude: true
#### Principle 0 - Memory/cpu disrepancy

.pull-left[![:scale 100%](images\memory2.png)]

.pull-right[![:scale 80%](images\memory1.png)]

---
exclude: true
class: middle, center

### Principle 1 - Fit the cache line

### Principle 2 - Fit the highest cache level

### Principle 3 - Design for sequential access

### Principle 4 - Avoid GC overhead

### Principle 5 - Avoid calls

### Principle 6 - Design against *false sharing*

---
### Design Patterns

Each *design pattern* is defined in a standard template:

--
* **Name**: Is... the name.

--
* **Problem:** What problem this pattern tries to solve?

--
* **Solution:** How do we solve the problem?

--
* **Benefits:** are there any addional benefits of applying this pattern? Besides solving above-mentioned problem.

--
* **Consequences:** Are there any potential drawbacks of applying this patterns?

---
class: center, middle

# Design Patterns

---
class: center, middle

## Pattern #1 - Frugal Object

---
### Pattern #1 - Frugal Object

**Problem:** We need to store efficiently set of data that can take various forms.

**Solution:** Instead of creating an object for each form separately, create kind of *discriminated union*.

**Benefits:** ...

**Consequences:** ...

---
#### Pattern #1 - Frugal Object - ASP.NET Core example

`Extensions/src/Primitives/src/StringValues.cs`:

```cs
/// Represents zero/null, one, or many strings in an efficient way.
public readonly struct StringValues : IList<string>, ...
{
	private readonly object _values;	
	...
	public string this[int index]
	{
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		get
		{
			var value = _values;
			if (index == 0 && value is string str)
			{
				return str;
			}
			else if (value != null)
			{
				// Not string, not null, can only be string[]
				return Unsafe.As<string[]>(value)[index]; // may throw
			}
			else
			{
				return OutOfBounds(); // throws
			}
		}
	}
}
```

---
#### Pattern #1 - Frugal Object

.center[![:scale 60%](images\twitter01.png)]

---
#### Pattern #1 - Frugal Object

.center[![:scale 90%](images\twitter03.jpg)]

---
#### Pattern #1 - Frugal Object

.center[![:scale 100%](images\twitter04.jpg)]

---
exclude: true
#### Pattern #1 - Frugal Object - WPF example

`./src/Microsoft.DotNet.Wpf/src/Shared/MS/Utility/FrugalList.cs`:

```cs
// These classes implement a frugal storage model for lists of type <T>.
// Performance measurements show that Avalon has many lists that contain
// a limited number of entries, and frequently zero or a single entry.
...
// The code is also structured to perform well from a CPU standpoint. Perf
// analysis shows that the reduced number of processor cache misses makes
// FrugalList faster than ArrayList or List<T>, especially for lists of 6
// or fewer items. Timing differ with the size of <T>.
```

```cs
internal sealed class SingleItemList<T> : FrugalListBase<T>
{
  public override T EntryAt(int index)
  {
    return _loneEntry;
  }
  ...
  private T _loneEntry;
}
```

---
exclude: true
#### Pattern #1 - Frugal objects - WPF example
	
```cs
internal sealed class ThreeItemList<T> : FrugalListBase<T>
{
  public override T EntryAt(int index)
  {
    switch (index)
    {
		case 0:
			return _entry0;

case 1:
			return _entry1;

case 2:
			return _entry2;

default:
			throw new ArgumentOutOfRangeException(nameof(index));
	}
  }
  ...
  private T _entry0;
  private T _entry1;
  private T _entry2;
}
```

---
exclude: true
#### Pattern #1 - Frugal objects - WPF example

```cs
internal class FrugalObjectList<T>
{
  public T this[int index]
  {
    get
    {
      // If no entry, default(T) is returned
      if ((null != _listStore) && ((index < _listStore.Count) && (index >= 0)))
      {
        return _listStore.EntryAt(index);
      }
      throw new ArgumentOutOfRangeException(nameof(index));
    }
    set
    {
	  ...
    }
  }
  internal FrugalListBase<T> _listStore;
}
```

---
### Pattern #1 - Frugal Object

**Problem:** We need to store efficiently set of data that can take various forms.

**Solution:** Instead of creating an object for each form separately, create kind of *discriminated union*.

**Benefits:** (Sometimes) smaller memory usage and better data locality. Better JIT optimizations - bound checks etc.

**Consequences:** Sometimes more complex API comparing to the plain approach. Some performance overhead due to type checks and/or additional wrappers.

---
class: center, middle

## Pattern #2 - Pooling

---
### Pattern #2 - Pooling

**Problem:** There is a non-trivial cost of creating objects very often. This cost may be direct (allocation/initialization overhead), indirect (added GC overhead, fragmentation, ...) or both.

**Solution:** Instead of creating an object each time, reuse some objects from a pre-allocated pool.

**Benefits:** ...

**Consequences:** ...

---
#### Pattern #2 - Pooling

Array pooling:
* instead of creating an array each time, reuse pooled array:
 ```cs
var pool = ArrayPool<int>.Shared;
int[] buffer = pool.Rent(minLength);
try
{
        Consume(buffer);
}
finally
{
        pool.Return(buffer);
}
```
* `Rent` returns an array with **at least** the specified length
* `Shared` instance has:
    * 17 buckets, with arrays of lengths: 16, 32, 64, 128, 256, 512, 1,024, 2,048, 4,096, 8,192, 16,384, 3,2768, 65,536, 131,072, 262,144, 524,288 and 1,048,576, each bucket contains maximum of 50 arrays
* they are created on demand
* **not cleared** when rented or returned (but `Return(T[] array, bool clearArray = false)`)
* **trimming mechanism** - explicit `Trim()` method

???

`ArrayPool<T>.Shared` uses `TlsOverPerCoreLockedStacksArrayPool<T>` class - there is a small per-thread cache of each array size and a cache shared by all threads split into per-core stacks (hence its name).

---
#### Pattern #2 - Pooling

```cs
[Benchmark]
public double VersionObjectArray()
{
	DataClass[] data = new DataClass[_itemsCount];
	for (int i = 0; i < _itemsCount; ++i)
	{
		data[i] = new DataClass();
		data[i].Age = _items[i].Age;
		data[i].Gender = Helper(_items[i].Description) 
						 ? Gender.Female : Gender.Male;
	}
	return ProcessBatch(data);
}
```

--
```bash
|                Method |       Mean |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|---------------------- |-----------:|-------:|------:|------:|----------:|
|    VersionObjectArray | 1,384.1 ns | 0.9689 |     - |     - |    4056 B |
```

---
#### Pattern #2 - Pooling

```cs
[Benchmark]
public double VersionClassArrayPool()
{
	DataClass[] data = ArrayPool<DataClass>.Shared.Rent(_itemsCount);
	for (int i = 0; i < _itemsCount; ++i)
	{
		data[i] ??= new DataClass();
		data[i].Age = _items[i].Age;
		data[i].Gender = Helper(_items[i].Description) 
		                 ? Gender.Female : Gender.Male;
	}
	double result = ProcessBatch(data, _itemsCount);
	ArrayPool<DataClass>.Shared.Return(data);
	return result;
}
```

---
#### Pattern #2 - Pooling

* abstract `MemoryPool<T>` - represents a pool of memory blocks
	* `MemoryPool<T>.Shared` - based on `ArrayPool`
	* `SlabMemoryPool : MemoryPool<byte>` - the memory pool behind Kestrel.
* Object pooling:
	* quite often not necessary - cost of handling outweighs benefits
		* maybe for heavy, costly in creation objects 
		* or tremendously often created
	* no standard implementation yet
		* internal [`ObjectPool<T>`](https://github.com/dotnet/roslyn/blob/master/src/Dependencies/PooledObjects/ObjectPool%601.cs) from Roslyn
		* ...
		* [Core support for object pooling](https://github.com/dotnet/coreclr/issues/23342) CoreCLR issue... is closed

---
### Pattern #2 - Pooling

**Problem:** There is a non-trivial cost of creating objects very often. This cost may be direct (allocation/initialization overhead), indirect (added GC overhead, fragmentation, ...) or both.

**Solution:** Instead of creating an object each time, reuse some objects from a pre-allocated pool.

**Benefits:** Smaller GC overhead, no allocation/initialization cost, better data locality.

**Consequences:** Trimming policy may be not trivial.

---
class: center, middle

## Pattern #3 - Zero-copy (Avoid copying)

---
### Pattern #3 - Zero-copy (Avoid copying)

**Problem:** Oparations on "sub-data" require a temporary object to represent it, which introduces a lot of short-living objects. Typical examples are `string.Substring()` or sub-arrays/sub-lists.

**Solution:** Introduce special types that allow *slicing* - represnting sub-regions without a memory copy.

**Benefits:** ...

**Consequences:** ...

---
#### Pattern #3 - Zero-copy (Avoid copying) - `Span<T>`

It contains a *managed pointer* and a length:

```cs
public ref struct Span<T>
{
*  internal ref T _pointer;
   private int _length;
   ...
}
```

.center[![:scale 40%](images\managedpointer01-1.png)]

---
#### Pattern #3 - Zero-copy (Avoid copying) - `Span<T>`

So we have our beloved `Span<T>`:

--
```cs
var array = new int[64];
Span<int> span1 = new Span<int>(array);
Span<int> span2 = new Span<int>(array, start: 8, length: 4);
```

--
```cs
Span<int> span3 = stackalloc[] { 1, 2, 3, 4, 5 };
```

--
```cs
IntPtr memory = Marshal.AllocHGlobal(64);
void* ptr = memory.ToPointer();
Span<byte> span4 = new Span<byte>(ptr, 64);
```

--
```cs
string str = "Hello world";
ReadOnlySpan<char> span5 = str.AsSpan();
```

--
Zero-copy slicing 😍:

--
```cs
var span6 = span.Slice(0, 4);
```

---
#### Pattern #3 - Zero-copy (Avoid copying) - `Span<T>`

* `Span<T>` contains *managed pointer*, it cannot appear on the Managed Heap

--
* the main concern - `async` methods with their *boxing* state machines

```cs
// Does not compile with an error:
// "Parameters or locals of type 'Span<char>' cannot be declared in async methods or lambda expressions"
public async Task DoAsync(Span<char> data)
{
    Do(data.Slice(0, 10));
    await DoOtherAsync();
}
```

--
Use `Memory<T>` instead - general-purpose slicing of arrays, strings and ...

```cs
// Does compile - Span is not a local variable here!
public async Task DoAsync(Memory<char> data)
{
	DoSync(data.Span.Slice(0, 10));
	await DoOtherAsync();
}

private void DoSync(Span<char> data) => Console.WriteLine(data.Length);
```

---
exclude: true
#### Pattern #3 - Zero-copy (Avoid copying) - `Span<T>`

```cs
public unsafe Span<byte> rocksdb_get_span(
	IntPtr db,
	IntPtr read_options,
	byte[] key,
	long keyLength,
	out IntPtr errptr,
	ColumnFamilyHandle cf = null)
{
	...
	var resultPtr = rocksdb_get(db, read_options, key, skLength, out UIntPtr valueLength, out errptr)
	...
	return new Span<byte>((void*)resultPtr, (int)valueLength);
}

public unsafe void dangerous_rocksdb_release_span(in Span<byte> span)
{
	ref byte ptr = ref MemoryMarshal.GetReference(span);
	IntPtr intPtr = new IntPtr(Unsafe.AsPointer(ref ptr));
	rocksdb_free(intPtr);
}
```

---
#### Pattern #3 - Zero-copy (Avoid copying)

Other examples:
* System.IO.Pipelines
* `ref` returning and argument passing

---
exclude: true
#### Pattern #3 - Zero-copy (Avoid copying) - ref returning collection

```cs
public class RefValueBookCollection
{
	public ValueBook[] books = {
		new ValueBook { Title = "Call of the Wild, The", Author = "Jack London" },
		new ValueBook { Title = "Tale of Two Cities, A", Author = "Charles Dickens" } };
	private ValueBook nobook = default;
	public ref ValueBook GetBookByTitle(string title)
	{
		for (int ctr = 0; ctr < books.Length; ctr++)
			if (title == books[ctr].Title)
				return ref books[ctr];
		return ref nobook;
	}

public static void Run()
	{
		var collection = new RefValueBookCollection();
		ref var book = ref collection.GetBookByTitle("Call of the Wild, The");
		book.Author = "Konrad Kokosa";
		Console.WriteLine(collection.books[0].Author);
	}
}
```
---
### Pattern #3 - Zero-copy (Avoid copying)

**Problem:** Oparations on "sub-data" require a temporary object to represent it, which introduces a lot of short-living objects. Typical examples are `string.Substring()` or sub-arrays/sub-lists.

**Solution:** Introduce special types that allow *slicing* - represnting sub-regions without a memory copy.

**Benefits:** You can operate on subset of data without overhead of memory copy - especially useful in various "descendant" parsers.

**Consequences:** API and code is being polluted with technical-specific types, instead of using generic, intuitive ones.

---
class: center, middle

## Pattern #4 - Struct of Arrays

---
### Pattern #4 - Struct of Arrays
	
**Problem:** Processing a lot of data is not efficient due to the memory access time.

**Solution:** Design data structures and processing steps to leverage data locality and sequential access. Most typically, in the form of plain arrays of data.

**Benefits:** ...

**Consequences:** ...