TL;DR: Never read the file. Stream it line by line through a generator pipeline: parse to records, group into per-instruction warp accesses, classify each, and fold the result into an aggregation keyed by instruction. Memory then depends on the number of distinct instructions, which is thousands, rather than on the number of records, which is billions. Report the worst offenders with a bounded heap rather than sorting the aggregate, since the aggregate may still be large and only the top few matter. Handle malformed lines by counting and skipping rather than raising, because a job that dies at hour three of a four-hour parse because of one truncated line has wasted the whole run, and a count of skipped lines is the honest way to report it. The classification itself, deciding whether a warp's addresses are coalesced, strided or irregular, is the small part and it is covered separately; this question is about everything around it.
How to approach it
Establish that the file cannot be read into memory, since that decides the whole shape. Build the pipeline as generators and say what each stage's memory is. Then the aggregation bound, which is the key insight. Then the two operational details, top-k and malformed input, that separate a script from something you would run on 40 GB. Close with parallelism, since that is the natural follow-up.
A strong answer
A typical situation: a script reads the trace with readlines(), works perfectly on the 200 MB sample, and is killed by the out-of-memory killer forty minutes into the real file. The second attempt streams correctly and dies at hour three on a truncated final line from an interrupted collection run.
The pipeline, with each stage's memory:
import heapq
from collections import defaultdict
def records(path):
"""Stage 1: lines to records. Memory: one line."""
bad = 0
with open(path) as f:
for lineno, line in enumerate(f, 1):
try:
inst, warp, lane, addr, width = line.split()
yield (inst, int(warp), int(lane), int(addr, 16), int(width))
except ValueError:
bad += 1
if bad <= 5:
print(f" skipping malformed line {lineno}: {line[:60]!r}")
if bad:
print(f" skipped {bad} malformed lines")
def warp_accesses(recs):
"""Stage 2: group consecutive records into one warp's access.
Memory: one warp's worth of lanes, at most 32."""
cur_key, lanes, width = None, [], None
for inst, warp, lane, addr, w in recs:
key = (inst, warp)
if key != cur_key:
if cur_key is not None:
yield cur_key[0], lanes, width
cur_key, lanes, width = key, [], w
lanes.append(addr)
if cur_key is not None:
yield cur_key[0], lanes, width
def aggregate(path, classify):
"""Stage 3: fold into per-instruction stats.
Memory: O(distinct instructions), typically thousands."""
stats = defaultdict(lambda: {"n": 0, "sectors": 0, "useful": 0, "patterns": defaultdict(int)})
for inst, addrs, width in warp_accesses(records(path)):
result = classify(addrs, width)
s = stats[inst]
s["n"] += 1
s["sectors"] += result.sectors
s["useful"] += result.useful_bytes
s["patterns"][result.pattern] += 1
return stats
def worst(stats, k=10):
"""Top-k by total sectors, without sorting the whole aggregate."""
return heapq.nlargest(k, stats.items(), key=lambda kv: kv[1]["sectors"])
The memory argument, which is the whole point:
naive: read the file
40 GB on disk, and Python objects are larger than their text, so several times that in RAM
fails on any machine
streaming records
one line at a time, so O(1) in the file size
warp grouping
holds one warp's lanes: at most 32 addresses
requires records for a warp to be contiguous in the file, which trace formats guarantee
if they are not, this stage needs a bounded buffer keyed on (instruction, warp) and a
flush policy, which is worth asking about before assuming
aggregation
one entry per distinct instruction
a kernel has thousands of instructions, not billions, so this is a few megabytes
THIS is the insight: the output is bounded by the program, not by the trace
top-k
heapq.nlargest is O(m log k) for m instructions and holds k entries
sorting the aggregate would be O(m log m) and, more importantly, would need it all in a
list at once, which it already is here but would not be if the aggregate were also streamed
the numbers, for a 40 GB trace
bytes per record, as text = about 40 B
records = 40e9 / 40 = 1e9
warp accesses (32 lanes each) = 1e9 / 32 = 3.1e7
distinct instructions in a kernel = about 5,000
aggregation entries = 5,000, at roughly 200 B each = 1 MB
ratio of input to state = 40e9 / 1e6 = 40,000 to 1
sanity: forty thousand to one is why this works at all. The output is a property of the
program being profiled, and the trace length is a property of how long it ran, so
running the kernel ten times longer does not make the aggregate any bigger
Parsing Kernel Traces and Logs covers the general pattern, and Producer-Consumer Pipelines covers the bounded-queue version of the same structure when the stages run in separate threads; the classifier this calls is the subject of a separate question, and keeping the two apart is deliberate: the parser should be testable without a real classifier and the classifier without a real trace.
Malformed input, which is an operational decision rather than a style one:
the two options
raise on the first bad line: correct for a small file where you want to know immediately
count and skip: correct for a long-running job over a large file
why skip for a 40 GB trace
the trace comes from a collection run that may have been interrupted, so a truncated last
line is expected rather than exceptional
dying at hour three discards three hours of work to report one bad line
and the information is preserved: the count is reported, and the first few are printed with
their line numbers so the cause is identifiable
what would make skipping wrong
a high skip rate, since silently discarding 30% of a trace produces confident wrong answers
so: report the count, and fail if the rate exceeds a threshold, which gets both properties
Parallelism, the natural follow-up:
the aggregation is a fold with an associative combine, so it parallelizes cleanly
split the file by byte ranges, aligned to line boundaries
each worker produces its own per-instruction stats dict
combine by summing the counters per instruction
the correctness constraint
a warp's records must not be split across workers, or one warp is classified as two partial
warps
fix: each worker starts at its offset and skips to the next instruction boundary, and
processes past its end until the current instruction ends
this is the same boundary handling any parallel line-oriented parser needs
speedup
8 workers on 40 GB: the parse is CPU-bound in the split and int conversion, so close to
linear until disk bandwidth binds
sanity: at 200 MB/s per worker and 8 workers, 40 GB takes about 25 seconds of wall clock
against 3.3 minutes single-threaded, if the storage can deliver 1.6 GB/s
The reversal condition: for a trace small enough to fit in memory, all of this is overhead and a straightforward read-and-process is clearer and faster to write. The threshold is not a fixed size but whether the file fits comfortably alongside everything else on the machine, and the honest engineering answer is to write the streaming version once and use it for both, since it is not much longer and it does not have a size limit. What is not worth doing is writing the simple version, discovering the limit in production, and rewriting under time pressure.
What interviewers probe next
- "What if records for a warp are interleaved rather than contiguous?" A bounded dictionary keyed on (instruction, warp) with a flush when an entry is complete or when the buffer is full, which trades memory for tolerance to interleaving.
- "How do you test this?" Feed the generators from a list rather than a file, so every stage is testable without I/O. That is the main practical argument for the generator structure.
- "What if the aggregate does not fit either?" Then aggregate in two passes or spill to disk keyed by instruction, but a kernel with millions of distinct instructions is not a real case.
- "How would you make it resumable?" Record the byte offset periodically with the partial aggregate, so an interrupted run restarts from the last checkpoint rather than the beginning.
Common mistakes
- Reading the file, which fails on anything past a few gigabytes.
- Building a list of all records before aggregating, which is the same failure one stage later.
- Raising on the first malformed line in a job that takes hours.
- Sorting the whole aggregate for a top-10 when a bounded heap does it in one pass.
Key takeaways
- Stream through generators: memory is one line, then one warp's 32 lanes, then one entry per distinct instruction.
- The aggregate is bounded by the program rather than by the trace, which is what makes 40 GB tractable in megabytes.
- Count and skip malformed lines with a reported total and a failure threshold, rather than dying at hour three.
- Top-k with a bounded heap is O(m log k); parallelize by byte range with instruction-boundary alignment, roughly 25 seconds for 40 GB on 8 workers at 1.6 GB/s.