Running unmodified Doom in the SQLite bytecode language

A few days ago we announced we're expanding the scope of what Turso is. Turso was born with the goal of rewriting SQLite in Rust, with a modern architecture and expanded feature set. It adds features like concurrent writes, change-data-capture (CDC), Live Materialized Views, among others.

But along the way, we realized something incredible: one of the underappreciated features of SQLite is that, deep down, it is a Virtual Machine: it compiles SQL to its own bytecode language, which is then executed in the processor. That language is not unlike other bytecode languages like .NET, WASM, or the JVM. Except it is specialized in database operations. It has high level operations like "open a btree". In SQLite, this is all hidden as part of the monolith: it is an implementation detail, not exposed or specified. Turso implements and extends that bytecode. So our ambition grew. What if we could turn that into the LLVM of databases?

Our ambition is to be able to reimplement other databases using the same infrastructure. We have already merged initial support for Postgres, and others will likely follow (and as a reminder, Turso is an Open Contribution project and we'll take your PR!)

But according to the rules of the internet, something is not really worthy of being called a language or compilation target if it can't run Doom. So we ported Doom to the SQLite bytecode VM, as implemented by Turso, using its extensions. This post will go into the details of how that works.

#Running Doom

First, let's show it working. It is likely work hours for you, and because you are reading a tech blog, whatever you do here counts as work. So here's Doom running natively in the browser (since Turso runs natively in the browser) executing on the Turso bytecode VM. See you in half an hour or more:

I have seen Doom running on databases before. Usually what happens is that you execute the Doom source code as an extension, or use text characters to render scenes of the game. This is different because it really is the actual Doom game, running as if it was a normal SELECT query, in a browser (It also runs natively, and it is a bit faster). The whole source code is here and you can follow along.

We'll now look at all the components that comprise this.

#Codegen

SQLite's VM bytecode language is called VDBE, short for Virtual DataBase Engine. The first step is to compile the Doom C source code into the VDBE. To achieve that, we wrote vdbecc, a C compiler that compiles C to the VDBE. This will never be fast and efficient to execute arbitrary C programs, but that's not our goal here. Our goal is to show that we can map one thing to the other. Writing a C compiler would be crazy, so in the best spirit of "the LLVM of databases", we use the actual LLVM to compile C to the LLVM Intermediate Representation. And that is what gets translated to VDBE. That is used as a backend for LLVM.

The whole architecture looks like this:

#Register allocation

A real CPU has 16 or 32 registers, so every compiler backend pours enormous effort into register allocation: deciding which values live in registers and which get spilled to the stack. It is one of the hardest problems in a backend.

The VDBE's register file is unbounded. It's a growable array, since it is a virtual language. So vdbecc doesn't allocate registers at all. It gives every single SSA value in the entire program its own permanent register, forever.

;; LLVM IR                      ;; VDBE bytecode
%sum = add i32 %a, %b           Add   r_a, r_b -> r_sum

#Instruction adaptations

There are a few fun consequences. The VDBE has no xor opcode, and Doom uses that a lot. The VDBE was built to compare index keys, not to render sprites. We could, of course, add one. And over time, as new database frontends come online, we certainly will. But here, our goal is just to get this shit running, so we synthesize it: a ^ b = (a | b) - (a & b), bit-exact.

Another interesting design decision is calling functions. Real CPUs have dedicated call/return instructions for this. The VDBE has no "call a function" instruction, because SQL has no functions in that sense, but it does have a way to jump into a subroutine and come back, because SQL uses subroutines internally (a subquery gets evaluated by jumping to a block of bytecode and returning a value). Those two opcodes are Gosub (jump somewhere, remember where you came from) and Return (jump back). That is exactly a call and a return. So this:

int y = square(x);

lowers to roughly this:

; put x where square expects its argument
Copy   r_x  -> ARG0
; jump in; LINK remembers where to come back to
Gosub  square, LINK
; read the result back out
Copy   RET  -> r_y

and square itself reads ARG0, does its work, drops the answer into RET, and Returns through LINK. That's the whole calling convention: a handful of fixed registers everyone agrees to use for the arguments, the return address, and the result.

Because the register file is infinite, a normal call pushes nothing to the stack. The only functions that need a real stack are recursive ones (which can be running more than once at the same time), and they save their registers into the Doom memory - but more on that later.

The trickier one is function pointers, which Doom leans on hard. Every monster, barrel, and door in a level is an object with a think field: a pointer to the function that defines its behavior. Function pointers were the standard way of doing OOP-like behavior before Object Oriented languages became a thing, so no surprise that Doom is full of them. The game loop walks every object and calls object->think(object), and which function actually runs is decided at runtime, per object. It's how a single loop drives an imp, a fireball, and a moving platform without knowing anything about them in advance.

On a real CPU a function pointer is just the memory address where that function's code lives, and "calling it" means jumping to that address. But in our world there are no code addresses: the program is VDBE bytecode that lives outside the addressable memory (remember, "memory" is that one BLOB). Functions simply don't have addresses you could store in a variable.

So we do the obvious thing and number them. Function #1, #2, #3, and so on. A function pointer is just that little integer, and it lives in Doom's memory like any other value: when a monster stores a pointer to its think function, it is really storing an integer in that BLOB. To call through it, we take the number and jump to the matching function through a dispatcher.

Now, we're a database, so you would expect us to store the number-to-function mapping in a table and look it up. But that mapping is not data, it is control flow: which code runs next. So it gets compiled straight into the program as a chain of comparisons. At Doom's scale even a linear scan of those would work, but that would bring immense shame upon the honor of John Carmack. So we emit a balanced binary search instead.

As a free bonus, C code that compares function pointers keeps working, because it's now just comparing two integers:

// "is this thing a regular monster?"
if (thinker->function == P_MobjThinker)

Obviously, I have absolutely no interest in writing a demo LLVM target by hand and wanted the clankers to do it. So once the architecture was decided, we landed on a differential test that compiles a corpus of C programs both natively and to VDBE and demands byte-identical output. Doom's framebuffer comes out byte-for-byte identical to the native clang build.

#Memory

Doom is C. C wants a flat address space: pointers, a heap, a stack. Where does that live when your "CPU" is a database engine?

In a table. The entire C address space is a single BLOB, in a single row, of an ordinary table:

CREATE TABLE _vdbecc_mem (id INTEGER PRIMARY KEY, ram BLOB);
INSERT INTO _vdbecc_mem VALUES (1, <64 MiB: zeros + globals + WAD>);

That BLOB is the RAM. Globals start at offset 0x1000; the stack grows down from the top. A C pointer is nothing more than a byte offset into that value.

So what is int x = *p; inside Doom? It's: read a few bytes out of the ram column of that row, at offset p. We open a cursor on the row once, at program start, and every load and store in the whole game is an in-place byte access into that one database value:

;; C:  x = *p  (a 4-byte load)
;; read 4 bytes from the row
BlobRead  cursor=ram, offset=r_p, amount=4 -> r_bytes
;; decode little-endian (x4, shift/or)
get_byte  r_bytes, 0 -> r_x

BlobRead/BlobWrite are the byte-level column accessors, the VDBE backing for SQLite's sqlite3_blob_read/write. The bytes-to-integer codec, get_byte/set_byte, are stock PostgreSQL binary-string functions that already shipped in the engine. SQLite doesn't have those constructs, but we had already added them previously to Turso as we expanded its capabilities beyond SQLite.

And here's the kicker. That BLOB is far bigger than a page, so it spills across the b-tree's overflow pages. The first time we reach into a region, the engine walks that chain, but it caches the page numbers in a flat array as it goes, so every access after that is an O(1) lookup. It is a software page table: the database builds an MMU for Doom's address space, and the reads are served by the same pager that runs your production queries. Doom's working set is paged in and out through a database's storage engine. memcpy is a bare BlobRead + BlobWrite.

The blitter that draws every pixel, dst = colormap[src], is a load feeding a store, which we special-case to shuttle raw bytes across without ever decoding them. That one path is ~80% of the instructions Doom executes, because Doom's memory bandwidth is now literally b-tree page I/O.

Could this be faster, especially if we used optimized and specialized memory instructions? Of course. In fact I tried it just for fun, and got the whole thing to run over 60fps. But the goal here is to demonstrate how the existing bytecode is already powerful enough to do this well, as well as have some fun and some unhingemaxxing. We're not trying to break any records here.

#Rendering a frame is a SELECT that never ends

Now the other direction: how do the pixels get out?

Doom's render loop ends in DG_DrawFrame, which copies the 320×200 framebuffer (256,000 bytes of RGBA) into a global and calls one intrinsic: vdbe_present().

vdbe_present() lowers to a ResultRow, the very opcode a SELECT uses to hand a row back to the client, and then it pauses. Pausing on a row and resuming on the next step is just how the VM already works: every SELECT hands you its rows one step at a time. What is special about Turso is that it is async all the way down (which is what lets it run natively in the browser, as you just did above), so it can also yield in the middle of the work to let the pager do I/O without ever blocking a thread. That is the STEP_IO branch you will see in the loop below.

So the whole game is one long-running statement. You step() it. Each step runs the engine forward until the next vdbe_present(), then hands you a row [ret, frame], where frame is the framebuffer BLOB, streamed straight out of linear memory:

// doomPrepare(IR modules, WAD, ticks, RAM bytes)
const doom = db.doomPrepare(irModules, wad, 20000, 64 << 20);

while (running) {
  // run Doom to the next frame, then yield a row
  const r = doom.stepSync();
  // the pager needs to do I/O
  if (r === STEP_IO) { await db.io(); continue; }
  if (r === STEP_DONE) break;
  // a 320x200 RGBA BLOB, straight from the result row
  paint(doom.row().frame);
  flushInput();
}

Playing Doom is iterating a streaming cursor. The frame is a BLOB column in the result row. The game only advances when you pull the next row. It is, genuinely, a SELECT * FROM doom that emits one 320×200 image per row and is designed never to reach the end of its result set.

#Controls are bind parameters

If frames come out as result rows, input has to go in while the statement is parked between two rows. SQL already has a mechanism for "change a value inside a running statement": bind parameters.

So that is the input device. Between frames, the browser rebinds parameters ?1..?10 on the paused statement. Inside the game, vdbe_fetch_input() reads them with the Variable opcode. The same one that reads ?1 in WHERE id = ?1. ?1 is a sequence number so the game ignores stale reads; ?2..?10 are packed key events, (pressed << 8) | doomkey:

inputSeq += 1;
// ?1: sequence number
stmt.bindIntAt(1, inputSeq);
// ?2: CTRL pressed -> fire
stmt.bindIntAt(2, (1 << 8) | 0xa3);
// resume; this tick sees the shot
doom.stepSync();

You press a key, you are binding a query parameter. Doom's input handler is a WHERE clause.

Is that clean? Probably not. Do I feel ashamed or proud? Perhaps a mix of both. One day, perhaps, I will find forgiveness.

#Loading the program

This is the only point where we made changes to the Turso core. The reason is that there is no interface in Turso to allow you to inject a pre-compiled VDBE program. You can prepare() a SELECT, and the engine will compile it to a VDBE program and run it. But that compiled program is never exposed.

And it is not that such an interface would be a bad idea: there are legit use cases for it, but I was not in the mood to rush one out for the sake of a demo. And the goal was just running the unmodified VDBE bytecode, which we accomplish.

So the one real change to the engine is a small load path: take a vdbecc-built program and wrap it in an ordinary Statement, the same type prepare("SELECT ...") hands back. From the engine's perspective there is no difference between "the program I compiled from a query" and "the program vdbecc handed me." It steps both the same way.

#Bonus: the save file is a SQLite database

One bonus of this architecture: If the entire game state (every monster, your health, the RNG seed, the position of every door) is a row in a table, then saving the game is saving the database. You don't write a serializer. There is nothing to serialize. The state is already in a database.

The demo above runs against an in-memory database, but "in-memory" here is the real pager doing real b-tree operations; pointing that same one-line open call at doom.db instead persists Doom's RAM to disk as an ordinary file. And because Turso is byte-compatible with SQLite's file format, that file opens in anything that speaks SQLite:

$ sqlite3 doom.db 'SELECT id, length(ram) FROM _vdbecc_mem;'
1|67108864

#The LLVM of databases.

Doom was our way to prove to ourselves and the world that yes, this direction works. It is also super cool, and it's been many years since I played it (which in a way made this project take longer, because I was constantly... well... testing it). But this lays the foundation to what we want to do. The Greeks believed the atom to be the smallest entity that all things were made of. Until later we found out that the atom itself is made of its various components.

So in a sense, that is our nuclear path: we're splitting the atom. We're taking the smallest database in the world, and breaking it apart even further, into its subatomic particles. And then reusing the components to build whatever your heart desires.

Our next move? Postgres. Reimagined. Built on this abstraction. That is already merged and will start seeing releases soon. But how about you? The doors of our community are wide open. We want you to build the LLVM of databases with us, and use that to build your dreams.