over-allocation
Reserving more memory than is needed right now so that future growth does not require a copy every time.
In more detail
CPython over-allocates list storage, which is why sys.getsizeof reports a list's size jumping in steps as items are appended. The spare capacity is what makes append amortised constant time. The cost is some unused memory at any moment.
Related terms
- capacity — The number of items a structure has room for before it must grow, as opposed to the number it currently holds.
- dynamic array — An array that grows on demand by allocating a larger block and copying the existing items across when it runs out of room.
- sys.getsizeof — A Python function that reports how many bytes an object itself occupies in memory.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers