DEV Community: CharlieTap

Interfacing with Wasm from Kotlin

CharlieTap — Sat, 08 Nov 2025 16:52:41 +0000

You may have heard you can compile Kotlin → Wasm but did you know you can call Wasm from Kotlin?

Why would you want to do that?

It may sound odd but theres genuine reasons why you would want to do this.

WebAssembly is a compilation target of almost every single language you can think of, Kotlin, Swift, Go, Rust, C, C* etc etc etc the list goes on. If you can interface with Webassembly, you have the potential to access libraries from any of these languages!

Fancy working on an AI project but you're stuck because machine learning engineers cannot write anything else but Python? No problem compile Pytorch to as Wasm module and you're off to the races... Okay thats not actually possible yet but it will be soon!

Programming language ecosystems for the longest time have been siloed, preventing not just the sharing of code, but also knowledge and ideas. Wasm presents the opportunity to change that. In the not too distant future we will have the equivalent of npm but for wasm modules, a dependency registry which is contributed to by every programming language ecosystem in the world. Fast, memory safe libraries written in Rust, high level ergonomic libraries written in you're favourite scripting language and everything in between.

But isn't Web-Assembly for the ... Web?

Not really no, whilst it got its start as a solution in the browser WebAssembly is simply the specification of a virtual machine, you can implement that virtual machine wherever you like. Today we're going to take a look at a WebAssembly virtual machine built on top of Kotlin Multiplatform, which runs everywhere Kotlin Multiplatform does.

The library in question is one I've been working on slowly for the past 2 years, its called chasm and it makes working with Wasm incredibly simple.

Lets dive in

First things first we need some Wasm

As mentioned Wasm is the compilation target of many languages, but rather than setup a language, its toolchain and compile a program were going to use a Wasm module I've prepared for us.

You can download it here

add.wasm is an incredibly simple wasm module which exports one function 'add', that takes two integers and you guessed it, adds them.

Go ahead and put add.wasm somewhere your build can see it (e.g. src/main/resources/add.wasm or src/commonMain/resources/add.wasm).

Generating our interface

Chasm is at its heart a Wasm virtual machine, virtual machines tend to have low level apis and really aren't beginner friendly. For this reason Chasm also ships a Gradle plugin, the plugin simplifies things by generating a typesafe Kotlin interface which hides the lower level virtual machine api.

Add the following config to your build.gradle file and run a Gradle sync

// build.gradle.kts
plugins {
    // your usual plugin(s), e.g. jvm, android, kmp
    id("io.github.charlietap.chasm.gradle") version "2.0.0-1.2.0"
}

chasm {
    modules {
        create("Adder") {
            binary = layout.projectDirectory.file("src/main/resources/add.wasm")
            packageName = "com.example.wasm"
        }
    }
}

On sync (or build), the plugin decodes your Wasm module and inspects its public exports. Using the type information available its able to synthesise a Kotlin interface and implementation for you to use.

If you take a look in your modules build directory you should find the following:

package com.example.wasm

interface Adder {
    fun add(a: Int, b: Int): Int
}

and

