Write barriers & remembered sets

The pointer a minor collection could miss

The garbage collector (GC) is the part of the JavaScript engine that frees memory your program no longer uses. Many engines split memory into two parts, called generations:

• The young generation holds new objects. Most of them are needed only for a moment.
• The old generation holds objects that have lived for a while.

A minor collection cleans only the young generation. It is fast because it does not look inside the old objects. Most new objects are already unused, so a short look at young memory is usually enough.

One more word: a pointer is how one object points at another object in memory. When you write cart[0] = item, the cart now holds a pointer to the item.

1const cart = []; // lived a long time, so imagine it is old2cart.push({ item: "tea" }); // new object, so imagine it is young3console.log(cart[0].item);

Line 1 makes an empty array called cart. The comment asks you to imagine it is old: it has been around for a long time. Line 2 makes a new object, { item: "tea" }, and puts it in the cart. The comment asks you to imagine this new object is young. Line 3 prints tea.

Line 2 creates a problem. A minor collection looks at young memory only. It does not look inside the old cart. Suppose nothing young points at the tea object. Then the collection could think tea is unused and free it, even though the cart still needs it.

Adding the sticky note is the write barrier's job. In this lesson, the notes are small JavaScript models that you can run. They don't look at your browser's real memory. Real engines may store their notes in other ways.

Old-to-young pointers

An old-to-young pointer is a pointer stored in an old object that points at a young object. The direction matters:

• Young to young: a minor collection already looks at young objects, so it finds this pointer.
• Old to old: this pointer leads to no young object, so a minor collection doesn't need it.
• Old to young: this is the one a minor collection could miss.

1const cart = { generation: "old" };2const tea = { generation: "young" };3console.log(cart.generation + "-to-" + tea.generation);

Line 1 makes a model cart with the label "old". Line 2 makes a model tea object with the label "young". Line 3 joins the two labels and prints old-to-young. These labels are only data for this lesson. Real engines don't give objects a generation property.

Here is the order of events:

1. The program writes the pointer.
2. Right after, the barrier checks the write: does it go from an old object to a young object?
3. If yes, the barrier writes a note. The note is ready before the next minor collection starts.

1const cart = { generation: "old", latest: null };Run2const tea = { generation: "young" };3const rememberedSet = [];4 5function writeField(owner, key, value) {6  owner[key] = value;7  if (owner.generation === "old" && value.generation === "young") {8    rememberedSet.push({ owner, key, value });9  }10}11 12writeField(cart, "latest", tea);13console.log(rememberedSet.length);

The replay calls the lesson's real writeField function. Notice that the minor collection still won't look inside the old cart. The note is what leads it from the cart to tea.

Remembered sets

A remembered set is the collector's list of notes about old-to-young pointers. In this lesson's model, each note has three parts:

• owner: the old object, like cart.
• key: the property name, like "latest".
• value: the young object it points at, like tea.

1const rememberedSet = [];2 3function writeField(owner, key, value) {4  owner[key] = value;5  if (owner.generation === "old" && value.generation === "young") {6    rememberedSet.push({ owner, key, value });7  }8}9 10const cart = { generation: "old" };11const tea = { generation: "young" };12writeField(cart, "latest", tea);13console.log(rememberedSet.length);

Line 1 starts rememberedSet as an empty array. Line 3 starts the writeField function, and line 4 stores the value in the owner. Line 5 checks two things: is the owner old, and is the value young? If both are true, line 6 adds a note. Line 12 writes tea into the old cart. Line 13 prints 1, because one note was added.

Real engines don't store notes as JavaScript objects like this. They may store memory addresses or other small, compact data. The goal is the same: a later minor collection can find every old-to-young pointer without looking at all of old memory.

The table lists four things a minor collection can use. You will meet store buffers and dirty cards later in this lesson. Read each row as: the thing, what it is, and why it helps.

Minor collection uses the notes

The notes help only if the collection reads them. A minor collection works in three steps:

1. It starts from the young roots. A root is a place the program can always reach, like a variable in use. Young roots are roots that point at young objects.
2. It adds the young values from the notes as extra starting points.
3. It follows pointers from young object to young object, as usual. Every object it reaches is live (still in use). Any other young object can be freed.

