V8's Algorithms

// inline cache lookup, as the algorithm it is: a tiny dispatch table keyed by map, specialised per call site
// state: uninitialised | monomorphic (1 entry) | polymorphic (2..4 entries) | megamorphic (global table)
function loadIC(site, obj) {                      // what the LoadIC handler does, in JS terms
  const map = obj.map
  for (const [m, handler] of site.entries)        // 1 compare when monomorphic; up to 4 when polymorphic
    if (m === map) return handler(obj)            // handler: "load slot 2", "load from prototype P", "call getter"
  // miss:
  const handler = fullLookup(obj, site.name)      // walk descriptors and the prototype chain: O(depth × properties)
  if (site.entries.length < 4) site.entries.push([map, handler])
  else site.state = 'megamorphic'                 // from now on: stubCache[hash(map, name)], a global 2-way set-associative table
  return handler(obj)
}
// complexity per access: mono O(1), poly O(k ≤ 4), mega O(1) expected via the hash + a full lookup on a stub cache miss
// the data structure choice: a per-site array (tiny, inlined into code) vs a global hash (shared, never inlined). the per-site array wins
// while it stays small; the global table is the fallback. the JS course part 3 has the machine code each state compiles to

// incremental marking as an algorithm: the same tri-colour marker, run in bounded steps, with the barrier keeping it honest
// state between steps: the grey worklist and the colour bits, which persist across mutator execution
function markStep(budgetBytes) {
  let done = 0
  while (grey.length && done < budgetBytes) { const o = grey.pop(); for (const c of children(o)) if (isWhite(c)) { setGrey(c); grey.push(c) } setBlack(o); done += size(o) }
  return grey.length === 0
}
// the scheduler: after each task (or on allocation when the heap grows), run markStep with a budget proportional to allocation since the last step
//   ("allocation-driven marking": the faster the program allocates, the more marking it must do, so marking keeps pace and the heap does not run away)
// concurrent marking: helper threads run markStep on their own worklists with work stealing; the barrier pushes to a per-thread buffer the marker drains
// finalisation: stop the world; drain all worklists; process weak references (ephemerons: a fixpoint over WeakMap entries); flip the colour sense
// the cost model: total marking work ∝ live heap; main-thread share ∝ what helpers could not do; pause ∝ what was left for finalisation