Tableau de structures contre structure de tableaux

Une table de ticks peut se ranger en mémoire de deux façons, et la bonne dépend de la manière dont vous la lisez. Parcourir une colonne d'une table rangée ligne par ligne charge cinq fois plus de mémoire que vous n'en utilisez ; lire des lignes entières dans des colonnes séparées gaspille autant dans l'autre sens. Ce cours compte les défauts des deux dispositions et laisse les chiffres choisir.

La mémoire est une longue file d'octets : une table à deux dimensions doit donc être aplatie. Il y a deux manières naturelles. Dans un tableau de structures, les cinq valeurs d'un jour (ouverture, plus haut, plus bas, clôture, volume) sont rangées ensemble, puis les cinq du jour suivant, et ainsi de suite. Dans une structure de tableaux, toutes les ouvertures viennent d'abord, puis tous les plus hauts, et ainsi de suite. Les valeurs et le programme sont les mêmes, mais les adresses diffèrent.

L'adresse d'une valeur découle de sa ligne et de sa colonne. En AoS, le numéro de la valeur est ligne fois le nombre de colonnes plus la colonne. En SoA, c'est colonne fois le nombre de lignes plus la ligne. Multipliez par 8 octets pour un float64. Le code ci-dessous affiche les adresses des clôtures des quatre premiers jours dans une table de 100 jours et 5 colonnes.

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. 1En AoS la ligne suivante est n_cols valeurs plus loin : deux clôtures consécutives sont espacées de 5 valeurs (40 octets).

En AoS, les clôtures de jours consécutifs sont espacées de 40 octets. En SoA, elles sont à 8 octets l'une de l'autre, l'une juste après l'autre, ce qui est exactement la lecture dans l'ordre du premier sujet de cette compétence.

Calculer la moyenne des clôtures lit une colonne de la table. Nous transformons cette lecture en une liste d'adresses, la passons dans le cache construit aux sujets précédents et comptons les défauts pour 1 000 jours. Le dernier nombre affiché est la part utile.

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

Le parcours SoA échoue 125 fois pour 1 000 valeurs, un défaut pour huit valeurs et rien de gaspillé. Le parcours AoS échoue 625 fois, cinq fois plus, et seuls 20 % des octets chargés sont des clôtures. Les 80 % restants sont des ouvertures, plus hauts, plus bas et volumes que la moyenne ne regarde jamais, et ils chassent des lignes utiles du cache.

Beaucoup de programmes de ticks posent une autre question : pour ce tick, donne-moi ensemble le prix, la taille et le sens. Cela lit chaque valeur d'une ligne. En AoS, toute la ligne est un bloc de 40 octets, dans une ou deux lignes de cache. En SoA, les cinq valeurs sont dans cinq tableaux différents, donc chaque ligne ouvre cinq lignes de cache. Le code lit une ligne sur sept et compte les défauts.

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

Maintenant AoS gagne d'un facteur trois : 214 défauts contre 625. La disposition cinq fois pire pour le parcours de colonne est trois fois meilleure pour la lecture de lignes. Aucune disposition n'est la meilleure : chacune est la meilleure pour une manière de lire.

Un vrai programme fait les deux sortes de lecture : le choix dépend donc du mélange. Pour chaque disposition, additionnez les défauts de la charge : parcours de colonne fois défauts de colonne plus lectures de lignes fois défauts de lignes. La disposition au total le plus petit gagne, et une égalité va à AoS. Le code ci-dessous essaie quatre mélanges sur la même 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

Le labo suit le cours : les deux dispositions, les deux sortes de lecture, la comparaison, le choix pour une charge, la part utile et l'étude sur la vraie table SPY.

• Fonction · questionS'appuie sur
• address(layout, row, col, n_rows, n_cols)Où vit cette valeur ?De l'arithmétique simple
• scan_column(layout, col, n_rows, n_cols)Quelles adresses un parcours de colonne lit-il ?address
• scan_rows(layout, rows, n_rows, n_cols)Quelles adresses une lecture de lignes touche-t-elle ?address
• compare(n_rows, n_cols, col, rows)Combien de défauts chaque lecture coûte-t-elle dans chaque disposition ?scan_columnscan_rows
• best_layout(...)Quelle disposition convient à cette charge ?compare
• useful_fraction(layout, col, n_rows, n_cols)Quelle part de ce qui est chargé est utilisée ?scan_column
• study(bars)Quelle disposition convient à la table SPY ?comparebest_layout

Sujet suivant : la disposition a décidé du pas d'une table. Dans Ordre de parcours et tuilage de boucles, la table est une matrice : vous choisissez l'ordre des boucles, puis les découpez en tuiles pour qu'un bloc de la matrice reste dans le cache pendant qu'on l'utilise.