An importer compacts a large byte buffer in place by shifting kept bytes down; what does a transformation chain cost here?
answer
- storage, not style
- one buffer, two cursors
- read cursor outruns write cursor
- a stage yields a value, not a slot
- peak memory holds both copies
basics
~20 sA chain yields new values, so it allocates a second buffer nearly the size of the first and fills it. The in-place loop rewrites the same storage with a read cursor and a write cursor, allocating nothing for the result.
solid answer
~50 sCompaction in place is one pass with two cursors: a read cursor visits every position, a write cursor marks the first free slot, and a kept byte is moved down to it. Survivors move within the same buffer and are never copied into new storage; when the scan ends the write cursor is the new length. A transformation chain cannot express that, because a stage yields a value rather than overwriting the input it was given — that is exactly the property that makes a chain safe to share and reorder. So the chain hands back a fresh buffer while the original is still live, and peak memory holds both. When the buffer is a real fraction of the memory budget, or the caller owns the buffer and expects its result there, that doubling is the deciding cost.
code
pseudocode · 7 linesfunction compactInPlace(buffer, length, isKept)
write = 0
for read from 0 to length - 1
if isKept(buffer[read])
buffer[write] = buffer[read]
write = write + 1
return write // the new length; bytes at or past it are stalego deeper
Recall that a transformation chain builds a new collection while the loop rewrites the buffer it was given. Be able to say where the extra memory comes from.
Explain the two-cursor mechanic and its consequence: the write cursor lags by the number of dropped bytes and ends up as the new length, and every holder of the buffer sees the change.
Justify the choice against a real budget — buffer size against the ceiling, allocation per batch — and fence the mutation inside a narrow boundary that owns the storage exclusively.
Decide where a codebase permits in-place mutation at all. A standard that allows it only inside modules with exclusive ownership lets the rest of the system keep reasoning in values.
## The job on the table An importer pulls a large block of bytes into one working buffer. Some of those bytes are padding, separators, or records already marked deleted, and the next stage wants the survivors contiguous at the front. **Compaction** is the pass that does it: walk the buffer once, and every byte that is kept moves down into the first free slot. What comes back is not a new collection — it is the same buffer plus a new length, with everything past that length now stale. Two cursors carry the whole algorithm: - a **read cursor** that visits every position exactly once and never moves backwards; - a **write cursor** that marks the first free slot and advances only when a byte is kept; - an invariant that `write <= read` at every step, with the gap between them equal to the number of bytes dropped so far. When the scan ends, the write cursor *is* the new length. Nothing was allocated for the result, and each survivor moved at most once — within the buffer it was already in. ## Why a transformation chain is a different program A stage in a transformation chain takes a value and yields a value. That is the entire contract, and it is what buys the chain its reasoning properties: the input is untouched, so it can be shared, retried, evaluated in a different order, or handed to another worker. Overwriting the input would break every one of those promises at once. So a chain that says "keep the bytes passing this test" gives you a **new** buffer of survivors and leaves the original standing. | axis | in-place loop | transformation chain | |---|---|---| | storage for the result | the input buffer itself | freshly allocated | | peak memory | one buffer | the input plus the result, plus any intermediates | | other holders of the input | see the compacted bytes at once | still see the original contents | | what the caller gets back | a new length | a separate value | | reordering or parallel evaluation | unsafe without extra care | safe by construction | Neither column is the right one. The table is a price list, not a verdict. ## The budget is the argument, not the taste An importer usually runs with a working buffer sized against a fixed ceiling. If that buffer is a meaningful fraction of the ceiling, doubling it at the moment of compaction is the difference between running and failing — and it fails on the largest input, which is the one you cared about. Allocation is not free even when there is room: every batch that allocates a buffer-sized object adds pressure someone has to reclaim, and a chain of several stages allocates once per stage unless the runtime is permitted to combine them, which is a separate subject with its own mechanism. Two further cases make in-place a requirement rather than an optimisation: 1. The buffer was handed in by a caller that will read the result out of **that** buffer. Returning a different one changes the contract, however clean the code looks. 2. The code runs where allocation is unavailable or forbidden — a constrained device, a hard no-allocate region, a path that must not disturb the allocator at all. ## What the loop costs you — say this part out loud - **Index arithmetic you can get wrong.** An off-by-one on the write cursor corrupts data quietly instead of failing loudly. - **Buried intent.** "Keep the bytes matching a predicate" has to be reconstructed by the reader out of cursor bookkeeping. - **It is not a pure function.** Anyone holding the buffer can observe a half-compacted state while the loop runs, so sharing it across workers becomes a problem you now own. - **A stale tail.** Bytes past the new length are still readable garbage; lose the length and you read them as data. ## Choosing, in three questions 1. Must the result live in the same storage — a memory ceiling, a caller-owned buffer, no allocator available? 2. Is the data large relative to the budget, so that a second copy is actually visible? 3. Is this the hot pass, run once per batch, rather than a one-off at startup? A "no" to all three means reach for the chain: the readability is worth more than an allocation nobody notices. A "yes" to the first is decisive on its own, because no amount of style preference makes a value-yielding stage write into the buffer it was handed. One caution when you go looking: some ecosystems offer bulk operations that *read* declaratively but mutate their receiver, and the naming differs between languages. The property to check is never the syntax — it is whether the operation produces new storage or rewrites existing storage.
- The read cursor has just skipped three dropped bytes. What does the write cursor point at?Still the first free slot — the position the next kept byte will land in. It lags the read cursor by exactly the number of bytes dropped so far, and that gap only ever grows. When the scan finishes, the write cursor's value is the new length of the compacted region.
- Why is it unsafe to compact a buffer another component is still reading?Because the mutation is visible to every holder of that buffer, not just to the compacting code. A reader mid-scan sees a region that is partly compacted and partly original, with no way to tell which bytes are which. In-place work requires exclusive ownership of the storage for the duration of the pass.
- If memory is plentiful, is there still a reason to prefer the loop here?Sometimes: when the caller owns the buffer and expects the result in it, the loop is the contract rather than an optimisation. Otherwise, with room to spare and a cold path, the chain's clearer intent and absence of index arithmetic usually wins.
Compacting in place is sliding books along the one shelf you own. The chain carries the keepers to a second shelf and leaves the first shelf standing until someone clears it.
saying these in an interview costs you the question
- Claims a transformation chain also writes into the original buffer
- Says allocation is free because a collector will clean it up
- Treats in-place work as faster regardless of the data size
- Cannot say what the write cursor points at mid-scan
- Thinks the choice is about style rather than storage
- Forgets the bytes past the new length are still readable garbage