1const youngRoots = [];2const rememberedSlots = [{ owner: "cart", key: "latest", value: "tea" }];3 4function minorCollection(roots, slots) {5  const live = new Set(roots);6  for (const slot of slots) live.add(slot.value);7  return [...live].sort();8}9 10console.log(minorCollection(youngRoots, rememberedSlots).join(","));

Line 1 says there are no young roots: the array is empty. Line 2 still has one note, from cart to tea. Line 4 starts the minorCollection function. Line 5 makes a set of live objects from the roots. Line 6 adds the value of each note. Line 10 prints tea. The note alone kept tea live in this model.

This is the speed trade. The collection skips every old object, but the notes must be correct. Suppose one note were missing. Then a young object that is still in use could look unused, only because the one pointer to it starts in old memory. The collection would free it, and the program would break.

1const cart = { generation: "old", latest: "tea" };Run2const tea = { generation: "young" };3const rememberedSet = [{ owner: cart, key: "latest", value: tea }];4 5function minorCollection(youngRoots, slots) {6  const live = new Set(youngRoots);7  for (const slot of slots) live.add(slot.value);8  return [...live];9}10 11console.log(minorCollection([], rememberedSet).map((value) => value === tea ? "tea" : "?").join(","));

Remembered sets and store buffers

A store buffer is a short list of recent writes that matter to the collector. It splits the work into two jobs:

• Now, during the write: add the write to the list. This is quick.
• Later: go through the list and turn each entry into a note in the remembered set.

Different engines use different names for these parts, but the idea is common.

1const storeBuffer = [];2 3function store(owner, key, value) {4  owner[key] = value;5  if (owner.generation === "old" && value.generation === "young") {6    storeBuffer.push({ owner, key, value });7  }8}9 10const cart = { generation: "old" };11const tea = { generation: "young" };12store(cart, "latest", tea);13console.log(storeBuffer.length);

Line 1 makes an empty buffer. Line 3 starts the store function, and line 4 stores the value. Lines 5 and 6 add an entry only for an old-to-young write. Line 12 makes that write, so line 13 prints 1. Later, another part of the engine can go through this short list.

The buffer doesn't let the engine forget a write. It only changes when and where the rest of the work happens. The collection must read every entry before it decides which young objects are live.

Card marking

Writing one exact note for every pointer can be too much work on every write. Card marking is a cheaper way:

• Old memory is split into small, equal parts called cards. Each card holds a few slots. A slot is one place that holds a value, like one property.
• When a write matters, the barrier marks its card as dirty. Dirty means "something changed here".
• Later, the minor collection checks every slot in each dirty card.

1const cardSize = 4;2const cardTable = [false, false, false];3const slot = 5;4const card = Math.floor(slot / cardSize);5cardTable[card] = true;6console.log(cardTable.join(","));

Line 1 says each card holds four slots. Line 2 makes a card table: one true or false flag per card. All three start as false, which means clean. Line 3 picks slot 5. Line 4 divides 5 by 4 and rounds down with Math.floor, which gives card 1. Line 5 marks card 1 as dirty. Line 6 prints false,true,false. Only the middle card is dirty.

A dirty card is less exact than a note for one slot, because it covers four slots. When the collection runs, some of those slots may not point at young objects any more. Checking them is extra work at collection time. In return, each write only has to set one flag, which is small and cheap.

1const cardSize = 4;2const cardTable = [false, false, false];3const slot = 5;4const card = Math.floor(slot / cardSize);5cardTable[card] = true;6console.log(cardTable.join(","));

The cost of barriers in JIT code

A JIT compiler (just-in-time compiler) turns JavaScript that runs often into fast machine code while the program runs. In that fast code, a property write is not always one simple step. The JIT may add a few checks to tell whether the write could create an old-to-young pointer. This small cost is normal for a collector with young and old memory.

1function store(owner, value) {2  if (valueIsSmallInteger(value)) return "no pointer";3  if (owner.generation === "young") return "young owner";4  if (value.generation === "old") return "old value";5  recordOldToYoung(owner, value);6  return "recorded";7}8 9console.log("recorded");

The checklist uses two made-up helper names, valueIsSmallInteger and recordOldToYoung. They stand for steps inside the engine. Line by line:

1. Line 2 skips a small whole number. The engine stores it as the number itself, not as a pointer to an object.
2. Line 3 skips when the owner is young, because the minor collection looks at young objects anyway.
3. Line 4 skips an old value, because the write doesn't point into young memory.
4. Line 5 records the only case left: an old owner and a young value. Line 6 returns "recorded".

