Paralleles Array - Parallel array

In der Computertechnik ist eine Gruppe paralleler Arrays (auch als Struktur von Arrays oder SoA bekannt) eine Form impliziter Datenstruktur , die mehrere Arrays verwendet , um ein einzelnes Array von Datensätzen darzustellen . Es führt für jedes Feld des Datensatzes ein separates, homogenes Datenarray, das jeweils die gleiche Anzahl von Elementen aufweist. Dann sind Objekte, die sich in jedem Array am gleichen Index befinden, implizit die Felder eines einzelnen Datensatzes. Zeiger von einem Objekt auf ein anderes werden durch Array-Indizes ersetzt. Dies steht im Gegensatz zum normalen Ansatz, alle Felder jedes Datensatzes zusammen im Speicher zu speichern (auch bekannt als Array of Structures oder AoS). Zum Beispiel könnte man ein Array von 100 Namen deklarieren, von denen jeder eine Zeichenfolge ist, und 100 Altersangaben, von denen jeder eine ganze Zahl ist, wobei jedem Namen das Alter zugeordnet wird, das denselben Index hat.

Beispiele

Ein Beispiel in C mit parallelen Arrays: 

int  ages[]   = {0,          17,        2,          52,         25};
char *names[] = {"None",     "Mike",    "Billy",    "Tom",      "Stan"};
int  parent[] = {0 /*None*/, 3 /*Tom*/, 1 /*Mike*/, 0 /*None*/, 3 /*Tom*/};

for (i = 1; i <= 4; i++) {
    printf("Name: %s, Age: %d, Parent: %s \n",
           names[i], ages[i], names[parent[i]]);
}

in Perl (mit einem Hash von Arrays, um Verweise auf jedes Array zu halten): 

my %data = (
    first_name   => ['Joe',  'Bob',  'Frank',  'Hans'    ],
    last_name    => ['Smith','Seger','Sinatra','Schultze'],
    height_in_cm => [169,     158,    201,      199      ]);

for $i (0..$#{$data{first_name}}) {
    printf "Name: %s %s\n", $data{first_name}[$i], $data{last_name}[$i];
    printf "Height in CM: %i\n", $data{height_in_cm}[$i];
}

Oder in Python : 

first_names   = ["Joe",  "Bob",  "Frank",  "Hans"    ]
last_names    = ["Smith","Seger","Sinatra","Schultze"]
heights_in_cm = [169,     158,    201,      199      ]

for i in range(len(first_names)):
    print("Name: %s %s" % (first_names[i], last_names[i]))
    print("Height in cm: %s" % heights_in_cm[i])

# Using zip:
for first_name, last_name, height_in_cm in zip(first_names, last_names, heights_in_cm):
    print(f"Name: {first_name} {last_name}")
    print(f"Height in cm: {height_in_cm}")

Vor-und Nachteile

Parallele Arrays haben gegenüber dem normalen Ansatz eine Reihe praktischer Vorteile:

  • Sie können in einigen Fällen viel Platz sparen, indem sie Ausrichtungsprobleme vermeiden. Einige Architekturen funktionieren beispielsweise am besten, wenn 4-Byte-Ganzzahlen immer beginnend an Speicherpositionen gespeichert werden, die ein Vielfaches von 4 sind. Wenn das vorherige Feld ein einzelnes Byte war, könnten 3 Byte verschwendet werden. Viele moderne Compiler können solche Probleme automatisch vermeiden, obwohl in der Vergangenheit einige Programmierer Felder explizit in der Reihenfolge abnehmender Ausrichtungsbeschränkungen deklarierten.
  • Wenn die Anzahl der Elemente klein ist, können Array-Indizes deutlich weniger Platz beanspruchen als vollständige Zeiger, insbesondere auf einigen Architekturen.
  • Das sequentielle Untersuchen eines einzelnen Felds jedes Datensatzes in dem Array ist auf modernen Maschinen sehr schnell, da dies einer linearen Durchquerung eines einzelnen Arrays entspricht, was eine ideale Lokalität des Referenz- und Cache-Verhaltens zeigt.
  • Sie können eine effiziente Verarbeitung mit SIMD-Befehlen in bestimmten Befehlssatzarchitekturen ermöglichen

