Skip to content

Instantly share code, notes, and snippets.

@buybackoff
buybackoff / Bench.cs
Last active April 11, 2021 20:54
ByRefCtor
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
namespace ByRefCtor
{
public readonly struct Test
{
private static ref TestMut AsMutable(ref Test d) => ref Unsafe.As<Test, TestMut>(ref d);
@buybackoff
buybackoff / gitclean.sh
Last active July 12, 2020 12:32
Keep only existing files in git history
# this doesn't support renamed/moved files
# from https://stackoverflow.com/a/17909526/801189
# Works fine on Windows with Git bash shell
$ git checkout master
$ git ls-files > keep-these.txt
$ git filter-branch --force --index-filter \
"git rm --ignore-unmatch --cached -qr . ; \
cat $PWD/keep-these.txt | tr '\n' '\0' | xargs -d '\0' git reset -q \$GIT_COMMIT --" \
--prune-empty --tag-name-filter cat -- --all
@buybackoff
buybackoff / Benchmark.md
Last active August 31, 2024 20:44
Avx2/branch-optimized binary search in .NET

Binary search is theoretically optimal, but it's possible to speed it up substantially using AVX2 and branchless code even in .NET Core.

Memory access is the limiting factor for binary search. When we access each element for comparison a cache line is loaded, so we could load a 32-byte vector almost free, check if it contains the target value, and if not - reduce the search space by 32/sizeof(T) elements instead of 1 element. This gives quite good performance improvement (code in BinarySearch1.cs and results in the table 1 below).

However, for larger N the search space reduction is quite minimal and the most gains come from switching to linear search. After an interesting discussion in Twitter (especially with @trav_downs), and trying to widen the pivot area to use 2 AVX2 vectors it became clear that just switching to linear search sooner is more important than using AVX2 vectors as pivots.

The linear search was not using AVX2, and for linear

@buybackoff
buybackoff / ManualResetValueTaskSourceCore.cs
Created May 7, 2019 15:31
ManualResetValueTaskSourceCore for net461
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
using System.Diagnostics;
using System.Runtime.ExceptionServices;
using System.Runtime.InteropServices;
namespace System.Threading.Tasks.Sources
@buybackoff
buybackoff / Test.cs
Created February 22, 2019 13:00
Fixed-size struct without unsafe keyword, using "safe" S.R.CS.Unsafe
[StructLayout(LayoutKind.Sequential, Size = Size)]
public struct Test
{
public const int Size = 32;
public byte this[int idx] => Unsafe.AddByteOffset(ref Unsafe.As<Test, byte>(ref Unsafe.AsRef(in this)), (IntPtr)idx);
public override string ToString()
{
Span<byte> bytes = stackalloc byte[Size];
for (int i = 0; i < Size; i++)
@buybackoff
buybackoff / Program.cs
Last active September 21, 2018 12:31
Create memory pressure on private working set. Exit after 30 seconds of inactivity (if on RDP and server hangs)
using System;
using System.Collections.Generic;
using System.Threading.Tasks;
namespace MemoryPressure
{
internal class Program
{
private static List<byte[]> _buffers = new List<byte[]>();
@buybackoff
buybackoff / typescript.json
Created May 5, 2018 06:21
TypeScript snippets to shorten typing of const vs let by default
{
// Place your snippets for typescript here. Each snippet is defined under a snippet name and has a prefix, body and
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the
// same ids are connected.
// Example:
// "Print to console": {
// "prefix": "log",
// "body": [
// "console.log('$1');",
@buybackoff
buybackoff / sum.ts
Last active April 11, 2018 21:41
sum.ts
let sum = (x?: number) => {
// the trick is to access inner from inside itself as `any` with `.sum` initialized to 0
// we know that the reference will be initialized
// we could certainly achieve the same effect by using `this.`
// but scoping with `this` is not intuitive
let inner;
inner = (x1?: number) => {
// need additional check for 0, e.g. calling sum(0)(1)(0)() is valid, same below
if (x1 || x1 === 0) {
@buybackoff
buybackoff / GDAXWebSocketsConnection.cs
Last active December 7, 2017 15:57
GDAX WebSockets connection
using System.Net.WebSockets;
var wsc = new ClientWebSocket();
await wsc.ConnectAsync(new Uri("wss://ws-feed.gdax.com"), CancellationToken.None);
Console.WriteLine("Connected...");
var msg = @"{""type"": ""subscribe"", ""product_ids"": [""BTC-USD"", ""ETH-USD"", ""ETH-BTC""]}";
Console.WriteLine(msg);
await wsc.SendAsync(new ArraySegment<byte>(Encoding.UTF8.GetBytes(msg)), WebSocketMessageType.Text, true, CancellationToken.None);
var buffer = new ArraySegment<byte>(new byte[4096]);
while (true)
{
@buybackoff
buybackoff / RLSEF.R
Created December 9, 2016 16:46
Recursive Least Squares with Exponential Forgetting
RLSF <- function(y,x,alpha=0.95,ist=30,xpxi=NULL,xpy0=NULL)
{
# http://queue.acm.org/detail.cfm?id=2534976
if(!is.matrix(x))x=as.matrix(x)
nT=dim(x)[1]
k=dim(x)[2]
xpx0 = NULL
#
if(is.null(xpxi)){
if(ist <= k)ist=k+1