DEV Community: James Turner

Fixing my BF1942 woes with Win32 APIs

James Turner — Fri, 21 Jan 2022 03:40:44 +0000

Battlefield 1942 was one of a number of great games I played when I was growing up. I was first introduced to the game through a demo disc on a magazine - it was the expansion "Secret Weapons of WWII". I spent many hours playing that demo and eventually managed to snag the complete set of the game with both expansions. It was game that ran pretty well on old hardware and have a lot of fun memories playing it.

Jumping forward several years, I wanted to give the old game another play. I knew the graphics wouldn't hold up but to play in its nostalgic sandbox would more than overcome that. I installed the game and the various patches, modified configuration files to use my monitor's native resolution (1080p) and tried to launch it. Unfortunately, it wouldn't launch at all.

Some people online suggest it was issues with SecureROM as that no longer works with Windows 10 while others suggest it is an issue with Direct Play. What ultimately solved it for me was an unofficial patch by a group called Team Simple.

Now with the game launching, I start to hear the classic BF1942 main menu music. Sped through the profile setup, jumped to instant battle, picked my favourite level (Hellendoorn) and pressed start. The music changes to, in my opinion, an even more iconic piece when the level is loading. The progress bar moves maybe a quarter of the way and then... I'm back on my desktop.

After going back and forth with settings and the resolution changes I made, I found it just didn't want to work in full screen.

For the sharp-eyed individuals, you might notice that this is actually playing through Parsec - this is part of my vision for a remote desktop experience. It actually plays great (no noticeable input lag) via Parsec, over Wi-Fi, from my desktop to my laptop. That said, I did try the game directly on that machine and it still crashed so something else was to blame.

While I could play in window mode, I couldn't actually move the window so I could see the whole screen. Anytime I attempted to drag the window, it would just bring the cursor back in the game. Tried shortcuts to maximise the window but none of those worked either.

So what would any good programmer do? ~~Search for an existing solution online.~~ Write their own program to fix it!

Seemed like the fun thing to do anyway.

The Plan

This is what I wanted to do:

Get rid of the game's window border as it was just taking space
Position the window so it is centered to the monitor

The second point is important - the menu displays at 800x600 but the game when loading and playing is at whatever resolution I configured in window mode. My plan was to build a launcher that would bootstrap the main game.

I've messed around with removing borders from applications years back when I wanted to run a console application in the background. The way I achieved it back then was to invoke Win32 APIs from .NET and figured that would be a good starting place. My initial task was to find the APIs I need to use.

Fortunately someone already found the APIs to use to remove borders and reposition the window. My job then was to work out how to bring that into my application.

//A snippet of the code that helped me with the Win32 APIs from the Simple Runtime Window Editor (SRWE)
//Source: https://github.com/dtgDTGdtg/SRWE/blob/b439859e15ca44b6c4715fdb015c321a49ef634a/SRWE/Window.cs
public void RemoveBorders()
{
    uint nStyle = (uint)WinAPI.GetWindowLong(m_hWnd, WinAPI.GWL_STYLE);
    nStyle = (nStyle | (WinAPI.WS_THICKFRAME + WinAPI.WS_DLGFRAME + WinAPI.WS_BORDER)) ^ (WinAPI.WS_THICKFRAME + WinAPI.WS_DLGFRAME + WinAPI.WS_BORDER);
    WinAPI.SetWindowLong(m_hWnd, WinAPI.GWL_STYLE, nStyle);

    nStyle = (uint)WinAPI.GetWindowLong(m_hWnd, WinAPI.GWL_EXSTYLE);
    nStyle = (nStyle | (WinAPI.WS_EX_DLGMODALFRAME + WinAPI.WS_EX_WINDOWEDGE + WinAPI.WS_EX_CLIENTEDGE + WinAPI.WS_EX_STATICEDGE)) ^ (WinAPI.WS_EX_DLGMODALFRAME + WinAPI.WS_EX_WINDOWEDGE + WinAPI.WS_EX_CLIENTEDGE + WinAPI.WS_EX_STATICEDGE);
    WinAPI.SetWindowLong(m_hWnd, WinAPI.GWL_EXSTYLE, nStyle);

    uint uFlags = WinAPI.SWP_NOSIZE | WinAPI.SWP_NOMOVE | WinAPI.SWP_NOZORDER | WinAPI.SWP_NOACTIVATE | WinAPI.SWP_NOOWNERZORDER | WinAPI.SWP_NOSENDCHANGING | WinAPI.SWP_FRAMECHANGED;
    WinAPI.SetWindowPos(m_hWnd, 0, 0, 0, 0, 0, uFlags);
}

I put together bits and pieces from that codebase like the remove border and window positioning code and combined it with additional API calls for monitor information. I needed the following Win32 APIs to do everything I wanted:

GetWindowInfo (for the current window bounds)
MonitorFromWindow (getting the monitor handle the window is on)
GetMonitorInfoW (getting the monitor bounds)
SetWindowPos (setting the window position)
SendMessageW (to send WM_EXITSIZEMOVE to the window, a tip from SRWE - never checked if it was strictly necessary for BF1942 though)
GetWindowLongW (getting window settings)
SetWindowLongW (updating window settings)

After doing a rough integration with pieces from that codebase, I gave it a run and... my application crashed. I was using process.MainWindowHandle to get BF1942's game window. Turns out that it isn't set till, well, there is a main window available. So I wrote some code to wait for that and bingo - it launched the game and worked!

Well, it mostly worked - see BF1942 has an interesting quirk where it launches a new process when you end a match and go back to the main menu. This required me to write logic to track when processes changed while also still allowing it to exit when BF1942 is closed properly.

Improving the Win32 APIs

While my prototype worked, cobbled together from bits of SRWE and my own bits, I wasn't entirely happy with how I integrated the Win32 APIs. Below is the snippet of code I had that takes a window handle, gets the window's size, the monitor's size, calculates the position and finally sets it.

unsafe static void UpdateWindowPosition(int handle)
{
    var info = new WINDOWINFO();
    var success = WinAPI.GetWindowInfo(handle, ref info);
    if (success)
    {
        var windowDimensions = info.rcWindow;
        var monitorHandle = WinAPI.MonitorFromWindow(handle, 0);
        var monitorInfo = new LPMONITORINFO
        {
            cbSize = (uint)sizeof(LPMONITORINFO)
        };
        WinAPI.GetMonitorInfoA(monitorHandle, ref monitorInfo);
        var monitorDimensions = monitorInfo.rcMonitor;
        var x = monitorDimensions.Width / 2 - windowDimensions.Width / 2;
        var y = monitorDimensions.Height / 2 - windowDimensions.Height / 2;
        SetPosition(handle, x, y);
    }
}

static void SetPosition(int handle, int x, int y)
{
    uint uFlags = WinAPI.SWP_NOSIZE | WinAPI.SWP_NOZORDER | WinAPI.SWP_NOACTIVATE | WinAPI.SWP_NOOWNERZORDER | WinAPI.SWP_NOSENDCHANGING | WinAPI.SWP_FRAMECHANGED;
    WinAPI.SetWindowPos(handle, WinAPI.HWND_TOPMOST, x, y, 0, 0, uFlags);
    WinAPI.SendMessage(handle, WinAPI.WM_EXITSIZEMOVE, 0, 0);
}

What I would prefer is to actually have it feel more like a typical .NET API, something more like:

static void UpdateWindowPosition(Window window)
{
    var monitorBounds = window.GetCurrentMonitor().GetBounds();
    var windowBounds = window.GetBounds();
    var x = monitorBounds.Width / 2 - windowBounds.Width / 2;
    var y = monitorBounds.Height / 2 - windowBounds.Height / 2;
    window.SetPosition(x, y);
}

All I'm doing is abstracting away the Win32 APIs but it makes my "business logic" here far cleaner. While doing this, I also decided to remove the pieces of SRWE and replace it with a more maintainable interface to the APIs.

I tried out both TerraFX.Interop.Windows and CsWin32, ultimately settling on the latter. CsWin32 was a little less intimidating as the API is generated based on strings in a text file rather than containing everything at once. Also I like jumping to definition of types to read more and explore APIs etc and doing that to one of the types in the TerraFX library crashed Visual Studio. That's more of a VS problem than a TerraFX library but still - CsWin32 would work great for what I'm doing.

The way I went about achieving my desired interface to the Win32 APIs I needed was via creating record-struct wrappers around the various native handles and having instance methods wrap the API calls themselves. For example, below is my Window type that I have most of my functionality hanging off of.

public readonly record struct Window(nint Handle)
{
    private HWND Win32Handle => new(Handle);

    public Monitor GetCurrentMonitor()
    {
        nint handle = PInvoke.MonitorFromWindow(Win32Handle, 0);
        return new(handle);
    }

    public void SetPosition(int x, int y)
    {
        var flags = SET_WINDOW_POS_FLAGS.SWP_NOSIZE | SET_WINDOW_POS_FLAGS.SWP_NOZORDER | SET_WINDOW_POS_FLAGS.SWP_NOACTIVATE |
            SET_WINDOW_POS_FLAGS.SWP_NOOWNERZORDER | SET_WINDOW_POS_FLAGS.SWP_NOSENDCHANGING | SET_WINDOW_POS_FLAGS.SWP_FRAMECHANGED;
        PInvoke.SetWindowPos(Win32Handle, PInvoke.HWND_TOPMOST, x, y, 0, 0, flags);
        PInvoke.SendMessage(Win32Handle, PInvoke.WM_EXITSIZEMOVE, default, default);
    }

    public Rectangle GetBounds()
    {
        var windowInfo = new WINDOWINFO();
        PInvoke.GetWindowInfo(Win32Handle, ref windowInfo);
        return Rectangle.From(windowInfo.rcWindow);
    }

    public void RemoveBorders()
    {
        var style = PInvoke.GetWindowLong(Win32Handle, WINDOW_LONG_PTR_INDEX.GWL_STYLE);
        style &= ~(int)(WINDOW_STYLE.WS_THICKFRAME | WINDOW_STYLE.WS_DLGFRAME | WINDOW_STYLE.WS_BORDER);
        _ = PInvoke.SetWindowLong(Win32Handle, WINDOW_LONG_PTR_INDEX.GWL_STYLE, style);

        style = PInvoke.GetWindowLong(Win32Handle, WINDOW_LONG_PTR_INDEX.GWL_EXSTYLE);
        style &= ~(int)(WINDOW_EX_STYLE.WS_EX_DLGMODALFRAME | WINDOW_EX_STYLE.WS_EX_WINDOWEDGE | WINDOW_EX_STYLE.WS_EX_CLIENTEDGE | WINDOW_EX_STYLE.WS_EX_STATICEDGE);
        _ = PInvoke.SetWindowLong(Win32Handle, WINDOW_LONG_PTR_INDEX.GWL_EXSTYLE, style);
        PInvoke.SendMessage(Win32Handle, PInvoke.WM_EXITSIZEMOVE, default, default);
    }
}

The End Result

I called my project Borderless 1942 and is available on GitHub. It is a self-contained, single-file .NET 6 application. Because it is self-contained, you don't need .NET 6 installed to run it.

I'm quite happy that I got this working and could enjoy the game again. In terms of the code, the main thing I'd want to change is to move from a constant loop resetting the window position to something that listens on window resize events. This is possible via the Win32 APIs but has its own complications which I haven't got around to addressing yet.

I'm also looking at turning the style of wrapper I wrote into a dedicated library. There seems to be some interest in improved access to the Win32 APIs. I don't know how far I'd go with it (what Win32 APIs I'd support) but I think it could make this a lot easier for developers in certain situations.

Fun with Flags, Enums and Bit Shifting

James Turner — Wed, 08 Dec 2021 06:49:01 +0000

While thinking of posts to write about, the title "Fun with Flags" came to mind from a certain TV show and I wondered how I might connect that to programming. There are enum flags in C# via the Flags attribute so maybe that was something I could write about. That said, I wanted to do something more creative than some humdrum post about using enums even if the end result isn't really practical.

Instead I decided to make real flags in C# with enums - turning a number like 52357729848 into a flag:

A gave myself certain requirements:

I needed to be able to generate more than one flag
I wanted to encode everything about the flag in a single value via enums

There are technical limitations too as I can't store a lot of data in an enum and will need to make compromises. An enum can be backed by a few different types but I chose long so I could get a full 64-bits of data to play with.

Encoding a Value

My initial thought with this was to pick the easiest form of flag - simple flags with stripes. If I split a typical flag into 9 segments, maybe I can store 9 colours and that would allow drawing of horizontal and vertical stripes. It seemed like the most straightforward approach at the time (I realised later it might have been better if I stored "shape" data instead for more flag variety but oh well).

The problem is, storing 9 segments in 64 bits is pretty hard and would leave me with about 7.11-bits per segment making colour data very limited. I wanted 3 colour channels so that only gives me really 2-bits per colour which is not a lot of variety. Having then 6-bits per segment, it left me with 10-bits that I don't really have much use for. Initially I tried using those bits to help extend the range of colours, acting as a multiplier for a specific channel. In the end though, it wasn't overly useful for this so I cut it.

This is the data structure I ended with:

[PPPPPPPPPP]
[RRGGBB][RRGGBB][RRGGBB]
[RRGGBB][RRGGBB][RRGGBB]
[RRGGBB][RRGGBB][RRGGBB]

P = Padding
R = Red Intensity
G = Green Intensity
B = Blue Intensity

My primary data only takes 54-bits so my data structure has 10-bits of padding at the front. Having the padding at the front allows the generated number to be smaller.

I will be using ImageSharp for converting this value into an actual image. Because I have 9 segments, it seemed like the best idea to treat the image as a 3x3 pixel square and get ImageSharp to resize it for me. The pixel format for the data though was RGB24 so I needed to work out how to scale up my colours from 2-bits to 8-bits per channel.

