You are handed a 40 GB kernel trace. Write the parser that turns it into per-instruction access statistics without running out of memory.

TL;DR: Read the trace incrementally, assemble one complete dynamic warp access at a time, and aggregate its statistics by instruction. This bounds memory only if line size, group size and the number of aggregate keys are bounded; establish those limits from the trace format.

How to approach it

Ask what identifies one dynamic instruction execution and whether its lane records are contiguous. Decide what malformed data means for the result before choosing to skip it. Implement parsing and grouping separately so each can be tested with a small fixture, then measure the aggregate's memory use.

A strong answer

Each trace line records one lane's memory access; a warp is a group of 32 GPU threads (lanes) that issue an instruction together, so one dynamic warp access is up to 32 lines. A 40 GB file need not occupy 40 GB of RAM. Processing one line at a time avoids retaining the input, but a streaming loop can still build an unbounded dictionary or one enormous group. Name each retained structure and what limits it.

For this example, each line contains instruction access_id lane address_hex width. The access ID identifies one dynamic execution, not merely a reusable warp ID. Records for that execution must be contiguous, lanes must be unique and between 0 and 31, and all lanes in the access use the same width. An inactive lane need not appear. These are assumptions of this fixture, not guarantees of every profiler's trace format.

import heapq
from collections import defaultdict

def accesses(path):
    current, lanes, width = None, {}, None
    with open(path) as f:
        lineno = 0
        while True:
            line = f.readline(4097)
            if not line:
                break
            lineno += 1
            if len(line) > 4096:
                raise ValueError(f"line {lineno}: exceeds format limit")
            try:
                inst, access_id, lane, address, size = line.split()
                lane, address, size = int(lane), int(address, 16), int(size)
                if not 0 <= lane < 32 or address < 0 or size <= 0:
                    raise ValueError("invalid lane, address or width")
            except ValueError as exc:
                raise ValueError(f"line {lineno}: malformed record") from exc
            key = (inst, access_id)
            if key != current:
                if current is not None:
                    yield current[0], [lanes[k] for k in sorted(lanes)], width
                current, lanes, width = key, {}, size
            if lane in lanes or size != width:
                raise ValueError(f"line {lineno}: duplicate lane or mixed width")
            lanes[lane] = address
        if current is not None:
            yield current[0], [lanes[k] for k in sorted(lanes)], width

def aggregate(path, classify):
    stats = defaultdict(lambda: {"accesses": 0, "sectors": 0, "lane_bytes": 0})
    for inst, addresses, width in accesses(path):
        result = classify(addresses, width)
        row = stats[inst]
        row["accesses"] += 1
        row["sectors"] += result["sectors"]
        row["lane_bytes"] += len(addresses) * width
    return stats

def worst(stats, k=10):
    if k < 0:
        raise ValueError("k must be nonnegative")
    return heapq.nlargest(k, stats.items(), key=lambda item: item[1]["sectors"])

The classifier is injected so the parser can be tested independently. Here is a complete fixture using a simple count of distinct 32-byte sectors touched by the addresses. This is a logical address calculation, not a measurement of physical HBM traffic or a full access-pattern classifier. lane_bytes counts bytes requested by lanes and can include duplicate addresses.

from pathlib import Path
from tempfile import TemporaryDirectory

def sectors(addresses, width):
    # Merge inclusive sector ranges without materializing every sector.
    ranges = sorted((a // 32, (a + width - 1) // 32) for a in addresses)
    total, start, end = 0, None, None
    for left, right in ranges:
        if start is None:
            start, end = left, right
        elif left <= end + 1:
            end = max(end, right)
        else:
            total += end - start + 1
            start, end = left, right
    return {"sectors": total + (end - start + 1 if start is not None else 0)}

with TemporaryDirectory() as directory:
    path = Path(directory) / "trace.txt"
    path.write_text("loadA 1 0 0x0 4\nloadA 1 1 0x4 4\nloadA 2 0 0x20 4\n")
    result = aggregate(path, sectors)
    assert result["loadA"] == {"accesses": 2, "sectors": 2, "lane_bytes": 12}
    assert worst(result, 1)[0][0] == "loadA"
    path.write_text("loadA 1 0 0x0 4\nloadA 1 0 0x4 4\n")
    try:
        list(accesses(path))
    except ValueError:
        pass
    else:
        raise AssertionError("duplicate lane accepted")

The format contract must guarantee that a completed access ID does not reappear later. The implementation does not retain every prior ID to prove this. If records are arbitrarily interleaved, use an external sort or a format-defined completion marker and bounded reordering policy. Flushing an incomplete group merely because memory is full silently changes its statistics.

Assuming 40 bytes per record, 40 billion bytes contain one billion records. If every access contains 32 lane records, that is 31.25 million accesses. Neither assumption is universal. A 5,000-key aggregate may be small relative to the file, but Python dictionaries have overhead; measure their actual memory instead of assigning an unsupported byte count per entry. Spill or partition the aggregation when distinct keys exceed the budget.

This implementation fails on malformed input because dropping one lane can change the classification of an entire access. A tolerant mode should mark or discard the affected group, report what was lost, and enforce an agreed quality threshold. Skipping lines is appropriate only when the resulting bias is acceptable. Parsing Kernel Traces and Logs develops that distinction.

Parallel workers must own complete dynamic accesses. Splitting at an arbitrary line or static instruction name is insufficient. Use the format's access boundaries and merge partial aggregates by summing counters. Throughput then depends on parsing cost, storage bandwidth and the merge stage; benchmark before promising a speedup. Producer-Consumer Pipelines covers bounded buffering when these stages run separately.

What interviewers probe next

• "What if the aggregate also exceeds memory?" Partition by instruction or spill counters to disk.
• "Can we resume halfway through?" Save the aggregate and input position consistently at a complete-access boundary.
• "Does top-k reduce the aggregate's memory?" No. It limits selection work after aggregation; the dictionary still holds every key.
• "How do you detect missing lanes?" Use the trace's active-lane mask or another completeness contract. A partial warp alone is not evidence of corruption.

Common mistakes

• Streaming lines but retaining every parsed record.
• Grouping repeated executions by static instruction and warp ID alone.
• Silently classifying groups damaged by skipped lines.
• Claiming a runtime from file size without measuring the parser.

Key takeaways

• Bound line, group and aggregate state separately.
• Preserve dynamic access identity when grouping or splitting work.
• A memory-efficient parser still needs an explicit data-quality policy.