Memory efficiency

intermediateCommon atAnthropicGoogleMetaStripeRead firstArrays Bit manipulation Complexity analysis Practise in the Sandbox →

Big-O space hides a constant that can be 40×. A Python list[int] spends about 40 bytes per number, a C# int[] spends 4, a bitset spends one bit. Memory-efficient code (1) estimates bytes per element before choosing a structure, (2) packs values side by side instead of one object per element, and (3) bounds what it keeps: stream, keep a fixed window, or evict. The invariant to state: memory stays proportional to what can still matter, not to everything ever seen.

The idea in plain words

Imagine storing a phone book. One way: a filing cabinet with a separate labelled folder per name, each folder holding one card. Another way: one printed page with names in a column. Same information; the cabinet needs a room, the page fits in your pocket.

In memory, the “folders” are objects. In Python and in JavaScript object arrays, each element is a pointer (8 bytes on a 64-bit machine) to a separate object that carries its own header (16 bytes or more) before any payload. In C#, a class instance carries a 16-byte header too. Packed arrays (array('q'), Int32Array, int[], an array of struct) store raw values back to back with no per-element overhead.

Every element costs four things:

payload: the bytes of the value itself (4 for an int32, 8 for a double, 1 bit for a flag);
a reference: the slot that points to it, if it is a separate object;
an object header: type pointer, reference count or GC bits, length;
slack: spare capacity in growable lists (up to 2×) and empty slots in hash tables (kept below a load factor).

See it

Pick a kind of data and drag n. The vertical line is your memory budget. Hover a row to see where the bytes go.

Bytes per element: same data, different containers

calculator

n = 10,000,000

memory budget

Python

list[int]

381 MB · 40 B

set[int]

629 MB · 66 B

array("q")

76.3 MB · 8 B

TypeScript

number[] (small ints)

76.3 MB · 8 B

Set<number>

200 MB · 21 B

Int32Array

38.1 MB · 4 B

List<object> (boxed)

305 MB · 32 B

HashSet<int>

210 MB · 22 B

int[] / List<int>

38.1 MB · 4 B

Hover or tap a row to see where the bytes go.

The vertical line is your budget. Approximate, 64-bit, measured with 10⁶ elements on CPython 3.14, Node 22 and .NET; expect ±20% across versions. The big jumps come from one thing: a pointer to a separate object per element versus raw values packed side by side.

Peak memory matters as much as steady state. Run the clock: loading everything grows with the input, a growing list spikes to about 3× while it copies, streaming stays flat, and a last-k window is capped at k.

Memory held while reading 100 records

run the clock

window k = 20

growing list4 now · peak 4

load all0 now · peak 0

last-k window0 now · peak 0

stream0 now · peak 0

Loading grows with the input; streaming stays flat; a fixed window is capped at k. A growing list also keeps up to 2× spare capacity and spikes on each copy.

growing list (doubling)load alllast-k windowstream

0 / 100 recordsspeed

When to reach for it

The problem says…	Why memory matters
“10⁸ events” / “a 50 GB file” / “runs for months”	Back-of-envelope first: n × bytes per element. 10⁸ Python ints in a list is ~4 GB.
“memory should not grow with old data”	Evict as you go: a time window, a ring of the last k, or a TTL.
“set of IDs from 0 to N” / “visited flags”	A bitset is 64× smaller than a list of booleans in Python or JS.
“millions of small records”	Columns of packed arrays (struct of arrays) instead of one object per record.
“process each line and report totals”	Stream: O(state) memory, not O(file).
“keep only the last k readings”	A fixed-size ring buffer: no growth, no shifting, O(1) per write.

How it works

1. Estimate before you choose

Write down n (worst case, not typical) and the element type.
Multiply by bytes per element for your container, from the calculator above, not by the payload size.
Add slack: ×1.5 to ×2 for growable lists and hash tables, and the copy spike while a list grows.
Compare with the budget and leave headroom (often half) for the runtime, the GC and everything else.

Approximate 64-bit numbers worth remembering (measured on CPython 3.14, Node 22 and .NET; earlier versions differ by roughly 10-20%):

	Python (CPython)	TypeScript (V8 in Node)	C# (.NET)