With 8-bits, the max value I can have is 255 for a single channel.
Full colour intensity for any channel is 3 so I decided to simply divide the max value by the full colour intensity leaving me the magic number of 85 to scale my values by.

That is the nuts-and-bolts of the format, now it was just to make that work in code.

A Bit Shifty

Knowing I can store the data is one thing, actually making it work was another. I don't often use bitwise and shift operators but for this, it was going to use them quite heavily.

Firstly, we need an enum of colour intensity values:

public enum Intensity : byte
{
    None = 0,
    OneThird = 1,
    TwoThirds = 2,
    Max = 3
}

The specific values here are important because of what they represent in binary.

00000000 // Intensity.None
00000001 // Intensity.OneThird
00000010 // Intensity.TwoThirds
00000011 // Intensity.Max

Because these values represent a single channel's intensity, we need to combine 3 of them together to form our full colour. We combine them by using bit shifting and bitwise OR operations to create our 6-bit colour value.

public enum Colour : long
{
    Black = 0,
    Red = Intensity.Max << 4,
    Green = Intensity.Max << 2,
    Blue = Intensity.Max,
    White = Red | Green | Blue
}

While we are using a long here (helping us with our later bit shifting operations), the values we are setting fit within 6-bits. Viewing the colours as bytes in binary, the shifting and OR-ing of data would look a little like this:

00110000 // Red = Intensity.Max << 4
00001100 // Green = Intensity.Max << 2
00000011 // Blue = Intensity.Max
00111111 // White = Red | Green | Blue

Using different intensity values for the different colour channels, we can create new colours too.

00110000 // Red = Intensity.Max << 4
00001000 // Green = Intensity.TwoThirds << 2
00000000 // Blue = Intensity.None
========
00111000 // Yellow = (Intensity.Max << 4) | (Intensity.TwoThirds << 2)

To create a few different types of flags, we will need a few more colours...

public enum Colour : long
{
    Black = 0,
    Red = Intensity.Max << 4,
    Green = Intensity.Max << 2,
    Blue = Intensity.Max,
    White = Red | Green | Blue,
    Orange = (Intensity.Max << 4) |
        (Intensity.OneThird << 2),
    Yellow = (Intensity.Max << 4) |
        (Intensity.TwoThirds << 2),
    MediumGreen = Intensity.TwoThirds << 2,
    LightBlue = (Intensity.TwoThirds << 2) |
        Intensity.Max,
    DarkBlue = Intensity.OneThird
}

Identifying the right combinations of values for colours was relatively straight forward - I used an RGB colour picker in Paint.NET and selected thirds of the different colour channels. Like if I had two thirds red and one third green, I'd approximately have orange.

So now we've got our colours, we need to encode the final value of a flag. In a similar approach to combining the colour channels, we need to combine the colours of the 9 segments by shifting and OR-ing.

public enum CountryFlags : long
{
    Germany = Colour.Black << 48 | Colour.Black << 42 | Colour.Black << 36 |
        Colour.Red << 30 | Colour.Red << 24 | Colour.Red << 18 |
        Colour.Yellow << 12 | Colour.Yellow << 6 | Colour.Yellow
}

While Colour.Black does encode as 0 so the first 3 values aren't actually needed, it made it easier to still think of it as 9 distinct segments that all needed colours set.

In binary, the operation to encode our German flag would look like:

        00000000 // Black, shifted by 48-bits
              00000000
                    00000000
                          00110000 // Red, shifted by 30-bits
                                00110000
                                      00110000
                                            00111000 // Yellow, shifted by 12-bits
                                                  00111000
                                                        00111000
================================================================
0000000000000000000000000000110000110000110000111000111000111000

As a decimal, that would be 52357729848. This is only half the job though, we have our flag data as number but we also need to decode it to an image.

Generating an Image

So how do we take 52357729848 and turn it into an image? We use more bit shifting and now AND-ing of our data to get each individual colour. Also, we will be reading the data in reverse.

var blueComponent = (byte)(flagData & 3) * 85;

The value flagData here is a long of our generated number.

To get the blue component, we don't need to shift but we do need to perform a logical AND of the data. We only want the last two bits of the number - if we just convert the number to a byte, we will get the last 8-bits.

0000000000000000000000000000110000110000110000111000111000111000
                                    // We only want this part ^^

By doing flagData & 3, we get just the last 2-bits from the full value. To get the next components, we do the same but now on a bit shifted value so the last 2-bits are of the colour we want.

var greenComponent = (byte)((flagData >> 2) & 3) * 85;
var redComponent = (byte)((flagData >> 4) & 3) * 85;

Now we have the 3 colour channels of the bottom right segment of our flag. As a reminder, the 85x multiplier is to adjust the colour to fit within a full 8-bits for the RGB24 pixel format. Really now, it is just a matter of wrapping the code within some loops to set it to an image.

using var image = new Image<Rgb24>(3, 3);
for (var y = 2; y >= 0; --y)
{
    for (var x = 2; x >= 0; --x)
    {
        var pixel = image[x, y];
        var blueComponent = (byte)((flagData >> 0) & 3) * 85;
        pixel.B = (byte)blueComponent;
        var greenComponent = (byte)((flagData >> 2) & 3) * 85;
        pixel.G = (byte)greenComponent;
        var redComponent = (byte)((flagData >> 4) & 3) * 85;
        pixel.R = (byte)redComponent;
        flagData >>= 6;
        image[x, y] = pixel;
    }
}

In our inner-most loop, we also shift our bits in flagData over 6-bits so we are in the next segment for the next iteration. This code though would only leave us with a 3x3 flag which doesn't look right so with a little more code, we can make it be bigger and more flag-like.

image.Mutate(x => x.Resize(400, 240, new NearestNeighborResampler()));

The NearestNeighborResampler here is important - it allows us to scale up our specific "blocky" image here without distorting or blurring it.

And that's basically it - we can take a bunch of enums and encode a value then take the value and decode it to an image. I've set up an Azure Function running this code to show it working and few flags I've generated:

https://funwithflags.turnerj.com/api/flag/generate.png?v=ENCODED_VALUE

Germany

Value: 52357729848

Germany = Colour.Black << 48 | Colour.Black << 42 | Colour.Black << 36 |
    Colour.Red << 30 | Colour.Red << 24 | Colour.Red << 18 |
    Colour.Yellow << 12 | Colour.Yellow << 6 | Colour.Yellow,

Italy

Value: 2532184938287088

Italy = Colour.MediumGreen << 48 | Colour.White << 42 | Colour.Red << 36 |
    Colour.MediumGreen << 30 | Colour.White << 24 | Colour.Red << 18 |
    Colour.MediumGreen << 12 | Colour.White << 6 | Colour.Red,

France

Value: 561852585091056

France = Colour.DarkBlue << 48 | Colour.White << 42 | Colour.Red << 36 |
    Colour.DarkBlue << 30 | Colour.White << 24 | Colour.Red << 18 |
    Colour.DarkBlue << 12 | Colour.White << 6 | Colour.Red,

Ireland

Value: 2532459817242612

Ireland = Colour.MediumGreen << 48 | Colour.White << 42 | Colour.Orange << 36 |
    Colour.MediumGreen << 30 | Colour.White << 24 | Colour.Orange << 18 |
    Colour.MediumGreen << 12 | Colour.White << 6 | Colour.Orange,

Luxembourg

Value: 13725272368788171

Luxembourg = Colour.Red << 48 | Colour.Red << 42 | Colour.Red << 36 |
    Colour.White << 30 | Colour.White << 24 | Colour.White << 18 |
    Colour.LightBlue << 12 | Colour.LightBlue << 6 | Colour.LightBlue,

Final Thoughts

What started out as a bit of a weird challenge I set myself turned into a fun and interesting learning experience. I rarely mess around with bit shifting and bitwise operations. While I still probably won't need to very often, I like that I know a lot more about them now.

If I were to approach this again, I'd probably look at encoding shapes instead of pixels of colours. That way I could encode a wider variety of flags like the flags of Sweden, Japan and perhaps even South Korea.

If you liked this...

If you liked the kinda strange and interesting nature of this, you might like my deep dive into Levenshtein Distance and the various optimizations.

Remote Desktop Experience (Part 1: Planning)

James Turner — Sat, 30 Oct 2021 14:09:46 +0000

I've had both a laptop and a desktop for several years. My desktop was my primary machine for work and play where my laptop was rarely used. Since leaving my previous job, I have been nearly entirely using my laptop to do work, leaving my desktop only for gaming. While I had a multi-monitor setup, I've found that I don't miss that but I do miss the performance. The work I do isn't usually too taxing for my laptop but the performance is thermally limited.

Both machines though are a few years old, both running Skylake processors so neither meet the minimum Windows 11 CPU requirements. I know there are still a few years of support for Windows 10 so that isn't a big issue, just something that I'm factoring into my planning. Anyway, neither machine is a slouch for what I do but thinking for the future and how I want to work, I need to plan the upgrade path for these machines.

I also have a small HP ProLiant MicroServer Gen8 that I got from working overtime at my old job, acting as a NAS for my home network. It holds my documents, photos, backup of my Steam library, runs a Plex server, a VM for Pi-hole, a VM for a local build server, a VM for Minecraft and a VM for Factorio. While I don't run all the VMs at once, it still isn't the most powerful machine even with an upgraded CPU and maxed out at 16 GB of RAM. In its 4 drive bays, I have one SSD for the host OS and 3 HDDs that split the rest of the data (no RAID). It has worked hard for many years but I'm starting to outgrow it so I want to plan its upgrade path too.

Current Machine Specs

	Desktop	Laptop	Server
CPU	i5-6600K (4C/4T)	i7-6700HQ (4C/8T)	Xeon E3-1230 V2 (4C/8T)
RAM	16 GB	16 GB	16 GB
GPU	GTX 970 4 GB	GTX 960M 4 GB	Matrox MGA-G200eH

These are the types of things I need to consider:

I don't have the budget to upgrade 3 machines - really only the budget to upgrade 1 really well, or maybe 2 pretty well.
While gaming is primarily on my desktop, I do play some games (FPS, RTS, Turn-based strategy) on my laptop when not at home.
For the NAS, I'd like more drive bays so I can have SSDs for the VMs and a HDD RAID for the personal files.
Depending how high-end I want to go, I may be able to re-use the desktop's GPU.

Potential 3-in-1 Solution

I've chatted with a friend of mine about upgrading my server and he was talking about his ideal setup. Instead of having a desktop and a server, he was going to run his desktop on his server which is a pretty clever idea. I was thinking how I could extend that to my setup and also improve working on my laptop and it hit me - why don't I also run my laptop's "desktop" on the server?

How would I do this though? Well, I was thinking about using Parsec. Effectively, I'd be remote connecting to a local server running my desktop for my laptop. My laptop and desktop machines would be thin clients for the powerful server.

Here are some of the benefits for doing this:

Would only need to upgrade one machine (the server) so I can save money and/or afford more powerful parts.
Laptop wouldn't need to worry about thermal constraints for work.
I could expand the storage space, greatly improve the CPU and massively increase the RAM.
If anything happened to my laptop (it dies or is stolen), all my important files are securely stored.
I could effectively work from anywhere while having potentially better battery life too.

There are some problems:

Gaming on my desktop will have more lag than current - maybe not noticeable but still more lag than none.
Gaming on my laptop gets more complicated as some games connect via LAN so having a remote desktop doesn't help - the laptop still needs to be fast enough to play games.
If I am working from anywhere, I'd still need a pretty good internet connection as it would be a streaming-heavy setup with Parsec.

Other concerns:

I run my server 24/7 so power usage is a concern - the existing server is quite power efficient.

At some point in the future, I will still need to upgrade the desktop and laptop machines. If the gaming side for the desktop machine through the server is fine, I might be able to get away with something as simple as a Raspberry Pi. For a future laptop, while I still want some gaming performance, I'd mainly be looking for a lightweight laptop with great battery life and probably USB-C power.

Renting-vs-Buying

Now there is another option that is possible - I could just rent a dedicated server somewhere and run everything there. That definitely is possible and would be lower the upfront cost, potentially help with backups and likely have faster internet. However, I don't like the idea that everything important to me would be hosted by someone else. Not to mention that buying the equipment means I can potentially flip the parts later if I need to upgrade down the road.

Also if I'm doing a lot of work still at home via my laptop, it seems a little redundant going outside my local network to connect to my remote desktop where instead I could just run it at home.

Secondary Goals

While the primary goals are to have a remote desktop, I do have a few secondary goals I'd like to achieve too...

Scriptable OS Install and Configuration

I like the idea of scripting an OS install/configuration. I've wanted to do this for a while and I know it may not seem necessary when I have a remote desktop setup but I still see some utility in it. The idea is using something like Chocolatey and a Powershell script to install all the software I want and configure it up just how I like it.

I see this still being useful because my laptop will still need an OS of some sort and some basic programs. Plus it allows me to tear down the VM that powers my remote desktop and rebuild it far easier - great if I screw something up.

Ultimately even if a remote desktop experience for my work isn't right, having an auto-setup script would help with clean re-installs and device upgrades. Other people have got basic scripts that do things like this for Windows already but often are limited to installing programs rather than configuring the OS.

Better Backups

Currently I backup my files onto a separate external drive but I am wanting to have a low-cost method for remote backup. I've looked at Backblaze but am also considering other options like storing my current/existing server at a friend's house and using it as a remote backup. If not the whole server, maybe we put space aside on eachother's servers to just run a backup VM for the other.

Either way, I'd like to improve my current system to make sure my data is more secure.

Testing and Next Steps

Stage 1A

Without splashing money on any new hardware straight away, I figure I should try and test this with what I've got currently.

Setup my current/old desktop machine with all the typical tools I use on my laptop.
Install Parsec on my desktop and laptop, treating my desktop machine as my remote desktop for my laptop.
Try working via Parsec for a week and note down any new pros/cons I find.
Additionally try some basic gaming via Parsec from my desktop machine to my laptop.

