Projet final : réorganiser une table de ticks et prouver la baisse des défauts

Tout ce que cette compétence a enseigné se retrouve dans une table de ticks. Huit colonnes, trois tâches qui la lisent de manières différentes et trois dispositions en mémoire. Vous modélisez l'adresse de chaque valeur, comptez les défauts de chaque tâche avec le cache que vous avez construit, les chiffrez avec le modèle de latence et prouvez quelle disposition gagne. Aucune ne gagne toutes les tâches ; l'hybride gagne le mélange, avec 1,5 fois moins de défauts que le tableau de structures.

Une table de ticks a 8 colonnes de 8 octets : un horodatage, les prix et tailles de bid et d'ask, le prix de transaction, sa taille et quelques indicateurs. Une ligne fait exactement 64 octets, la taille d'une ligne de cache. Trois tâches lisent cette table. Un balayage lit la colonne des prix de chaque ligne, pour une moyenne mobile. Une tâche cotation lit le bid, l'ask et la taille du bid de chaque ligne, pour construire un carnet. Une recherche lit le tick complet de 1 000 lignes choisies dans la table, comme le fait un débogueur ou un rejeu. La mémoire du premier sujet a une hiérarchie, le deuxième une ligne de 64 octets et le cinquième deux dispositions d'une table : le tableau de structures (les valeurs d'une ligne ensemble) et la structure de tableaux (chaque colonne seule). Il y a maintenant une troisième voie, l'hybride, qui garde ensemble les colonnes chaudes de cotation et ensemble les colonnes froides.

Les trois dispositions sont une seule idée. Une disposition est une liste de groupes de colonnes. Les valeurs d'un groupe sont rangées ligne après ligne, et les groupes se suivent. Un groupe avec toutes les colonnes est le tableau de structures ; un groupe par colonne est la structure de tableaux ; deux groupes de quatre colonnes forment notre hybride. Une seule fonction donne donc l'adresse de n'importe quelle valeur dans n'importe quelle disposition : sauter les groupes avant celui qui contient la colonne, puis avancer de row * len(group) + position valeurs dedans.

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. 1Un groupe occupe n_rows * len(group) * elem_bytes octets : le groupe suivant commence juste après.

Vérifiez les trois résultats à la main. Avec un groupe de trois colonnes, la ligne 2 colonne 1 est la valeur numéro 2 × 3 + 1 = 7, à l'octet 56. Avec un groupe par colonne, la colonne 1 commence après les 10 valeurs de la colonne 0, à l'octet 80, et la ligne 2 est 16 octets plus loin : 96. Dans l'hybride [[1, 2], [0]], le groupe de la colonne 0 vient en second, après 10 lignes de 2 valeurs (160 octets), et la ligne 3 est 24 octets plus loin : 184.

Une tâche est la liste des colonnes qu'elle lit pour chaque ligne visitée. Sa trace est, pour chaque ligne dans l'ordre, les adresses de ces colonnes ; le cache transforme la trace en défauts ; et le modèle de latence du premier sujet transforme les défauts en temps, avec 1 ns pour un succès et 80 ns pour un défaut. La comparaison est alors une boucle sur les dispositions et la preuve est le plus petit nombre. Lancez les trois tâches du cours sur 4 000 ticks et vous voyez que la meilleure disposition dépend de la tâche.

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

Le balayage veut une seule colonne : la structure de tableaux range huit prix par ligne (500 défauts) et le tableau de structures gaspille sept huitièmes de chaque ligne chargée (4 000 défauts). La recherche ponctuelle veut les huit valeurs d'une ligne : le tableau de structures prend une ligne (1 000 défauts) et la structure de tableaux huit (8 000). La cotation lit trois des quatre colonnes du groupe chaud, donc l'hybride est bon mais pas le meilleur. Quelle disposition choisir dépend de la fréquence de chaque tâche, et c'est ce que mesure le mélange.

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

Additionnés, le tableau de structures a 9 000 défauts, la structure de tableaux 10 000 et l'hybride 6 000. L'hybride ne gagne aucune tâche nettement et n'en perd aucune lourdement : les balayages et les cotations coûtent le double de la structure de tableaux, les recherches le double du tableau de structures, et le mélange favorise la disposition qui n'est jamais terrible. Dans le modèle de latence cela donne 498 µs contre 735 µs pour le tableau de structures : 1,5 fois moins de défauts et un tiers de temps en moins. C'est la preuve que demande le projet final, et elle ne vaut que pour ce mélange de tâches.

Le labo suit le cours : l'adresse d'une valeur dans n'importe quelle disposition, la trace d'une tâche, les défauts d'une tâche dans une disposition puis dans toutes, la meilleure disposition, le temps d'une tâche et l'étude de la table de ticks avec la preuve du mélange.

• Fonction · questionS'appuie sur
• address(groups, row, col, n_rows)Où est cette valeur en mémoire ?De l'arithmétique simple
• workload_trace(groups, n_rows, reads, rows)Quelles adresses la tâche touche-t-elle ?address
• layout_misses(groups, n_rows, reads, rows)Combien de défauts dans cette disposition ?workload_tracecount_misses
• compare_layouts(layouts, n_rows, reads, rows)Et dans chaque disposition ?layout_misses
• best_layout(misses)Laquelle gagne ?De l'arithmétique simple
• time_ns(accesses, misses)Combien cela coûte-t-il en temps ?De l'arithmétique simple
• study(bars)Quelle disposition gagne le mélange de tâches ?compare_layoutsbest_layouttime_ns

Compétence suivante : le côté mémoire de la performance est terminé. Les compétences suivantes de la voie optimisation passent au processeur : exécuter la même opération sur plusieurs valeurs à la fois dans des registres vectoriels, et partager des données entre cœurs sans verrous.