Most of the Time Is Going Somewhere That Does Not Appear Anywhere in Your Source
Last timeOne Instruction, Many Values
Allocation, following pointers, and the bookkeeping the language performs on your behalf routinely account for most of the run time, and none of it is visible in the code you wrote.
What allocation costs
The lessons so far have treated the program as arithmetic and memory accesses.
Real programs spend a great deal of their time on neither, and the work is
invisible in the source, which is why it is so often missed.
Start with allocation. Asking for a small object means finding a free block of
the right size, updating the structures that track what is free, and returning
a pointer. Releasing it means putting the block back, possibly merging it with
neighbours, and updating those structures again. A good allocator does this in
a few tens of cycles each way.
| cycles, roughly | visible in the source | |
|---|---|---|
| allocating one small obj | 40 | 0 |
| releasing it again | 30 | 0 |
| following a pointer alre | 4 | 0 |
| following a pointer not | 250 | 0 |
| a call through a functio | 15 | 0 |
| a bounds check on an acc | 2 | 0 |
| updating a reference cou | 8 | 0 |
Put that against what the object is used for. A loop that creates a small
temporary each iteration, does three arithmetic operations with it, and
discards it, spends roughly seventy cycles on the temporary and three on the
work. The profile will show the time inside the allocator, which is correct and
often misread as the allocator being slow, when the real finding is that it is
being called far too often.
- total cycles spent on object lifetime
- objects created during the operation
- cycles to allocate one
- cycles to release one
The remedies are all about the count rather than the cost per object. Reuse a
buffer across iterations instead of allocating one each time. Allocate a block
of objects together rather than individually. Keep the object on the stack when
its lifetime allows. Each of these reduces n, which is the only term you
control cheaply.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents