Array of structs against struct of arrays

A table of ticks can sit in memory in two ways, and the right one depends on how you read it. Scanning one column of a row-by-row table loads five times the memory you use; reading whole rows from separate columns wastes just as much the other way round. This lecture counts the misses of both layouts and lets the counts choose.

Memory is a long row of bytes, so a two-dimensional table has to be flattened. There are two natural ways. In an array of structs the five values of a day (open, high, low, close, volume) are stored together, then the five values of the next day, and so on. In a struct of arrays all the opens come first, then all the highs, and so on. The values and the program are the same, but the addresses differ.

The address of a value follows from its row and column. In AoS the value number is row times the number of columns plus the column. In SoA it is column times the number of rows plus the row. Multiply by 8 bytes for a float64. The code below prints the addresses of the closes of the first four days in a table of 100 days and 5 columns.

def address(layout, row, col, n_rows, n_cols, elem_bytes=8):    if layout == "aos":        return (row * n_cols + col) * elem_bytes1    return (col * n_rows + row) * elem_bytesclose = 3print("aos:", [address("aos", row, close, 100, 5) for row in range(4)])print("soa:", [address("soa", row, close, 100, 5) for row in range(4)])

aos: [24, 64, 104, 144]
soa: [2400, 2408, 2416, 2424]

1. 1In AoS the next row is n_cols values further, so consecutive closes are 5 values (40 bytes) apart.

In AoS the closes of consecutive days are 40 bytes apart. In SoA they are 8 bytes apart, one right after the other, which is exactly the in-order read of the first topic of this skill.

Averaging the closes reads one column of the table. We turn that read into a list of addresses, push them through the cache you built in the last topics, and count the misses for 1,000 days. The last number we print is the useful share.

def scan_column(layout, col, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in range(n_rows)]for layout in ("aos", "soa"):    misses = count_misses(scan_column(layout, 3, 1000, 5))    print(layout, "misses:", misses, "- useful share:", round(1000 * 8 / (misses * 64), 3))

aos misses: 625 - useful share: 0.2
soa misses: 125 - useful share: 1.0

The SoA scan misses 125 times for 1,000 values, one miss per eight values and nothing wasted. The AoS scan misses 625 times, five times more, and only 20% of the loaded bytes are closes. The other 80% are opens, highs, lows and volumes that the average never looks at, and they push useful lines out of the cache.

Many tick programs ask a different question: for this tick, give me the price, the size and the side together. That reads every value of a row. In AoS the whole row is one 40-byte block, which sits in one or two lines. In SoA the five values are in five different arrays, so each row opens five lines. The code reads one row in every seven and counts the misses.

def scan_rows(layout, rows, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in rows for col in range(n_cols)]rows = list(range(0, 1000, 7))for layout in ("aos", "soa"):    print(layout, "misses:", count_misses(scan_rows(layout, rows, 1000, 5)))

aos misses: 214
soa misses: 625

Now AoS wins by a factor of three: 214 misses against 625. The layout that was five times worse for the column scan is three times better for the row read. Neither layout is best; each is best for one way of reading.

A real program does both kinds of read, so the choice depends on the mix. For each layout add up the misses of the workload: column scans times the column misses plus row reads times the row misses. The layout with the smaller total wins, and a tie goes to AoS. The code below tries four mixes on the same table.

def compare(n_rows, n_cols, col, rows):    out = {}    for layout in ("aos", "soa"):        out[layout] = {            "column": count_misses(scan_column(layout, col, n_rows, n_cols)),            "rows": count_misses(scan_rows(layout, rows, n_rows, n_cols)),        }    return outdef best_layout(n_column_scans, n_row_reads, n_rows, n_cols, col, rows):    counts = compare(n_rows, n_cols, col, rows)    totals = {layout: n_column_scans * counts[layout]["column"] + n_row_reads * counts[layout]["rows"] for layout in counts}    return "soa" if totals["soa"] < totals["aos"] else "aos"rows = list(range(0, 1000, 7))for scans, reads in ((1, 4), (1, 2), (1, 1), (4, 1)):    print(scans, "column scans per", reads, "row reads:", best_layout(scans, reads, 1000, 5, 3, rows))

1 column scans per 4 row reads: aos
1 column scans per 2 row reads: aos
1 column scans per 1 row reads: soa
4 column scans per 1 row reads: soa

The lab follows the lecture: the two layouts, the two kinds of read, the comparison, the choice for a workload, the useful share and the study on the real SPY table.

• Function · questionBuilds on
• address(layout, row, col, n_rows, n_cols)Where does this value live?Plain arithmetic
• scan_column(layout, col, n_rows, n_cols)Which addresses does a column scan read?address
• scan_rows(layout, rows, n_rows, n_cols)Which addresses does a row read touch?address
• compare(n_rows, n_cols, col, rows)How many misses does each read cost in each layout?scan_columnscan_rows
• best_layout(...)Which layout suits this workload?compare
• useful_fraction(layout, col, n_rows, n_cols)How much of what is loaded is used?scan_column
• study(bars)Which layout suits the SPY table?comparebest_layout

Next topic: the layout decided the stride of one table. In Traversal order and loop tiling the table is a matrix and you choose the order of the loops, then cut the loops into tiles so that a block of the matrix stays in the cache while it is used.