Dev Diary #3: Column store for 2 million pops
In short: MKA Engine keeps the world as tables and columns: all values of a column sit one after another in memory (struct of arrays). All columns live in one region allocated once when the game loads, so a game day asks for no new memory. In our simple measurement summing 2 million units was 8 to 20 times faster in the column layout than in a layout where each unit is a separate object.
The world of a grand strategy game is a huge ledger: 30,000 locations, 250 countries and 2 million population units, each with dozens of facts. The engine reads and writes this ledger from start to end every game day. How the ledger is laid out in memory largely decides how smoothly the game runs. This diary covers MKA Engine's data store: the world as it sits in memory.
Box by box, or column by column?
Think of a population unit: its location, number of people, wealth, satisfaction, culture, religion. The usual way in programming is to keep each unit as a separate "box" carrying all of these facts. The worker on the left of the picture works this way: asked to "add up the people of the whole population", it goes to each of 2 million boxes and takes one number out of it. If the boxes are scattered in memory, each one is a separate trip.
Our way is like a spreadsheet. The world is made of tables ("locations", "countries", "population units") and each table of columns. The difference: all values of a column sit one after another in memory. The people counts of 2 million units form a single strip; adding them up is reading that strip from start to end in one pass, like the worker on the right. A processor reads data that sits in a row very fast, because it fetches the next value before it is asked for.
| Criterion | Box by box (each unit an object) | Column by column (MKA Engine) |
|---|---|---|
| What sits side by side in memory | All facts of one unit | The same fact of all units |
| "Add up all people counts" | Each box is visited separately | One strip is read from start to end |
| Facts not being read | Carried along with the box for nothing | Never touched |
| Splitting across threads | Who writes to which box must be tracked | The strip is cut into pieces, each piece belongs to one thread |
How much does it matter?
We saw it with a simple measurement. We ran the same calculation, adding up the people counts of 2 million population units, in three layouts: columns, boxes lined up one after another, and boxes scattered in memory. We put about ten facts in each box, as a real game would.
Adding up the people of 2 million units (ms)
| Label | Time |
|---|---|
| Columns (MKA Engine) | 1.59 |
| Boxes in a row | 12.95 |
| Scattered boxes | 31.64 |
The column layout came out about 8 times faster than boxes in a row and about 20 times faster than scattered boxes. The reason is simple: with a column the processor reads only the number it needs; with a box it carries nine unread facts along with every number, and with scattered boxes it goes to another corner of memory for each box. A game day is made of hundreds of passes like this.
The whole world in one region
The engine places every column of every table in one contiguous region of memory. Tables and columns are declared once when the game loads (we call this the schema); the size of the region is computed from the schema and allocated once. After that a game day asks for no new memory. The "zero allocations in the day loop" measurement in diary #0 comes from here.
- 2,000,000 population units (rows)
- 28 bytes four facts per unit: location, people, wealth, satisfaction
- 56 MB the whole population table
- 62 MB peak memory use of the 600-game-year run
Every column has a known type and a fixed size: numbers are 8 bytes, dates and small identifiers 4 bytes, smaller values 2 or 1 bytes. Text and variable-length data do not enter the region. So the position of a row is found from its row number with a single multiplication.
Where this region lives was a decision too. The formulas of mods run inside WebAssembly; instead of copying data to them piece by piece, we built the region on top of a shared WebAssembly memory. We measured: on light work that fits in the cache, copying pieces was 2.2 to 3.3 times slower; shared memory was as fast as plain Rust on heavy work and 12 to 34 percent slower on light work. The cost, too: WebAssembly's multi-threaded memory is a second-tier feature in the runtime we use, and security fixes are not backported to old versions.
The changed mark
Next to each row sits a single bit: "I changed this step". When a system writes to a row, the bit is set. At the end of the step the world's fingerprint (described in Diary #2) is recalculated only for the chunks that contain changed rows; unchanged chunks keep their old print. On an ordinary day when part of the 2 million rows changes, this means skipping most of the work.
The life of entities
In a strategy game the world is not fixed: armies are raised and disbanded, characters are born and die, countries fall. For this some tables are "dynamic": their rows are added and removed during the game.
Identity: seat and generation
An entity's identity is made of two numbers: the seat it occupies and which occupant of that seat it is, its generation. When a character dies the seat becomes free; when a new character takes the same seat the generation goes up by one. A record that still names the dead character as "my enemy" resolves not to the new character but to "nobody", because the generation does not match even though the seat is the same. An empty identity never matches a living entity.
Adding and removing at the end of the day
If something wants to add or remove an entity during a day, the request waits and is applied together at the end of the step. So all systems of a day see the same world; one cannot remove a row while another is calculating with it.
What happens to records that point to a removed entity is written up front in the column that defines the link:
| Rule | What happens | Example |
|---|---|---|
| Cascade | The linked record is removed too | When a country falls, its armies disband |
| Clear | The link becomes "nobody" | When a ruler dies, the "advisor" field is emptied |
| Keep | The old identity stays and resolves to nothing | A war's "started by" record stays for history |
If wanted, a copy of removed rows is written to a hidden archive table. A dead ruler leaves the game, but the record is not lost for the family tree and the history screen.
If a dynamic table outgrows its place in the region, its capacity doubles. This is one of the rare moments when memory is allocated, and it happens not once a day but once each time the table doubles in size.
Grouped tables, relations and indexes
Some questions are asked very often: "which population units are in this location?", "who are this country's vassals?", "what are this location's neighbours?". The store has three tools for these:
- Grouped tables: The rows of a table are kept in order of a key; for example population units in the same location sit side by side. "The population of this location" is reading one range. When rows move they are re-sorted at the end of the day; if few rows moved only those are put back in place, if many moved all are sorted at once. Both ways produce the same bytes.
- Relations: Links between two entities, such as "who is whose vassal", live in their own tables and can be searched from both ends. Relations that never change during the game, such as map adjacency, are built once at load as a compressed list.
- Indexes: An index is kept for reverse questions like "who belongs to this army". An index is not part of the world: it is not written to saves, and it is rebuilt from the columns at load. A debug build compares the index with a fresh rebuild at the end of every step.
Script variables
The game and mods also have small facts of their own: "has this country called a crusade", "this character's rivals". Opening a column for every entity in advance would waste memory, so these variables live outside the columns in a separate store, ordered by owner. They can be a number, a flag, an entity, a list of entities or a key-value map. An emptied list is removed, so the state in the store does not depend on the order in which it was written. When an entity is removed, only its own variables are removed.
Parallel access within a day
A game day is split across several threads. To make that safe, each system declares once, when the game loads, which tables it reads and which it writes. The engine checks at load that systems running in the same stage will not read what another writes; during the day no checks are made and no memory is allocated.
During the day a strip is cut into pieces and each piece is taken by a single thread; that thread writes only to the rows of its own piece. If a system wants to tell another row something (for example "send 10 soldiers to this location"), it leaves a message; messages are applied at the end of the stage in row order. That order does not change whatever the number of threads.
Limits
- Fixed-size data: Only fixed-size numbers and identifiers enter the region. Text and variable-length data live elsewhere.
- Growth is rare but not free: When a dynamic table outgrows its capacity, the capacity doubles and memory is allocated at that moment. The zero allocations we measured are in a fixed-size world.
- Writing means declaring: A system cannot write to a table it did not declare. That is an extra rule for mod authors.
- A variable holding a removed identity: If a script variable points to a removed entity, the identity stays but resolves to nothing; checking that is the content's job.
- Scope of the measurement: The layout comparison is a simple measurement of one calculation; it does not replace the cost of a real game day.
Frequently asked questions
What is struct of arrays (SoA)?
Instead of keeping all fields of an object together, each field is kept in its own array for all objects. Work that reads the same field for many objects uses the processor cache much better.
Is this an ECS (entity component system)?
A similar idea, but not the same. In MKA Engine data lives in tables and columns the game declares at load; systems declare in advance which tables they read and write, and the engine checks parallel work at load.
Does a removed character's identity get mixed up with a new one?
No. An identity is a seat and a generation number. A new character in the same seat has a different generation; records holding the old identity resolve to nobody, not to the new character.
Is memory allocated during the game?
In a fixed-size world a game day allocates no memory. When a dynamic table outgrows its capacity, the capacity doubles; memory is allocated at those rare moments.
Sources and records
External sources:
- Wikipedia, AoS and SoA (box and column layouts) (opens in a new tab)
- Wikipedia, Locality of reference (opens in a new tab)
- Wikipedia, Sparse matrix: the CSR format (opens in a new tab))
Our internal records (the engine repository is closed, so we cannot link them):
- Entity model decision: seat and generation identity, removal rules, archive, script variables, applying at the end of the day.
- Column store decision: one contiguous region, changed bits, slot tables, the variable store, indexes.
- Layout measurement: 15 October 2026, 2 million units, three layouts; taken while the computer was very busy.
- 600-year run: 14 October 2026, scale world, peak memory with
/usr/bin/time -v.
In the next diary we will cover the wheel that turns on top of this store: how a game day moves forward and how the work is shared across cores.
If you have questions or ideas about this diary, write to us from the contact page. For an overview of the engine see the MKA Engine page, and for all diaries the Developer Diaries list.