When designing a counted object representation, would you store each object's count in its header or in a side table?
answer
- in the object or beside it
- offset arithmetic versus address lookup
- every object pays, or only shared ones
- counting writes dirty the page
- steal header bits, spill on overflow
basics
~20 sA header count is one load and store on a line the code already touched, but every object pays the space and every update dirties the object's own page. A side table keeps objects clean and costs a lookup per update. Object size distribution and page sharing decide it.
solid answer
~50 sThe two placements trade locality against purity. A count in the object header is reached with no lookup and usually sits on a cache line the code is touching anyway, but it enlarges every object — expensive when most objects are small and most are never shared — and every increment writes into the object, which dirties pages and rules out putting objects in read-only or shared-across-process memory. A side table keyed by address keeps object bytes immutable and charges nothing for objects that are never counted, but every update pays a lookup and a probable extra cache miss, and the table needs its own memory and its own concurrency story. A common answer is a hybrid: a few stolen header bits for the common small count, spilling to a table on overflow. What decides it is the object size distribution, the fraction of objects ever shared, whether pages are shared copy-on-write between processes, and how hot the update path is.
go deeper
The count has to be stored somewhere: either inside the object itself or in a separate structure that maps an object's address to its count.
Explain the mechanical difference — constant-offset access against an address lookup — and that a header count adds space to every object whether it is ever shared or not.
Bring in the consequences for pages: counting writes into the object, so header counts dirty pages and conflict with read-only or cross-process shared data.
Defend a choice with evidence: object size and share-rate histograms, the page-sharing requirement, hot-path update frequency, and the hybrid that keeps small counts inline and spills the rest.
## The question behind the question Where a count lives is not a micro-optimisation; it constrains what the objects themselves can be. A count in the header makes every object mutable, because the count is part of the object and counting writes to it. A count beside the object keeps the object's own bytes untouched for its whole life. That single consequence is usually what decides the design, and the performance arguments are secondary. ## Count in the object header The count occupies a field, or a few bits of a field, in a fixed position in every counted object. What it buys: - **No lookup.** The address of the count is the address of the object plus a constant offset. An update is a load, an add and a store. - **Locality.** The header is almost always on the same cache line as the fields the code is about to use, so the count update usually rides along on a line that is already being fetched. - **Simplicity.** There is no second data structure to allocate, grow, or keep consistent with the heap. What it costs: - **Space on every object, shared or not.** If the typical object is 16 or 24 bytes and most of them only ever have one owner, an extra word is a large percentage overhead paid by objects that never needed counting at all. - **Writes into the object.** Every increment dirties the object's page. Where pages are shared copy-on-write between processes, merely *reading* a shared structure through counted handles forces private copies of those pages, and the memory saving the sharing was supposed to deliver evaporates. - **No read-only placement.** Constants, interned values and memory-mapped data cannot live in genuinely read-only pages if acquiring a handle to them must write a count, unless they are specially marked as exempt. ## Count in a side table The count lives in a separate structure keyed by the object's address — a hash map, or a per-region array indexed by an offset derived from the address. What it buys: - **Immutable objects.** The object's bytes are never written by memory management, so objects may live in read-only or cross-process shared pages, and pages stay clean. - **Pay only for what is shared.** Objects with exactly one owner need no entry at all; absence from the table can mean "count is one". If most objects are never shared, the table stays small. - **Counting things you do not own.** Memory you did not lay out — a mapped region, a block from a foreign allocator — can be counted without a header to modify. What it costs: - **A lookup on every update.** Hashing an address and probing is far more work than an offset store, and the probed line is unrelated to the object's own line, so it is a second likely cache miss on a path whose whole purpose is to be cheap. - **The table's own memory and growth.** It must be sized, grown and kept from becoming a hot spot of its own; it is also shared state that needs its own consistency story, which a per-object field does not. ## Comparing them | dimension | header | side table | |---|---|---| | cost to find the count | constant offset | address lookup | | locality of the update | same line as the object | unrelated line | | space for never-shared objects | paid by all of them | none | | object bytes written | yes, on every update | never | | read-only or cross-process pages | effectively excluded | supported | | extra structure to maintain | none | the table itself | ## What decides it in practice 1. **Object size distribution.** A heap of many tiny objects makes the header word a double-digit percentage of the footprint; a heap of large buffers makes it noise. 2. **Fraction ever shared.** If almost every object has exactly one owner for its whole life, a table that stores only the exceptions is far cheaper than a field in all of them. 3. **Page sharing and immutability.** If the design depends on sharing pages between processes, or on placing data in read-only memory, the header option is largely decided against. 4. **Update frequency on hot paths.** Where handles are copied constantly, the lookup cost of the table is paid on the hottest path in the system. A hybrid resolves most of it: steal a few bits in the header for the common small count, and spill to a side table for the rare object that outgrows them, or mark a class of immortal objects as exempt from counting entirely. The point to make in an interview is that this is a decision with no universally right answer, and that a defensible answer names the measurements it depends on — object size histogram, share rate, page sharing requirement — rather than asserting one placement is faster.
- Why does a header count interact badly with pages shared copy-on-write between processes?Because acquiring a handle writes into the object. A page shared read-only between processes is copied privately on its first write, so a process that only reads a shared structure still forces private copies of every page whose objects it takes handles to. The sharing that was meant to keep one copy of the data in memory then degrades towards one copy per process, which is the opposite of the intent.
- How can a side table avoid storing an entry for the vast majority of objects?By choosing a default. Absence from the table means the object has exactly one owner, so an entry is created only on the first additional acquire and removed when the count falls back to one. Since most objects in typical heaps are owned by a single location for their whole life, the table then holds only the genuinely shared minority, which is what makes its memory cost acceptable despite the per-entry overhead.
- What measurement would you take before choosing between the two?An object size histogram and a share-rate histogram from a representative workload: how many bytes the median object occupies, and what fraction of objects ever reach more than one owner. The first says what a header word costs as a percentage of the footprint; the second says how big a side table would be and how often the lookup would be paid. Without both, the argument is aesthetic.
saying these in an interview costs you the question
- Argues one placement is simply faster, without naming a workload
- Forgets that a header count enlarges objects that are never shared
- Ignores that counting writes dirty otherwise-clean shared pages
- Assumes a side table lookup is as cheap as an offset store
- Treats the two as exclusive and misses the stolen-bits hybrid