Capstone: re-laying out a tick table and proving the miss reduction

Everything this skill taught meets in one table of ticks. Eight columns, three jobs that read it in different ways, and three layouts in memory. You model the address of every value, count the misses of each job with the cache you built, price them with the latency model and prove which layout wins. No layout wins every job; the hybrid wins the mix, with 1.5 times fewer misses than the array of structs.

A tick table has 8 columns of 8 bytes: a timestamp, the bid and ask prices and sizes, the trade price, its size and some flags. A row is exactly 64 bytes, the size of a cache line. Three jobs read this table. A scan reads the price column of every row, for a moving average. A quote job reads the bid, the ask and the bid size of every row, to build a book. A lookup reads the full tick of 1,000 rows picked across the table, as a debugger or a replay does. The memory of the first topic has a hierarchy, the second topic a line of 64 bytes, and the fifth topic two layouts of a table: the array of structs (the values of a row together) and the struct of arrays (each column on its own). Now there is a third way, the hybrid, that keeps the hot quote columns together and the cold columns together.

All three layouts are one idea. A layout is a list of column groups. The values of one group are stored row after row, and the groups follow one another. One group with all the columns is the array of structs; one group per column is the struct of arrays; two groups of four columns is our hybrid. So one function gives the address of any value in any layout: skip the groups before the one that holds the column, then step row * len(group) + position values into it.

def address(groups, row, col, n_rows, elem_bytes=ELEM_BYTES):    base = 0    for group in groups:        if col in group:            return base + (row * len(group) + group.index(col)) * elem_bytes        base += n_rows * len(group) * elem_bytes1    raise ValueError("column %d is in no group" % col)print(address([[0, 1, 2]], 2, 1, 10))print(address([[0], [1], [2]], 2, 1, 10))print(address([[1, 2], [0]], 3, 0, 10))

56
96
184

1. 1A group takes n_rows * len(group) * elem_bytes bytes: the next group starts right after it.

Check the three results by hand. With one group of three columns, row 2 column 1 is value number 2 × 3 + 1 = 7, at byte 56. With one group per column, column 1 starts after the 10 values of column 0, at byte 80, and row 2 is 16 bytes further: 96. In the hybrid [[1, 2], [0]] the group of column 0 comes second, after 10 rows of 2 values (160 bytes), and row 3 is 24 bytes further: 184.

A job is the list of columns it reads for each row it visits. Its trace is, for every row in order, the addresses of those columns; the cache turns the trace into misses; and the latency model of the first topic turns misses into time, with 1 ns for a hit and 80 ns for a miss. The comparison is then a loop over the layouts and the proof is the smallest number. Run the three jobs of the lecture on 4,000 ticks and you see that the best layout depends on the job.

def workload_trace(groups, n_rows, reads, rows):    return [address(groups, row, col, n_rows) for row in rows for col in reads]def layout_misses(groups, n_rows, reads, rows=None):    rows = range(n_rows) if rows is None else rows    return count_misses(workload_trace(groups, n_rows, reads, rows))def compare_layouts(layouts, n_rows, reads, rows=None):    return {name: layout_misses(groups, n_rows, reads, rows) for name, groups in layouts.items()}def best_layout(misses):    return min(misses, key=misses.get)def time_ns(accesses, misses, hit_ns=HIT_NS, miss_ns=MISS_NS):    return (accesses - misses) * hit_ns + misses * miss_nsprint(workload_trace([[0, 1]], 4, [1, 0], [2]))for job, reads in WORKLOADS.items():    rows = sampled_rows(4000) if job == "lookup" else None    result = compare_layouts(LAYOUTS, 4000, reads, rows)    print(job, result, "->", best_layout(result))

[40, 32]
scan {'aos': 4000, 'soa': 500, 'hybrid': 2000} -> soa
quote {'aos': 4000, 'soa': 1500, 'hybrid': 2000} -> soa
lookup {'aos': 1000, 'soa': 8000, 'hybrid': 2000} -> aos

The scan wants a single column: the struct of arrays packs eight prices per line (500 misses) and the array of structs wastes seven eighths of every line it loads (4,000 misses). The point lookup wants all eight values of a row: the array of structs takes one line (1,000 misses) and the struct of arrays eight (8,000). The quote job reads three of four columns of the hot group, so the hybrid is good but not the best. Which layout to choose depends on how often each job runs, and that is what the mix measures.

def study(bars):    n_rows = min(int(bars.shape[0]), 4000)    misses = {}    accesses = 0    for job, reads in WORKLOADS.items():        rows = sampled_rows(n_rows) if job == "lookup" else None        misses[job] = compare_layouts(LAYOUTS, n_rows, reads, rows)        accesses += len(reads) * (len(rows) if rows is not None else n_rows)    mixed = {name: sum(misses[job][name] for job in WORKLOADS) for name in LAYOUTS}    best = best_layout(mixed)    return {"mixed": mixed, "mixed_best": best, "reduction": mixed["aos"] / mixed[best],            "ns": {name: time_ns(accesses, mixed[name]) for name in LAYOUTS}}out = study(load_bars())print(out["mixed"], "->", out["mixed_best"])print(round(out["reduction"], 2), "times fewer misses than the array of structs")print({name: round(ns / 1000) for name, ns in out["ns"].items()}, "microseconds")

{'aos': 9000, 'soa': 10000, 'hybrid': 6000} -> hybrid
1.5 times fewer misses than the array of structs
{'aos': 735, 'soa': 814, 'hybrid': 498} microseconds

Added up, the array of structs misses 9,000 times, the struct of arrays 10,000 and the hybrid 6,000. The hybrid has no job it wins outright, and none it loses badly: the scans and the quotes cost twice what the struct of arrays pays, the lookups twice what the array of structs pays, and the mix favours the layout that is never terrible. In the latency model that is 498 µs against 735 µs for the array of structs: 1.5 times fewer misses and a third less time. This is the proof the capstone asks for, and it holds only for this mix of jobs.

The lab follows the lecture: the address of a value in any layout, the trace of a job, the misses of a job in one layout and in all of them, the best layout, the time of a job and the study of the tick table with the proof of the mix.

• Function · questionBuilds on
• address(groups, row, col, n_rows)Where is this value in memory?Plain arithmetic
• workload_trace(groups, n_rows, reads, rows)Which addresses does the job touch?address
• layout_misses(groups, n_rows, reads, rows)How many misses in this layout?workload_tracecount_misses
• compare_layouts(layouts, n_rows, reads, rows)And in every layout?layout_misses
• best_layout(misses)Which one wins?Plain arithmetic
• time_ns(accesses, misses)What does it cost in time?Plain arithmetic
• study(bars)Which layout wins the mix of jobs?compare_layoutsbest_layouttime_ns

Next skill: the memory side of performance is done. The next skills in the optimization track move to the processor: running the same operation on many values at once in vector registers, and sharing data between cores without locks.