internal class AdderImpl(
  private val binary: ByteArray,
  ... //omitted for brevity
) : Adder {

Note that the concrete implementation accepts the Wasm binary at runtime. Although that might seem counterintuitive since the plugin is already configured with a binary but it’s intentional. This design lets you swap implementations at runtime: you can ship Adder v1 with your project and later download v2 to update the behaviour in-process... Yes this is legal on Android and IOS because Chasm is an interpreter.

Thats it! You have everything you need and you can now instantiate your AdderImpl and call it like any other Kotlin class.

Whats happening under the hood

Before we dive further into the intricacies and gotchas, I want to explain a little bit about how this plugin runs your code on each platform.

It helps to distinguish between Chasm’s virtual machine API and the code generation this plugin produces. Chasm is a Kotlin Multiplatform (KMP) project that runs on the JVM and most native targets, but it doesn’t target the web directly. Browsers already provide a WebAssembly VM that unlike Chasm can JIT and AOT-compile Wasm, delivering near-native performance.

To take advantage of that, the Gradle plugin generates code against an abstract VM interface. On the JVM and native targets it uses Chasm (an interpreter). On JavaScript targets it delegates to the browser’s builtin Wasm runtime (V8, SpiderMonkey, or JavaScriptCore), inheriting their JIT/AOT compilation and performance.

Gotchas, gotchas gotchas

It’d be great if everything were as simple as the Adder example, but WebAssembly is still evolving. We’re not yet at the point where you can grab any off the shelf library and interface with it from Kotlin without friction. In the next section, we’ll walk through the pitfalls you’re likely to hit and how the Wasm roadmap aims to address them.

Lets talk Strings

Sooner or later you’ll want to call a function that takes or returns a String. Here’s the catch: core WebAssembly (Wasm) has no built in string type. Different languages represent strings differently (think &str vs String in Rust, plus OS and FFI-oriented variants), so most current approaches settle on “just bytes”: UTF-8 encoded data living in linear memory.

Compilers work around this in a few common ways, typically by writing the string into module memory and returning a pointer (and sometimes a length). It’s easier to see by example.

Say you had a function like:

fun username(): String = "foo"

Some compilers will emit:

(func (export "username") (result i32 i32))

That’s two i32s: the first is a pointer to the string in memory, the second is its length.

Others will emit:

(func (export "username") (result i32))

So how do you know where the string ends? It depends on the calling convention. Some toolchains use null-terminated strings; others encode the length at (or just before) the pointer. The important bit is: you must know your compiler’s string encoding strategy.

The good news: Chasm has support for all of these different encoding strategies. Even if the Wasm interface uses integers under the hood, Chasm can still generate a Kotlin interface that deals in String. You just need to steer the config with the right encoding hint.

Assume the compiler null-terminates strings and returns a single integer:

chasm {
    modules {
        create("Foo") {
            binary = layout.projectDirectory.file("src/commonMain/resources/foo.wasm")
            packageName = "com.foo.bar"
            function("username") {
                stringReturnType(StringEncodingStrategy.NULL_TERMINATED)
            }
        }
    }
}

So for String parameters we would just add stringParam()?

Yes... but there’s one more piece. When you pass a String, Chasm has to write it into the VM’s memory. To do that safely, it needs to coordinate with your Wasm module’s allocator. If your toolchain exports allocator functions, Chasm can use them.

Assuming null-terminated strings and that your module exports the classic malloc/free, you can wire up an allocator like this:

fun truncate(input: String): String

chasm {
    modules {
        create("Truncator") {
            binary = layout.projectDirectory.file("src/commonMain/resources/truncate.wasm")
            packageName = "com.foo.bar"
            allocator = ExportedAllocator("malloc", "free")
            function("truncate") {
                stringParam(StringEncodingStrategy.NULL_TERMINATED)
                stringReturnType(StringEncodingStrategy.NULL_TERMINATED)
            }
        }
    }
}

If you want to see working examples of multiple string encodings, the example project has a particular module which demonstrates this.

This isn’t ideal, you can see I'm jumping through hoops to make all this work. It forces callers to understand compiler conventions, and it doesn’t work if the compiler doesn’t expose the needed behaviours (Kotlin itself is not capable of any of the above). Things get even trickier for functions that return classes/structs or other aggregate types; there’s no portable way to express those over the core ABI.

However... as mentioned before Wasm is an evolving spec and for the problems highlighted there is light at the end of the tunnel. The upcoming Wasm Component Model proposal looks to address all of these issues.

The Component Model

The Component Model is a clever proposal. It tackles the awkward reality that modules compiled from different languages have differing binary interfaces and yet we still want them to interoperate. You can’t just bolt a string type onto core Wasm and call it done; that wouldn’t help the thousands of existing modules already in the wild. So the proposal comes at the problem from two angles:

Add a language-neutral type system
This is WIT (WebAssembly Interface Types) an IDL and type system for describing functions and rich data (string, list, records, variants, result, etc.). With WIT, everyone agrees on what crosses the boundary, independent of any one compiler’s ABI.
Wrap existing modules in a "component"
A component is a new concept to WebAssembly, its essentially a wrapper around a core Wasm module that exposes WIT defined imports/exports. The component acts as a translator speaking WIT to the outside world, and internally lifting and lowering types from modules differing binary interfaces

The Component Model is currently a Stage 1 WebAssembly proposal. It’s been actively developed for the last few years and is inching toward standardisation. When a formal spec lands, I'll be promptly updating Chasm...

So once the Component Model ships, will everything “just work”?

Kind of... but not by itself. The Component Model standardises type boundaries. At the start of this post we spoke about ubiquitous programming components, true universal binaries and for that to be a reality we need to talk about syscalls and operating systems.

Syscalls, WASI and the elusive universal binary

WebAssembly is a specification of an abstract virtual machine, but it has no notion of an operating system. Instead the specification details a system of imports and exports. You can for example import functions from the host system, it's through this mechanism Wasm can import all the operating system functionality it needs.

Right... but how do modules know what to imports to call?

They target WASI (the WebAssembly System Interface), which is an entirely separate specification which standardises a set of OS-like capabilities as well known imports. In simple terms: the module asks for functions defined by WASI, and the host provides implementations for the current platform.

WASI is nascent in comparison to Wasm, there have been three iterations of it so far, preview 1,2 and 3 and you can infer from the naming this is not the endgame.

Preview 1 is the broadly supported baseline that works with today’s stable Wasm runtimes (Wasm 3.0). It covers file I/O, clocks, random, etc., but it lacks networking.

Preview 2 and 3 are largely complete but they unfortunately depend on types from The Component Model...

Chasm supports WASI Preview 1 today via the excellent wasi-emscripten-host but you have to wire the imports yourself. I will automate this once we get something complete that works with stable Wasm but for now I'm busy working on some other "things" I think will have more impact.

Closing Thoughts

Despite all the rough edges and limitations, I think we’re trending in the right direction. Chasm makes interacting with the Wasm of today feel seamless. It’s Kotlin Multiplatform from the ground up, you can write one module and run it across web, iOS, and Android whilst programming against the same consistent interface.

For the more curious you can check out the Kotlin Multiplatform example project here!

Free android lint perf

CharlieTap — Wed, 27 Aug 2025 18:12:42 +0000

Want your Android lint check to run a little faster? Have an Android project which doesn't support Android Wear (WearOS) devices?

Add the following to your lint.xml

    <issue id="InvalidWearFeatureAttribute" severity="ignore" />
    <issue id="SquareAndRoundTilePreviews" severity="ignore" />
    <issue id="TilePreviewImageFormat" severity="ignore" />
    <issue id="TileProviderPermissions" severity="ignore" />
    <issue id="WatchFaceEditor" severity="ignore" />
    <issue id="WatchFaceForAndroidX" severity="ignore" />
    <issue id="WatchFaceFormatDeclaresHasNoCode" severity="ignore" />
    <issue id="WatchFaceFormatMissingVersion" severity="ignore" />
    <issue id="WatchFaceFormatInvalidVersion" severity="ignore" />
    <issue id="WearableActionDuplicate" severity="ignore" />
    <issue id="WearableConfigurationAction" severity="ignore" />
    <issue id="WearStandaloneAppFlag" severity="ignore" />
    <issue id="WearSplashScreen" severity="ignore" />
    <issue id="WearRecents" severity="ignore" />
    <issue id="WearPasswordInput" severity="ignore" />
    <issue id="WearMaterialTheme" severity="ignore" />
    <issue id="WearBackNavigation" severity="ignore" />

What the helly?

Whilst profiling the lint task on an Android project I noticed that around 5% of overall time taken could be attributed to Android Wear checks. This was weird as the project didn't have support for Android Wear!

The longest running Wear related lint detector was the following

WearDetector        2846 ms

Looking up the source for this you can see it's a base class which other detectors can inherit from.

Some detectors correctly use the base class to only register interest in ast symbols if wear is enabled. However most don't, and that means these detectors run even on non wear projects.

WearDetector itself parses the merged manifest associated with your projects in order to determine if they support wear devices. However this call is not cached, meaning every implementor of WearDetector which calls the function isWearProject causes the linter to reparse the manifest.

In order to avoid a detector running you must ignore all the checks they register, ignoring one is not sufficient. The above xml does just that for android wear related checks.

WearDetector        0 ms

If you're wondering about the profiler I used, it's here. It's not very well maintained tbh and I had to rewrite parts of the project to make it work. It also depends on a proprietary JVM profiler which costs money... but theres a trial if you're keen

Emulating classes with functions in Kotlin for maximum performance 🚀

CharlieTap — Mon, 07 Oct 2024 04:59:46 +0000

If you're building quality software in Kotlin, you'll undoubtedly be using classes and dependency injection to ensure your code is testable.

And you'd be correct to do so! In fact, 99.9999% of the time I would say that's always the right approach to take. But sometimes it isn't... You see, there are certain drawbacks to this style of programming, more specifically drawbacks surrounding the maximum performance of your programs.

Let’s take a look

Generally, if you’re following the Single Responsibility Principle, you’ll have one class for every ‘behavior.’ Your programs become deeply nested graphs of classes composed of one another. But classes are not zero-cost abstractions; they introduce overhead, and as you’ll see later, this overhead translates to a significant number of instructions beyond the functions the classes expose. Worse still, they require allocation, which can mean a system call, increased GC pressure, and potentially an O(N) search across the heap to find an appropriate spot for their associated data.

It gets worse if your class extends an interface, this guarantees dynamic dispatch. You can think of this as another layer of indirection, it involves chasing a pointer through a v-table just so you can address the code you want to run.

You pay these aforementioned costs for every class you create, so this effect is compounding!

There's a lot more to touch on here surrounding CPU architecture changing a lot since the naissance of object oriented programming and Java but I want to keep us on track.

Now don't panic! I said you're almost certainly doing the right thing and I mean it. In most everyday applications these overheads are in the nano/microsecond range. This delay is likely imperceivable to your customers and certainly not something you should be sacrificing the ergonomics of you codebase for!

But the project I've been working on for the past year is bit different...

Introducing Chasm. A WebAssembly interpreter built on top of Kotlin Multiplatform

Now chasm is not any old software project, its a web assembly interpreter, and being an interpreter its goal is to translate the instructions it receives into the minimal amount of instructions for the underlying cpu.

For example in web assembly we have an instruction:

i32.add

and if the interpreter was doing the absolute minimum we would see something like this on ARM.

add w0, w1, w2

Theres actually a little bit more to this as web assembly is a stack machine and we would have to pop the operands from the stack but its easier to explain like this.

You can imagine at some point all interpreters boil down to a loop executing an instruction.

We’re going to walk through a contrived example where we have classes and interfaces that aim to simply add two numbers. Though this is a bit silly, we should be easily able to identify the add instruction and thus recognise pretty much everything else as overhead.

Let's start with a class that's responsible for doing the adding:

interface Adder {
    fun add(x: Int, y: Int): Int
}

class AdderImpl: Adder {
    override fun add(x: Int, y: Int): Int = x + y
}

And now, let’s do some composition using dependency injection, as we normally would when writing modern Kotlin, to construct another class.

interface AddInstructionExecutor {
    fun add(x: Int, y: Int): Int
}

class AddInstructionExecutorImpl(
    val adder: Adder,
): AddInstructionExecutor {
    override fun add(x: Int, y: Int): Int = adder.add(x, y)
}

Finally lets add a main function where we construct and invoke the executor.

fun main(x: Int, y: Int): Int = AddInstructionExecutorImpl(AdderImpl()).add(x, y)

We're going to use Romain Guys fantastic Kotlin-Explorer project to inspect the generated assembly. Please give it a star as it's an awesome bit of kit!

So first the AdderImpl

Okay not too bad, just the add instruction alongside returns for the initializer and add function. And now for the AdderInstructionExecutorImpl

Oof 7 instructions and 1 branch in the initializer, and 20 instructions for the add function... let's see how that affects main

47 instructions and 8 branches! Thats the cost we're paying for our abstraction and we're only going through two layers of indirection. You can imagine how this scales within deep dependency graphs.

So the question is can we avoid this? maintain some abstraction and keep our code testable?

The answer is yes! kinda... there's some tradeoffs ... lets take a look

Adder implementation and interface

typealias FastAdder = (Int, Int) -> Int

inline fun FastAdder(x: Int, y: Int) = x + y

The first thing you'll notice is that we are no longer using an interface, instead we opt for a typealias. Alongside this we have swapped the class out with an inline function. If you have a keen eye theres already a tradeoff here, without a class or interface we've lost a concrete type, any function which takes two ints and returns on could satisfy our alias.

So does it make any real difference?

We've saved an instruction! Thats definitely worth compromising our type system 🤣 Hold on we're getting there...

AdderInstructionExecutor implementation and interface

typealias FastAddInstructionExecutor = (Int, Int) -> Int

fun FastAddInstructionExecutor(
    x: Int,
    y: Int,
) = FastAddInstructionExecutor(x, y, ::FastAdder)

internal inline fun FastAddInstructionExecutor(
    x: Int,
    y: Int,
    adder: FastAdder,
) = adder(x, y)

So again a typealias rather than the interface but this time we have two functions oddly? the second of which is inlined? What's happening here. Well.. This is very manual dependency injection, the first function is the one you would call, without dependencies and also the function you would use in places where the typealias is expected. The second function is the actual implementation, all the dependencies are extracted into parameters so its entirely testable. It's very important for the second function to be inline, as you'll see from the following assembly

As you can see, the function call is actually identical to FastAdderImpl, the compiler has simply inlined it and it does nothing extra. The second function however has a lot more going on, this is because the compiler is unaware of what function will be given at runtime and thus have to deal with invoking the function reference. Fortunately this second function is unused by our program.

Finally lets turn our attention to the main function, you can probably see where this is going...

fun fastMain(x: Int, y: Int): Int = FastAddInstructionExecutor(x, y)

Just 2 instructions! And ultimately this makes sense, everything else is just abstraction that we've added to make our program easier to maintain.

Cool! So we're able to emulate classes, perform dependency injection, and create abstractions using functions whilst achieving maximum performance. But it could get better right? After all we have the following tradeoffs:

We've lost the unique type of the class and interface
We are hardcoding our dependencies, potentially in multiple places
We use two functions to emulate dependency injection, this a bit of a song and dance

However, the ergonomics of the above approach may change in the future due to forthcoming updates to the Kotlin language. For example

Context receivers

Context receivers allow us to separate the "context" of a function call from its arguments. Theoretically if the compiler can resolve those dependencies and they are immutable then it may be able to provide the same inlining we see in the above approach. This is very hand wavy and probably doesn't work but kinda like this

@JvmInline
value class ExecutorContext(val adder: FastAdder)

context(ExecutorContext)
inline fun FastAddInstructionExecutor(
    x: Int,
    y: Int,
) = adder(x, y)

Anyway, I hope this breakdown brought you something new! I appreciate you're unlikely to be doing this in your day job, but think of it as another tool in your tool belt.

I wrote this post on a flight from London to Tokyo, with spotty WiFi and not a lot of sleep, you'll have to forgive any typos. If you like this style of content give it a like and if you're super kind give my repository a star as its goes a long way! I'll have a blog post out in the not to distant future talking more about the interpreter itself and how it might change the way you build your applications

Charlie

Making my concurrent algorithm 6000% better 🚀

CharlieTap — Sun, 29 Oct 2023 20:11:11 +0000

Would you trade a little bit of memory for a whole lot of concurrency?

This is the concept behind a concurrent data structure I've been implementing in my Kotlin Multiplatform library.

The data structure is known as LeftRight and it's here to give you an alternative to those pesky locks that everyone wraps around shared mutable state.

I'll explain

What is LeftRight?

LeftRight is a concurrency primitive, it allows you turn any mutable data structure into concurrent version of itself.

For example... Have a mutable set you need to be thread safe?

Voilà

val sharedSet = LeftRight<MutableSet<T>(::mutableSetOf)

Or more likely you have mutable HashMap ...

val sharedMap = LeftRight<MutableMap<T>(::mutableMapOf)

Or any other data structure you may want to share, LeftRight is generic over T and just requires a constructor for T to work.

Thats cool but why would I bring in your library as another dependency to my project when I can just wrap my data in a lock?

Well you'd be saying goodbye all of your concurrent performance if you did that. Locks don't scale. LeftRight doesn't use locks, at least not for coordinating reads and writes.

How can your library be safely exposing state whilst allowing reads and writes to access the same memory address, thats impossible?

You're right thats impossible...

What???

Maybe the picture above can give you a clue...

Nope? Okay...

How do we LeftRight?

At its core LeftRight is incredibly simple, it consists of two copies of a given data structure and an atomic pointer. The atomic pointer works like a traffic warden at a fork in the road, directing read traffic to one data structure and write traffic to the other.

So we have 2x the memory footprint?

Probably not no, Kotlin is a pointer heavy language, data structures tend to store references to objects rather than the objects themselves. So what we end up with is just two times the amount of pointers.

The beauty of LeftRight lies in its ability to allow reads to progress without using locks or even asking them to wait. And this isn't an easy feat!

The problem

Imagine we have a LeftRight<MutableSet>, this means we will have two MutableSets internally, we'll call them L and R for short. Initially the atomic pointer is directing writes to L and reads to R.

A write comes in and we update L.

Now we somehow need to let readers know about the change, so we redirect the pointer such that L is now accepting reads and R is now accepting writes.

But we haven't applied the change from before to R yet, so no problem right we just apply it to R and we're good?

Nope, this isn't safe, because we don't know if readers have departed from R yet. Maybe they read the pointer just before we redirected it and are now about to read from the side we also are about to write to ... Somehow we need to signal to writes that reads have departed without using traditional lock/wait based solutions like mutexes or semaphores.

LeftRight has a very clever solution to this problem, the algorithm goes something like this:

We create a global array of counters (these are just 32 bit Ints)

val counters: Array<Counter> = arrayOf(maxReaderParallelism)

When a read comes in:

We increment our counter
We read from the data structure designated by the atomic pointer
We increment our counter again

Given each reader thread has its own index into the global array and thus its own private counter, we can infer that there is only ever one thread writing to the counter. If there is only one writer then we do not need any locks or waits. In fact the counters needn't even be atomic as a CAS loop would never fail, we do however need to mark them as volatile to ensure all threads see the events in the order they happened and that the compiler doesn't rearrange our code in weird and wonderful ways.

For writes:

We perform the write on the data structure designated by the atomic pointer
We switch the atomic pointer so now reads will see this update
Now we need to wait for readers to depart from the old read side (the new write side)
We perform the write again on the new write side of the data structure

So how do we determine that readers have departed?

The is where the counters come in and the magic happens. Remember reads increment the counter twice, once before and once after a read. When the counter is odd, we know a reader is actively in the map, but when its even we know its finished its work and the following read will have to go through the atomic pointer again. So, we filter out all the counters that are odd and then we loop on them, waiting for them to change, not necessarily become even, but change. Any change means that the counter will have moved onto the new write side of the data structure.

Whats with the weird sizing on the counter array?

The size of this array dictates the amount of reader threads left right supports, this is one of the constraints on my implementation. If we allowed the array to grow or be resized then we would have wrap it in a lock. Instead we attempt to anticipate the upper bound on threads in your program, we do this using the same logic Kotlin coroutines does for thread pool sizing.

Why LR?

I created LR for two reasons:

There are no Kotlin Multiplatform concurrent datastructures
Locks are not a suitable replacement in 2023

Kotlin Multiplatform is still in its infancy, at present there are no Kotlin Multiplatform concurrent data structures. You can't just simply just reach for ConcurrentHashMap like you could when you were working within the JVM ecosystem, everything depends on what targets your project supports.

In the absence of the wealth of JVM based libraries, I see more and more people reaching for locks. Whilst this may be perfectly acceptable for a given use case, I don't believe generally replacing concurrent data structures with locks is a smart move in 2023.

Locks strip our multicore CPUs of their parallelism super powers through contention, and contention isn't something thats going to go away, quite the opposite actually it's going to augment. Computers are gaining more cores year on year, high end consumer chips now have up to 24 cores, that will shortly rise to 32 and within the next decade we will undoubtedly see core counts that breach the 100 mark. Do you really want 99 cores waiting on your mutex? We'll see the performance ramifications of this later on.

LeftRight gives you a scalable alternative to locks and positions itself generic concurrent data structure with more than acceptable performance.

LeftRight is not a direct competitor to the highest performing concurrent data structures, like ConcurrentHashMap for example. ConcurrentHashMap is a bespoke concurrent HashMap implementation, its not a wrapper around a HashMap, it is the HashMap. LeftRight however is a generic wrapper around a data structure, as always with indirection we incur the cost of chasing pointers. LeftRight is also entirely ignorant to the workings of the thing its wraps, it knows just two invariants, that a reads will occur and that writes will occur. For this reason it's unable to provide domain specific optimisations.

Less talk more benchmarks

Time to put my money where my mouth is, I've been moaning a fair bit about locks, lets dive into some benchmarks.

We're going to compare:

Javas ConcurrentHashMap (The gold standard 👑)
LeftRight (The new kid 🤠)
ReentrantReadWriteLock (The best locks have to offer 🔒)

I've been generous here, rather than use a standard mutex I've gone with a read write mutex in order to really get the best out of locks.

The below benchmarks are all run on an Apple M1 Max, the benchmark suite can be found in the repo here

ReentrantReadWriteLock

Operation	Single Threaded	Multi Threaded
read throughput	0.0069 ops/ns	0.0018 ops/ns
read avg time	14 ns/op	5,783 ns/op
write throughput	0.0789 ops/ns	0.0056 ops/ns
write avg time	13 ns/op	227 ns/op

Single threaded benchmarks look pretty good as you would expect of a lock under no contention but it's not looking so great for the multithreaded side of things. The average time of a read is 400x slower and overall throughput around 6x less when accessing the hashmap from multiple threads.

LeftRight

Operation	Single Threaded	Multi Threaded
read throughput	0.0808 ops/ns	0.6449 ops/ns
read avg time	12 ns/op	16 ns/op
write throughput	0.0381 ops/ns	0.0324 ops/ns
write avg time	28 ns/op	437 ns/op

LeftRight shows a remarkable improvement in both single threaded and multi threaded benchmarks. More importantly the multithreaded throughput of reads is showing an 8x linear improvement which checks out given my CPU has 8 performance cores. Writes are as expected given they are serialised with a mutex.

ConcurrentHashMap

Operation	Single Threaded	Multi Threaded
read throughput	0.1406	1
read avg time	7 ns/op	9 ns/op
write throughput	0.0093	0.0073
write avg time	10 ns/op	1,398 ns/op

As expected reads are blazingly fast and ahead of both the previous two implementations, but interestingly LR comes within 80-90% which is better than we could have hoped for a data structure with inherently more indirection. Writes seem to struggle but this is likely a quirk a of the benchmark writing to the same key and thus the same bin (ConcurrentHashMap uses bin level locking), in reality writes would have a much fairer distribution and I would expect Concurrent HashMap to come out on top.

Here's a graph depicting all the above courtesy of ChatGPT

What you came here for

LeftRight is remarkably performant for a generic concurrency primitive. But things weren't always this way... lets take a look at an earlier implementations benchmark

Operation	Single Threaded	Multi Threaded
read throughput	0.0716 ops/ns	0.0107 ops/ns
read avg time	14 ns/op	534 ns/op
write throughput	0.0368 ops/ns	0.0376 ops/ns
write avg time	27 ns/op	442 ns/op

You can see from the above, the performance takes a nose dive with the introduction of more threads/cpu cores. I expected this to be the case for mutations, after all we have a single writer policy which is enforced using lock.

But for reads this didn't make sense at all, not only is the average time of a read 50x slower but the throughout is 7x less??? I'm using a lock-free/wait-free algorithm for reads! Wtf??? Theres no shared memory and nothing for threads to contend on???

Well ...

It transpires that it's not enough to have threads guard their own private memory when accessing shared resources. Due to the nature of modern CPU cache architectures, even adjacent memory locations can be a source of contention.

It's like contention through osmosis 😭 😭

This phenomenon, known as false sharing, occurs when multiple threads, running on different cores, access different variables that reside on the same cache line. Even though they're not directly sharing data, the mere fact that their data resides closely in memory means they effectively compete for the same cache line. This can cause performance degradation as threads constantly invalidate each other's cache lines, even if they're not accessing shared data directly.

Honestly I just keep coming back to this quote over and over again in my career...

There are only two hard things in Computer Science: cache invalidation and naming things.
-- Phil Karlton

So how do we fix this?

The problem stems from the original implementation of my global counter array

val globalEpochArray = Array<AtomicInt>(64)

When the arrays allocated, it will more than likely allocate those 64 AtomicInt objects next to one another on the heap.

AtomicInt is just a wrapper around a 4 byte integer, and every class has a 12 byte (on a 64 bit JVM) object header, making one allocation of AtomicInt take 16 bytes of space.

So we now have a 16 * 64 byte block of contiguous memory allocated on the heap.

When thread 1 loads the first counter (which should be just [0 - 16] bytes) it in fact loads an entire cache line worth of memory, on my laptop (M1 Max) an L1 cache line is 128 bytes. So now the core running thread one has the first [0 - 128] bytes and thus the first 8 counters inside of its cache line.

When thread 2 tries to load the second counter it does the same, now thread 2 has counters 2 through to 10 in its cache line.

Now what happens when thread 1 mutates its counter?

It invalidates the cache line of up to 8 other cores, and when poor thread two comes round to trying to change its counter, it now has to load it from RAM again.

To give a rough idea of impact heres the load times between L1 CPU cache and RAM:

L1 Cache Lookup: 0.5 to 1 nanoseconds.
RAM Lookup: 50 to 100 nanoseconds

This explains my average read time went from 14ns to 534ns

So how do stop this?

With this abomination

class PaddedVolatileInt(initialValue: Int) {

    @Volatile private var p1: Long = 0
    @Volatile private var p2: Long = 0
    @Volatile private var p3: Long = 0
    @Volatile private var p4: Long = 0
    @Volatile private var p5: Long = 0
    @Volatile private var p6: Long = 0
    @Volatile private var p7: Long = 0
    @Volatile private var p8: Long = 0
    @Volatile private var p9: Long = 0
    @Volatile private var p10: Long = 0
    @Volatile private var p11: Long = 0
    @Volatile private var p12: Long = 0
    @Volatile private var p13: Long = 0
    @Volatile private var p14: Long = 0

    @Volatile var value: Int = initialValue

Essentially we pad our counter object such that fits perfectly inside an L1 cache line.

12 byte header + (14 * 8) + 4 = 128 bytes

This is really isn't an ideal solution, padding should be dynamic such that on cpus with smaller cache lines are accommodated for but well we don't have this level of control from Kotlin.

But with that change our multithreaded throughput and average time fall dramatically.

Operation	Before (Multi Threaded)	After (Multi Threaded)	% Change
read throughput	0.0107 ops/ns	0.6449 ops/ns	+5927.10%
read avg time	534 ns/op	16 ns/op	-97.00%
write throughput	0.0376 ops/ns	0.0324 ops/ns	-13.83%
write avg time	442 ns/op	437 ns/op	-1.13%

The value of throughput now grows linearly with the amount of cores available, thus you would see different increases/decreases depending on the machine.

Rapping up

You can find my repository containing LeftRight here, you'll notice that the repo is actually called cachemap. That's because the repo contains two libraries, LeftRight and CacheMap, the latter is essentially just a batteries included LeftRight<MutableMap>.

Both LeftRight and CacheMap are experimental at the moment so please proceed with caution despite the positive looking benchmarks. Be extra careful with the suspending variants as these haven't yet been benchmarked nor optimised.

Theres lots of optimisations to be made, writes suck more than need to at the moment. I have a rough design of a write batching algorithm which should amortise the cost of the lengthy writer wait step.

I'm currently in the process of publishing the artifacts in Maven Central (the process is not fun 🤯), hopefully by the time you read this I will have instructions on the repo of how to pull the each artifact.

Acknowledgements

I learned of LeftRight in a youtube stream from Jon Gjengset a while back, Jon is in my opinion the best comp sci content creator out there. Please go like and subscribe to his channel if you're keen on learning!

You can also find what I believe to be the first paper on the primitive here.

All Illustrations were created by incredible artist that is Dalle 3

A Blazing Fast 🔥 Kotlin Native Cross Compilation Environment

CharlieTap — Thu, 11 May 2023 19:13:59 +0000

This post was written over the course of one evening, it's a brain-dump of information I've accumulated recently. You can expect the following:

Me continuously going on a tangent and failing 🤣
A full development environment for cross compiling Kotlin Native 🔥🔥🔥
Some real bleeding edge Docker techniques 🔪
Remote development inside a container from Intelli 🤯
Emojis 🤓 🤖 🦄

Lets set the scene

As part of an upcoming project involving io_uring (a Linux system IO library) I needed to create an environment capable of compiling a Kotlin Native application on my shiny Apple Silicon machine. Given my OS is macos and I'm trying to develop an application for Linux I understood this would require some form of cross compilation.

So I took a look at the Kotlin Official Site and found this snippet

While cross-platform compilation is possible, which means using one platform to compile for a different one, in this Kotlin case we'll be targeting the same platform we're compiling on.

Easy peasy, so I set up my application and configured one target for my native application as follows:

linuxArm64("native")

We're just going to build for now, obviously the binary produced couldn't run on a mac.

./gradlew linkDebugExecutableNative

And .... nothing, this is going to be a theme throughout the course of this blog post. If you run this on any mac you will receive no artifacts what so ever. I wasted an hour or so trying different permutations before realising that whilst cross compilation of some sort may be possible in Kotlin, mac to linux right now isn't happening.

To VM or not to VM

Given we clearly aren't capable of compiling and running this application on our own machine we're going to need a linux environment. This is where Docker comes in, with Docker we can spin up containers with whatever OS we want, additionally those containers can also target different cpu architectures (Why would I wanna do that ... you'll see).

My reason for reaching for Docker over spinning up a VM (yes i know Docker for mac using a vm behind the scenes) is because Docker makes it easy to try different OS's quickly. Additionally Docker allows me to mount my filesystem into the containers filesystem which I hoped would allow me to develop on my machine and just have the build and run of my application happen inside the container.

So my first decision, what base image should I go for. In the interest of speed I took a look at what Gradle themselves had built on their Dockerhub repo. I figured this would at least mean I wouldn't have to worry about configuring both Gradle and the JDK and I could just focus on the libs I need for my application. If you've worked in this space before you'll know that images extend other images and typically you end up with the following set of operating systems to choose from:

scratch (this is no OS so not useful)
alpine (this uses musl c and is very small)
debian
ubuntu

I like small containers and Gradle had an alpine based image with the JDK 17 built in so I went for this. It's worth noting I'm on ARM machine and therefore this will pull an ARM container by default.

Before I setup a full environment I wrote a quick Dockerfile to validate it built my "Hello World" linuxArm64 application correctly.

FROM gradle:8.1.1-jdk17-alpine

RUN apk update && \
    apk add --no-cache \
    build-base \
    liburing-dev

COPY . /app
WORKDIR /app

RUN ./gradlew --stacktrace linkDebugExecutableNative


CMD ["build/bin/native/DebugExecutable/koru.kexe"]

Lets try to build that

docker build --platform linux/amd64 -t koru-dev -f Dockerfile  .

But ... no bueno. It turns out that you cannot compile Kotlin native applications on a linux arm host.

Okay no problem we change the Dockerfile a little

FROM -platform=linux/amd64 gradle:8.1.1-jdk17-alpine

We change our Kotlin Native target also

linuxX64("native")

Boom! Another crash 😔

This time the culprit is root of the problem is JDK 17. I'll admit I didn't fight this one too much and just downgraded to JDK 11.

FROM -platform=linux/amd64 gradle:8.1.1-jdk11-alpine

💥 💥 💥

Still nothing, it turns out that decision to use a container based on musl c came back to bite me. The Kotlin native toolchain uses glibc in places, meaning a musl c based container would be missing a bunch of necessary libs.

I had a quick stab at adding some compat

RUN apk update && \
    apk add --no-cache \
    build-base \
    liburing-dev \
    gcompat \

💥 💥 💥

Same result, I iterated some more and actually got pretty close to making this work (I actually think its possible) but eventually chose to cut my losses and went with an ubuntu base image.

FROM --platform=linux/amd64 gradle:8.1.1-jdk11

✅

And with that I had some thing build! Albeit slowly, but building! Does its run?

docker run --rm -ti --platform linux/amd64 koru-dev

✅

The beautiful "Hello World" graces my terminal

The time you enjoy wasting is not wasted time

Okay its slow but building the source into a container image was never the original plan, the original plan was to mount my filesystem at runtime and have the build/execution happen when the container runs.

Given I'd already wasted a ton of time on this surely it wasn't time for another risk right? Well I'm stupid so thats what I did 🤣.

You see I've worked with containers for a long time, and the pattern I planned to use of mounting the filesystem at runtime has some flaws. You see working this way you end up with slightly different containers between dev and your other environments (where the binary itself is baked in) and I'd recently learned about a way to potentially get great dev environment performance whilst creating an image I could use agnostic of environment.

Lets give it a go

FROM  --platform=linux/amd64 gradle:8.1.1-jdk11

RUN apt-get update && \
    apt-get install -y \
    build-essential \
    liburing-dev


COPY . /app
WORKDIR /app

RUN \
    --mount=type=cache,target=/app/.gradle,rw \
    --mount=type=cache,target=/app/bin/build,rw \
    --mount=type=cache,target=/home/gradle/.gradle,rw \
    gradle --stacktrace linkDebugExecutableNative


RUN \
    --mount=type=cache,target=/app/bin/build,rw \
    find /app/bin/build/ \
        -maxdepth 4 \
        -type f -executable \
        -exec cp {} /usr/local/bin \;

CMD ["build/bin/native/DebugExecutable/koru.kexe"]

The new lines add cache volumes during the build phase of the container. So our first run came out at around 1 minute 30, and the second ... 1 minute. That isn't half bad. But I noticed in the logs that the Kotlin Native compiler Konan is being downloaded every time. After some fiddling I found a solution

# For some reason konan seems to wipe the $HOME/.konan folder between builds
# By defining this env variable konan will write cache out to a folder we are already using for caching
ENV KONAN_DATA_DIR=/home/gradle/.gradle

✅ 🚀

45 Seconds! To build that is, a second or so to run. That's pretty fast, but remember this is Hello World and 45 seconds is still a poor development cycle. A large portion of the build time can be attributed to the Gradle daemon warming up and bootstrapping a JDK, something that wouldn't be an issue if we were running back to back builds on a running container...

I had to compare it to the OG solution, for science! worst case we can use these image build time optimisations in our prod container.

So what does the other solution look like?

FROM  --platform=linux/amd64 gradle:8.1.1-jdk11

ENV KONAN_DATA_DIR=/home/gradle/.gradle

# /home/gradle/.gradle is already declared a volume in the base image
#VOLUME /app/bin/build

WORKDIR /app

RUN \
    --mount=type=cache,target=/var/cache/apt \
    apt-get update && \
    apt-get install -y \
    build-essential \
    liburing-dev

CMD ["gradle", "-t", "runDebugExecutableNative", "--debug"]

However we will be doing more than just building and running, we'll also have to mount our local filesystem into the container. The container won't look to run our program and exit either, instead it will build our project continuously, recompiling and rerunning tasks every time the files change

docker build --platform linux/amd64 -t koru-dev -f Dockerfile  .

docker run --rm -ti --platform linux/amd64 -v "$(pwd):/app" koru-dev

💥 💥 💥

Back to things breaking 😭, and its this line

CMD ["gradle", "-t", "runDebugExecutableNative", "--debug"]

The short of it that is that is the command that gets run when the container starts and more specifically runs a Gradle task every time your project files change. Unfortunately the file watching impl is broken (I never found a good reason as to why) and the this results in the task being run 1000 times per second. Okay Plan B, we will just launch the container with a shell and connect to the shell ourselves, issuing our own commands.

A minor change

CMD ["/bin/bash"]

✅

We're back in action. I connect to the shell and issue my Gradle command.

./gradlew runDebugExecutableNative

The first run is slow, this is expected. The second however takes around 45 seconds... How could it be this bad given we have a warm Gradle daemon ready to go?

It transpires both our container and emulated file system are running slow. My first tip of this post, enable Rosetta 2 translation for x86 images in the Docker settings!

Remember we're running x86 images now, Docker supports running Rosettas translation over them ahead of time to get them running natively 😍.

Whilst you're in the settings I want you to also enable the Virtio FS which can be found under the General tab. This will give a speedier filesystem for our bind mounted project code.

With those changes made, I restart Docker entirely and issue my command again inside of the running container

./gradlew runDebugExecutableNative

✅ 🚀🚀🚀

19 Seconds !!! thats absolutely rapid and really no different than Kotlin Native builds on my own machine.

This approach is definitively faster, it seems the Gradle Daemon being up and running makes all the difference.

Thats a wrap? Right? Well ....

If you're only using the standard native lib yes, but I need c interop for io uring, and it turns out Intellij is unable to use the bindings that get generated inside of the container despite the fact they share the same filesystem.

😠😠😠🤬🤬🤬😭😭😭

Another tangent 📐

It's okay, I can work with this... the container is working and I've invested a ton of time optimising it, so let's not throw that away. IntelliJ is struggling because its outside the container observing files being generated on a linux machine.

What if we could get it on the inside? its possible for IDE to connect to remote environments and run a backend inside the container whilst the frontend runs on the host. You might have heard of Intelli J connecting to Github Codespaces or other remote development environments, why couldn't it connect to our docker container?

Well it can!

I make some changes once again to the cross compilation development container. This time adding an ssh server and making this the containers process.

FROM  --platform=linux/amd64 gradle:8.1.1-jdk11

ENV KONAN_DATA_DIR=/home/gradle/.gradle

WORKDIR /app

RUN \
    --mount=type=cache,target=/var/cache/apt \
    apt-get update && \
    apt-get install -y \
    build-essential \
    liburing-dev \
    openssh-server \
    sudo

RUN useradd -rm -d /home/ubuntu -s /bin/bash -g root -G sudo -u 1001 test

RUN echo 'test:test' | chpasswd

RUN service ssh start

EXPOSE 22

CMD ["/usr/sbin/sshd","-D"]

I build and run the container one final time, do note how I'm now binding port 20 on my local to that of the container on the run command

docker build --platform linux/amd64 -t koru-dev -f Dockerfile  .

docker run --rm -ti --platform linux/amd64 -v "$(pwd):/app" -p 22:22 koru-dev

It started okay lets try and connect to it. Inside IntelliJ I go to File > Remote Development...

Enter the following credentials, remember we made a user called test with a password of test when we built the Docker container

After what feels like an eternity I'm greeted with an IDE, with working intellisense on my C bindings !!!!!!!

Final thoughts

Despite wasting a week trying to get this working, I have in the process learned a lot and opened up some opportunities for the future.

I did take some time to tidy up after myself, I moved the cross compilation Dockerfile into a file called Dockerfile.dev and made a second file for production called Dockerfile which has all the optimisations I worked on originally. I also made a small Makefile to save myself writing the same docker commands over and over

BINARY_NAME=koru.kexe
IMAGE_NAME=koru

BUILD_ARG_BINARY=--build-arg BINARY=$(BINARY_NAME)

.DEFAULT_GOAL := help
.PHONY: build build-release build-verbose debug run help

build:
    docker build --platform linux/amd64 $(BUILD_ARG_BINARY) -t $(IMAGE_NAME) .
build-dev:
    docker build --platform linux/amd64 -t $(IMAGE_NAME)-dev -f Dockerfile.dev .
build-release:
    docker build --platform linux/amd64 $(BUILD_ARG_BINARY) --build-arg MODE=release -t $(IMAGE_NAME) .
build-verbose:
    docker build --platform linux/amd64 $(BUILD_ARG_BINARY) -t $(IMAGE_NAME) --progress=plain .
debug: build
    docker run --rm -ti --platform linux/amd64 $(IMAGE_NAME) /bin/bash
run: build
    docker run --rm -ti --platform linux/amd64 $(IMAGE_NAME)
run-dev: build-dev
    docker run --rm -ti --platform linux/amd64 -v "$(CURDIR):/app" -p 22:22 $(IMAGE_NAME)-dev
run-release: build-release
    docker run --rm -ti --platform linux/amd64 $(IMAGE_NAME)

help:
    @echo "Available targets:"
    @echo "  build         Build the Docker image in debug mode"
    @echo "  build-release Build the Docker image in release mode"
    @echo "  build-verbose Build the Docker image in debug mode with verbose output"
    @echo "  debug         Build (if necessary) and run the container attaching a bash shell"
    @echo "  run           Build (if necessary) and run the Docker container"
    @echo "  help          Display this help message"

With this I just run the following to spin up the environment

make run-dev

If you're interested in any of the above I've made the project I'm working on public here. Just please bare in mind this repository is part of a larger project so things may change.

I think thats a wrap, I hope you learned something, I sure did!

Synking all the things with CRDTs: Local first development

CharlieTap — Wed, 12 Apr 2023 09:39:20 +0000

So you want to build a local first application? You want the application to work both offline and online seamlessly with no interruption to the end user?

How hard could it be right?...

For the past few months I've been working on a library in this space, something quite novel that I think offers an avenue for simplifying local first development and the challenges it presents. But before I introduce Synk I think its worth exploring this problem space, taking a look at why its particularly tricky and what existing solutions are out there. This blog post should serve as a good primer for anyone looking to get into local first development and CRDTs.

Local first applications work offline, they work in isolation, the application shouldn't need to be connected to the internet in order to function. From a technical perspective this is grand departure from traditional client server applications.

In order to work detached from the network, the client device must be capable of computing all the states that would typically be derived by the server... thats a lot business logic on the client. So the clients FAT, so what? Well that aside you've just decided to create a distributed system and with that comes an entire field of computer science worth of problems!

But wait how did this happen?

Let me explain, in a traditional client server architecture, the server is gospel, the state it holds is the truth and entirety. We'll skip over the fact that most servers are a facade hiding a deeper distributed system, the net of distribution we cast extends only as far as the server infrastructure, not the clients themselves. Whereas in a distributed system, the totality of the state is not found in a single node (like the server) the state is the aggregation of the state found across all the nodes in the system. Now that the client application can work and evolve in isolation from the network (and importantly the centralised server state), we've undoubtedly waded into distributed waters.

Thats Cap! ...Theorem

Okay so we're saying that local first applications are actually complex distributed systems, we should probably classify what type. If you ever had the pleasure sitting through a CS lecture on DS then you've probably come across CAP Theorem. It a nutshell it states that distributed systems can have at most two of the three following properties:

Property	Description
Consistency	Every read receives the most recent write or an error.
Availability	Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
Partition tolerance	The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes

Having at most two of the above properties means we end up with systems that are either CA, CP or AP. Can you guess what property doesn't hold in local first applications? ...

It's Consistency, we're unable to guarantee strong consistency because we want them to work offline, they can't possibly return the most recent write if they can't coordinate with other nodes in the system. Instead they are what we call "Eventually Consistent", once they have reconnected and synchronised the latest changes. In my opinion dropping the C is a blessing, solutions that guarantee strong consistency involve complex consensus algorithms... If you've ever studied Paxos or Raft you'll know why I say this is good thing.

Okay so we're AP, Local first applications are AP distributed systems, cool, well whats does that mean? Well its means we'll face a certain subset of problems and we can lean on a subset of solutions. Lets have a look at the type of problems we will face.

Problem	Description
Replication	How do changes get propagated to other clients without being lost?
Conflict resolution	What happens when two devices change the same piece of data whilst offline? Who's change wins and why?
Causal Ordering	Who changed what when exactly? Can you really be sure on a timeline of events? What if the local clocks on the clients are out of synk?.. oops I mean sync

Spoiler! Synk concerns itself with the bottom two. After all it's quite likely you already have made up your mind on how you want propagate data, for example what transport (Http, RPC, Sockets) and serialization format you want to use in your application. So replication is on you... but we have solutions for the rest. It's about time I introduce one of the most common solutions in AP distributed systems and exactly the thing you'll need to replicate.

CRDTs

"It's Cee Arr Dee Tees not Serdts"

CRDTs also known as Conflict-free replicated data types are the mechanism we will use to achieve "Eventual Consistency" in our AP distributed system.

In simple terms, they're data structures that cannot conflict, each (and there are many!) has an algorithm that lets them deterministically merge updates. For almost all basic data structures you can think of (maps, sets, lists etc) there will exist CRDT implementations, often with different quirks but all guaranteeing conflict free merging of updates.

Now if we're to use proper Distributed systems terminology these updates which are sent between nodes to keep the system up to date are known as "Messages". CRDTs are categorised by whats contained in the messages they produce.

Category	Behaviour
State	State based CRDTs will send messages that include the entire current state of the CRDT. This can be thought of as being similar to a POST/PUT request
Operation	Operation based CRDTs will send messages that include the operation and parameters that need to be applied. This can be thought of as being similar to an RPC call.
Delta	Delta based CRDTs will send messages that contain only the values that have changed in the CRDT. This can be thought of as being similar to a PATCH request

And thats not all, CRDTS are ACID 2.0. Another acronym if you hadn't guessed, let me break that down for you:

Associative

a + b = b + a

This means it doesn't matter if you merge a into b or b into a its the same

Commutative

(a + b) + c = a + (b + c)

This means it doesn't matter how you group the merges

Idempotent

a + a + a + b = a + b

This means you can merge the same CRDT multiple times but the result doesn't change

Distributed

???

In all honesty this is here to make the acronym work 🤣

The above properties are incredibly powerful and make the job of replication in AP systems far far simpler. It doesn't matter if you accidentally send the same CRDT twice, it doesn't matter if you send updates out of order, it doesn't matter if you merge client A's updates into client B's before merging client C's... The system will always reach the same deterministic result (Thats the whole eventually consistent thing I mentioned).

Now you might be thinking, thats a lot of rules surely it's hard to create something that satisfies all those constraints. But honestly its simpler than you might think, I'm going to run you through the two Synk uses under the hood and you'll see what I mean.

Alright first up my favourite, and arguably the simplest...

Ladies and gentleman please welcome G-SET!!!

A G-Set or Grow-only Set is simply a Set without the remove operation, meaning it grows and never shrinks. Lets have a look at its behaviour in psuedocode:

val gset = GSet<String>()
gset.add("foo") 

// println(gset) 
// [
//  “foo”,
// ]

gset.add("foo")
gset.add("bim")
gset.add("bar")

// println(gset) 
// [
//   “bar”,
//   “bim”,
//   “foo”,
// ]

You can see from above it's associative and commutative because the set has some intrinsic ordering which makes it agnostic to insertion/grouping order. It's idempotent because being a set it disallows duplicates. A G-Set is ACID 2.0 compliant making it a verified CRDT...

The elephant in the room at this point is that it doesn't seem particularly useful. But like all data structures in computer science CRDTs can and should be composed together to model larger structures. A G-set is a collection, so now we need the collection to hold something useful, another CRDT.

Without further Ado I introduce LWW-Map

It stands for "Last write wins map" and it's a key value map with a couple of stipulations.

The value has to be a tuple where one of the items is always a timestamp. On map insertion if the key already exists then the existing timestamp is compared with the new timestamp and the victor is the most recent.
You can't delete entries, thats generally a recurring theme in CRDTs but well address that shortly.

You can get an idea of its behaviour from the following psuedocode:

val map = LWWMap()
map["foo"] = Pair(“Ali G”, 123)

// println(map) 
// {
//  “foo” : { “value”: “Ali G”, “ts”:123 },
// }

map["foo"] = Pair(“Ali G is da best”, 234)
map["foo"] = Pair(“Ali G is da best”, 234)
map["foo"] = Pair(“Ali G is not da best”, 112)

// println(map) 
// {
//   “foo” : { “value”: “Ali G is da best”, “ts”:234}
// }

Maps ultimately allows us to serialize structs/data classes, so now combining both a G-Set and an LWW Map we can model collections of classes.

James Long took this observation further in his talk CRDTs for mortals, and stated that we can actually make tables in databases behave like G-Sets of LWW-Maps with a few tweaks. Stay with me hear I appreciate this is a leap of faith but we'll run through it.

Tables with primary keys can behave like G-Sets so long as we never remove entries, a table is a collection of rows after all. But what about modelling a row as an LWW Map? Let's take a look at an example

id	fn	ln	age
1	bob	smith	35
2	jack	jones	28

The rows in the table above couldn't possibly satisfy the conditions of an LWW-Map because they're missing the associated timestamp data. So let's add that

id	fn	fn_ts	ln	ln_ts	age	age_ts
1	bob	12345	smith	12345	35	12345
2	jack	12345	jones	12345	28	12345

Notice the id in the table above is the only column without timestamp meta, this is because it functions as the key in the map and is immutable, immutable values cannot change and thus the meta isn't needed. For the rest, if we check the current timestamp on insertion and use this to determine the new value and timestamp then our row behaves as an LWW Map, turning our table into a CRDT.

But I need to delete things? 😅

I thought you'd say that, well I have a solution, its imperfect but it works.

Tombstones

Tombstones are also known as soft delete flags outside the realms of distributed systems. It's a reasonably simple concept, add a flag to signify whether a record has been deleted, use this same flag to ignore deleted records in subsequent queries.

id	fn	fn_ts	ln	ln_ts	age	age_ts	del	del_ts
1	bob	12345	smith	12345	35	12345	0	12345
2	jack	12345	jones	12345	28	12345	1	12345

I've got 99 problems but a conflict ain't one

CRDTs are an awesome solution to a difficult problem, personally I find them to be the most natural solution in the distributed systems domain, but I must admit I have problems with existing libraries that leverage them.

CRDTs are usually implemented in two ways, either at the domain level, which requires objects to implement some mergeable interface, or at the data level, in the form of a very bespoke (often not general purpose) datastore. The common denominator an intrusive piece of technology which has a large impact on the shape and design of the application you are creating.

What if this wasn't the case? What if we could have conflict resolution as a pluggable piece of software? Something we could bootstrap existing systems with to give them distributed powers.

Synk

A Kotlin Multiplatform CRDT library for local first applications.

Synk is a state based CRDT library, it monitors state changes over time using a special type of timestamp which is capable of tracking events in a distributed system. Synk maintains this data in its own persistent key value storage database locally on each client,

It's important to understand Synk does not store your data, merely it stores timestamps associated with it. Remember that timestamp data we added to the table? Well Synk tracks that separately, leaving your data layer entirely untouched, allowing you to build apps with the same technologies you always have.

At its core Synk is comprised of just two functions!

Synk.outbound(new: T, old: T? = null): Message<T>

Whenever a new record/object is created or updated in your application locally, give Synk the latest version and the old version (if applicable) and Synk will return you a message. This message needs to be propagated to all other clients.

Synk.inbound(message: Message<T>, old: T? = null): T

When receiving a Message from another client application, inbound needs to be called. This function will perform conflict resolution for you and return an instance of your object ready to be persisted.

Synk is deliberately minimal, you give it objects and it gives you messages, propagate those messages to the right clients and your application will have no conflicts, it's that easy!

A distributed database... but you bring the database

I'm excited to see what people come up with using this technology, the innovation in the CRDT space right now is crazy. Ultimately I had an idea with this project of creating a minimal library which gives the tools to turn a local database into a distributed one, all whilst exposing some but not all of the distributed primitives. The result is something quite novel, I hope the idea of using CRDTs to resolve your conflicts has piqued your interest.

There's a bunch of detail I chose to omit in this blog, more for brevity than anything else. However theres a lot more information on the repository if you're interested! I've learned so much building out this project, I hope this blog has taught you a thing or two yourself, if you have any questions feel free to comment.

References

A huge inspiration in all the above was James Longs presentation CRDTs for mortals, if you haven't seen it already go and watch its awesome

All images were generated by Dalle-2, you can see the prompts I used below

Image	Prompt
	“An oil painting of 4 databases trying really hard to synchronise with each other”
	“An oil painting of a monkey attempting to solve the most complex puzzle imaginable”
	“Ali G replicating himself into multiple people as an oil painting”

Making PR checks pretty by example

CharlieTap — Mon, 14 Feb 2022 21:08:30 +0000

If you've worked on a project with any form of continuous integration before, then you'll likely be familiar with the concept of checks that run when you submit your code to version control.

For those that aren't aware, typically tasks are run in response to submission/updates of code, these tasks can run tests, linting checks and a plethora of other code verifications. In most setups, branches are usually protected by a pull review process, which runs checks on proposed code changes before they are reviewed and potentially merged into the codebase.

In this post I'm going to walk you through setting up a simple continuous integration task using GitHub Actions, which runs the popular Ktlint library and adds the output back onto the Pull Request in a way that's easy to digest using a tool called ReviewDog.

Ktlint meets Gradle

Whilst it's possible to run Ktlint from CLI, I prefer to introduce it in the form of a Gradle task. Providing it in this way allows all the configuration (albeit none in this case) to rest within the project itself, guaranteeing you and your teammates will have the same output when running it. Another benefit is that you can hook this task into the existing android linting task, just saving you one less thing to run in your CLI.

My task of choice:

kotlinter

This particular plugin is very performant, it uses gradles incremental build system, and parallelises the linting work using the Gradle Worker API, making it very fast if you have a multi module workspace. Ultimately these checks are run often, so saving 10-15 seconds adds up over the course of a year.

I won't cover the setup here, you can follow the link above or even checkout my example application to support this blog post which is found at the bottom.

Once you think you are setup, run the following task to verify:

gradle lintKotlin

If you have any errors appear, there exists another task which may be able to automatically correct them for you:

gradle formatKotlin

Be aware there are certain things this task will be unable to fix for you and therefore you'll have to rectify them yourself using the feedback you get.

Making this task run on Pull Requests

To run any workflow in GitHub Actions you simply place a yaml file in the folder .github/workflows relative to the project root with the instructions you want to run.

For example we could put the following:

`.github/workflows/code-quality.yml`

name: Code Quality
on: [pull_request]
jobs:
  ktlint:
    name: Run ktlint
    runs-on: ubuntu-latest

    steps:
      - name: Clone repo
        uses: actions/checkout@master
        with:
          fetch-depth: 1

      - name: Ktlint
        run: gradlew lintKotlin

This would suffice, in running the linter and providing a check on PR which would validate the code. However we want to do something which produces more meaningful feedback like this:

...

The pretty part ...

So we know how to:

Run ktlint with Gradle
Run the Gradle task from CI

Now we need to figure out how to use review dog to comment on the pull request with the results of the gradle lint task.

So it's important to understand the output of that linting task. By default, kotlinter will create report files, one for each module you run it on. You'll find these reports inside the modules generated build folder (i.e if you run it on app, you'll find the report in app/build/...). Whilst its possible to aggregate these files and pass their contents onto review dog, it also writes any errors it finds to stderr. With a little bit shell scripting you can tailor this output ready to be piped into ReviewDog and save yourself the task of aggregating all of the reports.

So lets look at the shape we need the listing report to be in for review dog to accept it:

"reviewdog accepts any compiler or linter result from stdin and parses it with scan-f like 'errorformat', which is the port of Vim's errorformat feature."

In simple terms, each line we feed into standard input of review dog must have a particular format, we can dictate that format to some extent, but ultimately we have to conform to errorformat.

For example if we tell review dog through the command line argument "efm" to expect the format:

%f:%l:%c:%t: %m

Review dog will the expect each line to be in the following format:

{file}:{line number}:{column number}:{error type}: {message}

Thankfully the stderr from the lintKotlin task is largely already in this form.

We just need to filter for the lines we care about

grep 'Lint error > '

Tweak them to replace the text 'Lint error > ' with the error type which in this case can simply be 'e' for error.

sed 's/ Lint error > /e: /g'

You can read more about the types and meanings of the format substitutions here

Et Voila

`.github/scripts/check.sh`

#!/usr/bin/env bash

./gradlew lintKotlin 2>&1 | grep 'Lint error > ' | sed 's/ Lint error > /e: /g' | reviewdog  \
-name="ktlint" \
-reporter=github-pr-review \
-efm="%f:%l:%c:%t: %m" \
-level=error \
-filter-mode=nofilter \
-fail-on-error

Something to be aware of here, if you want scripts to be executable when they are run inside of CI, you'll need to instruct git of the executable permission. I.e git update-index --chmod=+x .github/scripts/check.sh

Putting it all together

Lets update the yaml file from earlier to look like the following:

`.github/workflows/code-quality.yml`


name: Code Quality
on: [pull_request]
jobs:
  ktlint:
    name: Run ktlint
    runs-on: ubuntu-latest

    steps:
      - name: Clone repo
        uses: actions/checkout@master
        with:
          fetch-depth: 1

      - name: Install Review Dog
        uses: reviewdog/action-setup@v1
        with:
          reviewdog_version: latest

      - name: Ktlint
        env:
          REVIEWDOG_GITHUB_API_TOKEN: ${{ secrets.github_token }}
        run: .github/scripts/check.sh

Without going into too much detail, we added a new job to install review dog, and another to run our bash script we wrote earlier (You don't have to configure the secret, this secret is included for you).

I've put an example project here for anyone that gets stuck and wants to copy this across, you'll also see the PR mentioned in the post on this repo.

Gradle versions catalog integration

CharlieTap — Fri, 28 Jan 2022 18:57:05 +0000

This post is a continuation from another, I'd advise reading that prior to tucking it this. You can find it here

A versions what?

Gradles versions catalog is new feature in modern versions of Gradle that allows you to centralise your projects dependencies, plugins and their respective versions into a single location. (though its possible to have more than one).

If you've worked with projects that have more than one module, you'll know the pain of trying to keep all of your dependencies in alignment across all of the modules. The solution prior to the versions catalog introduction, was to create files inside the special Gradle buildSrc folder which could then be referenced in your build.gradle files. Whilst there's nothing terribly wrong with this approach, Gradle advocates for the versions catalog, and it has some additional benefits which you can leverage in certain conditions.

For example, imagine you work in a large team, on a big project, and you have several repositories which are essentially modules for the same application. Rather than having different catalogs in each repository, you could publish the catalog to a repository like Maven and consume it in each repository, ensuring that even separate repos have their dependencies aligned. You can read more about this here

Okay enough spiel, lets see it what it looks like

The catalog is written in a config language called toml, I've put a cut down implementation below just to showcase the sections.

`build.gradle`

[versions]

compileSdk = "31"
minSdk = "23"
targetSdk = "31"

appVersionCode = "1"
appVersionName = "1.0"
applicationId = "com.x.y"

kotlin = "1.5.31"
android-build-tools-plugin = "7.1.0"

hilt-core = "2.40.5"
hilt-integrations = "1.0.0"

[plugins]

plugin-kotlin = { id = "org.jetbrains.kotlin.jvm", version.ref = "kotlin" }
plugin-kotlin-android = { id = "org.jetbrains.kotlin.android", version.ref = "kotlin" }
plugin-android = { id = "com.android.application", version.ref = "android-build-tools-plugin" }
plugin-android-lib = { id = "com.android.library", version.ref = "android-build-tools-plugin" }

[libraries]

hilt-core = { module = "com.google.dagger:hilt-android", version.ref = "hilt-core"}
hilt-compiler = { module = "com.google.dagger:hilt-compiler", version.ref = "hilt-core"}
hilt-integrations-work = { module = "androidx.hilt:hilt-work", version.ref = "hilt-integrations"}
hilt-integrations-compiler = { module = "androidx.hilt:hilt-compiler", version.ref = "hilt-integrations"}
hilt-integrations-compose = { module = "androidx.hilt:hilt-navigation-compose", version.ref = "hilt-compose"}


[bundles]

hilt-deps = [ "hilt-core", "hilt-integrations-work", "hilt-integrations-compose" ]
hilt-compilers = [ "hilt-compiler", "hilt-integrations-compiler" ]

Thats... different

It is, but at a high level its very simple, there's four sections:

A section for declaring versions
A section for declaring plugins
A section for declaring libraries
A section for declaring bundles (basically a logical grouping of libraries)

You place this file in your projects top level gradle folder and you should be ready to use it.

How to reference the different sections

For plugins

You can reference them when loading them into the classpath as discussed in the prior article.

That looks like this:

`build.gradle`

plugins {
    alias(libs.plugins.plugin.kotlin.android) apply false
}

Remember the apply false, you don't want to apply it here, it needs to be applied in each module you need it in respectively.

Applying inside the module using the alias notation requires Gradle 7.4 which is currently at rc-01, if you're willing to upgrade early you can do this.

`app/build.gradle`

plugins {
    alias(libs.plugins.plugin.android) 
}

The default is to apply, thus when not putting apply at all it will apply the plugin on that module.

If you are not in a position to upgrade and for Gradle versions < 7.4, you can do this:

`app/build.gradle`

plugins {
    id "org.jetbrains.kotlin.android"
}

For versions

Individual versions can be referenced in your build.gradle files, it allows you to do things like this:

`app/build.gradle`

android {

    compileSdkVersion libs.versions.compileSdk.get() as Integer

    defaultConfig {
        applicationId libs.versions.applicationId.get()
        minSdkVersion libs.versions.minSdk.get() as Integer
        targetSdkVersion libs.versions.targetSdk.get() as Integer
        versionName libs.versions.appVersionName.get()
        versionCode libs.versions.appVersionCode.get() as Integer
    }
...

For libraries

For libraries its equally simple

`app/build.gradle`

dependencies {
    implementation libs.material
}

For bundles

Bundles provide a great way to group related dependencies and save you some line space, similarly to bundles they can be implemented like so:

`app/build.gradle`

dependencies {
    implementation libs.bundles.hilt.deps
    kapt libs.bundles.hilt.compilers
}

Fin

Next up I'll be looking at tidying up Gradle files using precompiled Gradle script plugins..

Upgrading to Gradles modern plugin configuration

CharlieTap — Wed, 26 Jan 2022 21:40:37 +0000

Android studio Bumblebee became stable this week and with it comes a bunch of new features and updates. One of which being that new projects created in Bumblebee have a modernised Gradle configuration. You can read about this here

Whilst this is great for new projects, it's important to keep legacy projects up to date, and migrating from old to new is great way to understand the new approach (I say "new" here, but the syntax has in fact been around for quite some now, it just hadn't been widely adopted).

Why Upgrade?

A quick scan of the Gradle docs goes on to explain the following:

Alongside this, generally its good to keep your configuration compliant with the latest version of Gradle, it eases the migration path when moving between versions.

How did we used to do it again?

Historically Android projects would use the buildscript DSL to load load plugins into the classpath, you would do this is your top level build.gradle file.

It should look something like this:

`build.gradle`

buildscript {

    repositories {
        google()
        gradlePluginPortal()
    }

    dependencies {
        classpath 'com.android.tools.build:gradle:x.y.z'
        classpath "org.jetbrains.kotlin:kotlin-gradle-pluginx.y.z"
    }
}

Theres two things happening inside this block:

It's declaring a set of repositories, these are repositories which will be searched when Gradle looks for the plugins you have declared. This is similar to the list of repositories you declare when you are configuration your dependencies, however these repositories will only be searched when Gradle looks for plugins.
It's declaring a set of plugins you wish to use in your project and loading a particular version for each into the classpath.

Applying the plugins in your application

Inside your :app modules build.gradle you would use the now legacy apply plugin syntax to enable the plugins on that particular module.

`app/build.gradle`


apply plugin: 'com.android.application'

If you've ever worked on projects that have more than one Gradle module you realise the benefits of the separation above as you'll be able to enable plugins on a module by module basis, and lock the plugin versions to a consistent version across all of your modules.

Okay but what does it look like now

Well, the part where you declared the repositories for the plugins... that's moved, its now in your top level settings.gradle file

`settings.gradle`


pluginManagement {
    repositories {
        gradlePluginPortal()
        google()
        mavenCentral()
    }
}

This makes more sense when you realise the repositories for your dependencies are also now moved the settings.gradle file

`settings.gradle`


dependencyResolutionManagement {
    repositoriesMode.set(RepositoriesMode.FAIL_ON_PROJECT_REPOS)
    repositories {
        google()
        mavenCentral()
        maven { url 'https://jitpack.io' }
    }
}

Loading the plugins

Loading the plugins (but not applying them), still takes place in the top level build.gradle file

`build.gradle`

plugins {
    id 'com.android.application' version 'x.y.z' apply false
    id 'org.jetbrains.kotlin.android' version 'x.y.z' apply false
}

Enabling the plugins

This takes place in whatever module you want to apply the plugin on, for example:

`app/build.gradle`


plugins {
    id('com.android.application')
    id('org.jetbrains.kotlin.android')

}

Thats all?

Well as with everything new, there's some gotchas here to be aware of. The most important of which is that not all plugins will work the new syntax.

Notice how before you would say something like:

apply plugin: 'kotlin-android'

and now you say something like:

id('org.jetbrains.kotlin.android')

The difference is the latter uses a particular id, and only plugins which are configured with Gradle Project Market Artifact will work out of the box with this syntax.

In particular I have found one popular plugin at this time which is not compliant and that is the Dagger Hilt Plugin.
You can track the support for it here, it's quite likely by the time you read this post that it will already have been released.

Is there any point if not all plugins work

Well there's a workaround, and for the plugins you do configure, you'll theoretically optimise your build time by adopting those.

Workaround

We'll use the case of Dagger as I imagine this to be the most common. For future proofing I have put the future syntax, commented out in the examples below.

Put the following in your top level build.gradle

`build.gradle`


// it will look like this once Dagger publishes the marker
// id 'com.google.dagger.hilt.android' version 'x.y.z' apply false

// for now
id("dagger.hilt.android.plugin") apply false

Then in your settings.gradle the following:

`settings.gradle`


pluginManagement {
    resolutionStrategy {
        eachPlugin {
            if( requested.id.id == 'dagger.hilt.android.plugin') {
                useModule("com.google.dagger:hilt-android-gradle-plugin:x.y.z")
            }
        }
... repository management config
}

Finally apply the plugin in your app modules build.gradle

`app/build.gradle`


plugins {
//  id 'com.google.dagger.hilt.android' in the future
    id 'dagger.hilt.android.plugin'
}

The above solution should work for any legacy Gradle plugin which lacks the marker you need.

Cool, so anything else?

This is the first in a three post series, the following two will cover:

Integration of the new plugin system and Gradles' new version catalog system, you can find it here
Creating your own pre compiled script plugins for tidying up your build.gradle config and give an example showcasing config for the popular the popular versions gradle plugin