Optymalizowanie danych zależnych od czasu kompilacji

Question

W niektórych przypadkach podczas kompilacji użytkownik wie, jaka konkretna część danych algorytmu wygląda i może chcieć przekazać tę informację do kompilatora. To pytanie dotyczy tego, jak najlepiej to osiągnąć.

Tytułem przykładu, rozważmy następujący przykład rzadkiej mnożenia macierzy, w których matryca jest stała i znana w czasie kompilacji:

matrix = [ 0, 210, 0, 248, 137] 
     [ 0, 0, 0, 0, 239] 
     [ 0, 0, 0, 0, 0] 
     [116, 112, 0, 0, 7] 
     [ 0, 0, 0, 0, 165] 

W takim przypadku, w pełni branchless realizacja może zostać zapisane realizacji wektor mnożenie macierzy do dowolnego wektora wejściowego:

#include <stdio.h> 

#define ARRAY_SIZE 8 
static const int matrix[ARRAY_SIZE] = {210, 248, 137, 239, 116, 112, 7, 165}; 
static const int input_indices[ARRAY_SIZE] = {1, 3, 4, 4, 0, 1, 4, 4}; 
static const int output_indices[ARRAY_SIZE] = {0, 0, 0, 1, 3, 3, 3, 4}; 

static void matrix_multiply(int *input_array, int *output_array) 
{ 
    for (int i=0; i<ARRAY_SIZE; ++i){ 
     output_array[output_indices[i]] += (
       matrix[i] * input_array[input_indices[i]]); 
    } 
} 

int main() 
{ 
    int test_input[5] = {36, 220, 212, 122, 39}; 
    int output[5] = {0}; 

    matrix_multiply(test_input, output); 

    for (int i=0; i<5; ++i){ 
     printf("%d\n", output[i]); 
    } 

} 

drukowany poprawny wynik dla macierzy-wektor (81799, 9321, 0, 29089, 6435).

Można przewidzieć dalsze optymalizacje, które opierają się na specyficznej dla danych wiedzy na temat obszaru pamięci odniesienia.

Oczywiście, jest to podejście, z którego można korzystać, ale staje się ono nieporęczne, gdy rozmiar danych staje się duży (powiedzmy ~ 100 MB w moim przypadku), a także w każdej rzeczywistej sytuacji zależałoby od meta-programowania generować powiązaną wiedzę zależną od danych.

Czy ogólna strategia pieczenia w wiedzy dotyczącej danych ma przebieg w zakresie optymalizacji? Jeśli tak, jakie jest najlepsze podejście do tego?

W podanym przykładzie, na jednym poziomie, całość nie zostanie zredukowana do wiedzy o ARRAY_SIZE z tablicami ustawionymi w czasie wykonywania. To prowadzi mnie do myślenia, że ​​podejście jest ograniczone (i tak naprawdę jest to problem struktur danych), ale jestem bardzo zainteresowany, aby wiedzieć, czy ogólne podejście danych pochodzących z optymalizacji kompilacji jest przydatne w każdej sytuacji.

Answer 1

Nie sądzę, że jest to bardzo dobra odpowiedź na to pytanie, ale i tak spróbuję to zaoferować. Jest to również bardziej poszukiwanie tej samej podstawowej odpowiedzi.

Pracuję w 3D VFX, w tym raytracing, gdzie nie jest rzadkością podejmować dość skromne dane wejściowe z strukturami danych, które budują się w ciągu sekundy, a następnie wykonać monumentalną ilość przetwarzania, aż do punktu, w którym użytkownik może czekać godzinami wysokiej jakości produkcja w trudnych warunkach oświetleniowych.

Przynajmniej teoretycznie mogłoby to nastąpić o wiele szybciej, gdybyśmy mogli dokonać "optymalizacji danych". Zmienne mogą zmienić się w stałe literowe, może być wymagane znacznie mniej rozgałęzień, dane, które zawsze mają górną granicę 45 elementów, mogą być przydzielane na stosie zamiast sterty lub wykorzystują wcześniej inną uprzednio przydzieloną pamięć, lokalizacja odniesienia może być wykorzystywanym w większym stopniu niż kiedykolwiek wcześniej, wektoryzacja może być łatwiejsza w zastosowaniu, osiągnięcie zarówno bezpieczeństwa gwintu i wydajności może być dużo łatwiejsze, itp.

