How Kosshi Handles Large Outlines

Kosshi is built around keeping everything in one outline. Projects, journals, and tasks all go into the same outline, not separate files. Used this way, the outline grows to thousands, then tens of thousands of rows.

Kosshi uses native frameworks for input and drawing. But that alone is not enough as an outline grows. The app also needs to avoid checking every row after every action.

This article explains the internal work Kosshi does to keep interaction responsive as an outline grows.

Work that gets slower as the outline grows

Whenever you type or collapse a row, Kosshi chooses what to show and updates row positions. If that work finishes quickly, the screen responds smoothly.

Problems appear when some of that work scales with the number of rows.

For example, finding "the third visible row from the top" looks simple, but a naive implementation walks the outline from the beginning — "this one is hidden by a collapse, skip; this one is visible, first; next one visible, second." Double the rows and the work doubles; ten times the rows, ten times the work. In programming this is called O(n), where n is the row count.

Even when the work for one row is very small, scanning every row takes longer as the outline grows. Work that goes unnoticed in a small outline can eventually show up as stuttering or a delay between input and response.

Kosshi uses performance tests with large outlines to find work that takes longer as the row count grows.

The goal is not only to make each step a little faster. It is to avoid work that scans every row on every interaction.

Only part of the outline is visible

The outline has a few properties:

• You usually zoom into the part you care about
• Collapse hides descendants that are not relevant right now
• Only a small part of the outline fits on screen at once

Even with a large outline open, only a small fraction is on screen. The rest is either folded, outside the scroll range, or outside the zoom. Kosshi draws mainly what is visible on screen and skips folded or zoomed-out sections as a group. After an edit, it focuses its updates on the parts affected by that change instead of rebuilding the entire outline.

That requires a way to find the needed rows quickly.

Finding the needed row with a SumTree

Drawing only what is visible requires Kosshi to find quickly which row belongs at each scroll position. Counting from the beginning every time would get slower as the outline grows.

Kosshi uses an internal index called a SumTree for this job. Much as a table of contents lets you jump to a chapter, a SumTree divides rows into groups and skips groups on the way to a target. Each group also records information such as its row count and height on screen, so Kosshi does not need to inspect every row inside it.

The name SumTree follows the one used by the Zed code editor.¹ Kosshi adapts the same type of structure for an outliner.

Skipping whole groups

The SumTree is separate from the outline hierarchy you see on screen. You do not need to be aware of it while using Kosshi. It exists inside the app to handle many rows efficiently.

The structure is shown below.

To find a row far down in the outline, Kosshi skips groups that do not contain the target instead of counting from the top. It narrows the search from larger groups to smaller ones until it reaches the row.

This is why the work of finding a row does not grow at the same rate as the total number of rows.

Collapsing and zooming

Collapse and zoom can change a large part of the visible outline at once.

Suppose a parent has 10,000 descendants. A naive implementation visits all 10,000 to mark them hidden the moment you fold. The more rows there are, the longer the wait becomes.

Kosshi finds those descendants as one range and removes them from the screen together. It does not need to update every unrelated row that follows. When the section is expanded, Kosshi adds back the rows that need to appear.

Zoom works in a similar way by skipping everything outside the selected branch. Rows far from the screen do not have to be measured precisely at first. Kosshi measures and draws them precisely only as they approach the screen.

Information that does not need to be recounted

The information stored for each group helps with more than finding rows. Kosshi keeps totals such as the number of rows, completed rows, and their combined height on screen.

After an edit, only the related groups need to update their information. Kosshi does not have to recount the entire outline whenever it needs a total or position.

This work stays out of sight, but it is part of what keeps a large outline responsive.