Stage 1B

Simultaneously I can also look at my secondary goals...

Identifying what programs and configuration I want to script.
Test out the script in a VM that I can easily reset and try again.

Stage 2

Assuming no major issues with testing Parsec for my work (Stage 1A)...

Put together a parts list for my ideal server - I'm thinking something with a lot of cores.
Cut that parts list down to something actually realistic. 😢
Save up money to buy any of those parts (something something supply chain issues).
Buy the parts, build the server.

Stage 3

Once I have the new server built (Stage 2) and my auto-setup script ready (Stage 1B)...

Setup a new VM on the new server for my remote desktop.
Run my new auto-setup script for configuring the OS.
Connect to it via Parsec and start giving my remote desktop experience a real try on the final hardware.

Stage 4

Assuming I'm happy with everything with Stage 3...

Do a clean install of Windows on my laptop to get rid of the tools I no longer use - at this point I'm fully committing to the change for work.
Try gaming from my desktop machine to my remote desktop, testing the performance/lag and see how happy I am with it.
If I'm happy with how gaming works, wipe my desktop and commit to the same change like my laptop.

Let's do this thing!

There is a lot to do between now and having my ideal setup. Those stages also hide a lot of complexity so it won't be a fast process to go from where I am now to a fully remote desktop experience. Ultimately though, I'm pretty excited to get started with this and looking forward to a powerful desktop experience wherever I am.

What is Structured Data?

James Turner — Fri, 29 Oct 2021 10:03:47 +0000

Structured data is data that is structured - that is perhaps the most succinct summary of it without telling you anything you didn't already expect. To take away something more than that, it can be useful to break down what structured data can look like.

When we say a set of data is structured, it has properties and values that hold a specific meaning. One value might represent some amount of money, another value might represent a date, and a third might be an address. When labelled appropriately, these values can then represent a greater context - perhaps they represent details on an invoice or payslip.

{
  "amount": 20.00,
  "datePaid": "2017-08-12T12:56:00",
  "address": "123 Example Street, Some Suburb, Some City"
}

This data could be in a database, a spreadsheet, a JSON blob - it doesn't matter. If there is data and a defined data model, that is structured data. When data is structured well, it makes it easier to query, process and generally use the data.

In contrast, there is also unstructured data. The value for our address property in the example above is itself unstructured data.

123 Example Street, Some Suburb, Some City

That single value has multiple internal components we would need to parse out depending what we are wanting to do. If we wanted to group all the records on the same street, we'd need to carefully parse the street, suburb and city out of our data. Different countries can have different formats and rules for addresses it is hard to process. Making the wrong assumption when parsing the data can lead to irregularities in the data, causing problems for whatever we wanted to consume that data. For instance, depending where you are in the world, can you assume all streets even have names?

While structured data can definitely be easier to work with, it doesn't make unstructured data useless. Instead, think of unstructured data as untapped potential - useful data exists but is difficult to get to.

Structured Data and Web Pages

Web pages are an interesting example of both structured and unstructured data. There are specific elements one could look at for certain information like the <title> element or other semantic elements like <article> or <section>. The problem though is that these elements are more like our "address" example earlier - they often contain more than just the strict data we are looking for. A title might have a prefix or suffix of the website's name. An article or section might have many other layers of <div>, <span> or any other elements to help form the site's structure. To top it off, the HTML structure can vary wildly from site to site. If you were wanting to extract data from multiple websites, it can get very hard very fast.

That said, there are a number of ways to embed structured data into web pages. A web page could use Microdata, RDFa, JSON-LD or Open Graph to express structured data. More than that though, a web page can use multiple of these at the same time. Open Graph is commonly used as a method of defining details for a link preview while the others might express more complex data like product pricing or reviews.

Having standard formats like Microdata or JSON-LD are a good start but only represent the format of the data - we need a common vocabulary so we can understand the data those formats encode. One common vocabulary used is called Schema.org and provides over 700 types including types to describe people, places, products, recipes, reviews, vehicles, movies and medical devices. Using Schema.org for structured data on a website can help search engines provide richer experiences in the search results.

Summary

Structured data, through standardising expected properties and value formats, makes the sharing and processing of data easier. Web pages in particular benefit from encoding structured data in their mark-up where it can be used by search engines and other tools.

The pain points of C# source generators

James Turner — Wed, 07 Apr 2021 07:37:38 +0000

I've recently completed my first foray into writing a C# source generator for Schema.NET. There is a lot to like about source generators however there are a few things I wish I understood more before diving into it.

For those that are unaware, source generators are a new feature added to C# whereby one can analyse existing source code and generate new source code all from C# itself. One area where this is of interest is serialization - being able to generate an ideal serializer at compile time prevents the need of using reflection at runtime.

In Schema.NET, we had hundreds of classes and interfaces that mapped to Schema.org types. While we had our own tool to generate these, the generated files sat in our Git repository creating a lot of noise when trying to change our tooling behaviour. Source generators would allow us to remove these files and have them exist only as part of the compiled binary. The move to source generators was also a good time to refactor the generating logic itself, making it easier to add new features later.

Pain Point 1: Debugging Source Generators

Honestly I expected the debugging process to be:

Put a breakpoint in the source generator code
Press the "Debug" button in Visual Studio
Code stops at the breakpoint

Unfortunately, it isn't that simple. The source generator runs during compilation however the debugging experience starts after meaning our break point would never be hit. After some research, it seems there are two different methods suggested.

Invoke the debugger from the source generator

Found this solution from Nick's .NET Travels. Inside our source generator, likely in the "Initialize" method, we can invoke the debugger to attach to the current process with the following:

#if DEBUG
if (!Debugger.IsAttached)
{
    Debugger.Launch();
}
#endif

What we are doing here is using the preprocessor directive #if to conditionally include this code if the build configuration is "Debug". When we are in the "Debug" configuration, we check if the debugger is already attached and if not, attach it via Debugger.Launch(). After the debugger launches, it comes up with a prompt about where to debug it (I chose a new instance of Visual Studio). From here, the code will be paused on the Debugger.Launch() line and this new instance of Visual Studio will listen for any breakpoints you may add.

I probably spent a good few hours using this method and while it works, it is not a great experience. For starters, the prompt I mention, it was appearing multiple times during a debugging session. I'm not sure if the issue related to different target frameworks building simultaneously or maybe some timeout logic being handled by the build process. Additionally I had Visual Studio crash a few times in either instance of Visual Studio I had open.

Don't take my word for it, others have had similar difficulties.

Run the source generator manually

A source generator itself is effectively like any other class - we can instantiate and call the initialization methods ourselves.
There is a detailed document in the Roslyn repo that covers all sorts of things with regards to source generators. One of the sections specifically covers testing source generators.

Here is a modified version of their example that shows the general gist:

Compilation inputCompilation = CreateCompilation(@"
namespace MyCode
{
    public class Program
    {
        public static void Main(string[] args)
        {
        }
    }
}
");

CustomGenerator generator = new CustomGenerator();

// Create the driver that will control the generation, passing in our generator
GeneratorDriver driver = CSharpGeneratorDriver.Create(generator);

// Run the generation pass
driver.RunGeneratorsAndUpdateCompilation(inputCompilation, out var outputCompilation, out var diagnostics);

static Compilation CreateCompilation(string source)
    => CSharpCompilation.Create("compilation",
        new[] { CSharpSyntaxTree.ParseText(source) },
        new[] { MetadataReference.CreateFromFile(typeof(Binder).GetTypeInfo().Assembly.Location) },
        new CSharpCompilationOptions(OutputKind.ConsoleApplication));

Basically this creates a compilation that the source generator can run against. This method can be quite verbose as, depending on your source generator itself, you may require a lot of boilerplate source code for your generator to work upon.

In my case with Schema.NET, I'm generating hundreds of classes based on some JSON so I have minimal boilerplate. I could have gone this route however I decided on a more direct approach:

var generator = new SchemaSourceGenerator();
generator.Initialize(new Microsoft.CodeAnalysis.GeneratorInitializationContext());
generator.Execute(new Microsoft.CodeAnalysis.GeneratorExecutionContext());

My generator didn't care about any existing syntax tree - its job was to just pump out new classes and interfaces.
This method does have a bit of a fatal flaw in that calling most (any?) of the methods on GeneratorInitializationContext or GeneratorExecutionContext may fail. These types are not instantiated with their different properties correctly configured which is something that more verbose way above did. For my SchemaSourceGenerator, I needed to comment out context.AddSource(sourceName, sourceText) so it wouldn't throw an exception.

My recommendation is for anyone working on a source generator, either have a separate console application to debug your source generator or create a special unit test. Do it properly though and have the more verbose compilation code as shown in the earlier example so you don't need to modify your source generator to run it.

Pain Point 2: No Async/Await

The methods exposed by source generators (Initialize and Execute) do not return tasks so you can't invoke async APIs.
According to the Roslyn team this is by design as the IO for reading/writing files is handled by the compiler.

For Schema.NET, we do a HTTP request to get the JSON we need to build. There are reasons this isn't a good idea but this is what we do and it works well for us. The HttpClient has only had async APIs for a long while and while that is changing, source generators must target .NET Standard 2.0 so we can't leverage that change.

My first iteration of getting the source generator to work was effectively wrapping my code in a Task.Run() call:

public void Initialize(GeneratorInitializationContext context) => Task.Run(async () =>
{
    ...

    SchemaObjects = await schemaService.GetObjectsAsync();
}).GetAwaiter().GetResult();

This admittedly did work but I really didn't like it - it felt like such a kludge solution. There is a lot of information available about when and where you should be using Task.Run() - Stephen Cleary has a good blog post or two about it.
While a source generator is likely a new special case where it depends, I still decided to change it. I ended up with calling .GetAwaiter().GetResult() directly on the method of mine that was async instead.

public void Initialize(GeneratorInitializationContext context)
{
    ...

    SchemaObjects = schemaService.GetObjectsAsync().GetAwaiter().GetResult();
}

I'll be honest - I don't know if this is technically better in this scenario but I know it works.

Pain Point 3: Transient Dependencies

An issue with dependencies was something I wasn't expecting at all when I started with my source generator - why should it be?
Every other library and application I've written in C# in the last few years follows a fairly predictable pattern of using a <PackageReference> to define which package and version. The basics of including a package reference like that for source generators is still the same, it is just all the other bits it now also requires.

For Schema.NET, our source generator was parsing JSON so we needed a serializer. We were previously using Newtonsoft.Json for our tool however in this refactor, we were also moving to using System.Text.Json for the parsing of the initial schema data from Schema.org. This dependency needs to only exist for the generator, not the library the generator is creating classes etc for. Normally you can just specify PrivateAssets="all" on the package reference and that's it but for source generators, you need to specify a few more things:

<ItemGroup>
    <PackageReference Include="System.Text.Json" Version="5.0.1" GeneratePathProperty="true" PrivateAssets="all" />
</ItemGroup>

<PropertyGroup>
    <GetTargetPathDependsOn>$(GetTargetPathDependsOn);GetDependencyTargetPaths</GetTargetPathDependsOn>
</PropertyGroup>

<Target Name="GetDependencyTargetPaths">
    <ItemGroup>
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Text_Json)\lib\netstandard2.0\System.Text.Json.dll" IncludeRuntimeDependency="false" />
    </ItemGroup>
</Target>

Not too bad right? Well, what if I told you that you needed to do this for all dependencies. By that I mean every dependency in the dependency tree which for us was:

Microsoft.Bcl.AsyncInterfaces, 5.0.0
System.Buffers, 4.5.1
System.Memory, 4.5.4
- System.Numerics.Vectors, 4.4.0
System.Numerics.Vectors, 4.5.0
System.Runtime.CompilerServices.Unsafe, 5.0.0
System.Text.Encodings.Web, 5.0.0
System.Threading.Tasks.Extensions, 4.5.4

Our example would look more like:

<ItemGroup>
    <PackageReference Include="System.Text.Json" Version="5.0.1" GeneratePathProperty="true" PrivateAssets="all" />
    <PackageReference Include="Microsoft.Bcl.AsyncInterfaces" Version="5.0.0" GeneratePathProperty="true" PrivateAssets="all" />
    <PackageReference Include="System.Runtime.CompilerServices.Unsafe" Version="5.0.0" GeneratePathProperty="true" PrivateAssets="all" />
    <PackageReference Include="System.Threading.Tasks.Extensions" Version="4.5.4" GeneratePathProperty="true" PrivateAssets="all" />
    <PackageReference Include="System.Text.Encodings.Web" Version="5.0.1" GeneratePathProperty="true" PrivateAssets="all" />
    <PackageReference Include="System.Buffers" Version="4.5.1" GeneratePathProperty="true" PrivateAssets="all" />
    <PackageReference Include="System.Memory" Version="4.5.4" GeneratePathProperty="true" PrivateAssets="all" />
    <PackageReference Include="System.Numerics.Vectors" Version="4.4.0" GeneratePathProperty="true" PrivateAssets="all" />
</ItemGroup>

<PropertyGroup>
    <GetTargetPathDependsOn>$(GetTargetPathDependsOn);GetDependencyTargetPaths</GetTargetPathDependsOn>
</PropertyGroup>

<Target Name="GetDependencyTargetPaths">
    <ItemGroup>
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Text_Json)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
        <TargetPathWithTargetPlatformMoniker Include="$(PKGMicrosoft_Bcl_AsyncInterfaces)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Runtime_CompilerServices_Unsafe)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Threading_Tasks_Extensions)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Buffers)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Memory)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Numerics_Vectors)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
        <TargetPathWithTargetPlatformMoniker Include="$(PKGSystem_Text_Encodings_Web)\lib\netstandard2.0\*.dll" IncludeRuntimeDependency="false" />
    </ItemGroup>
</Target>

If any of these dependencies pick up any new dependencies themselves, they need to be included too - this can happen with patch version changes like between System.Text.Encodings.Web going from 5.0.0 to 5.0.1 where it picked up a few new dependencies.

