Tablica równoległa

W informatyce grupa tablic równoległych (znana również jako struktura tablic lub SoA) jest formą ukrytej struktury danych , która wykorzystuje wiele tablic do reprezentowania pojedynczej tablicy rekordów . Przechowuje oddzielną, jednorodną tablicę danych dla każdego pola rekordu, z których każde ma taką samą liczbę elementów. Wtedy obiekty znajdujące się w tym samym indeksie w każdej tablicy są niejawnie polami pojedynczego rekordu. Wskaźniki z jednego obiektu do drugiego są zastępowane indeksami tablicy. Kontrastuje to z normalnym podejściem polegającym na przechowywaniu wszystkich pól każdego rekordu razem w pamięci (znanym również jako tablica struktur lub AoS). Na przykład można zadeklarować tablicę zawierającą 100 imion, z których każde jest łańcuchem, i 100 grup wiekowych, z których każde jest liczbą całkowitą, łącząc każde imię z wiekiem o tym samym indeksie.

Przykłady

Przykład w C przy użyciu tablic równoległych:

      0                                     
                      
    0      int  wiek  []  =  {  ,  17  ,  2  ,  52  ,  25  };  char  *  imiona  []  =  {  "Brak"  ,  "Mike"  ,  "Billy"  ,  "Tomek"  ,  "Stan"  };  int  rodzic  []  =  {  /*Brak*/  ,  3  /*Tomek*/  ,  1  /*Mike*/  ,  0   

        
    
             
 /*Brak*/  ,  3  /*Tomek*/  };  for  (  i  =  1  ;  i  <=  4  ;  i  ++  )  {  printf  (  "Imię: %s, Wiek: %d, Rodzic: %s  \n  "  ,  imiona  [  i  ],  wiek  [  i  ],  imiona  [  rodzic  [  ja  ]]);  }

w Perlu (używając skrótu tablic do przechowywania odniesień do każdej tablicy):

   
                  
         
                           

  my  %data  =  (  imię  =>  [  'Joe'  ,  'Bob'  ,  'Frank'  ,  'Hans'  ],  last_name  =>  [  'Smith'  ,  'Seger'  ,  'Sinatra'  ,  'Schultze'  ],  height_in_cm  =>  [  169  ,  158  ,  201  ,  199  ]);  za  $i  0 
       
      
 (  ..  $#  {  $dane  {  imię  }})  {  printf  "Imię: %s %s\n"  ,  $ dane  {  imię  } [  $i  ],  $ dane  {  nazwisko  } [  $i  ];  printf  "Wysokość w CM: %i\n"  ,  $data  {  wysokość_w_cm  }[  $i  ];  }

Lub w Pythonie :

              
     
                       

    imiona  =  [  "Joe"  ,  "Bob"  ,  "Frank"  ,  "Hans"  ]  nazwiska_nazwisk  =  [  "Smith"  ,  "Seger"  ,  "Sinatra"  ,  "Schultze"  ]  wysokość_w_cm  =  [  169  ,  158  ,  201  ,  199  ]  dla  i  w  zasięgu  (  len  ( 
        
      


       first_names  )):  print  (  "Nazwa:  %s  %s  "  %  (  imion  [  i  ],  last_names  [  i  ]))  print  (  "Wysokość w cm:  %s  "  %  heights_in_cm  [  i  ])  # Używając zip:  for  first_name  ,  nazwisko  ,  wzrost_w_cm  w  zip  (  imiona  ,  nazwiska  
     
     ,  wysokości_w_cm  ):  print  (  f  "Imię:  {  imię  }  {  nazwisko  }  "  )  print  (  f  " Wzrost w cm:  {  wysokość_ w cm  }  "  )

Plusy i minusy

Tablice równoległe mają szereg praktycznych zalet w porównaniu z podejściem normalnym:

