3. Numbers, widths and layout
The normative CP Lang 0.3 specification.
This is the normative specification (source). For a gentler introduction, start with the guides.
Status: draft for 0.3.0, aligned with Ryan 2026-11-21 (decision 149). Scope: how numbers stay small in memory
without the contestant thinking about bytes, and how ?T costs nothing
for ints, structs, records, enums and arrays. Modular arithmetic, floats
and overflow semantics are summarized where they touch layout; their
detailed rules stay in design/spec/11-types.md.
The model in one paragraph
Values compute in 64 bits; storage takes the fewest bytes the type
allows. A local Int lives in a register, where width is free, so
locals and arithmetic are always Int (i64) and nobody tunes them.
Bytes matter only where values are stored many times: arrays, lists,
struct fields, tables inside library structures. There, the storage
width comes from the type you already wrote for a different reason: a
domain ([V]T, V positions), a range from the statement
(read<1..=1e9>), a Mod<P>, a Bool. Every type also has a set of
spare values it never holds (Int.MIN, hi + 1 for a range, P for
Mod<P>, 2 for Bool); ?T stores None in one of them, so it is as
wide as T. A struct's spare values are its fields' spare values, so
?Edge is as wide as Edge with no annotation. Both choices are
automatic only because they never lose (same operations, never more
bytes, never slower), and cpl explain prints every layout.
1. Where widths come from
| Written | Storage | Why it is the type you'd write anyway |
|---|---|---|
Int, no bound | 8 bytes | the default; nothing is guessed |
lo..=hi (static ends) | narrowest of u8/u16/u32/u64 (i8.. when lo < 0) that holds the range; ? adds a byte only when no spare is left (0..=255) | statement bounds: read<[V]1..=1e9> |
0..=V.count, 1..=V.count | as V's positions | counts, sizes, depths |
a domain position V | narrowest that holds V.count + 1 values | every index |
Mod<P> | u32 when P < 2^31, else u64 | the modulus |
Bool | 1 byte; Bits<V> when you ask for bits | |
Char | 1 byte, ASCII 0..=127 | strings and grids |
U64, I128 | exactly that | hashes and bit tricks (wrapping U64); products past i64 (I128) |
F64 | 8 bytes |
- Domain widths follow the static bound of the count.
let n = read<1..=2e5>(); domain V = 0..ngives 4-byte positions;n: 1..=5000gives 2-byte positions. Every[V]Vparent array,List<V>stack and[V]0..=V.countsize array shrinks with it. (R03.1.1) - Locals never narrow.
let x: 0..=1e9 = ...is a contract checked at assignment, but it lives in an i64 register. Narrowing a local saves nothing and costs conversions. (R03.1.2) - Struct fields need static bounds (unchanged): layout never depends
on input. A field may be
V(a domain position), since the domain's width bound is static. (R03.1.3) - Loads widen, stores check. Reading
a[i]from a[V]0..=1e9is one zero-extending load; arithmetic is inInt, soa[i] * a[j]can't overflow 32 bits. Storing into a range-typed slot checks the range unless the checker proves it (a[i] = a[i] % 7needs no check). A range type is a contract:cpl runand checked builds trap on a violation; release builds don't check (decision 100), the same deal asIntoverflow, so valid programs pay nothing on the judge. (R03.1.4) - No
I32,U32orU8. A narrow slot is a range:[V]0..=255is one byte per element,[V]0..=4e9four. Decision 1.7 keeps the number types toInt,U64,I128andF64; a byte of text isChar. (R03.1.5) - Narrow arithmetic when proven. Semantically every operation is in
Int. When the range proof shows an expression and its operands fit in 32 bits (a[i] + b[i]with both0..=1e9is at most2e9, a u32), the C++ computes it in 32 bits. Same answer, never slower, and twice the lanes when the loop vectorizes, so it majorizes;cpl explainmarks it. (R03.1.6)
Why this split: in registers, 64-bit + - * < & cost the same as 32-bit
on every judge CPU; only division by a runtime value is slower on older
Intel. Width costs in memory (half the values per cache line, MLE) and in
SIMD (4 i64 lanes vs 8 i32 per 256-bit register). So locals stay Int,
storage narrows, and vectorizable arithmetic narrows only when proven.
Ops decide what a structure stores
Generic structures store their element type, so the narrow width flows
through SegTree, Heap, List, Dsu with no extra syntax. The fold op
decides the element type of the folds:
| Structure | a: [V]0..=1e9 stores | Why |
|---|---|---|
SegTree(max, a) | 4-byte nodes | max is Selective: the result is one of the inputs, so it stays in 0..=1e9 |
SegTree(+, a) | 8-byte nodes | + is not closed on a range; with n <= 2e5 sums reach 2e14, so T is Int |
SegTree(+, b), b: [V]1..=1e4, n <= 2e5 | 4-byte nodes | a node sums at most V.count inputs: 0..=2e9, proven |
SegTree<0..=4e9>(+, a) | 4-byte nodes | you named the node type; node writes are range stores |
SegTree(+, a.map(Z)) | 4-byte nodes | Mod<P> is closed under + |
Prefix(+, a) | [V.cuts]Int | sums |
Heap(by: .d) of (d: Int, v: V) | 16 bytes (12 + padding) | each field at its own width |
This is the law machinery of round 5 doing layout work: Selective
already promised "returns one of its operands", which is exactly the fact
that keeps a range closed. + gets the same treatment from its interval
rule: with N the static bound of V.count, a fold of at most N
inputs in lo..=hi lies in min(0, N*lo) ..= max(0, N*hi), and the node
type narrows when that fits. The bound comes from the static bound of V.count, so it
holds for every input; with act: or point writes of unbounded values
there is no bound and nodes stay Int.
To force a width, name the type parameter: SegTree<0..=4e9>(+, a). Every
node write is then a range store under decision 148: checked builds trap
with the node and the value, release truncates. (R03.1.7)
Seeing and steering it
cpl explainlists every array, list and structure with its element layout and its peak bytes at the input bounds, e.g.dist: [V]?Int, 8 B, 1.6 MB at n = 2e5.- A static peak above the judge profile's memory limit is an error (E0904) naming the three largest arrays. (R03.1.9)
- Lint
wide_array: an array with a static size of at least 1e6 whose element type isIntwhile every value written into it has a narrower static range (a read, a domain position, a constant,min/maxof those). It suggests the annotation, e.g.[V]0..=1e9. Purely local: it looks only at the writes in the same function. (R03.1.8) - Override with an explicit type in either direction:
[V]Intwidens,[V]0..=4e9stores 4 bytes. - The editor shows the same facts from the same computation:
- hover on a type or variable gives its size, field storage order,
padding and where
Nonelives (?Edge 8 B: None = all-ones in to); - an inlay hint after each array or structure declaration gives element
size and peak bytes at the input bounds (
8 B × 2e5 = 1.6 MB); - a code lens at the top of the file gives total static peak against the profile's
limit;
wide_arrayand padding over 20% come with quick fixes.
- hover on a type or variable gives its size, field storage order,
padding and where
2. Spare values
Every type has a fixed set of spare values: bit patterns of its
storage that no valid value uses. The set is a property of the type, never
of a use, so two ?Edges always agree on layout. (R03.2.1)
| Type | Spare values | None is |
|---|---|---|
Int | INT64_MIN (Int is -(2^63-1)..=2^63-1) | INT64_MIN |
lo..=hi in width W | every W value outside lo..=hi | hi + 1 if it fits, else lo - 1 |
domain position V | indices >= V.count | the all-ones pattern |
Mod<P> | P .. up to the width | P |
Bool | 2..=255 | 2 |
unit enum with k variants | k..=255 | k |
F64 | quiet-NaN payloads (NaN traps in checked runs) | one fixed payload |
Char | 128..=255 | 128 |
U64, I128 | none | needs a flag |
?T | T's spares minus the one None took |
Structs, records and tuples
?S borrows the first field, in declaration order, that has a spare
value. It writes None into that field and leaves the others
undefined. So a struct of Ints has a niche because Int has one: (R03.2.2)
struct Edge: to: V, w: Int // 4 + 8 -> 16 B (padded)
var best: [V]?Edge = [V].filled(None) // 16 B per slot, not 24
var span: ?(lo: Int, hi: Int) = None // 16 B: None lives in lo- Records and tuples follow the same rule, since they are structs without names.
- Nesting is free while spares remain:
?(?Int), a[V]?Edgeinside a?Paths,Dsuparents stored as[V]?V. - No user
Nichetrait (decision 28.10). A library could name a value its own code later produces, turning a wrongNoneinto silent corruption. Every struct that has a spare value already has one in a field, and a range type on one field is how you give it one:struct H: h: U64, len: 0..=1e6puts?Hinlen. (R03.2.3)
Enums with payloads
The tag goes into a spare value when that is free; otherwise it is a byte:
- One payload variant plus k unit variants (
Option-like:Cellwith variantsWall,EmptyandBox(id: V)): the unit variants take k spare values of the payload.Cellis 4 bytes. (R03.2.4) - Several payload variants: the largest variant (first on a tie) sets
the layout. Every other variant is one spare value of a single field of
it, the first field in declaration order with enough spares, provided
that variant's own fields fit in the bytes outside that field.
Evwith variantsAdd(v: V)andAsk(l: V, r: V)is 8 bytes:Addkeepsvinl's slot and writes all-ones intor's slot, so a validrmeansAsk.?Evtakes another spare ofrand is also 8. (R03.2.5) - Otherwise a tag byte beside the largest payload, rounded up to alignment: when no field has enough spares (every bit pattern is a valid value) or a smaller variant can't fit around the field holding them. (R03.2.6)
- The rule is Rust's niche filling, restricted to "first field with enough
spares", so it is predictable without reading the compiler;
cpl explainprints the encoding.
Arrays of optionals
[V]?T is [V]T with spares wherever T has one: the distance array
[V]?Int is 8 bytes per vertex, [V]?V parents 4 bytes. When T has no
spare ([V]?U64), the flag is stored inline next to each element. The
compiler never splits it into a side bitset on its own: that would be
smaller but costs a second load per access, so it doesn't majorize. Ask
for it with Opt<V, T> (a library struct of [V]T plus Bits<V>) if
memory is the limit. (R03.2.7)
Field order
Storage order is chosen to minimize padding (largest alignment first,
then declaration order); visible order (constructors, patterns, print,
derives, ..R rows) stays declaration order. Nothing in the language
observes addresses, so reordering never changes behaviour, and it only
removes padding. A struct passed to @cpp code keeps declaration order,
since C++ would see the storage. cpl explain shows the storage order. (R03.2.8)
Cache layout
Width is half of cache behaviour; layout is the other half. The defaults
already favour locality: narrow storage packs more values per 64-byte
line, Graph is CSR (a vertex's arcs are contiguous), trees reorder by
t.Pre (subtrees are ranges, heavy chains are runs), segment trees are
one flat array, and niches mean ?T never costs a second miss on a flag
array.
Padding stays when a struct's fields don't fill its alignment
((d: Int, v: V) is 12 bytes of data in 16), as in C++. Two explicit
fixes, neither automatic because neither is never-worse:
| Spelling | Bytes | Trade |
|---|---|---|
Packed<S> (decision 1.2) | data only | unaligned loads; some elements straddle a line |
layout: columns on [V]S, List<S>, Heap<S> | data only | one array per field: a scan or sift touching one field reads only that column; touching all fields reads several lines |
cpl explain flags any structure above 1 MB whose padding exceeds 20% of
its element and names both fixes.
3. Operations on niche types
- Testing
Noneis one compare with the fixed pattern. (R03.3.1) max=on?Intis branch-free:INT64_MINis below everyInt, soNoneis already the identity ofmax(the tropical rule in decision 1.3).min=on?Intcompiles to one compare and a conditional move. (R03.3.2)- Producing a spare value is an overflow.
Intarithmetic that lands onINT64_MINtraps in debug like any overflow; in release it is part of the wrap contract (a wrapped value may read asNone). An out-of-range store is the same: checked builds trap before it writes a spare; release truncates, and the result may read asNone. (R03.3.3) - Reading input rejects a value equal to a spare (
read<Int>of-9223372036854775808is an input error naming the bound). (R03.3.4) - Generic code sees no difference:
?TinsideSegTree<T>or a user struct getsT's layout after monomorphization.
4. Overflow, in one table
Ranges carry the proofs; the build decides what an unproven step does.
The rule for every check. On the judge only valid programs matter, so
release optimizes for them: no runtime check is on by default, and a wrong
program gets a wrong answer. Checked builds (cpl run, stress, -DLOCAL)
trap on every violation, so bugs show up before submission. The emitted
C++ still has no undefined behaviour (wrapping goes through unsigned
casts, which compile to the same instructions), so -O2 never
miscompiles the valid paths around a bug. To keep a check on the judge,
opt in: with checks(ranges: on, overflow: on) on a block or file, or
release_checks: in the judge profile. (R03.4.1)
| Situation | Debug and cpl run | Release on the judge |
|---|---|---|
Int arithmetic proven in range | no check | no check |
Int arithmetic unproven | trap with values | wraps |
| store into a range type, unproven | trap | no check: truncates to the width |
U64 | wraps | wraps |
I128 arithmetic unproven | trap with values | wraps |
wrapping_add and friends | wraps | wraps |
result range exceeds i64 (1..=1e9 cubed) | the result is plain Int; overflow checks apply |
Proofs are intraprocedural interval arithmetic on lets and declared
ranges (already decided); nothing crosses calls, so compile time stays
linear. (R03.4.2)
5. Modular numbers
Mod<P> is stored in 0..P, so it is 4 bytes for every common prime,
?Mod<P> is free (P is spare) and SegTree(+, a.map(Z)) stores 4-byte
nodes. Multiplication widens to u64 (or I128 for moduli above 2^32,
which the profile must allow). A runtime modulus is a scoped type
(Mod<p> with p read once) using Barrett reduction, one local edit
from the constant form. (R03.5.1)
6. Examples
let n = read<1..=2e5>()
domain V = 0..n
let a = read<[V]1..=1e9>() // 4 B per element
var par: [V]?V = [V].filled(None) // 4 B, None = all ones
var dist: [V]?Int = [V].filled(None) // 8 B, None = INT64_MIN
var mx = SegTree(max, a) // 4 B nodes: max is Selective
var sm = SegTree(+, a) // 8 B nodes: sums are Int
struct Item: w: 1..=1e9, v: 1..=1e9, id: V // 12 B, ?Item 12 Bcpl explain on this prints, per line, the storage and the reason
("a: u32, from 1..=1e9; spare 1e9 + 1").
7. What this needs
- Core: storage width for static range types, domain positions and
domain-relative ranges (implemented for 1D and nested arrays); niche
borrowing for structs (28.10, implemented for
Intand position fields); spare-value niches for enums,Bool,Mod, ranges and records (codegen debt); padding-minimizing field order (new). - Library:
Opt<V, T>(new),Bits<V>(exists). - Tools:
cpl explainlayouts and peak memory, thewide_arraylint, the build-time memory warning.
Later
- Vectorization by judge profile. A profile names the instruction set
(
isa: avx2); codegen emits the matching#pragma GCC targetand, for loops whose shape it can prove (narrow-width element loops,GroupandSelectivefolds, prefix scans), vectorizes them itself.cpl explainsays which loops vectorized and why the others didn't. Not designed yet.
Open
wide_arraythreshold. 1e6 cells is a guess; the goal is to flag the arrays that decide MLE and stay quiet otherwise.