small integer, as an object	28 B (`sys.getsizeof(1)`), 32 B after allocator rounding; -5..256 are shared	stored inline as a “Smi” (small integer) in a tagged slot	24 B when boxed
reference / slot	8 B	8 B (4 B with pointer compression, as in Chrome)	8 B
empty object header	16 B (`object()`), ~48+ B for a class instance	~24-40 B for a small object	16 B (min object 24 B)
packed int32 array	`array('i')`: 4 B	`Int32Array`: 4 B	`int[]`: 4 B
short ASCII string	41 B + 1 B per char	~16 B header + 1 B per char	~22 B + 2 B per char (UTF-16)
hash map entry (int → int)	~42 B + the key/value objects	~29 B (`Map`)	~28 B (`Dictionary<int,int>`)

2. Pack values, don’t box them

Python: array('q'), bytes/bytearray, __slots__ on classes (no per-instance __dict__), tuples over dicts for fixed records. NumPy arrays pack too, but are third-party.
TypeScript: typed arrays (Int32Array, Float64Array, Uint8Array) for numbers. Keep plain arrays monomorphic: an array of only small ints stays in V8’s packed-Smi form and an array of only numbers in the packed-double form. One string mixed in, or a hole created by arr[1e6] = x, and V8 falls back to a slower, generic kind; it never moves back.
C#: arrays of structs store fields inline. Span<T> and ArrayPool<T>.Shared avoid copies and repeated allocations. Avoid List<object> and non-generic collections that box value types.
Struct of arrays: three columns xs, ys, ids instead of a list of {x, y, id} objects. Smaller, cache-friendly, and each column can use the narrowest type.

3. One bit per flag

A bitset stores flag i in bit i % w of word i / w. The sieve below marks composites for 100,000 numbers in 12.5 KB; a Python list[bool] would take 800 KB.

