Dropflow lets you quickly get the size of rich text and paint it later. The separation of those two steps is important: you may have a lot of rich text in different positions (for example, if you’re implementing an infinitely scrollable and zoomable canvas) and only paint the text that’s in the viewport. That means there may be tens or hundreds of thousands of layouts held in memory — indeed, our spreadsheet implementation in CellEngine holds a layout for every unique text value in a cell.
To support hundreds of thousands of layouts in memory, dropflow must use as little memory as possible. Three optimizations to the storage of box areas will be explored here.
Areas
First, some quick background: what is an “area”? We can’t talk about areas without talking about boxes first. Boxes are the main subject of the CSS layout specifications, and they’re roughly equivalent to HTML elements. Areas are rectangles produced by the content, border, or padding of a box. Boxes are the input to layout and areas are the output1.
Areas form a hierarchy similar to boxes. A box’s containing block is a parent box’s content area, though not necessarily the direct parent2.
When a box spans across different lines, pages, or columns, its areas are split into multiple areas for the same box.
Areas in dropflow are represented with the following data structure:
class BoxArea {
parent: BoxArea | null;
box: Box;
blockStart: number;
blockSize: number;
lineLeft: number;
inlineSize: number;
}
I’ll explain each field.
The containing block is the parent of the border area is the parent of the padding area is the parent of the content area. A parent reference is held directly on the BoxArea so that relative coordinates can be turned absolute by a method that takes no arguments. But I realized this field can be used for much more: it will be the subject of the first two optimizations.
The box that produced the area is needed so we can look at the writing mode to know which side of a child area to update for positioning. It’s also used for logging.
Logical units
The four number properties of BoxArea are named according to how they’re used in logical space. In normal flow layout, boxes are stacked after one another by increasing the blockStart, which will be a Y coordinate in a horizontal writing mode and an X coordinate in a vertical writing mode. Rather than checking which physical dimension a box should be laid out in, the layout code increments the blockStart dimension and converts it after layout is done.
After layout, we run a pass over the tree called “postlayout”. Here is where we calculate absolute values from relative and map from logical (blockStart) space to physical (x or y) based on the writing mode. This happens in the pre-order visit of depth-first traversal since positioning an area absolutely requires that its parent be positioned absolutely.
Physical units
For writing-mode: horizontal-tb; direction: ltr, the translation from logical to physical is:
x = lineLeft;
y = blockStart;
width = inlineSize;
height = blockSize;
For writing-mode: vertical-lr; direction: ltr, the translation is:
x = blockStart;
y = lineLeft;
width = blockSize;
height = inlineSize;
Optimization #1: re-use of fields
Originally, dropflow stored both coordinate systems on the same object: {x, y, width, height, blockStart, lineLeft, blockSize, inlineSize}. (That’s an oversimplification; it would have been more obvious had I organized it that way!).
But only one of the two sets of coordinates is ever needed at once: logical coordinates for layout, and physical coordinates for painting. We can instead use 4 fields named after one coordinate system, and create aliases of the other coordinate system with getters and setters:
class BoxArea {
get x() {
return this.lineLeft;
}
set x(val: number) {
this.lineLeft = val;
}
get y() {
return this.blockStart;
}
set y(val: number) {
this.blockStart = val;
}
get width() {
return this.inlineSize;
}
set width(val: number) {
this.inlineSize = val;
}
set height(val: number) {
this.blockSize = val;
}
}
Using the variables defined above, for a given writing-mode, absolutizing a BoxArea is simple:
this.x = this.parent.x + x;
this.y = this.parent.y + y;
this.width = width;
this.height = height;
This is kind of the opposite of an implementation that might store physical coordinates during layout. Instead of branching on the writing mode every time a logical coordinate needs to be stored, we just store it, and move that branching logic to a single point in time, when we’re done with layout!
There is one more postlayout step for the curious: pixel snapping! This must happen in the postlayout traversal’s post-order visit, because otherwise, a child box would position itself absolutely against snapped pixels - an instance of the common problem of rounding too early and propagating error.
Since they’re 8-byte doubles, this optimization saves 32 bytes per area as opposed to having {x, y, width, height} on the instance. In CellEngine, this translated to a few megabytes saved when viewing large spreadsheets.
Optimization #2: changing how a box’s area is retrieved
BoxAreas used to be stored like this:
class Box {
borderArea: BoxArea;
paddingArea: BoxArea;
contentArea: BoxArea;
}
But it isn’t uncommon to have boxes without any padding or border. In such cases, the areas are redundant, and memory is wasted. Ideally, we would only store areas that are different. If we re-use the content area as the padding area when there is no padding, and as the border area when there is no border, we can save a decent amount of memory.
To start we’ll replace all 3 properties with a generic area property, which directly represents the content area:
class Box {
area: BoxArea;
}
If we can pull this off, we’ve saved 2 fields on a very commonly used data structure.
The parent pointer on BoxArea can be used to walk up and find the desired area. We have a chain of 3 when there is both border and padding, a chain of 2 when there is either, and 1 when there is neither:
class Box {
constructor() {
this.area = new BoxArea(this);
const hasBorder = this.style.hasBorderArea();
const hasPadding = this.style.hasPaddingArea();
if (hasBorder && hasPadding) { // b -> p -> c
const b = new BoxArea(this);
const p = new BoxArea(this);
this.area.setParent(p);
p.setParent(b);
} else if (hasBorder || hasPadding) { // b -> c or p -> c
this.area.setParent(new BoxArea(this));
}
}
}
That allocates and links the right number of BoxAreas per box, but which is which, and can we find out without using any more memory?
If there’s padding, up one level is the padding area, otherwise the padding area is the same as the content area. If there’s a border, one level up is the border area when there’s no padding, two levels up when there is.
class Box {
getBorderArea(): BoxArea {
const hasBorder = this.style.hasBorderArea();
const hasPadding = this.style.hasPaddingArea();
if (hasBorder && hasPadding) {
return this.area.parent!.parent!;
} else if (hasBorder || hasPadding) {
return this.area.parent!;
} else {
return this.area;
}
}
getPaddingArea(): BoxArea {
if (this.style.hasPaddingArea()) {
return this.area.parent!;
} else {
return this.area;
}
}
getContentArea(): BoxArea {
return this.area;
}
}
This again saved a notable amount of memory in CellEngine: a bit less than 1 MiB is saved when viewing a large spreadsheet.
Optimization #3: changing how a containing block is retrieved
The containing block used to be stored like this:
class Box {
containingBlock: BoxArea;
}
You can probably guess where this one is going, but it took me a bit longer to realize! The containing block is simply the parent of whatever getBorderArea returns:
class Box {
getContainingBlock(): BoxArea {
return this.getBorderArea().parent!;
}
}
All of the boxes get linked to each other in the prelayoutPreorder pass. The context object stores the most recent parents, which already have their parents set since the function is called in the preorder phase.
class Box {
prelayoutPreorder(ctx: PrelayoutContext) {
if (this.style.position === 'absolute') {
this.getBorderArea().setParent(ctx.lastPositionedArea);
} else {
this.getBorderArea().setParent(ctx.lastBlockContainerArea);
}
}
}
Now that I’ve explained it all, the original implementations seem obviously wrong. Can you even call it an optimization if it was a bad solution from the start? I think the answer is yes. Optimizing code is the same thing as finding a clean solution, because in both of them, you’re primarily concerned with finding the hidden structure of the problem.