W niektórych przypadkach mogą zaoszczędzić znaczną ilość miejsca, unikając problemów z wyrównaniem. Na przykład niektóre architektury działają najlepiej, jeśli 4-bajtowe liczby całkowite są zawsze przechowywane, zaczynając od lokalizacji pamięci, które są wielokrotnością 4. Jeśli poprzednie pole było jednym bajtem, 3 bajty mogą zostać zmarnowane. Wiele nowoczesnych kompilatorów może automatycznie uniknąć takich problemów, chociaż w przeszłości niektórzy programiści jawnie deklarowali pola w kolejności malejących ograniczeń wyrównania.
Jeśli liczba elementów jest mała, indeksy tablicy mogą zajmować znacznie mniej miejsca niż pełne wskaźniki, szczególnie w przypadku niektórych architektur.
Sekwencyjne badanie pojedynczego pola każdego rekordu w tablicy jest bardzo szybkie na nowoczesnych maszynach, ponieważ jest to równoznaczne z liniowym przechodzeniem pojedynczej tablicy, wykazującym idealną lokalizację odniesienia i zachowanie pamięci podręcznej.
Mogą umożliwiać wydajne przetwarzanie z instrukcjami SIMD w pewnych architekturach zestawu instrukcji

Kilka z tych zalet silnie zależy od konkretnego języka programowania i używanej implementacji.

Jednak tablice równoległe mają również kilka poważnych wad, co wyjaśnia, dlaczego nie są one ogólnie preferowane:

Mają znacznie gorszą lokalizację odniesienia podczas odwiedzania rekordów niesekwencyjnie i badania wielu pól każdego rekordu, ponieważ różne tablice mogą być przechowywane dowolnie daleko od siebie.
Zaciemniają związek między polami pojedynczego rekordu (np. żadna informacja o typie nie odnosi się do indeksu między nimi, indeks może być błędnie użyty).
Mają niewielką bezpośrednią obsługę języków (język i jego składnia zazwyczaj nie wyrażają żadnego związku między tablicami w tablicy równoległej i nie mogą wychwytywać błędów).
Ponieważ pakiet pól nie jest „rzeczą”, przekazywanie go jest żmudne i podatne na błędy. Na przykład, zamiast wywoływać funkcję w celu zrobienia czegoś z jednym rekordem (lub strukturą lub obiektem), funkcja musi przyjąć pola jako osobne argumenty. Gdy nowe pole jest dodawane lub zmieniane, wiele list parametrów musi ulec zmianie, a przekazanie obiektów jako całości pozwoliłoby całkowicie uniknąć takich zmian.
Ich powiększanie lub zmniejszanie jest drogie, ponieważ każda z kilku macierzy musi zostać ponownie przydzielona. Tablice wielopoziomowe mogą złagodzić ten problem, ale wpływają na wydajność ze względu na dodatkowe pośrednictwo potrzebne do znalezienia pożądanych elementów.
Być może najgorsze jest to, że znacznie zwiększają prawdopodobieństwo popełnienia błędów. Każde wstawienie, usunięcie lub przeniesienie musi być zawsze stosowane konsekwentnie do wszystkich tablic, w przeciwnym razie tablice nie będą już ze sobą synchronizowane, co prowadzi do dziwacznych wyników.

W niektórych przypadkach można złagodzić złą lokalizację odniesienia: jeśli strukturę można podzielić na grupy pól, które są ogólnie dostępne razem, można skonstruować tablicę dla każdej grupy, a jej elementami są rekordy zawierające tylko te podzbiory większej struktury pola. (patrz projektowanie zorientowane na dane ). Jest to cenny sposób na przyspieszenie dostępu do bardzo dużych struktur z wieloma członkami, przy jednoczesnym utrzymaniu powiązanych ze sobą części struktury. Alternatywą dla wiązania ich razem za pomocą indeksów tablicowych jest użycie odniesień do powiązania części razem, ale może to być mniej wydajne w czasie i przestrzeni.

Inną alternatywą jest użycie pojedynczej tablicy, w której każdy wpis jest strukturą rekordów. Wiele języków umożliwia deklarowanie rzeczywistych rekordów i ich tablic. W innych językach można to zasymulować, deklarując tablicę o rozmiarze n*m, gdzie m jest rozmiarem wszystkich pól razem, pakując pola w coś, co faktycznie jest rekordem, mimo że dany język nie obsługuje bezpośrednio dokumentacja. Niektóre optymalizacje kompilatora , szczególnie dla procesorów wektorowych , są w stanie wykonać tę transformację automatycznie, gdy w programie tworzone są tablice struktur. ^{[ potrzebne źródło ]}

Zobacz też

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7 . Strona 209 sekcji 10.3: Implementacja wskaźników i obiektów.
Skeet, Jon (3 czerwca 2014). „Anty-wzór: kolekcje równoległe” . Źródło 28 października 2014 r .