Einige dieser Vorteile hängen stark von der jeweiligen Programmiersprache und der verwendeten Implementierung ab.

Parallele Arrays haben jedoch auch mehrere starke Nachteile, was erklärt, warum sie im Allgemeinen nicht bevorzugt werden:

  • Sie haben eine wesentlich schlechtere Referenzlokalität, wenn sie die Datensätze nicht sequentiell besuchen und mehrere Felder jedes Datensatzes untersuchen, da die verschiedenen Arrays beliebig weit voneinander entfernt gespeichert werden können.
  • Sie verschleiern die Beziehung zwischen Feldern eines einzelnen Datensatzes (zB keine Typinformationen beziehen den Index zwischen ihnen, ein Index kann fälschlicherweise verwendet werden).
  • Sie haben wenig direkte Sprachunterstützung (die Sprache und ihre Syntax drücken normalerweise keine Beziehung zwischen den Arrays im parallelen Array aus und können keine Fehler abfangen).
  • Da das Bündel von Feldern kein "Ding" ist, ist es mühsam und fehleranfällig, es herumzureichen. Anstatt beispielsweise eine Funktion aufzurufen, um etwas mit einem Datensatz (oder einer Struktur oder einem Objekt) zu tun, muss die Funktion die Felder als separate Argumente annehmen. Wenn ein neues Feld hinzugefügt oder geändert wird, müssen sich viele Parameterlisten ändern, wobei die Übergabe von Objekten als Ganzes solche Änderungen vollständig vermeiden würde.
  • Sie sind teuer zu wachsen oder zu verkleinern, da jedes von mehreren Arrays neu zugewiesen werden muss. Arrays mit mehreren Ebenen können dieses Problem lindern, beeinträchtigen jedoch die Leistung aufgrund der zusätzlichen Umleitung, die zum Auffinden der gewünschten Elemente erforderlich ist.
  • Das Schlimmste ist vielleicht, dass sie die Möglichkeit von Fehlern erheblich erhöhen. Jedes Einfügen, Löschen oder Verschieben muss immer konsistent auf alle Arrays angewendet werden, sonst werden die Arrays nicht mehr miteinander synchronisiert, was zu bizarren Ergebnissen führt.

Die schlechte Lokalität der Referenz kann in einigen Fällen gemildert werden: Wenn eine Struktur in Gruppen von Feldern unterteilt werden kann, auf die im Allgemeinen gemeinsam zugegriffen wird, kann für jede Gruppe ein Array konstruiert werden, dessen Elemente Datensätze sind, die nur diese Teilmengen der größeren Struktur enthalten Felder. (siehe Datenorientiertes Design ). Dies ist eine wertvolle Möglichkeit, den Zugriff auf sehr große Strukturen mit vielen Mitgliedern zu beschleunigen, während die Teile der Struktur zusammengehalten werden. Eine Alternative zur Verknüpfung mit Array-Indizes besteht darin, Referenzen zu verwenden, um die Teile miteinander zu verknüpfen, aber dies kann zeitlich und räumlich weniger effizient sein.

Eine andere Alternative besteht darin, ein einzelnes Array zu verwenden, wobei jeder Eintrag eine Datensatzstruktur ist. Viele Sprachen bieten eine Möglichkeit, tatsächliche Datensätze und Arrays davon zu deklarieren. In anderen Sprachen kann es möglich sein, dies zu simulieren, indem ein Array der Größe n*m ​​deklariert wird, wobei m die Größe aller Felder zusammen ist, und die Felder in einen effektiven Datensatz gepackt werden, obwohl die jeweilige Sprache keine direkte Unterstützung für Aufzeichnungen. Einige Compiler-Optimierungen , insbesondere für Vektorprozessoren , sind in der Lage, diese Transformation automatisch durchzuführen, wenn im Programm Arrays von Strukturen erstellt werden.

Siehe auch

Verweise

  • Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest und Clifford Stein . Einführung in Algorithmen , Zweite Auflage. MIT Press und McGraw-Hill, 2001. ISBN  0-262-03293-7 . Seite 209 von Abschnitt 10.3: Implementieren von Zeigern und Objekten.
  • Skeet, Jon (3. Juni 2014). "Anti-Muster: parallele Sammlungen" . Abgerufen am 28. Oktober 2014 .