Currently for Schema.NET, I'm only specifying System.Text.Json and System.Text.Encodings.Web directly which allows our builds to work on our CI but Visual Studio complains during the build.
I raised an issue with the Roslyn team about this extra weird behaviour though it seems to amount for a difference between builds triggered by .NET Framework (Visual Studio and MSBuild) and .NET Core (dotnet build).

My biggest gripe here though is: Why doesn't the compiler just do this for us?

The compiler knows all our dependencies so with some sort of flag to indicate that this is a source generator, the compiler should do all this work for us. The burden to make sure we keep track of all transient dependencies when any dependency gets an update is something I don't want to do.

Potential Transient Dependency Workaround

While not a perfect solution, if you are like me and really don't like specifying every package reference in the dependency tree like that, you can automate it somewhat with a custom MSBuild target.

<ItemGroup>
    <PackageReference Include="System.Text.Json" Version="5.0.1" PrivateAssets="all" />
</ItemGroup>

<PropertyGroup>
    <GetTargetPathDependsOn>$(GetTargetPathDependsOn);GetDependencyTargetPaths</GetTargetPathDependsOn>
</PropertyGroup>

<Target Name="GetDependencyTargetPaths" AfterTargets="ResolvePackageDependenciesForBuild">
    <ItemGroup>
        <TargetPathWithTargetPlatformMoniker Include="@(ResolvedCompileFileDefinitions)" IncludeRuntimeDependency="false" />
    </ItemGroup>
</Target>

This "works" in the sense that ResolveCompileFileDefinitions does contain a list of our transient dependencies so everything that needs to be passed in is passed in. The problem with this solution is that ResolveCompileFileDefinitions contains more than the specific dependencies we are wanting and could have undesired behaviour.

Ideally I'd like something like this to be an automatic target for source generator projects but perfected to target only private dependencies so they are bundled correctly.

Conclusion: Was migrating to source generators worth it?

Yes.

Switching to source generators, combined with my refactor, added 700 lines of code while removing 69,203 lines of code. My pull request affected 765 files, the vast majority being generated classes and interfaces that no longer need to sit in the repository.

The refactor of our generation code also sets us up nicely for the future where we can support pending Schema.org types (something that has been requested by a few people).

While these pain points are annoying, source generators are a great feature that I hope getting tool updates to improve the developer experience.

What is Microdata?

James Turner — Sun, 20 Sep 2020 12:09:42 +0000

Microdata is a HTML standard, created by WHATWG, for describing rich metadata in web pages. This rich metadata can be used by search engines or other computer systems to better understand the content of the web page.

Microdata is made of up a number of attributes including itemscope, itemprop and itemtype. Below is an example of a basic web page using Microdata.

<html>
  <head>
    <title>What is Microdata?</title>
  </head>
  <body itemscope itemtype="https://schema.org/WebPage">
    <article itemscope itemtype="http://schema.org/Article" itemprop="mainEntity">
      <meta itemprop="url" content="https://brandvantage.co/blog/what-is-microdata">
      <meta itemprop="image" content="https://brandvantage.co/blog/2020/images/what-is-microdata-cover.png">
      <h1 itemprop="name headline">What is Microdata?</h1>
      <time itemprop="datePublished" datetime="2020-09-20">20th of September, 2020</time>
      <div itemprop="articleBody">
        Hello and welcome to this example!
      </div>
    </article>
  </body>
</html>

The "itemprop" Attribute

The itemprop attribute defines a name-value pair for data. The value associated to the property can be derived from:

The inner text content of the tag
The content attribute (if defined)
The src attribute (for img, audio, video, iframe etc tags)
The href attribute (for link or a tags)
The value attribute (for data or meter tags)
The datetime attribute (for time tags)

An item property can also contain a group of name-value pairs through the use of the itemscope attribute. Additionally, the value on the itemprop attribute may refer to multiple properties.

You can see a number of different examples of itemprop in the previous example.

Grouping Properties Together

<article itemscope itemtype="http://schema.org/Article" itemprop="mainEntity">

With the use of itemscope attribute here, the "mainEntity" property is grouping other name-value pairs together.

Value from a "content" Attribute

<meta itemprop="url" content="https://brandvantage.co/blog/what-is-microdata">
<meta itemprop="image" content="https://brandvantage.co/blog/2020/images/what-is-microdata-cover.png">

Here we have two properties ("url" and "image") with their values defined from the content attribute.

Setting Two Properties at Once

<h1 itemprop="name headline">What is Microdata?</h1>

The itemprop here is setting two properties at once ("name" and "headline") with the value from the inner text.

Value from a "datetime" Attribute

<time itemprop="datePublished" datetime="2020-09-20">20th of September, 2020</time>

The "datePublished" property uses the time tag with the datetime attribute. The date is formatted as an ISO 8601 date.

Value from Inner Text

<div itemprop="articleBody">
    Hello and welcome to this example!
</div>

The "articleBody" property uses the inner content for its value.

The "itemtype" Attribute

While itemprop helps set the values of properties, without a method to define what properties to expect, the usefulness can be called into question. This is where itemtype comes in, giving context to the properties used through a URL which identifies the vocabularly.

One common vocabularly to use is Schema.org, a joint venture between Google, Microsoft, Yahoo and Yandex. A shared vocabularly like Schema.org makes interoperability easier for third parties who want or need to use the data. This being said, there is nothing stopping you from using other vocabularies or even making your own. If a third party doesn't understand your vocabularly, your metadata may not be processed and used.

In the previous example, there were two uses of itemtype:

  <body itemscope itemtype="https://schema.org/WebPage">
    <article itemscope itemtype="http://schema.org/Article" itemprop="mainEntity">

The first is defining the scope as a WebPage schema object which has a number of useful properties including "breadcrumb" and "significantLink". In the Schema.org vocabularly, a WebPage extends CreativeWork which has a property "mainEntity". This property can be any Thing, the base type in the Schema.org vocabularly.

Now for the "mainEntity" property, we are defining the type to be an Article schema object for the scope. This means for all subsequent properties inside the article tag are properties of our Article.

The "itemscope" Attribute

The itemscope defines a group (scope) of name-value pairs (properties), effectively treating the property value as an object. It doesn't require the presences of an itemtype however without one, the interoperability between systems can be very limited without a common vocabularly.

Summary

Microdata allows website developers to enrich a webpage with rich metadata, allowing for search engines and other systems to integrate the data into their systems. You can define individual properties with different values including nesting values through scopes.

While there are a number of other aspects about Microdata including additional attributes, this should serve as a basic introduction to the world of Microdata.

Additional Resources

A Better Mousetrap

James Turner — Tue, 15 Sep 2020 07:11:21 +0000

Today is a big day for me as after many months (or years depending how you look at it), I've finally launched the first product for my business, BrandVantage. This post is the story of how I started with one idea and ended up launching with a different one.

The Original Idea: Let's build a digital brand expert!

I worked as a web developer for a local web development agency for a number of years and in that time, I learnt a lot about how a variety of different businesses operated online.

There were a few key "problems" I found in common across many of those businesses:

Under-utilising analytics
Misunderstanding analytics
Not keeping on top of industry information
Lack of competitor analysis/understanding
Difficulty with Search Engine Optimization (SEO)

In moderate-to-large companies where you have marketing departments, most of this stuff can be covered by one or more staff dedicated to these things. In smaller companies, the business owner is normally the one where these tasks fall on to, but they are already wearing many different hats. It felt like something was here - if I could automate some of these tasks in different ways, I could both help business owners and earn myself some money along the way.

Automation of tasks, especially ones in analytics or SEO spaces, isn't a new idea. In fact, I've seen many businesses in a similar space launch on Product Hunt over the years since starting, but that didn't deter me. I was building a better mousetrap and wanting to launch it at a lower price, not something truly innovative so it was going to be an uphill battle. This area though, helping small businesses online be as efficient in tasks as some bigger businesses can, is something I felt passionately about so I proceeded anyway.

Attempt One: Very Hacky (in PHP)

Way back in 2015/16/17, while still at my full-time job, I spent nights and weekends building and tinkering on solutions to the problems business owners face. It was a hacky PHP solution pulling real-time information from sources like Twitter, Google Analytics and Facebook. A hacky approach seemed like a good idea as that seemed to be the way people launched things, do the quickest and hackiest thing you can to get it out the door.

While working on it, I had a few interested parties though what I built could barely be considered a prototype. The thing was a mess. I could do some basic queries, but it wasn't what I considered sellable and definitely not user-friendly, something I considered key to the product. I was also running into technical problems with scale - any sufficiently complex query was performed real-time, which was getting more complicated. Real-time processing had to be out. I needed to pre-compute and store it in a database.

I wanted to take this more seriously and I didn't feel like a "quick and hacky" approach to building a product was right for me. With this in mind, it seemed like a good opportunity to change the tech stack to something that would be better long term.

Attempt Two: Slightly Less Hacky (in .NET)

Moving to .NET felt like the smart move for me as at my job I had spent a lot more time working in .NET than PHP, plus I vastly prefered the tooling in .NET vs PHP. That said, the .NET code I had worked on to-date would definitely be considered "legacy code".

My first version in .NET (specifically .NET Framework), predating my use of version control, was trying to keep costs low by using MySQL through Entity Framework. After a lot of pain and suffering with that, I had a short stint of MSSQL before I settled upon MongoDB.

MongoDB might seem like a weird choice - there are some people that have very strong opinions about which type of database you should use. Honestly it came down to a gut feel after messing around with it - it seemed more compatible to the way I was approaching problems than a relational database would. I liked the code-first approach to Entity Framework so much though that I recreated the "feel" of Entity Framework for MongoDB with some custom code. This later became an open source project of mine called MongoFramework.

I'm not going to lie, progress was... slow. While I was putting quite a lot of time into working on it, it was still an extremely ambitious project. I have strong feelings about building "MVPs" where some people focus too much on the "minimum" without enough focus on the "viable". At the end of the day people buy products that meet their needs, and cutting too much out would meet no-ones needs. If someone was going to use this, in a market with many competitors of varying quality, it had to do its job well. There didn't seem much I could reasonably cut to make it any more minimal if I wanted people to buy it.

I kept working at it every night, building pieces to extract and store data from a variety of sources. I was pulling in data from Google Analytics, Google Webmaster Tools (now called Google Search Console), Twitter, Facebook, IP Geolocation, DNS information and also from news articles. What I thought I could do is once I had the different data sources together, I would write custom rules that could infer insights from individual or combined data sets. These insights would form the basis of the "digital brand expert". After all, that was the goal of the idea, something that could help out small business owners.

After 2 years of working on this in my spare time, it felt the right time to leave my job and go into this full time. I felt like I was so close to launching and I just needed something more than the same day-to-day work. So I did it - I left my job after 7 years.

Going Full-time into the Idea

Right out of the gate, I had moved from .NET Framework to .NET Core, was working on UI/UX improvements for the application and launched the website for it. I worked with an accountant and a lawyer to setup the business, bought a trade mark for the product name, and I felt good like I was only a few months away from launching. This feeling didn't last though...

Over time, it felt like I was taking two steps forward then one step back - some technical, some business related. Sure, that is still progress, but having new issues crop up every day or so can really crush your motivation.

My best/happiest/most productive days were days I ignored or avoided different issues I had. If I had a problem with the login system, I would focus on how the UX of the menus worked. If I had a problem with data gathering, I would add more tests to the codebase. While I didn't entirely ignore the problem, I would wait a week or two before I looked at it again, somewhat hoping it would solve itself - unfortunately that isn't how things work.

In time though, I got to a stage where it felt like I could launch and was hyping myself up until reality struck: I didn't actually build what I set out to build.

The UI/UX was good, I had strategies for deployment and plans for next steps, but it wasn't a "digital brand expert". It was instead a glorified data store for information that people could better access through existing tools. That's kinda a big problem!

When realising this I poured time into fixing that huge lapse in judgement, but I couldn't do it. No matter how I tried, I just couldn't figure out how to build this rules engine. It was like my entire thought process was just clouded. I couldn't see the solution to the problem like I can for most other things.

This was depressing and I ended up having a month or so hiatus from working on it. When I have had stints of not feeling like or not being able to do programming in the past, I try and spur it on again by watching some show or movie which has some strong relation to technology (fictional or not). My go-to is usually something like Iron Man, but this time I was rewatching Halt and Catch Fire where I found some inspiration.

The Pivot: An API to the Internet

Later in the series a lot of the focus is around the Web, and it was in these episodes where my thoughts about the Internet and the data on it have changed. There is a quote from one of the main characters at the end of Season 3 that resonates with me:

"The moment we decide what the Web is, we've lost. The moment we try to tell people what to do with it, we've lost.
All we have to do is build a door and let them inside."

- Joe MacMillan (Season 3, Episode 10)

The Internet is a treasure trove of information, it is searchable but generally unstructured. People have managed to create all sorts of different pages in HTML, but in the process of making a website everything is designed for a human user. It is this way for obvious reasons, we are the consumers of web pages after all... aren't we?

Behind these user-friendly web pages are usually other specific bits of markup, providing some level of structured data for specific situations. Sometimes it is a description metatag for search engines, other times it might be Open Graph metatags for social media links. We build these things to help aid computers processing our web pages.

In 2011, Schema.org was created.
This was a collaborative effort between Google, Bing and Yahoo (later that year, Yandex as well) with the mission to "create, maintain, and promote schemas for structured data on the Internet, on web pages, in email messages, and beyond". Through 3 different encodings (Microdata, RDFa and JSON-LD), websites could express detailed structured data.

There is another quote from Halt and Catch Fire which I like:

"Computers aren't the thing. They're the thing that gets us to the thing."

- Joe MacMillan (Season 1, Episode 1)