class Bitset:
    """n booleans in n/8 bytes. A list[bool] costs 8 bytes per slot (a pointer)."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.words = bytearray((n + 7) // 8)    # 1. one byte holds 8 flags

    def set(self, i: int) -> None:
        self.words[i >> 3] |= 1 << (i & 7)      # 2. byte i // 8, bit i % 8

    def clear(self, i: int) -> None:
        self.words[i >> 3] &= ~(1 << (i & 7)) & 0xFF

    def test(self, i: int) -> bool:
        return (self.words[i >> 3] >> (i & 7)) & 1 == 1

    def count(self) -> int:
        return sum(b.bit_count() for b in self.words)  # 3. popcount per byte (Python 3.10+)


def count_primes_below(n: int) -> int:
    """Sieve of Eratosthenes with one bit per number: 12.5 KB for n = 100,000."""
    composite = Bitset(n)
    for p in range(2, int(n**0.5) + 1):
        if not composite.test(p):
            for m in range(p * p, n, p):
                composite.set(m)
    return n - 2 - composite.count() if n > 2 else 0  # 0 and 1 are not prime


if __name__ == "__main__":
    b = Bitset(20)
    b.set(3); b.set(17); b.set(3)
    assert b.test(3) and b.test(17) and not b.test(4) and b.count() == 2
    b.clear(3)
    assert not b.test(3) and len(b.words) == 3
    assert count_primes_below(100) == 25
    assert count_primes_below(100_000) == 9592
    print("ok")

import assert from "node:assert/strict";

/** n booleans in n/8 bytes. A boolean[] costs a full tagged slot (8 bytes in Node) per element. */
export class Bitset {
  readonly words: Uint32Array;

  constructor(readonly n: number) {
    this.words = new Uint32Array(Math.ceil(n / 32)); // 1. one 32-bit word holds 32 flags
  }
  set(i: number): void {
    this.words[i >>> 5] |= 1 << (i & 31); // 2. word i / 32, bit i % 32
  }
  clear(i: number): void {
    this.words[i >>> 5] &= ~(1 << (i & 31));
  }
  test(i: number): boolean {
    return ((this.words[i >>> 5] >>> (i & 31)) & 1) === 1;
  }
  count(): number {
    let c = 0;
    for (let w of this.words) for (; w !== 0; c++) w &= w - 1; // 3. clear lowest set bit until empty
    return c;
  }
}

/** Sieve of Eratosthenes with one bit per number: 12.5 KB for n = 100,000. */
export function countPrimesBelow(n: number): number {
  if (n <= 2) return 0;
  const composite = new Bitset(n);
  for (let p = 2; p * p < n; p++) {
    if (!composite.test(p)) for (let m = p * p; m < n; m += p) composite.set(m);
  }
  return n - 2 - composite.count(); // 0 and 1 are not prime
}

const b = new Bitset(40);
b.set(3); b.set(37); b.set(3);
assert.ok(b.test(3) && b.test(37) && !b.test(4));
assert.equal(b.count(), 2);
b.clear(3);
assert.ok(!b.test(3));
assert.equal(b.words.length, 2);
assert.equal(countPrimesBelow(100), 25);
assert.equal(countPrimesBelow(100_000), 9592);
console.log("ok");

using System.Numerics;

var b = new Bitset(100);
b.Set(3); b.Set(97); b.Set(3);
if (!b.Test(3) || !b.Test(97) || b.Test(4) || b.Count() != 2) throw new Exception("set/test/count");
b.Clear(3);
if (b.Test(3)) throw new Exception("clear");
if (CountPrimesBelow(100) != 25) throw new Exception("expected 25");
if (CountPrimesBelow(100_000) != 9592) throw new Exception("expected 9592");
Console.WriteLine("ok");

/// Sieve of Eratosthenes with one bit per number: 12.5 KB for n = 100,000.
static int CountPrimesBelow(int n)
{
    if (n <= 2) return 0;
    var composite = new Bitset(n);
    for (int p = 2; p * p < n; p++)
        if (!composite.Test(p))
            for (int m = p * p; m < n; m += p) composite.Set(m);
    return n - 2 - composite.Count(); // 0 and 1 are not prime
}

/// n booleans in n/8 bytes. A bool[] spends a whole byte per flag. (System.Collections.BitArray does this too.)
sealed class Bitset(int n)
{
    readonly ulong[] _words = new ulong[(n + 63) / 64];     // 1. one 64-bit word holds 64 flags

    public void Set(int i) => _words[i >> 6] |= 1UL << (i & 63);   // 2. word i / 64, bit i % 64
    public void Clear(int i) => _words[i >> 6] &= ~(1UL << (i & 63));
    public bool Test(int i) => (_words[i >> 6] & (1UL << (i & 63))) != 0;
    public int Count() => _words.Sum(w => BitOperations.PopCount(w)); // 3. hardware popcount per word
}

Stdlib options: C# has System.Collections.BitArray; Python’s arbitrary-size int works as a bitset with |, & and int.bit_count() (3.10+), though each update allocates a new int; JS has nothing built in, so use a Uint32Array.

4. Stream instead of loading

If the answer is a fold over the input, read one record at a time and keep only the accumulator. Python iterates a file object line by line; .NET’s File.ReadLines streams while File.ReadAllLines loads; Node’s readline over fs.createReadStream streams while fs.readFileSync(...).split('\n') loads.

from collections.abc import Iterable, Iterator


def bytes_by_status(lines: Iterable[str]) -> dict[str, int]:
    """Total response bytes per HTTP status, one line at a time.
    Memory is O(distinct statuses), not O(lines): the input is never materialised."""
    totals: dict[str, int] = {}
    for line in lines:                      # 1. pull one line; the previous one can be freed
        parts = line.split()
        if len(parts) < 3 or not parts[2].isdigit():
            continue                        # 2. skip malformed lines instead of crashing mid-stream
        status, size = parts[1], int(parts[2])
        totals[status] = totals.get(status, 0) + size  # 3. fold into a small accumulator
    return totals


def fake_log(n: int) -> Iterator[str]:
    """A generator stands in for open('access.log'): lines are produced on demand."""
    for i in range(n):
        yield f"GET {'200' if i % 4 else '404'} {i % 100}"


if __name__ == "__main__":
    small = ["GET 200 512", "GET 404 0", "POST 200 128", "garbage", "GET 500 -"]
    assert bytes_by_status(small) == {"200": 640, "404": 0}
    big = bytes_by_status(fake_log(1_000_000))  # a million lines, a two-key dict in memory
    assert set(big) == {"200", "404"} and big["404"] == sum(i % 100 for i in range(0, 1_000_000, 4))
    print("ok")

import assert from "node:assert/strict";

/** Total response bytes per HTTP status, one line at a time.
 *  Memory is O(distinct statuses), not O(lines): the input is never materialised. */
export function bytesByStatus(lines: Iterable<string>): Map<string, number> {
  const totals = new Map<string, number>();
  for (const line of lines) { // 1. pull one line; the previous one can be collected
    const parts = line.split(/\s+/);
    if (parts.length < 3 || !/^\d+$/.test(parts[2])) continue; // 2. skip malformed lines
    const [, status, size] = parts;
    totals.set(status, (totals.get(status) ?? 0) + Number(size)); // 3. fold into a small accumulator
  }
  return totals;
}

/** A generator stands in for readline over a file stream: lines are produced on demand. */
function* fakeLog(n: number): Generator<string> {
  for (let i = 0; i < n; i++) yield `GET ${i % 4 ? "200" : "404"} ${i % 100}`;
}

const small = ["GET 200 512", "GET 404 0", "POST 200 128", "garbage", "GET 500 -"];
assert.deepEqual(Object.fromEntries(bytesByStatus(small)), { "200": 640, "404": 0 });
const big = bytesByStatus(fakeLog(1_000_000)); // a million lines, a two-key map in memory
let want404 = 0;
for (let i = 0; i < 1_000_000; i += 4) want404 += i % 100;
assert.deepEqual([...big.keys()].sort(), ["200", "404"]);
assert.equal(big.get("404"), want404);
console.log("ok");

var small = new[] { "GET 200 512", "GET 404 0", "POST 200 128", "garbage", "GET 500 -" };
var s = BytesByStatus(small);
if (s.Count != 2 || s["200"] != 640 || s["404"] != 0) throw new Exception("small log");
var big = BytesByStatus(FakeLog(1_000_000)); // a million lines, a two-key dictionary in memory
long want404 = 0;
for (int i = 0; i < 1_000_000; i += 4) want404 += i % 100;
if (big.Count != 2 || big["404"] != want404) throw new Exception("big log");
Console.WriteLine("ok");

/// Total response bytes per HTTP status, one line at a time.
/// Memory is O(distinct statuses), not O(lines). File.ReadLines streams; File.ReadAllLines would load it all.
static Dictionary<string, long> BytesByStatus(IEnumerable<string> lines)
{
    var totals = new Dictionary<string, long>();
    foreach (var line in lines)                       // 1. pull one line; the previous one can be collected
    {
        var parts = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        if (parts.Length < 3 || !long.TryParse(parts[2], out long size) || size < 0) continue; // 2. skip malformed
        totals[parts[1]] = totals.GetValueOrDefault(parts[1]) + size;   // 3. fold into a small accumulator
    }
    return totals;
}

/// An iterator stands in for File.ReadLines: lines are produced on demand.
static IEnumerable<string> FakeLog(int n)
{
    for (int i = 0; i < n; i++) yield return $"GET {(i % 4 != 0 ? "200" : "404")} {i % 100}";
}

See Streaming and online algorithms for summaries that go beyond sums.

5. Bound what you keep

Fixed window (ring buffer). A preallocated array of capacity k plus a start index and a count. The i-th oldest item lives at (start + i) % k; writing past the end wraps around. No growth and no shifting.
Time window. Drop entries older than the horizon as time advances, and aggregate per second or per bucket instead of per event when many events share a time.
Eviction. Caches need a size cap and a policy (LRU, LFU, TTL); an unbounded Map used as a cache is a memory leak with good intentions. See Caching.

6. Compact

Compaction moves live data together so free space becomes one contiguous region. In an array, it is the two-pointer “write index” pass (xs[w++] = xs[r] for each kept item), then truncate: O(n), in place. Hash tables shrink when you rebuild them (dict(d) in Python, TrimExcess() in .NET). Garbage collectors in .NET and V8 compact the heap for you; CPython does not move objects, so a fragmented heap stays fragmented. Interning (sys.intern, string.Intern) is compaction for duplicates: a million copies of "status=ok" become one.

What it costs

Technique	Memory	Time trade-off
list of boxed objects	n × (slot + header + payload)	flexible, slow to scan (pointer chasing)
packed array / typed array / struct array	n × payload	fast scans; fixed element type
bitset	n / 8 bytes	O(1) test/set; popcount per word
streaming fold	O(state)	one pass; can’t revisit data
ring buffer of k	O(k), preallocated	O(1) push; older data is gone
hash map	~1.5-3× the entries’ size	O(1) average lookup
compaction	reclaims holes	O(live data) copy; addresses change
growing list	up to 2× slack, ~3× peak while copying	amortised O(1) append

Variations you’ll meet

Delta and varint encoding. Sorted IDs or timestamps stored as differences, each in 1-2 bytes instead of 8 (Protocol Buffers varints, posting lists in search engines).
Memory-mapped files. Let the OS page a large read-only file in on demand (mmap, MemoryMappedFile).
Columnar formats. Parquet and Arrow are struct-of-arrays on disk, with per-column compression.
Object pools. Reuse buffers instead of allocating per request (ArrayPool<T>), cutting GC pressure rather than total size.
Approximate structures. Bloom filters, count-min sketches and HyperLogLog give bounded error in fixed memory.

Pitfalls

Counting payload, not overhead. “10⁷ ints is 40 MB” is true in C# and false in Python (~400 MB).
Retained parents. V8 can keep a large parent string alive behind a short substring (a “sliced string”); a Python memoryview or a NumPy view keeps the whole buffer alive; a C# Span can’t escape to the heap, but a Memory<T> or a substring cache can retain more than you think.
Leaks by reference. Event listeners, closures, static dictionaries and caches without eviction keep objects reachable forever, and the GC can’t help.
readlines() / ReadAllLines / readFileSync on big input. All load the whole file.
Holey or mixed JS arrays. new Array(n) starts holey, and V8 never moves an array back to packed, so even new Array(n).fill(0) stays holey. Use Array.from({ length: n }, () => 0), push in order, or a typed array.
Peak vs steady state. A list that ends at 1 GB may have needed 3 GB while growing. Pre-size when you know n (new List<int>(n), [0] * n, new Int32Array(n)).

In the interview

Ask: How many elements, worst case? How long does it run? What is the memory budget? Must old data stay queryable?
Do the arithmetic out loud: “10⁸ events × 16 bytes packed is 1.6 GB; as Python objects it’s ~6 GB, so I’ll keep per-second counts instead: 86,400 buckets a day.”
Name the bound: “Memory is O(window), not O(events): anything older than the window is dropped on every call.”
Expect follow-ups: it must run for a year, the box has 512 MB, make it 10× smaller, how would you measure it.

Check yourself

pick one

You store 50 million distinct integers (each above 256) in a Python list. Roughly how much memory?

Check yourself

pick one

A service keeps per-user counts in a dictionary that is never cleaned, and memory grows slowly for weeks. What is the most likely root cause?

Check yourself

pick one

You need visited flags for node IDs 0..10⁹ in a Node service, and only about 0.1% (10⁶) will ever be visited. Which is the smallest?

Practice on your own

These are classic textbook exercises, not gym questions:

Measure list[int], array('q'), and a set[int] of 10⁶ elements with tracemalloc; explain each number.
Rewrite a list of {x, y, z} points as three Float64Arrays and benchmark summing all x values.
Sieve of Eratosthenes up to 10⁹ storing only odd numbers in a bitset (62.5 MB).
Remove all zeros from an array in place with one read pointer and one write pointer; then truncate.
Compute the 10 most frequent words in a 10 GB file with bounded memory (hint: what if the vocabulary doesn’t fit either?).

Go deeper

Python docs: sys.getsizeof, array, tracemalloc, and the data model on __slots__.
V8 blog: Elements kinds in V8 and Pointer compression in V8.
Microsoft Learn: Choosing between class and struct and Memory<T> and Span<T> usage guidelines. Konrad Kokosa, Pro .NET Memory Management, for object layout.
Ulrich Drepper, What Every Programmer Should Know About Memory (2007), for why packed data is also faster.

Streaming and online algorithmsOne pass, fixed-size summaries, sketches.

Bit manipulationThe tricks behind bitsets: masks, shifts, popcount.

Queues and dequesBounded FIFOs and the ring buffer behind them.

Resource allocation and quotasFragmentation and compaction of a fixed space.

Memory efficiency

The idea in plain words

See it

When to reach for it

How it works

1. Estimate before you choose

2. Pack values, don’t box them

3. One bit per flag

4. Stream instead of loading

5. Bound what you keep

6. Compact

What it costs

Variations you’ll meet

Pitfalls

In the interview

Check yourself

Practice on your own

Go deeper

Related