To jest dla mnie kłopotliwe, ponieważ wymaga to informacji o danych wejściowych użytkownika które mogą być dostarczone tylko po zwykłym pojęciu "kompilacji". W związku z tym wiele moich zainteresowań dotyczy technik generowania kodu podczas działania aplikacji.

Teraz wyraźnie jest to podejście, które mogą być używane, ale zaczyna coraz nieporęczny, gdy wielkość danych pobiera duże (powiedzmy ~ 100MB w moim przypadku), a także w każdym realnym świecie sytuacja będzie zależeć na meta-programowanie w celu wygenerowania powiązanej wiedzy zależnej od danych.

Myślę poza tym, jeśli rozmiar danych staje się nadmierne, wówczas mamy często potrzebują dobrego udział rozgałęzienia i zmiennych tylko w celu uniknięcia generowania kodu tak dużo, że zaczną być wąskich gardeł przez pomyłek ICACHE.

Jednak nawet możliwość zmiany kilkunastu zmiennych często używanych w czasie kompilacji i umożliwienie garstce struktur danych do wykorzystania większej wiedzy na temat określonych danych wejściowych (i przy pomocy agresywnego optymalizatora) może przynieść tutaj duże przebiegi , zwłaszcza biorąc pod uwagę, jak dobrze optymalizują się, pod warunkiem, że posiadają niezbędne informacje dostarczone z wyprzedzeniem.

Niektóre z nich można rozwiązać normalnie dzięki coraz bardziej złożonemu i uogólnionemu kodowi, technikom metaprogramowania itp., Ale szczyt tego, jak daleko możemy się tam posunąć: optymalizator może zoptymalizować tylko tyle, ile informacja jest dostępna z góry . Trudność polega na dostarczaniu tej informacji w praktyczny sposób. I, jak już się domyślacie, może to szybko stać się niewygodne, trudne do utrzymania, a produktywność staje się równie wielką (jeśli nie większą) troską niż wydajnością.

Najbardziej obiecujące techniki, które kręciłem w odniesieniu do technik generowania kodu dostrojonych dla konkretnej dziedziny problemowej, ale nie dla konkretnych danych wejściowych (optymalizacja pod kątem konkretnego wejścia będzie polegać bardziej na optymalizatorze, generowanie kodu jest tak, aby możemy dostarczyć więcej informacji potrzebnych dla optymalizatora łatwiej/odpowiednio). Skromny przykład, że już robi coś takiego jest Open Shading Language, gdzie używa kompilację JIT, który wykorzystuje tę ideę na skromnym poziomie:

OSL wykorzystuje ramy kompilatora LLVM tłumaczyć sieci shaderów do kodu maszynowego na latać (w samą porę lub "JIT"), a w procesie silnie optymalizuje shadery i sieci z pełną wiedzą o parametrach cieniowania i innych wartościach wykonawczych, które nie mogły być znane, gdy shadery zostały skompilowane z kodu źródłowego. W rezultacie, my widzimy, że nasze sieci cieniowania OSL są wykonywane o 25% szybciej niż równoważne shadery stworzone ręcznie w C! (To, jak nasze stare shadery działało w naszym renderujący.)

Choć poprawa 25% w stosunku do kodu odręcznym jest skromna, to jeszcze nic wielkiego w renderującego produkcji, a wydaje się, że moglibyśmy pójść znacznie dalej .

Wykorzystanie węzłów jako wizualnego języka programowania oferuje również bardziej restrykcyjne środowisko, które pomaga zmniejszyć błędy ludzkie, pozwala na wyrażanie rozwiązań na wyższym poziomie, widząc wyniki zmian wprowadzanych w locie (natychmiastowe przetwarzanie) itp. - więc dodaje nie tylko wydajność, ale także wydajność, której potrzebujemy, aby nie zgubić się w takich optymalizacjach. Utrzymywanie i budowanie generatora kodu może być trochę skomplikowane, ale wymaga jedynie minimalnej ilości wymaganego kodu i nie skaluje się pod względem złożoności ilości generowanego za jego pomocą kodu.

Przeprosiny - to nie jest odpowiedź na twoje pytanie jako komentarz, ale myślę, że szukamy czegoś podobnego.