As much as I like computers and programming, they are used to help us achieve other goals. From my attempts of trying to build a "digital brand expert", I knew that data is fundamental to help build more advanced systems and give new insights. Having easier access to other forms of data from web pages around the world may allow new and different tools to be built.

So I decided rather than try and solve a problem that I was clouded by, I would pivot my product. It wouldn't be the "digital brand expert" (yet), instead it would be a data provider in its own right. The scope of functionality was smaller and the path seemed clearer - I provide structured data from web pages.

Being a data provider in this manner can help me achieve my original goal at a later point in time - I'll have a different and unique dataset that my competitors wouldn't actually have or have it at a lower cost than they might. For example, when I was integrating news articles into my "digital brand expert", the service I was using had a high monthly cost and still was relatively limited on queries. Instead as my own data provider, I could get access to something like news articles at no additional cost.

Thinking this way, I'm basically letting my "digital brand expert" concept take a hiatus while I could earn money providing data for others to build tools or integrate into their own workflow. So I pivoted in late 2019 to build a tool to get structured data out of web pages.

Actually Building the Thing

The goal was standization and interoperability so I needed to support the major existing types of structured data, but also derive structured data for where it is missing. For interoperability reasons, I didn't want to create a new standard for structured data. Instead, I decided the Schema.org vocabulary would be a good fit for my use case.

There are a lot of types in Schema.org and I didn't want to write them myself so I found a library called Schema.NET. And because I care about open source, and I would be taking a large dependence on the library, I contributed a variety of patches and performance improvements. I'm now a joint collaborator on the project with the project's creator, Muhammad Rehan Saeed.

I built an initial prototype to see if it would be doable and it was - I was able to extract common known data formats into a singular format. Over the next few weeks, I continued to refine it and expand it with some basic logic to derive new structured data from pages without any.

Now that I achieved the goal I set out for, I needed to put it into something sellable.

I had all my code to date for my "digital brand expert" and a lot of it would actually be useable, so I just ripped out what I didn't need and started to port my prototype into it. It needed a bit of work to tie it together, but overall this part went pretty smoothly.

Everything seemed good till I was actually integrating subscriptions/payment into the application. What I had for the "digital brand expert" idea was flawed in a few ways and I recently discovered the fun world of international sales tax.

I tried a few different solutions and was liaising with my accountant about what would work though ended up taking way longer than I wanted. Each of these different business/integration issues hurt my productivity like the issues I had with my original idea - it has been hard.

I did hit different productivity slumps (and one breakdown) though in the end, I slowly and steadily made progress and finally reached the point of launching something.

Behind the Technical Curtain

I like knowing about how things work and I'm sure other people out there are similar so here is the technical breakdown of some aspects:

The core is an ASP.NET Core 3.1 application running as an Azure App Service on Linux. The database is powered by MongoDB (on MongoDB Atlas) using my open source "Entity Framework"-like library called MongoFramework.
The various pages in the application are Razor Pages and the API itself is using MVC.

Internally to the API, I am using Schema.NET for converting to/from the Schema.org vocabulary. The API itself honours Robots.txt files when converting pages so I built a robust open source solution for parsing Robots.txt files.

Additionally different aspects of the system internally use caching where I used Cache Tower, my own caching library that supports multi-layer caching.

For handling background tasks like removing old data from the database, I use Hangfire. For error logging, I use Sentry which I've written a custom layer to hook Hangfire exceptions into. For performance monitoring, I use MiniProfiler where I've added support for MongoFramework so I can see how long my queries take.

GitHub manages the code itself with Azure DevOps managing the building, testing and deploying of the application. I actually run my own Azure DevOps build agent locally which helps quite a bit with build and release performance.

Conclusion

There's something cathartic about writing this post as I am closing one chapter of my life and opening another. Launching BrandVantage is a big step for me - I'm both excited and nervous about doing so, though optimistic in the future of the business.

I have a lot of big plans for BrandVantage including:

News API: News articles from around the web as Article Schema objects
Product API: Product pages restuctured to Product Schema objects
Plus a few others...

I do plan to revisit the "digital brand expert" idea again. I still think there is something good there, but next time I think I'll be a little more prepared.

Multilayer Caching in .NET

James Turner — Sun, 07 Jun 2020 12:27:17 +0000

Caching is a powerful tool in a programmer's toolbox but it isn't magic. It can help scale an application to a vast number of users or it can be the thing dragging down your application. Layered caching is a technique of stacking different types of cache on top of each other which play to different strengths.

I was first inspired to the idea of multilayered caching by Nick Craver. He wrote a great article about how Stack Overflow do caching which has a lot of interesting insights - definitely worth checking out if you haven't already. It was his article that inspired me to create Cache Tower, my own multilayered caching solution for .NET with an emphasis on performance.

Using the example he illustrated in his post, our own computers already do multiple layers of caching:

L1/L2 CPU Cache
RAM
SSD/HDD (Pagefile)

The performance profiles of each of these is drastically different where the CPU caches are the fastest but also hold the least amount of data. This is probably the first important takeaway from caching - its not just what you cache, its how you cache it.

There is an interesting case with Cloudflare where they put unpopular items in the RAM and more popular items into their SSD storage. They use a multilayered cache system of RAM then SSD. While they have some extremely fast SSDs, it turns out when you read and write to them at the same time, you can suffer a performance penalty.
To avoid that penalty, they realised that having unpopular items (items never hit or hit only once) purely in the RAM allowed their overall system to perform better. It may not be perfect but they got some interesting results!

Looking at caching from an application's point of view, the layers may look a bit different but the concept is still the same. We move from the fastest layers which have limited space to slower layers which have more space.

In-Memory Cache
Redis/Memcached
Database/File

While it might seem simple enough to implement yourself, there are a few considerations to keep in mind for building a scalable multilayered caching solution.

Keeping Cache Layers Up-to-Date

Scenario: You have multiple instances of an application with their own local caches (in-memory) while also having a shared cache (Redis).

Like in a normal caching scenario, you want to avoid cache misses. In multilayered caching, we have two types of cache misses - close misses and complete misses. If your in-memory cache does not have the item but Redis does, this is a close cache miss. You will need to propagate the cache result back to your in-memory cache to achieve maximum performance.

You could do this via a background task however this wouldn't scale. It would require iterating all keys of one cache layer and comparing them to the keys in another.

To get the best benefit here, you will want only propagate the item if you actually need it. This keeps your in-memory cache as small as what it actually requires. Because we are having to fetch the item from the shared cache anyway, we can spend a few extra cycles storing it in our local in-memory cache.

The extra time spent storing it in our in-memory cache should pale in comparison to the time required for a complete cache miss.

Managing Evictions

Scenario: You have an in-memory cache and a filesystem cache for a single application instance

Depending on the in-memory caching solution, you might already have an auto-eviction system. This can be found, for example, in Microsoft's MemoryCache. Unlike what is available in something like Redis though, caching to a file is both extremely slow and doesn't have a method to auto-evict expired items.

While your code may consider expired cache items as "missed", its important to actually evict the expired records as they may be taking up precious space in memory, disk or a database. It seems pretty straight forward, loop over the items known to be in the cache and evict any expired records.

Its important to consider that some cache layer technologies may have optimizations that allow bulk eviction of records instead of individual evictions. For example, a database cache layer would likely be able to query all expired items at once and be able to run a single "delete" operation.

This bulk eviction "cleanup" is a good candidate for a background task - something where there are few instances of it and it can start the cleanup at regular intervals.

Background Refreshing (Stale vs Expired Cache Items)

Background refreshing isn't exclusive to a multilayer cache solution however it can be invaluable for maximising performance in one.
The important part for background refreshes is working out the best time for refreshing. Refreshing too early may put an unnecessary strain on the data source however refreshing too late may have the data be overly stale.

The control of the refreshing is important too - you don't want to do this on a schedule as the cache may be overly eager. Like propagating between cache layers, you want to perform this if the cache item is actively being hit.

To keep throughput up, we need to simultaneously return our "stale" cache item while triggering a refresh to update our data. This update of data needs to hit every cache layer too so other application instances can benefit from the refreshed data.

Distributed Locking

Scenario: You have multiple instances of an application with their own local caches (in-memory) while also having a shared cache (Redis).

If you're looking at a multilayered caching solution, you likely are running multiple instances of your application. If "Web Server 1" is already attempting to update Redis then "Web Server 2" doesn't need to waste any time doing the same. This is important to factor especially if retrieving the original data is an expensive operation.

Distributed locking helps alleviate this however there is a catch - you don't want multiple requests on the same server checking the distributed cache every time for a lock. If the same server already has a lock, you will want to track that locally in-memory so the lock-check is faster.

Summary

Layered caching can provide the best of multiple different cache types. You can get the performance of in-memory cache with the larger cache sizes from a Redis instance, database or file system. It won't automatically solve every caching performance problem but in the right scenarios, can be an extremely useful tool.

I hope these tips can help you out with your own caching solution. If you don't want to roll your own, check out my library Cache Tower which supports these things and more.

TurnerSoftware / CacheTower

An efficient multi-layered caching system for .NET

Cache Tower

An efficient multi-layered caching system for .NET

Overview

Computers have multiple layers of caching from L1/L2/L3 CPU caches to RAM or even disk caches, each with a different purpose and performance profile.

Why don't we do this with our code?

Cache Tower isn't a single type of cache, its a multi-layer solution to caching with each layer on top of another A multi-layer cache provides the performance benefits of a fast cache like in-memory with the resilience of a file, database or Redis-backed cache.

This library was inspired by a blog post by Nick Craver about how Stack Overflow do caching. Stack Overflow use a custom 2-layer caching solution with in-memory and Redis.

📋 Features

High performance with low allocations (see comparison to other caching solutions).
Local system caching with in-memory and file-based caches.
Distributed system caching with MongoDB and Redis.
Supports one…

View on GitHub

Levenshtein Distance with SIMD (Bonus Part)

James Turner — Wed, 04 Mar 2020 01:53:51 +0000

This is a bonus part because the other post was already jam-packed with optimizations plus this is a pretty exotic optimization that less developers are likely to directly use.

"Single Instruction, Multiple Data" (SIMD) is a method by which you can operate on a vector of data - allowing for certain mathematical and logic operations to take place on every element in the vector at the same time. This differs from Simultaneous Multithreading (SMT) where threads perform independent instructions - SIMD does a single instruction but to more than one bit of data at once.

To make things more confusing, there is also "Single Instruction, Multiple Threads" (SIMT) which is effectively how modern GPUs operate but that is a topic for a different post.

If you haven't heard of SIMD before, you may have heard of it under specific implementation names such as:

This is a very low level, CPU specific, optimization and is suited for algorithms that can be vectorized. Some instructions operate on 128-bits, some on 256-bits and some can go all the way to 512-bits (AVX-512).

The Levenshtein Distance algorithm isn't exactly a good candidate as processing a single cell relies on the computation of the cells around it. Nevertheless, there are some areas that SIMD instructions will still help us.

To target SIMD instructions in our code, we will be making using of new APIs specifically in .NET though SIMD instructions are most commonly found in lower-level languages like C, C++ or hand-written assembly. In the future, even WebAssembly may support SIMD instructions.

Let's run through a super basic example of a SIMD vector operation, adding numbers across two vectors.

[ 1, 2, 4, 6 ]
  +  +  +  +
[ 3, 5, 3, 2 ]
  =  =  =  =
[ 4, 7, 7, 8 ]

If we look at the individual columns in the above vector calculation, you'll see how it operates (1 + 3 = 4, 2 + 5 = 7, 4 + 3 = 7, 6 + 2 = 8). Assuming those numbers are all 32-bit Signed Integers, that could be the SSE2 Add instruction "PADDD".

Let's look at another example, comparing two vectors.

[  1,  2,  4,  6 ]
  ==  ==  ==  ==
[  4,  2,  4,  9 ]
   =   =   =   =
[  0, -1, -1,  0 ]

What we are getting as a result here is the HIGH and LOW value where HIGH (all bits are 1) means equal and LOW (all bits are 0) means not equal. We are using a 32-bit Signed Integers again here so an "all bits are 1" case means our result is -1. If we used an unsigned number, the value would be the maximum value of that number instead.

Using 32-bit Signed Integers, the instruction to do the vector comparison could be the SSE2 Compare Equals instruction "PCMPEQD".

Where we can actually use SIMD instructions for our Levenshtein Distance optimizations include:

Comparing the beginning and end characters of a string
Filling our initial row with an incrementing sequence
Branchless calculating the minimum of two values

Comparing the beginning and end characters of a string

Put simply, our best comparison/trimming code for the start and end of strings was performing one-character comparisons at a time.

var startIndex = 0;
var sourceEnd = source.Length;
var targetEnd = target.Length;

while (startIndex < sourceEnd && startIndex < targetEnd && source[startIndex] == target[startIndex])
{
    startIndex++;
}
while (startIndex < sourceEnd && startIndex < targetEnd && source[sourceEnd - 1] == target[targetEnd - 1])
{
    sourceEnd--;
    targetEnd--;
}

var sourceLength = sourceEnd - startIndex;
var targetLength = targetEnd - startIndex;

ReadOnlySpan<char> sourceSpan = source;
ReadOnlySpan<char> targetSpan = target;

sourceSpan = sourceSpan.Slice(startIndex, sourceLength);
targetSpan = targetSpan.Slice(startIndex, targetLength);

In .NET, the individual char of a string is a ushort - a 16-bit value. With this in mind, we could compare 8 characters at a time with a 128-bit vector or 16 characters with a 256-bit vector. We'll opt for the 16 character comparison which will utilise AVX2 SIMD instructions.

var charactersAvailableToTrim = Math.Min(sourceEnd, targetEnd);
if (charactersAvailableToTrim >= 16)
{
    fixed (char* sourcePtr = source)
    fixed (char* targetPtr = target)
    {
        var sourceUShortPtr = (ushort*)sourcePtr;
        var targetUShortPtr = (ushort*)targetPtr;

        while (charactersAvailableToTrim >= 16)
        {
            var sectionEquality = Avx2.MoveMask(
                Avx2.CompareEqual(
                    Avx.LoadDquVector256(sourceUShortPtr + startIndex),
                    Avx.LoadDquVector256(targetUShortPtr + startIndex)
                ).AsByte()
            );

            if (sectionEquality != -1)
            {
                break;
            }

            startIndex += 16;
            charactersAvailableToTrim -= 16;
        }

        while (charactersAvailableToTrim >= 16)
        {
            var sectionEquality = Avx2.MoveMask(
                Avx2.CompareEqual(
                    Avx.LoadDquVector256(sourceUShortPtr + (sourceEnd - 16 + 1)),
                    Avx.LoadDquVector256(targetUShortPtr + (targetEnd - 16 + 1))
                ).AsByte()
            );

            if (sectionEquality != -1)
            {
                break;
            }

            sourceEnd -= 16;
            targetEnd -= 16;
            charactersAvailableToTrim -= 16;
        }
    }
}

while (charactersAvailableToTrim > 0 && source[startIndex] == target[startIndex])
{
    charactersAvailableToTrim--;
    startIndex++;
}

while (charactersAvailableToTrim > 0 && source[sourceEnd - 1] == target[targetEnd - 1])
{
    charactersAvailableToTrim--;
    sourceEnd--;
    targetEnd--;
}

There are a lot of things going on in this block of code but let's focus on the most important part for us - the SIMD instructions.

while (charactersAvailableToTrim >= 16)
{
    var sectionEquality = Avx2.MoveMask(
        Avx2.CompareEqual(
            Avx.LoadDquVector256(sourceUShortPtr + startIndex),
            Avx.LoadDquVector256(targetUShortPtr + startIndex)
        ).AsByte()
    );

    if (sectionEquality != -1)
    {
        break;
    }
    startIndex += 16;
    charactersAvailableToTrim -= 16;
}

Our SIMD instructions are:

Avx.LoadDquVector256: Loads a 256-bit vector from a pointer ("VLDDQU")
Avx2.CompareEqual: Our equality comparison of two 256-bit vectors ("VPCMPEQW")
Avx2.MoveMask: Creates a bitmask from the most significant bit of each item in the vector ("VPMOVMSKB")

Basically we are saying "Unless all characters of this 16-character chunk are equal, break from the loop".

Because we are operating in 16-character blocks, we will still fall back to individual character comparisons so we can have the smallest strings to compare in the main Levenshtein Distance calculating code.

Filling our initial row with an incrementing sequence

In Part 2, we showed how there is a simple loop that fills in the initial row of data.

for (var i = 1; i <= target.Length; ++i)
{
    previousRow[i] = i;
}

But we can go faster, much faster...

var columnIndex = 0;
var columnsRemaining = previousRow.Length;

fixed (int* previousRowPtr = previousRow)
{
    var lastVector256 = Vector256.Create(0, 1, 2, 3, 4, 5, 6, 7);
    var shiftVector256 = Vector256.Create(8);

    while (columnsRemaining >= 8)
    {
        columnsRemaining -= 8;
        Avx.Store(previousRowPtr + columnIndex, lastVector256);
        lastVector256 = Avx2.Add(lastVector256, shiftVector256);
        columnIndex += 8;
    }

    if (columnsRemaining > 4)
    {
        columnsRemaining -= 4;
        previousRowPtr[columnIndex] = ++columnIndex;
        previousRowPtr[columnIndex] = ++columnIndex;
        previousRowPtr[columnIndex] = ++columnIndex;
        previousRowPtr[columnIndex] = ++columnIndex;
    }

    while (columnsRemaining > 0)
    {
        columnsRemaining--;
        previousRowPtr[columnIndex] = ++columnIndex;
    }
}

Our implementation now is partially using SIMD and is partially unrolled. Because our previousRow is an array of 32-bit Integers, we are only doing 8 characters at a time on a 256-bit vector.

Focusing on the SIMD instructions:

var lastVector256 = Vector256.Create(0, 1, 2, 3, 4, 5, 6, 7);
var shiftVector256 = Vector256.Create(8);

while (columnsRemaining >= 8)
{
    columnsRemaining -= 8;
    Avx.Store(previousRowPtr + columnIndex, lastVector256);
    lastVector256 = Avx2.Add(lastVector256, shiftVector256);
    columnIndex += 8;
}

We create an initial vector of the first 8 values (lastVector256), we get a vector we want to increment by (shiftVector256) and we simply work up the remaining columns of previousRow 8 items at a time.

Our SIMD instructions:

Avx.Store: Save a 256-bit vector to the specified pointer location ("VMOVDQA")
Avx2.Add: Adds two 256-bit vectors together, returning the result ("VPADDD")

Branchless calculating the minimum of two values

In Part 3, we covered cutting out branches by re-organizing code or unrolling loops. We can actually take it slightly further using SIMD instructions by abusing/misusing how a SIMD Min comparison works.

Here is our last version of the calculating code:

localCost = previousDiagonal;
deletionCost = previousRow[j];
if (sourceChar != target[j - 1])
{
    localCost = Math.Min(previousColumn, localCost);
    localCost = Math.Min(deletionCost, localCost);
    localCost++;
}
previousColumn = localCost;
previousRow[j++] = localCost;
previousDiagonal = deletionCost;

We can't eliminate the if-statement - I've tried, multiple times - but we can eliminate the branches that would occur as part of Math.Min. To be clear, Math.Min isn't a slow function and by itself, it should perform faster than what we are about to do however when there are two in a row, we can start to benefit from our optimization.

To gain the most performance out of this, we don't want to jump to and from vectors - the more operations we can do while it is a vector, the better it will be for our performance. This is the latency-vs-throughput potential with SIMD instructions.

localCostVector = previousDiagonalVector;
deletionCostVector = Vector128.Create(previousRowPtr[columnIndex]);
if (sourcePrevChar != targetPtr[columnIndex])
{
    localCostVector = Sse2.Add(
        Sse41.Min(
            Sse41.Min(
                previousColumnVector,
                localCostVector
            ),
            deletionCostVector
        ),
        allOnesVector
    );
}
previousColumnVector = localCostVector;
previousRowPtr[columnIndex++] = localCostVector.GetElement(0);
previousDiagonalVector = deletionCostVector;

While most of the variables are the same with just "Vector" at the end, there are some differences to know about.

deletionCostVector = Vector128.Create(previousRowPtr[columnIndex]);

This creates a 128-bit vector of the value at that specific pointer. That is to say, it is only a single value that is in the vector 4 times.

localCostVector = Sse2.Add(
    Sse41.Min(
        Sse41.Min(
            previousColumnVector,
            localCostVector
        ),
        deletionCostVector
    ),
    allOnesVector
);

Like the original code, we are doing two Math.Min equivalent operations and then adding 1 to the result. The vector allOnesVector is aptly named because the vector only contains the number 1 in all positions.

previousRowPtr[columnIndex++] = localCostVector.GetElement(0);

Finally, we end with taking only the first element from the vector and storing it at our specific column.

You might realise now why I said we were abusing/misusing SIMD here - we don't actually care about how big the vector is as we simply don't use anything more than one item in the vector. This is because we are not taking advantage of the vector, we are taking advantage that Sse41.Min makes our code effectively branchless in the minimum value comparison. With the constraint that the Levenshtein Distance calculation relies on previously calculated cells, I can't see a situation where you can make use of the full vector to speed up the calculations further.

Our SIMD instructions:

Sse41.Min: Gets the minimum of each value in the vector ("PMINUD")
Sse2.Add: Adds the values across the vectors ("PADDD")

Caveats of SIMD Instructions

Besides that the data and algorithm needing to support vectorization, it isn't a magic bullet. When digging this deep for performance, you'll be looking at the latency and throughput of instructions.

The latency and throughput of instructions will differ per CPU model.

The best resource that I have found that digs into the latency and throughput for specific models are the optimization manuals by Agner. That said, Intel does have some information about them on their Intrinsics Guide.

It is important for you to benchmark your code to see if it is an appropriate optimization for your own code and the machines you are targeting.

Helpful Links

Levenshtein Distance (Part 3: Optimize Everything!)

James Turner — Wed, 04 Mar 2020 01:53:00 +0000

In Part 1 we went through what the Levenshtein Distance is and in Part 2 we covered a few major optimizations for memory and performance. In Part 3 (this post) we will be taking things up to 11 and trying to squeeze every bit of performance out of our code.

While there are some aspects of this post that are language agnostic, this post will talk about a number of C# specific optimizations - there may be equivalent optimizations in your programming language of choice.

Being Smarter with Data

In Part 2, one of our best versions had an inner loop that looked like this:

for (var i = 1; i <= source.Length; ++i)
{
    var previousDiagonal = previousRow[0];
    var previousColumn = previousRow[0]++;

    for (var j = 1; j <= target.Length; ++j)
    {
        var insertOrDelete = Math.Min(previousColumn, previousRow[j]) + 1;
        var edit = previousDiagonal + (source[i - 1] == target[j - 1] ? 0 : 1);

        previousColumn = Math.Min(insertOrDelete, edit);
        previousDiagonal = previousRow[j];
        previousRow[j] = previousColumn;
    }
}

If you look carefully at how we are accessing some of this data, we are doing some relatively repetitive actions - specifically, how we access the "source" character for the comparison.

Each iteration of the inner-loop, we are looking up source[i - 1] which we can actually cache in the body of the outer-loop like so:

for (var i = 1; i <= source.Length; ++i)
{
    var previousDiagonal = previousRow[0];
    var previousColumn = previousRow[0]++;
    var sourceChar = source[i - 1];

    for (var j = 1; j <= target.Length; ++j)
    {
        var insertOrDelete = Math.Min(previousColumn, previousRow[j]) + 1;
        var edit = previousDiagonal + (sourceChar == target[j - 1] ? 0 : 1);

        previousColumn = Math.Min(insertOrDelete, edit);
        previousDiagonal = previousRow[j];
        previousRow[j] = previousColumn;
    }
}

While it might not be the largest performance boost, we are in the territory where every little performance boost helps.

There is another way we can be smarter here by analysing that inner-most loop logic. We are always doing 2x Math.Min calls and always adding our source-target comparison to our previousDiagonal value. These might not be the slowest operations you can run but when you run them thousands of times, it does add up.

If you shift the code around just right, we can actually cut down the number of operations in one path of our code.

for (var i = 1; i <= source.Length; ++i)
{
    var previousDiagonal = previousRow[0];
    var previousColumn = previousRow[0]++;
    var sourceChar = source[i - 1];

    for (var j = 1; j <= target.Length; ++j)
    {
        if (sourceChar == target[j - 1])
        {
            previousColumn = previousDiagonal;
        }
        else
        {
            previousColumn = Math.Min(previousColumn, previousDiagonal);
            previousColumn = Math.Min(previousColumn, previousRow[j]);
            previousColumn++;
        }

        previousDiagonal = previousRow[j];
        previousRow[j] = previousColumn;
    }
}

This change plays on the fact that when the two characters are equal, the substitution cost (aka. previousDiagonal) will be the lowest cost of the three values to compare.

Going one step further, you might notice that one path actually has two calls to previousRow[j] - we can eliminate this too with more local variables. With a bit of refactoring, it could look something like this:

for (var i = 1; i <= source.Length; ++i)
{
    var previousDiagonal = previousRow[0];
    var previousColumn = previousRow[0]++;
    var sourceChar = source[i - 1];

    for (var j = 1; j <= target.Length; ++j)
    {
        var localCost = previousDiagonal;
        var deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j] = localCost;
        previousDiagonal = deletionCost;
    }
}

These tweaks combined will amount to a decent increase in performance but we aren't done yet...

`Span`-ing the Memory

Memory allocations - they aren't all bad BUT if we can eliminate some, that will help us. We are dealing with strings, potentially very big strings, and depending how we handle them we can allocate a lot of memory.

In Part 2, I showed a way we can trim the strings that have equal prefixes and suffixes to give us a performance boost. This code, while works, actually isn't the best.

As a reminder, here is the piece of code I shared:

var startIndex = 0;
var sourceEnd = source.Length;
var targetEnd = target.Length;

while (startIndex < sourceEnd && startIndex < targetEnd && source[startIndex] == target[startIndex])
{
    startIndex++;
}
while (startIndex < sourceEnd && startIndex < targetEnd && source[sourceEnd - 1] == target[targetEnd - 1])
{
    sourceEnd--;
    targetEnd--;
}

var sourceLength = sourceEnd - startIndex;
var targetLength = targetEnd - startIndex;

source = source.Substring(startIndex, sourceLength);
target = target.Substring(startIndex, targetLength);

Our biggest problem here is the last two lines and their Substring call. In C#, getting a substring of another string performs another allocation equal to the length of the new string. So if we had a 500 character string being substring'd to 200 characters, we would be allocating 200 characters worth of string.

This might not be bad individually but we can do better - we can do a ZERO allocation substring by using a (relatively) new feature of C# called Span.

The most concise description I can give, Span and its comparison type ReadOnlySpan allow access to a block of memory. This block of memory might be an array, it might be a pointer or it might be a string. Accessing data in a Span is the same as accessing data in a normal array like mySpan[42]. While wrapping these various types of memory is extremely useful for safe access to data, it also has one killer function - Slice - giving us a slice of the memory without actually allocating/copying it.

To use it in our example with a string, we need to cast it to ReadOnlySpan<char> (We must use ReadOnlySpan specifically because strings are immutable). After that, we simply replace our Substring calls with their Slice equivalent.

var startIndex = 0;
var sourceEnd = source.Length;
var targetEnd = target.Length;

while (startIndex < sourceEnd && startIndex < targetEnd && source[startIndex] == target[startIndex])
{
    startIndex++;
}
while (startIndex < sourceEnd && startIndex < targetEnd && source[sourceEnd - 1] == target[targetEnd - 1])
{
    sourceEnd--;
    targetEnd--;
}