The program never calls store. Line 9 only prints recorded, the name of the last step.

This is a sketch. It is not real machine code, and it is not exactly how any one engine works. Engines use what they learn while the code runs to make common safe writes cheap. For example, an engine may learn that a property always holds a number. When the engine can't be sure a write is safe, it keeps the barrier. Being correct comes first.

1function barrierDecision(ownerGeneration, value) {2  if (typeof value === "number") return "skip: primitive";3  if (ownerGeneration === "young") return "skip: young owner";4  if (value.generation === "old") return "skip: old value";5  return "record: old-to-young";6}7 8console.log(barrierDecision("old", 3));9console.log(barrierDecision("young", { generation: "young" }));10console.log(barrierDecision("old", { generation: "young" }));

A primitive is a simple value like a number or a string, not an object. Line 2 sees the number 3, a primitive, and skips. Line 3 skips a young owner. Line 4 would skip an old value. Only an old owner with a young object reaches line 5. So lines 8, 9, and 10 print skip: primitive, skip: young owner, and record: old-to-young.

So most writes are not expensive. The JIT must keep one rule: every old-to-young pointer gets a note. It also keeps common safe writes short. A few quick checks on each write usually cost much less than looking at all of old memory later.

What your app code should know

Your code never calls a writeBarrier() function after an assignment. JavaScript has no such function. The engine adds its own barrier steps to normal writes: property writes, array writes, and other writes that store an object. Your code stays normal JavaScript.

1const cart = [];2cart.push({ item: "tea" });3console.log(cart.length);

Line 1 makes an array. Line 2 puts a new object in it. Line 3 prints 1. If this array is old and the new object is young, the engine may run a barrier at line 2. Your program doesn't need to know how the engine stores its notes.

This helps when you read a profile: a recording, made with your browser's developer tools, of where your program spends its time. Many small writes can add some collector work. But changing code because of a guess rarely helps. First measure a real slowdown. Then use the browser's tools to find the cause.

Common misconceptions

These words are easy to mix up, because they all happen inside the engine, below your JavaScript. Each one has one small job:

• The write barrier notices a write.
• The remembered set holds notes about old-to-young pointers.
• Card marking marks a small part of old memory to check again.

• “I should call a barrier from my app.” No. The engine runs it for you during normal writes.
• “A remembered set copies all old objects.” No. It holds only notes about old-to-young pointers.
• “A dirty card names one exact pointer.” No. It names a small part of memory that must be checked again.
• “Minor collection can ignore old memory completely.” No. It doesn't look at all of old memory, but it must read the notes.
• “Every write has the same cost.” No. JIT code can prove that many writes need no barrier work.

The table shows four terms. Each row says what the term is and what it is not.

This lesson shows one common design. It is not a rule for every JavaScript engine. V8 (in Chrome), JavaScriptCore (in Safari), SpiderMonkey (in Firefox), and smaller engines can choose different details. Your JavaScript code behaves the same in all of them.

Practice exercises

const cart = { generation: "old" };
const tea = { generation: "young" };
console.log(cart.generation === "old" && tea.generation === "young");

const cart = { generation: "old" };
const tea = { generation: "young" };
console.log(cart.generation === "old" && tea.generation === "young");

const cardSize = 4;
const slot = 9;
console.log(Math.floor(slot / cardSize));

const cardSize = 4;
const slot = 9;
console.log(Math.floor(slot / cardSize));

const owner = { generation: "old" };
const value = 3;
console.log(typeof value === "number" ? "skip" : "record");

Check your understanding

For each question, first ask which way the pointer goes: old to young, or not. Then ask what the collector uses: an exact note, a store buffer entry, or a dirty card.

Key takeaways

• A minor collection is fast because it looks at young memory, not all of old memory.
• So every old-to-young pointer needs a note. Otherwise a young object that is still in use could be freed.
• Remembered sets, store buffers, and card tables are different ways to keep or sort those notes.
• Card marking gives up the exact slot. In return, each write only sets one flag, and the collection checks the whole dirty card later.
• JIT code adds small checks to writes, but skips them when it can prove a write is safe.
• Your app code never calls a barrier. If something is slow, measure it with a profile first.

Coming next: Incremental, concurrent & parallel GC. There, collectors split their work into small steps or run beside your code, so your page doesn't freeze in one long pause.