# HeapManager: time and space complexity

[Repository overview](../README.md) | [High-level design](HeapManager_HLD.md) | [Low-level design](HeapManager_LLD.md)

## Reading the costs

`O(1)` means a fixed amount of algorithmic work. `O(n)` means the work can grow in proportion to `n`. These are code-level bounds for a valid heap, not measured timings or guarantees about Windows scheduling.

| Symbol | Meaning |
| --- | --- |
| `F` | Number of backend free-list nodes inspected; use the maximum list length across retries for a worst-case bound. |
| `B` | Number of physical blocks in the committed region. |
| `K` | Number of size classes: 51 in this implementation. |
| `D` | Number of parked blocks drained during an operation. |
| `N` | Requested payload bytes to clear. |
| `P` | Bytes copied by a realloc that moves. |
| `C`, `R` | Committed and reserved bytes. |

Lock waiting, console/file output, Windows memory calls, and page faults add costs outside the pointer-operation bounds below.

## Public functions

| Function or path | Time, excluding lock wait and OS/I/O latency | Extra working space |
| --- | --- | --- |
| `my_heap_create` | `O(K)` bookkeeping initialization, plus reserve/commit and logging | `O(1)` temporary space; creates the reserved region |
| `my_heap_destroy` | `O(1)` library work plus Windows region release; no per-block walk | `O(1)` |
| `my_malloc`: cache hit with no retirement | `O(1)` | `O(1)` beyond returned block |
| `my_malloc`: backend search without reclaim/growth | `O(F)` | `O(1)` beyond returned block |
| `my_malloc`: reclaim path | `O(F + K + D)`; add `O(B)` seam lookup if growth occurs, plus the OS commit | `O(1)` beyond returned block |
| `my_free` | `O(B)` physical-pointer lookup, then `O(1)` link, merge, and fixed guard work | `O(1)` |
| `my_calloc` | Cost of `my_malloc` plus `O(N)` zero-fill | `O(1)` beyond returned block |
| `my_realloc`: old capacity is enough | `O(B)` pointer lookup, then constant metadata work | `O(1)` |
| `my_realloc`: moves | Cost of `my_malloc` plus `O(B + P)` lookup/copy/free | New and old blocks coexist until the copy succeeds |
| `my_heap_validate` | Worst case `O(B² + K)` | `O(K)` local bucket counters |
| `my_heap_report`: Release | Validation cost plus fixed counter formatting/output | `O(K)` |
| `my_heap_report`: Debug | Validation cost plus `O(B)` walk and live-block output | `O(K)` |
| `my_heap_snapshot` | Validation cost plus `O(B + K)` summary and copy work | `O(K)` internally; caller provides `O(B + K)` output storage |

A bucket hit is not **always** a constant-time public allocation: `my_malloc` can run its periodic retirement sweep before checking the bucket.

## Helper costs

| Helper | Cost and reason |
| --- | --- |
| `SizeClassOf`, `BucketClassSize` | `O(1)` arithmetic and a fixed set of range checks. |
| `FlInsert`, `FlRemove`, `BucketPush`, `BucketPop` | `O(1)` updates to a known node and its neighbors. |
| `FindFit` | Best case `O(1)`; worst case `O(F)` because it may inspect every free node. |
| `SplitBlock` | `O(1)`; makes at most one remainder. |
| `BackendFree` | `O(1)`; checks and merges at most the two immediate physical neighbors. |
| `BlockShapeValid`, `RequestSizeValid` | `O(1)` bounded field/arithmetic checks. |
| `FindPayloadBlock` | `O(B)` physical walk; only then is a candidate payload accepted. |
| `FreePredecessorAtSeam` | `O(B)` physical walk to the old committed boundary; never guesses from a used payload's trailing bytes. |
| `GrowHeap` | `O(B)` seam lookup plus fixed metadata work and the Windows commit cost. |
| `DrainBucket` | `O(D)`; each popped block takes constant-time backend work. |
| `RetireColdBuckets`, `DrainWarmBuckets` | `O(K + D)`; inspect class state and process the drained blocks. |

There are only a fixed number of backend retries in an allocation. That is why several scans still give `O(F + K + D)`, rather than a nested `O(F * D)` bound.

Full integrity checking is different: every backend/bucket node is looked up in the physical layout before its pointers are trusted. There can be `O(B)` nodes, each with an `O(B)` lookup, producing the `O(B²)` bound. The code chooses this straightforward diagnostic check rather than building another ownership index. It runs for validation, reports, and snapshots, not every malloc.

## Why the free list is not entirely O(1)

```mermaid
flowchart LR
	A["Have a specific block pointer"] --> B["Unlink using prev and next"]
	B --> C["O(1)"]
	D["Need any block large enough"] --> E["Scan free blocks until one fits"]
	E --> F["O(F) worst case"]
```

An intrusive node makes removal cheap once the block is known. It does not supply an index by size or prove that an arbitrary caller pointer belongs to a live allocation. The new boundary scan adds that second check; public free is no longer described as constant-time.

## Space use

- `R` bytes of virtual address space are reserved. `C` bytes are committed; actual resident RAM remains under Windows control.
- The heap metadata has `O(K)` bucket state, stored inside that region.
- Each block has a constant-sized header. A backend free block additionally uses space within itself for two node pointers and a footer.
- Debug adds header fields and eight guard bytes per allocation.
- Size-class rounding and small unsplittable tails create unused space inside allocated blocks, called **internal fragmentation**.
- Free space separated by live blocks may be too fragmented for a large request, called **external fragmentation**.
- Parked blocks occupy committed space even though the live-allocation counters exclude them.
- Per-class parked length is capped at at most 256 blocks under normal operation. The block-count bound is `51 * 256`; the actual byte use depends on class sizes and cannot exceed the heap's available committed space.

Keeping `K` and the caps visible explains the design, even though their current numeric values are constants. Cache retention can still have a noticeable memory cost.

## Concurrency is not a speed guarantee

One heap lock means metadata operations cannot all run at once on the same heap. A free can wait behind another scan, drain, report, or snapshot. Snapshot serialization happens in ClientApp after the heap lock is released, but validation/copying hold the lock.

No benchmark currently measures these costs. The client validates behavior under a workload; it does not establish throughput, latency, or superiority to the Windows heap.