var sourceLength = sourceEnd - startIndex;
var targetLength = targetEnd - startIndex;

ReadOnlySpan<char> sourceSpan = source;
ReadOnlySpan<char> targetSpan = target;

sourceSpan = sourceSpan.Slice(startIndex, sourceLength);
targetSpan = targetSpan.Slice(startIndex, targetLength);

One caveat is that from now on, we can only deal with methods that accept ReadOnlySpan<char> so if a method only accepts string type, we would need to re-allocate our span back to a full string.

This can be one of the few downsides with these types - there are many APIs that simply don't have overloads to accept Span etc. That said, the .NET team have done a lot of work adding new overloads to accept Span or ReadOnlySpan across the entire framework.

Even with that in mind, Span has other limitations like it being stack-only, you can't store a Span on the heap (eg. as a property in a class). With what we are doing above though, Span works out perfectly.

For more information about Span, have a read of Adam Sitnik's blog post about Span.

F Pooling around with Arrays

Strings are not our only source of allocations in our code. If we look back to how we instantiate our previousRow array, that is itself an allocation.

var previousRow = new int[target.Length + 1];

Our problem is that we need this array but creating new arrays is an allocation - how do we remove this allocation? With ArrayPool of course!

Another one of the gems that have been added to .NET is sharing/renting arrays. We ask for an array of X size and we get an array at least that big. After we are done, we just return the array back to the pool for it to be used elsewhere.

While there is a lot of magic that goes on behind the scenes to make that work and scale with various size arrays, for the size arrays we can reasonably deal with, ArrayPool is a perfect fit.

So how do we use this in our code? Just two places need to change - the start and end of our code.

Start of Code

var arrayPool = ArrayPool<int>.Shared;
var previousRow = arrayPool.Rent(target.Length + 1);

End of Code

var result = previousRow[targetLength];
arrayPool.Return(pooledArray);
return result;

That's it - our array allocation is now gone thanks to the hard work of the .NET team.

There are limitations with ArrayPool like by default the array won't be empty, the array may be longer than what you rented and has a default max rent size of 1,048,576.

For more information about ArrayPool, Adam Sitnik did another great post.

Dabbling in Parallel Processing

The Levenshtein Distance algorithm isn't exactly parallel friendly. In my effort to write the fastest Levenshtein Distance implementation, I did find a brute force way to make it happen. I don't want to get your hopes up - while the code can be very fast, it is riddled with race conditions because threading is hard - this means that it won't always be correct if you run it on the same strings each time. If you have the time and patience to implement it properly, you'll certainly have one of the fastest implementations around.

Anyway, let's dig into this!

The theory goes like this - if we divide a virtual matrix by the number of cores available on the machine, we could "stagger" our calculations. Visualising this as a matrix will give you some idea of how it would work and why it is hard.

The two colours of the matrix above represent the area our threads will calculate and write to. When it comes to reading data is where the problem lies - the section on the right (blue) is dependent on the column with the letter "u" which is written to by the left side (pink). While it is certainly possible to carefully hand off from one thread to another - this is most certainly going to be the hardest part of the implementation to solve.

We can see above what is might look like during a parallel calculation. The left thread (pink) needs to only perform scans on the first 4 characters of "Saturday" before moving onto the next line. The thread on the right (blue) can only start if the left thread (pink) has completed that row.

This doesn't seem all bad - the left thread (pink) could run dozens of rows ahead of the right thread (blue) and we would still calculate everything correctly. In Part 2 though, we covered shrinking a full matrix down to a single row - how will that work for our parallel-ness? If we want to adopt the same optimization, it is going to make our threading a lot more complicated.

Using the row above (with our same threading colours) as an example of what our calculation row would look like. The left thread (pink) can proceed because the right thread (blue) has written its first value for that row.

Let's skip forward and say the left thread (pink) manages to fill in all its values for the next row while the right thread (blue) manages to fill one value.

Now we are in a bit of a pickle - if the left thread (pink) manages to write another row before the right thread (blue) reads the "shared" value, it will miscalculate.

Oh no, now that shared value is 3 instead of the expected 2 - now our right thread (blue) will have the wrong insert cost when it starts the next row.

Expand this problem across bigger string comparisons with more threads and the chances of hitting this condition go up unless you have measures in place to trigger the right threads at the right time - not impossible but not trivial either.

Even with the performance bonus of a successful parallel implementation, you will be hit with performance penalities just keeping tracking of all the rows that threads are in not to mention the thread starting/stopping cost. You could (like me) just stuff threads in a while(true) loop but let's be honest, that is a bad idea.

With my (broken) implementation, for small strings it was up to 12x slower. For medium length strings (500 characters), it performed about the same as a non-parallel version. One the string length was around 8000 characters, it was performing up to 3x faster (with 8 threads) than a relatively well optimized non-parallel version.

Keeping in mind my version is flawed, that is still a significant speed boost. With more threads, bigger performance gains could likely be made.

In conclusion - I thought it would be interesting to share as a proof-of-concept but in reality, a good implementation of parallelism in Levenshtein Distance is not going to be a fun time.

Unless you have absolutely HUGE strings, I wouldn't even bother going this direction.

The Enemy of Processing: Branch Misprediction

Processors are fast using a variety of tricks with one of them being branch prediction. Put simply, it is the idea that the processor guesses whether a conditional jump will be taken or not. With its guess, it will start fetching, decoding and potentially even speculatively executing it.

It works wonders when it guesses right but when it guesses wrong, a mispredict, the processor may need to unroll and re-execute the code correctly.

All of this is important to consider given our nested for-loops - every loop performs a conditional jump (our comparison to the source or target strings). With two 1,000 character strings to compare, our inner for-loop would iterate 1,000,000 times. Two 8,000 character strings would iterate 64,000,000 times.

Earlier in this post, we covered a clever optimization to avoid our Math.Min calls - part of the benefit there wasn't avoiding just another instruction, it was avoiding a conditional jump instruction.

for (var i = 1; i <= source.Length; ++i)
{
    var previousDiagonal = previousRow[0];
    var previousColumn = previousRow[0]++;
    var sourceChar = source[i - 1];

    for (var j = 1; j <= target.Length; ++j)
    {
        var localCost = previousDiagonal;
        var deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            // The conditional jumps associated with Math.Min only execute
            // if the source character is not equal to the target character.
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j] = localCost;
        previousDiagonal = deletionCost;
    }
}

Even with this in mind, we still have a lot of conditional jumps going on in our code. To take this to the next level, we will want to think about loop unrolling.

The basic premise is, cut down on the number of instructions for each iteration of the loop. In our case, we will use this to avoid our "j <= target.Length;" cost for every iteration.

for (var i = 1; i <= source.Length; ++i)
{
    var previousDiagonal = previousRow[0];
    var previousColumn = previousRow[0]++;
    var sourceChar = source[i - 1];

    var j = 1;
    var columnsRemaining = target.Length;

    int localCost;
    int deletionCost;

    while (columnsRemaining >= 8)
    {
        columnsRemaining -= 8;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;
    }

    if (columnsRemaining >= 4)
    {
        columnsRemaining -= 4;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;
    }

    while (columnsRemaining > 0)
    {
        columnsRemaining--;

        localCost = previousDiagonal;
        deletionCost = previousRow[j];
        if (sourceChar != target[j - 1])
        {
            localCost = Math.Min(previousColumn, localCost);
            localCost = Math.Min(deletionCost, localCost);
            localCost++;
        }
        previousColumn = localCost;
        previousRow[j++] = localCost;
        previousDiagonal = deletionCost;
    }
}

There is quite a bit to unpack for that code but one of the things you might be able to tell is how long some basic unrolling code might be.

while (columnsRemaining >= 8)

Our first of 3 processing chunks - we are unrolled to 8 columns of calculations at a time. This means for every loop, we've removed 7 conditional jumps that needed handling.

Once this has processed all it can, we have between 0 and 7 columns remaining for processing.

if (columnsRemaining >= 4)

In our second of 3 processing chunks, we attempt to unroll 4 columns if there are enough columns available to do so. We are removing 3 conditional jumps in this block.

Once this has processed all it can, we have between 0 and 3 columns remaining for processing.

while (columnsRemaining > 0)

In our final processing chunk, there is no unrolling - we process each item individually. At worst, we are only needing to loop through 3 columns.

The actual calculation code in each chunk is identical, just replicated the number of times needed for the given chunk.

localCost = previousDiagonal;
deletionCost = previousRow[j];
if (sourceChar != target[j - 1])
{
    localCost = Math.Min(previousColumn, localCost);
    localCost = Math.Min(deletionCost, localCost);
    localCost++;
}
previousColumn = localCost;
previousRow[j++] = localCost;
previousDiagonal = deletionCost;

This technique above, going from 8 to 4 to 1, was inspired by how the .NET runtime does this for their SpanHelpers code. While there likely was some significance to the numbers chosen for optimizing cache lines relative to the size of the code unrolled, our code likely doesn't benefit to the same extent.

One of the biggest drawbacks to applying loop unrolling like this is the dramatic increase in binary size for the same functionality, not to mention the maintenance overhead having all of those blocks repeated. A single mistake in one could break the whole calculation.

Don't even think about pushing that to its own function as function calls have overheads too unless the compiler will inline it for you!

That said, loop unrolling still provided us a net benefit if all we cared about was raw performance.

You could go further and unroll the outer loop some amount too. If done right, you would be able to minimise the number of lookups of characters in the target string. That however I will leave as an exercise to the reader.

Bonus: Using SIMD Instructions

Due in part to the extraordinary length of this post, I've split the longest part about SIMD instructions to a separate post. If you want to dive into how vectorizing CPU instructions can help us perform even faster - check it out here.

Summary

We've extracted a lot of performance out of an algorithm which isn't very performant while dramatically decreasing our memory usage.

This whole blog series about Levenshtein Distance came up purely because I wanted to build a fast and memory efficient implementation. Besides parallel support, I have actually made a version which implements every other performance feature I've talked about this series - I call it Quickenshtein!

Turnerj / Quickenshtein

Making the quickest and most memory efficient implementation of Levenshtein Distance with SIMD and Threading support

Quickenshtein

A quick and memory efficient Levenshtein Distance calculator for .NET

Performance

Quickenshtein gets its speed and memory efficiency from a number of different optimizations To get the most performance out of the library, you will need .NET Core 3 or higher as this has support for hardware intrinsics.

Quickenshtein takes advantage of the following hardware intrinsics. On any recent x86 system, you will likely have these available.

If your computer doesn't have one of the hardware intrinsics available, Quickenshtein will still work - just slower than optimal.

Multi-Threading

By default, Quickenshtein performs in single-threaded mode as this mode performs best for small to medium size strings while having no memory allocations. When dealing with huge strings of 8000 characters or more, it may be useful to switch to multi-threaded mode. In this mode, the calculation is broken up and shared between multiple cores in a system.

…

View on GitHub

If its not the fastest Levenshtein Distance implementation, it is surely close to it - all while allocating 0 bytes.

If .NET is your thing and this could help you, check it out. If you want to implement your own version in another language, feel free to use my implementation as a guide.

Until next time fellow readers - let your code be fast and your allocations be nil.

Levenshtein Distance (Part 2: Gotta Go Fast)

James Turner — Thu, 13 Feb 2020 20:08:46 +0000

In Part 1 I explained what the Levenshtein Distance is and that it is both computationally and memory inefficient in a simple form. In Part 2 (this post), I'll cover ways to decrease the memory overhead and increase the performance.

Example Levenshtein Implementation

Before we get started, I'll walk through a real implementation of Levenshtein Distance with no optimizations - this is what we will be improving from.

Note: While the examples in this post are in C#, there is very little that couldn't be copied over to any other programming language with only minor edits.

public int CalculateDistance(string source, string target)
{
    var costMatrix = Enumerable
      .Range(0, source.Length + 1)
      .Select(line => new int[target.Length + 1])
      .ToArray();

    for (var i = 1; i <= source.Length; ++i)
    {
        costMatrix[i][0] = i;
    }

    for (var i = 1; i <= target.Length; ++i)
    {
        costMatrix[0][i] = i;
    }

    for (var i = 1; i <= source.Length; ++i)
    {
        for (var j = 1; j <= target.Length; ++j)
        {
            var insert = costMatrix[i][j - 1] + 1;
            var delete = costMatrix[i - 1][j] + 1;
            var edit = costMatrix[i - 1][j - 1] + (source[i - 1] == target[j - 1] ? 0 : 1);

            costMatrix[i][j] = Math.Min(Math.Min(insert, delete), edit);
        }
    }

    return costMatrix[source.Length][target.Length];
}

Breaking this down:

var costMatrix = Enumerable
  .Range(0, source.Length + 1)
  .Select(line => new int[target.Length + 1])
  .ToArray();

This builds our matrix - an array of arrays - to be one longer than the source string (eg. "Sunday") in rows and one longer than the target string (eg. "Saturday") in columns.

for (var i = 1; i <= source.Length; ++i)
{
    costMatrix[i][0] = i;
}

for (var i = 1; i <= target.Length; ++i)
{
    costMatrix[0][i] = i;
}

These two for-loops build the top row and left column of our matrix. With the example "Saturday" and "Sunday", it would look like this:

We have our main code:

for (var i = 1; i <= source.Length; ++i)
{
    for (var j = 1; j <= target.Length; ++j)
    {
        var insert = costMatrix[i][j - 1] + 1;
        var delete = costMatrix[i - 1][j] + 1;
        var edit = costMatrix[i - 1][j - 1] + (source[i - 1] == target[j - 1] ? 0 : 1);

        costMatrix[i][j] = Math.Min(Math.Min(insert, delete), edit);
    }
}

Simply put - for every column in every row, check the cell to my left (insert), the cell above (delete) and the cell diagonally to the left (edit). We do our Levenshtein Distance math (explained in Part 1) and we store that in the current cell.

