When a smaller operand is stretched across a larger one, what is actually allocated - the repeat, the result, or both?
answer
- definition is not implementation
- the walk can stand still on one side
- nothing built for the stretch
- the result is sized by the stretched extent
- a thousand by a thousand is a million
basics
~20 sThe result always. The repeat need not be: an implementation can walk the larger operand while re-reading the same stored value at each step, so the stretch allocates nothing. Implementations that materialise the repeat first pay for both.
solid answer
~50 sThe operation is *defined* as if the smaller operand had been repeated to the larger size, but definition and allocation are separate questions. An implementation can walk the larger operand and re-read one stored value at each step - a repeating stride - so nothing is built for the stretch at all; only the result is new memory. Other implementations materialise the repeat first and then operate on two equal-sized buffers, paying for both. That is why "stretching is cheap" and "that expression used far more memory than I expected" are both true at once: the cheap part is the stretch, and the expensive part is the result, whose number of positions is the *stretched* size. Two thousand-value operands arranged so that each stretches against the other produce a million positions. Predict the result's positions, not the operands'.
go deeper
Recall that the smaller operand is reused rather than necessarily copied, and that the thing you pay for is the result. That distinction alone prevents most wrong estimates at this level.
Explain the split between definition and implementation: the answer is defined as if the operand were repeated, while the pass can re-read one stored value as it advances. Then price the result by multiplying the stretched lengths.
Show the estimate as a habit before the run, and connect it to the diagnosis: an expression whose result is unexpectedly large is usually an accidental stretch, and the fix is upstream, removing the length-one axis rather than economising on the result.
The angle is where memory estimates belong in a team's practice - which steps carry a predicted extent, and whether a transform whose peak depends on an implementation detail of the stretch should be written that way at all.
## Two separate questions hiding in one "Does stretching cost memory?" bundles two questions that have different answers: 1. **What does the stretch itself allocate?** Possibly nothing. 2. **What does the result allocate?** Always something, and it is sized by the *stretched* extent, not by either operand. Confusing the two produces both of the wrong intuitions people arrive with: that stretching is inherently wasteful, and that an expression over two small operands must be cheap. ## The semantics do not dictate the implementation The rule says the result is what you would get if the smaller operand were repeated until both sides presented the same number of positions. That is a **definition of the answer**, not an instruction about how to compute it. A compiled pass over two operands walks positions in order and, at each step, reads one value from each side. If one side has a single stored value standing in for an entire axis, the pass can simply **read that same stored value again at every step** - advancing through the large operand while standing still on the small one. This is a repeating stride: the walk advances zero distance on the stretched axis. No repeat is built, nothing is copied, and the arithmetic is identical to what a materialised repeat would have produced. Not every implementation does this. Some build the repeat first and then run an ordinary equal-size pass over two full buffers. Both are legitimate; they differ in what is live at the peak, not in the answer. | what the implementation does | allocated for the stretch | allocated for the result | |---|---|---| | Re-reads the one stored value as the pass advances | Nothing | The full stretched extent | | Materialises the repeat before operating | A full copy of the smaller operand at the stretched extent | The full stretched extent | ## The cost people actually hit The result is where the memory goes, and it is easy to underestimate because you are looking at the operands. Take two operands of a thousand values each, one laid out so that it varies down the rows and the other so that it varies across the columns. Each has a length-one axis where the other is longer, so both stretch, and the result has a thousand by a thousand positions: **a million**, from two operands of a thousand. The stretch may have cost nothing at all, and the expression can still be the largest allocation in the program. This is the shape of the surprise: - the operands are small and you inspected them; - the stretch is free and you may even know that; - the result is the product of the stretched lengths and you never wrote that number down. ## Estimating before you run A workable discipline, and it costs nothing: 1. Write down each operand's axis lengths - not its value count. 2. Apply the rule to get the result's lengths. 3. Multiply them. That product, not either operand's size, is what you are about to allocate. 4. If the product surprises you, the expression is not the one you meant to write. Step four is the one that matters. An accidentally rectangular result is usually a mistake, and the size estimate catches it before the run does. ## Consequences worth knowing - **"Stretching is cheap" is a true statement about the wrong thing.** It describes the stretch, and people hear it as a statement about the expression. - **Chaining compounds it.** Once an expression has produced a stretched result, every subsequent operator in the chain works at the stretched extent, not the original one. - **A free stretch does not mean a free read.** The pass still touches every position of the result; the saving is in what was allocated, not in how many results are computed. - **The intended fix is usually upstream.** If the stretched extent is not what you wanted, remove the length-one axis from whichever operand carries it, rather than trying to make the large result cheaper. ## The answer in one line The result is always allocated; the repeat need not be. Judge the cost of an expression by the number of positions in its result, and treat the stretch itself as free unless you have reason to believe the implementation materialises it.
- When does the stretch actually cost memory?When the implementation materialises the repeat before operating - building a full copy of the smaller operand at the stretched extent and then running an ordinary equal-size pass over two full buffers. The answer is the same either way; what differs is what is live at the peak. Where the pass instead re-reads the one stored value as it advances, the stretch allocates nothing.
- Which number should you predict before running an expression with a stretch in it?The number of positions in the *result*, obtained by applying the size rule to the two operands' axis lengths and multiplying the resulting lengths. The operands' own sizes are misleading precisely because a stretch decouples them from the result. If that product surprises you, you have written a different expression from the one you intended.
A rubber stamp against a stack of pages. You do not photocopy the stamp a thousand times to mark a thousand pages - the stamp is re-inked and reused where it stands, which is the stretch costing nothing. The stack of stamped pages is what piles up on the desk, and that is the result.
saying these in an interview costs you the question
- Says stretching always materialises a full copy of the smaller operand
- Claims the stretch is free, so the whole expression must be cheap
- Confuses the result's extent with the smaller operand's size
- Estimates memory from the inputs rather than from the result's positions
- Assumes a free stretch also means fewer results are computed