And finally, our humble return of the last cell in the matrix - our Levenshtein Distance.

return costMatrix[source.Length][target.Length];

Now let's start making this faster and more memory efficient!

Memory Optimizations

Turning `(n+1)(m+1)` into `(n+1)2`

One of the biggest problems is the sheer amount of memory a full matrix of two long strings would require BUT it isn't necessary and here is why: We don't actually need all the data all the time.

Using same example we had in Part 1 with "Saturday" and "Sunday", yellow is the values we depend on and green is the values we calculate AND depend on.

If we continue this for the next row, it looks like this:

We can see that we no longer depend on the very first row of the matrix so in reality, we only need two rows of memory.

Below is an example of how that might look in code:

public int CalculateDistance(string source, string target)
{
    var costMatrix = Enumerable
      .Range(0, 2)
      .Select(line => new int[target.Length + 1])
      .ToArray();

    for (var i = 1; i <= target.Length; ++i)
    {
        costMatrix[0][i] = i;
    }

    for (var i = 1; i <= source.Length; ++i)
    {
        costMatrix[i % 2][0] = i;

        for (var j = 1; j <= target.Length; ++j)
        {
            var insert = costMatrix[i % 2][j - 1] + 1;
            var delete = costMatrix[(i - 1) % 2][j] + 1;
            var edit = costMatrix[(i - 1) % 2][j - 1] + (source[i - 1] == target[j - 1] ? 0 : 1);

            costMatrix[i % 2][j] = Math.Min(Math.Min(insert, delete), edit);
        }
    }

    return costMatrix[source.Length % 2][target.Length];
}

So what is going on here?

Our costMatrix variable is nearly instantiated the same however we only are creating two rows.
We dropped one of our for-loops, the one that builds the left column values. Instead, we now have costMatrix[i % 2][0] = i; in our main loop that effectively mimics this behaviour.
We are using i % 2 in a lot of places, allowing us to switch which row we are on.

That last point about % 2 switching what row we are on might sound odd so let me explain. The % operator is called the "Modulo" operator - it gets the remainder after a division.

If i = 0, the remainder of dividing by 2 is 0
If i = 1, the remainder of dividing by 2 is 1
If i = 2, the remainder of dividing by 2 is 0
and so on...

It is a nice little shortcut for us to switch between the two rows of data as if we had a full matrix.

The source.Length % 2 on the return will always get us the "last" row.

So at this point, we've dramatically decreased the memory usage but know we can do better - what if we only needed one row...

Turning `(n+1)*2` into `n+1`

I said earlier that we don't need all the data all the time and that is still the case with the two-row example above - we don't need all the data. In this case, we don't need all the data in the same row.

How does that work? Let's look at the matrix again...

With the yellow cells being what we depend on and green being what we calculated, we are only depending on 3 values. The next cell will also depend on only 3 values...

Now repeating this for one more cell, we can see more clearly the values we don't care about any more for this row.

When calculating the third cell, we don't actually care about the first cell we calculated. Taking this in mind, an implementation might look like this:

public int CalculateDistance(string source, string target)
{
    var previousRow = new int[target.Length + 1];

    for (var i = 1; i <= target.Length; ++i)
    {
        previousRow[i] = i;
    }

    for (var i = 1; i <= source.Length; ++i)
    {
        var previousDiagonal = previousRow[0];
        var previousColumn = previousRow[0]++;

        for (var j = 1; j <= target.Length; ++j)
        {
            var insertOrDelete = Math.Min(previousColumn, previousRow[j]) + 1;
            var edit = previousDiagonal + (source[i - 1] == target[j - 1] ? 0 : 1);

            previousColumn = Math.Min(insertOrDelete, edit);
            previousDiagonal = previousRow[j];
            previousRow[j] = previousColumn;
        }
    }

    return previousRow[target.Length];
}

There are a lot more changes here and now with different variable names so let's break this down:

var previousRow = new int[target.Length + 1];

Our costMatrix is out for a single array called previousRow - this will still hold our costs but from the point of view of our calculation, they will always be the "previous" set of data.

We still have our for-loop setting the first row like normal.

Our main loops are the other big differences:

for (var i = 1; i <= source.Length; ++i)
{
    var previousDiagonal = previousRow[0];
    var previousColumn = previousRow[0]++;

    for (var j = 1; j <= target.Length; ++j)
    {
        var insertOrDelete = Math.Min(previousColumn, previousRow[j]) + 1;
        var edit = previousDiagonal + (source[i - 1] == target[j - 1] ? 0 : 1);

        previousColumn = Math.Min(insertOrDelete, edit);
        previousDiagonal = previousRow[j];
        previousRow[j] = previousColumn;
    }
}

Starting with previousDiagonal, this represents our last substitution/edit cost. At the start of each logical row, the cost here is always one less than the insert cost (our previousColumn).

Speaking of previousColumn, with it being our last insert cost and knowing that our insert costs start one higher than our substitution/edit cost, we add one to the value of the previousDiagonal.

Our delete costs for our current column are found in previousRow[j] which also coincides with the value we are about to set.

In the meat of the for-loops, we can see I'm playing around with the variables a bit setting the previousColumn and previousDiagonal before finally setting previousRow[j] - this is all to make sure we have the right values in the right spots.

We set previousColumn to be our result because our result will be the "previous" result for the next column over.
We set previousDiagonal to be our our delete cost (previousRow[j]) as for the next column, our delete cost is their substitution/edit cost.

Finally after all the processing is done - we return the last value of our previousRow.

Now n+1 is great but what if we wanted n-sized array instead? I can say it is totally possible with a bit more footwork with what variables you set where but I'll leave that up to the reader to work out. (Or stay tuned for Part 3 where we push things to 11)

Performance/Time Optimizations

Now while the memory optimizations are great and will increase performance through less memory lookups or even from the removal of one of the for-loops, there are still big performance-specific optimizations on the table.

There are some basic shortcuts to the Levenshtein Distance, these include:

If StringA is empty, the Levenshtein Distance is StringB's length.
If StringB is empty, the Levenshtein Distance is StringA's length.
If StringA is equal to StringB, the Levenshtein Distance is 0.

Those are good but we can do better - What if we didn't even need build a matrix of all the letters from both words? What if we could trim the words that share a prefix or suffix? Now we're onto something...

With our example strings Saturday and Sunday, they share a common prefix and suffix so makes a great example for this. We only need to start where the strings are different and end on the last difference.

This makes "Saturday"-"Sunday" become "atur"-"un", a much smaller amount to process and as a bonus, a much smaller amount of memory needed!

Just to be sure it works, let's look at a matrix of this:

We can actually find this segment in the full matrix of "Saturday" and "Sunday":

This optimization can be extremely useful on large strings, bringing them down to a far more manageable size.

A partial implementation of this might look like:

var startIndex = 0;
var sourceEnd = source.Length;
var targetEnd = target.Length;

while (startIndex < sourceEnd && startIndex < targetEnd && source[startIndex] == target[startIndex])
{
    startIndex++;
}
while (startIndex < sourceEnd && startIndex < targetEnd && source[sourceEnd - 1] == target[targetEnd - 1])
{
    sourceEnd--;
    targetEnd--;
}

var sourceLength = sourceEnd - startIndex;
var targetLength = targetEnd - startIndex;

source = source.Substring(startIndex, sourceLength);
target = target.Substring(startIndex, targetLength);

Gotta Go Faster - I want more optimizations!

So do I! In Part 3, we will take everything we've done to 11! We will remove any memory allocations we have, decrease the number of string lookups, use hardware intrinsics to improve performance, learn the secrets of loop unrolling and even dabble in parallel processing! 😈

It's gonna be great!

Levenshtein Distance (Part 1: What is it?)

James Turner — Fri, 07 Feb 2020 13:53:45 +0000

The Levenshtein Distance is a deceptively simple algorithm - by looping over two strings, it can provide the "distance" (the number of differences) between the two. These differences are calculated in terms of "inserts", "deletions" and "substitutions".

The "distance" is effectively how similar two strings are. A distance of 0 would mean the strings are equal (no differences). A distance can be as high as there are as many characters in the longest string - this would mean there is absolutely nothing "similar" between these strings.

An application of the Levenshtein Distance algorithm is spell checking - knowing how similar two words are allows it to provide suggestions on what you may have intended to type.

Calculating the Levenshtein Distance

Take the words "Saturday" and "Sunday". What do we know about these words?

Saturday is 8 characters long and Sunday is 6.
They both start with "S" and end with "day".
Relative to the beginning of the string, the shared "u" is in a different position.
This just leaves "a", "t" and "r" from Saturday and "n" from Sunday as the only other differences.

Calculating the Levenshtein Distance of these two strings is effectively like building a matrix of values which represent the various inserts, deletions and substitutions required.

Let's build a matrix of this ourselves. We're going to start with the top row and left most column filled with numbers from 0 to each of the string's lengths.


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	*
u	2
n	3
d	4
a	5
y	6

Starting from the position of where the asterisks is, we will look at the cell above (the deletion cost), the cell to the left (the insertion cost) and the cell diagonally top-left (the substitution cost).

The operations to fill our cell are as follows:

Get the minimum of the insert cost (1) and deletion cost (1), adding 1 to the result (MIN(1,1) + 1 = 2)
Get the substitution cost (0), adding 1 to it if the letter on this column ("S") and row ("S") are different (0 + 0 = 0)
Take the minimum of those numbers (MIN(2,0) = 0) and put that in our cell


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0
u	2
n	3
d	4
a	5
y	6

Rinse and repeat for the next cell in the row:

Get the minimum of the insert cost (0) and deletion cost (2), adding 1 to the result (MIN(0,2) + 1 = 1)
Get the substitution cost (1), adding 1 to it if the letter on this column ("a") and row ("S") are different (1 + 1 = 2)
Take the minimum of those numbers (MIN(1,2) = 1) and put that in our cell


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1
u	2
n	3
d	4
a	5
y	6

This keeps going for the whole row:


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2
n	3
d	4
a	5
y	6

And eventually the whole table:


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

The actual Levenshtein Distance can be found in the bottom-right cell (3). Amazing right?

"Deceptively Simple"

I said early this algorithm is deceptively simple - I say this because of its computational complexity. This has a "Big-O" notation of O(n*m) where n is the length of one string and m is the length of the other. Memory-wise, building that matrix above is effectively (n+1)*(m+1) cells.

For the example above, there are 48 character comparisons with 96 checks for minimum value. Representing that table in memory ((6+1)*(8+1) cells by 4 bytes a cell, assuming 32-bit numbers) would account for 252 bytes!

Yes, I'm sure you're rolling your eyes that I'm squawking at 252 bytes. The problem is when you want to compare bigger strings. How about comparing two 1000 character strings? You'd be looking at... 4 megabytes.

That might not sound like a lot for a single lookup but now imagine doing that dozens or hundreds of times in a language that utilises garbage collection - the allocations would be huge!

When I first learnt about Levenshtein Distance I wanted to use it on web pages, to see how different two web pages are. Web pages can be quite large when counting every character in the HTML (this very page on DEV - at the time of writing - is north of 77K characters) or even just every text node (6K+ characters on this page at time of writing). Punching that into the same calculations above would be ~34 megabytes for 6K characters or a whopping 5 gigabytes for 77K characters!

Now what if we could reduce the number of cells we need from (n+1)*(m+1) to (MIN(n,m)+1)*2 or even just MIN(n,m)? In Part 2, I'll talk about the strategies of making this algorithm faster and more memory efficient.


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

DEV Community: James Turner

Fixing my BF1942 woes with Win32 APIs

The Plan

Improving the Win32 APIs

The End Result

Fun with Flags, Enums and Bit Shifting

Encoding a Value

A Bit Shifty

Generating an Image

Germany

Italy

France

Ireland

Luxembourg

Final Thoughts

If you liked this...

Remote Desktop Experience (Part 1: Planning)

Current Machine Specs

Potential 3-in-1 Solution

Renting-vs-Buying

Secondary Goals

Scriptable OS Install and Configuration

Better Backups

Testing and Next Steps

Stage 1A

Stage 1B

Stage 2

Stage 3

Stage 4

Let's do this thing!

What is Structured Data?

Structured Data and Web Pages

Summary

The pain points of C# source generators

Pain Point 1: Debugging Source Generators

Invoke the debugger from the source generator

Run the source generator manually

Pain Point 2: No Async/Await

Pain Point 3: Transient Dependencies

Potential Transient Dependency Workaround

Conclusion: Was migrating to source generators worth it?

What is Microdata?

The "itemprop" Attribute

Grouping Properties Together

Value from a "content" Attribute

Setting Two Properties at Once

Value from a "datetime" Attribute

Value from Inner Text

The "itemtype" Attribute

The "itemscope" Attribute

Summary

Additional Resources

A Better Mousetrap

The Original Idea: Let's build a digital brand expert!

Attempt One: Very Hacky (in PHP)

Attempt Two: Slightly Less Hacky (in .NET)

Going Full-time into the Idea

The Pivot: An API to the Internet

Actually Building the Thing

Behind the Technical Curtain

Conclusion

Links

Multilayer Caching in .NET

Keeping Cache Layers Up-to-Date

Managing Evictions

Background Refreshing (Stale vs Expired Cache Items)

Distributed Locking

Summary

TurnerSoftware / CacheTower

An efficient multi-layered caching system for .NET

Cache Tower

Overview

📋 Features

Levenshtein Distance with SIMD (Bonus Part)

Comparing the beginning and end characters of a string

Filling our initial row with an incrementing sequence

Branchless calculating the minimum of two values

Caveats of SIMD Instructions

Further Reading: Using SIMD for Sorting

Helpful Links

`Span`-ing the Memory

Turning `(n+1)(m+1)` into `(n+1)2`

Turning `(n+1)*2` into `n+1`


		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3