Witam,
Napisałem algorytm SI Backpropagation w C++, później przepisałem go do C# oczekując może z 20-30% spadku wydajności, lecz okazało się ze wynosi ponad 920%. Co może być przyczyna tego zjawiska? W C# używam list do przechowywania danych a w C++ vectorow.
Do pomiarow czasow uzylem:
Stopwatch sw = Stopwatch.StartNew();
sw.Stop();
clock_t t = clock();
t = clock() - t;
cout << "Czas: " << ((float)t)/CLOCKS_PER_SEC << endl;
...Pokaż algorytm?
W nim musi być bubel.
Jestem pewien że żadnego bubla nie ma, dodałem liczniki aby sprawdzić czy pętle robią tyle samo obrotów:
public void Train(double[] inputs, double[] targets)
{
int licznik = 0;
ComputeOutputs(inputs);
ComputeErrors(inputs, targets);
for (int k = 0; k < network.Count; k++)
{
for (int i = 0; i < network[k].Count; i++)
{
for (int j = 0; j < network[k][i].Count; j++)
{
if (j == network[k][i].BiasIndex)
{
network[k][i][j] += learningCoefficient * errors[k][i] * bias;
}
else
{
if (k == 0)
{
network[k][i][j] += learningCoefficient * errors[k][i] * inputs[j];
}
else
{
network[k][i][j] += learningCoefficient * errors[k][i] *
activationResults[k - 1][j];
}
}
licznik++;
}
}
}
}
//*************************
private void ComputeOutputs(double[] inputs)
{
int licznik = 0;
for (int k = 0; k < network.Count; k++)
{
for (int i = 0; i < network[k].Count; i++)
{
activationResults[k][i] = 0.0;
for (int j = 0; j < network[k][i].Count; j++)
{
if (j == network[k][i].BiasIndex)
{
activationResults[k][i] += network[k][i][j] * bias;
}
else
{
if (k == 0)
{
activationResults[k][i] += network[k][i][j] * inputs[j];
}
else
{
activationResults[k][i] += network[k][i][j] * activationResults[k - 1][j];
}
}
licznik++;
}
activationResults[k][i] = network[k][i].Activate(activationResults[k][i]);
}
}
}
//*********************
private void ComputeErrors(double[] inputs, double[] targets)
{
int licznik = 0;
int licznik2 = 0;
int lastLayerIndex = network.Count - 1;
RMSError = 0.0;
for (int k = lastLayerIndex; k >= 0; k--)
{
for (int i = 0; i < network[k].Count; i++)
{
if (k == lastLayerIndex)
{
errors[k][i] = targets[i] - activationResults[k][i];
RMSError += Math.Pow(errors[k][i], 2);
}
else
{
errors[k][i] = 0.0;
for (int j = 0; j < network[k + 1].Count; j++)
{
licznik2++;
//TODO sprawdzic czy nie ma bledu po wylaczeniu polaczenia
errors[k][i] += errors[k + 1][j] * network[k + 1][j][i];
}
}
errors[k][i] = network[k][i].ComputeDerivative(activationResults[k][i]) * errors[k][i];
licznik++;
}
}
RMSError = Math.Sqrt(RMSError);
}
void Nauczaj(const vector<double> &probka)
{
int licznik = 0;
LiczY(probka);
LiczE(probka);
for(unsigned int k = 0; k < siecNeuronowa.size(); k++)
{
for(unsigned int i = 0; i < siecNeuronowa[k].size(); i++)
{
for(unsigned int j = 0; j < siecNeuronowa[k][i].size(); j++)
{
if(k == 0)
{
siecNeuronowa[k][i][j] += 2 * wspolczynikUczenia * bledy[k][i] * probka[j];
}
else
{
if(j == 0)
{
siecNeuronowa[k][i][j] += 2 * wspolczynikUczenia * bledy[k][i] * x0;
}
else
{
siecNeuronowa[k][i][j] += 2 * wspolczynikUczenia * bledy[k][i] *
wynikiOstatnichAktywacji[k-1][j-1];
}
}
licznik++;
}
}
}
cout << licznik << endl;
}
//**********************
void LiczY(const vector<double> &probka)
{
int licznik = 0;
for(unsigned int k = 0; k < siecNeuronowa.size(); k++)
{
for(unsigned int i = 0; i < siecNeuronowa[k].size(); i++)
{
wynikiOstatnichAktywacji[k][i] = 0;
for(unsigned int j = 0; j < siecNeuronowa[k][i].size(); j++)
{
if(k == 0)
{
wynikiOstatnichAktywacji[k][i] += siecNeuronowa[k][i][j] * probka[j];
}
else
{
if(j == 0)
{
wynikiOstatnichAktywacji[k][i] += siecNeuronowa[k][i][j] * x0;
}
else
{
wynikiOstatnichAktywacji[k][i] += siecNeuronowa[k][i][j] * wynikiOstatnichAktywacji[k-1][j-1];
}
}
licznik++;
}
wynikiOstatnichAktywacji[k][i] = Aktywacja(wynikiOstatnichAktywacji[k][i]);
}
}
cout << licznik << endl;
}
//*********************
void LiczE(const vector<double> &probka)
{
int licznik = 0, licznik2 = 0;
int indeksWyniku = iloscWyjscY;
for(int k = indeksOstatniejWarstwy; k >= 0; k--)
{
for(unsigned int i = 0; i < siecNeuronowa[k].size(); i++)
{
if(k == indeksOstatniejWarstwy)
{
bledy[k][i] = probka[probka.size()-indeksWyniku] - wynikiOstatnichAktywacji[k][i];
bledyPrzedPochodna[k][i] = bledy[k][i];
indeksWyniku--;
}
else
{
bledy[k][i] = 0;
for(unsigned int j = 0; j < siecNeuronowa[k+1].size(); j++)
{
bledy[k][i] += bledy[k+1][j] * siecNeuronowa[k+1][j][i+1];
licznik2++;
}
bledyPrzedPochodna[k][i] = bledy[k][i];
}
bledy[k][i] = PochodnaAktywacji(wynikiOstatnichAktywacji[k][i]) * bledy[k][i];
licznik++;
}
}
cout << licznik << " " << licznik2 << endl;
}
Nauczaj, Train: licznik = 9;
LiczY, ComputeOutputs: licznik = 9;
LiczE, ComputeErrors: licznik = 3, licznik2 = 2
Zacznijmy od oczywistości (które każdemu się zdarza przeoczyć).
Wersję C# uruchamiasz Release czy Debug?
edit - jeśli jednak Release - prześlij, proszę, .exe z wersji .net i C++ (ew. pełne źródła gotowe do skompilowania).
msm napisał(a):
Zacznijmy od oczywistości (które każdemu się zdarza przeoczyć).
Wersję C# uruchamiasz Release czy Debug?
edit - jeśli jednak Release - prześlij, proszę, .exe z wersji .net i C++ (ew. pełne źródła gotowe do skompilowania).
Należy podkreślić, że nawet, jak się release uruchamia przez kompilator (polecenie Run), to pracuje wolniej, niż jak się ją uruchomi z pliku exe.
Popełniłem mały błąd i w projekcie C# dodawałem dll debug zamiast release, ale różnica dalej pozostała dość znaczna.
C# = 4.6 sec.
C++ = 1.38 sec.
Spostrzeżenie 1)
public static class Utility
{
public static double Rand()
{
Random r = new Random(DateTime.Now.Millisecond);
Thread.Sleep(1); // ???
return r.NextDouble();
}
}
Prawdopodobnie wydajniejsze będzie:
public static class Utility
{
static Random r = new Random();
public static double Rand()
{
return r.NextDouble();
}
}
(i działające lepiej - wszystkie Twoje randomy tworzone w jednej ms zwracają tą samą wartość...)
Podstawowa różnica między C++ a językami zarządzanymi w takich przypadkach to to, że C++ nie sprawdza indeksów tablic (tzn nie sprawdza czy indeksy wychodzą poza rozmiar tablicy), a .NET, JVM, Python, itd sprawdzają. JVM ma dość dobre heurystyki do optymalizacji takich sprawdzeń czy też wycinania nadmiarowych. Jak jest w .NET nie wiem. W każdym razie można zrobić prosty test i pobawić się disasemblerem: http://stackoverflow.com/questions/9304726/array-bounds-check-elimination-in-the-clr
Przede wszystkim te kody nie są równoważne. W C# neuron jest klasą. Wszystko jest z resztą obiektowe, a w C++ masz tablicę i kilka funkcji.
ad. @Rev:
C#:
public double Activate(double net)
{
return activator.Activate(net);
}
interface IActivatable
{
double Activate(double net);
double ComputeDerivative(double value);
}
struct SigmoidalActivator : IActivatable
{
public double Activate(double net)
{
return 1.0 / (1.0 + Math.Exp(-net));
}
public double ComputeDerivative(double value)
{
return value * (1.0 - value);
}
}
C++:
double Aktywacja(double s)
{
return 1 / (1 + exp(-s));
}
Hmm...
Rzeczywiscie obiektowość tutaj ma trochę znaczenie ale nie kluczowe, napisałem specjalnie prościutką klasę. Dzięki temu zyskałem całe 0.8 sec. A gdzie się marnuje reszta czasu?
C++ = 1.28;
C# = 3.83;
Backpropagation.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SimpleBP
{
class BackPropagation
{
List<List<List<double>>> network;
List<List<double>> errors;
List<List<double>> activationResults;
double bias = 1;
double learningCoefficient = 0.1;
static Random r = new Random();
public BackPropagation()
{
CreateNetwork();
}
private void CreateNetwork()
{
network = new List<List<List<double>>>();
//warstwy
network.Add(new List<List<double>>());
network.Add(new List<List<double>>());
//neurony i wagi
network[0].Add(new List<double>(new double[3]));
network[0].Add(new List<double>(new double[3]));
network[1].Add(new List<double>(new double[3]));
//errors
errors = new List<List<double>>();
errors.Add(new List<double>(new double[2]));
errors.Add(new List<double>(new double[1]));
//activationResults
activationResults = new List<List<double>>();
activationResults.Add(new List<double>(new double[2]));
activationResults.Add(new List<double>(new double[1]));
}
public void Train(double[] inputs, double[] targets)
{
ComputeOutputs(inputs);
ComputeErrors(inputs, targets);
for (int k = 0; k < network.Count; k++)
{
for (int i = 0; i < network[k].Count; i++)
{
for (int j = 0; j < network[k][i].Count; j++)
{
if (j == network[k][i].Count - 1)
{
network[k][i][j] += learningCoefficient * errors[k][i] * bias;
}
else
{
if (k == 0)
{
network[k][i][j] += learningCoefficient * errors[k][i] * inputs[j];
}
else
{
network[k][i][j] += learningCoefficient * errors[k][i] *
activationResults[k - 1][j];
}
}
}
}
}
}
public void ComputeOutputs(double[] inputs)
{
for (int k = 0; k < network.Count; k++)
{
for (int i = 0; i < network[k].Count; i++)
{
activationResults[k][i] = 0.0;
for (int j = 0; j < network[k][i].Count; j++)
{
if (j == network[k][i].Count - 1)
{
activationResults[k][i] += network[k][i][j] * bias;
}
else
{
if (k == 0)
{
activationResults[k][i] += network[k][i][j] * inputs[j];
}
else
{
activationResults[k][i] += network[k][i][j] * activationResults[k - 1][j];
}
}
}
activationResults[k][i] = Activate(activationResults[k][i]);
}
}
}
public void ComputeErrors(double[] inputs, double[] targets)
{
int lastLayerIndex = network.Count - 1;
for (int k = lastLayerIndex; k >= 0; k--)
{
for (int i = 0; i < network[k].Count; i++)
{
if (k == lastLayerIndex)
{
errors[k][i] = targets[i] - activationResults[k][i];
}
else
{
errors[k][i] = 0.0;
for (int j = 0; j < network[k + 1].Count; j++)
{
errors[k][i] += errors[k + 1][j] * network[k + 1][j][i];
}
}
errors[k][i] = ComputeDerivative(activationResults[k][i]) * errors[k][i];
}
}
}
private void Rand()
{
for (int k = 0; k < network.Count; k++)
{
for (int i = 0; i < network[k].Count; i++)
{
for (int j = 0; j < network[k][i].Count; j++)
{
network[k][i][j] = r.NextDouble();
}
}
}
}
public double Activate(double net)
{
return 1.0 / (1.0 + Math.Exp(-net));
}
public double ComputeDerivative(double value)
{
return value * (1.0 - value);
}
}
}
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace SimpleBP
{
class Program
{
static void Main(string[] args)
{
BackPropagation bp = new BackPropagation();
double[][] x =
{
new double[] { 0.9, 0.9 },
new double[] { 0.9, 0.1 },
new double[] { 0.1, 0.9 },
new double[] { 0.1, 0.1 }
};
double[][] y =
{
new double[] { 0.1 },
new double[] { 0.9 },
new double[] { 0.9 },
new double[] { 0.1 }
};
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < 500000; i++)
{
for (int k = 0; k < 4; k++)
{
bp.Train(x[k], y[k]);
}
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
}
}
}
To jest dla mnie trochę dziwne:
List<List<List<double>>> network;
List<List<double>> errors;
List<List<double>> activationResults;
Użyj tablic wielowymiarowych (np. double[,,] network). Z tego co widzę na pierwszy rzut oka nie jest ci koniecznie potrzebne dodawanie nowych elementów tablic w locie.
pozytywista napisał(a):
To jest dla mnie trochę dziwne:
List<List<List<double>>> network;
List<List<double>> errors;
List<List<double>> activationResults;
Użyj tablic wielowymiarowych (np. double[,,] network). Z tego co widzę na pierwszy rzut oka nie jest ci koniecznie potrzebne dodawanie nowych elementów tablic w locie.
Przepisałem cały algorytm na nowo z użyciem tablic jagged i uzyskałem 1.7 sec, co nie jest już złym czasem.
Teraz mam kolejny problem, nie wiem dlaczego banalne wręcz przypisanie, które nawet nie wykonuje się dużo razy zajmuje tyle czasu.
Daj obecny kod to spróbuję wyprofilować/zoptymalizować trochę (na razie się nie bawiłem, tylko przeglądałem kod)
``` <joke>Pewnie to branch prediction</joke> - i bez komentarzy mi somekindziesama zmiana
RMSError += Math.Pow(errors[k][i], 2);
na
RMSError += errors[k][i]*errors[k][i];
przyspiesza program o 20%.
A zresztą, nie wychodzę dzisiaj z domu, kogo obchodzi że jest piątek.
Czas obecnie: 940 ms
(Liczony ofc na moim komputerze / środowisku etc - u innych efekt może być zupełnie inny)
Cel - zbić czas do połowy tego, tzn. 470 ms
public void Train(double[] inputs, double[] targets)
{
activationResults[inputsIndex] = inputs;
ComputeOutputs();
ComputeErrors(targets);
int jMax, iMax, kMax = network.Length; // <<<<<<<<<<<<
for (int k = 0; k < kMax; ++k)
{
iMax = network[k].Length;
for (int i = 0; i < iMax ; ++i)
{
jMax = network[k][i].Length;
for (int j = 0; j < jMax; ++j)
{
network[k][i][j] += learningCoefficient * errors[k][i] * activationResults[k][j];
}
}
}
}
Tak /nie/ robimy - to, domyślam się, miała być optymalizacja, ale niestety - kompletnie nietrafiona (dlatego nie warto optymalizować na ślepo ;) ).
Jak już wspominałem, zasady dot. ABCE w .NET (tzn. obecne szczegóły implementacyjne które mogą się zmienić blablabla) są bardzo dziwne.
Na przykład dla
for (int i = 0; i < arr.Length; i++)
otrzymujesz ABCE, ale dla
int l = arr.Length;
for (int i = 0; i < l; i++)
Już nie. Cóż, musimy z tym żyć.
Moja wersja:
public void Train(double[] inputs, double[] targets)
{
activationResults[inputsIndex] = inputs;
ComputeOutputs();
ComputeErrors(targets);
for (int k = 0; k < network.Length; ++k)
{
var layer = network[k];
for (int i = 0; i < layer.Length; ++i)
{
var neuron = layer[i];
for (int j = 0; j < neuron.Length; ++j)
{
neuron[j] += learningCoefficient * errors[k][i] * activationResults[k][j];
}
}
}
}
U mnie przyśpieszenie ze średnio 940 do 900 - ok, zawsze jakiś początek.
Oczywiście problem jest taki, że errors i activationResults dalej powodują ABC...
Czas obecnie: 900 ms
Można iść dalej w tym kierunku:
public void Train(double[] inputs, double[] targets)
{
activationResults[inputsIndex] = inputs;
ComputeOutputs();
ComputeErrors(targets);
for (int k = 0; k < network.Length; ++k)
{
var layer = network[k];
var layer_errs = errors[k];
var layer_activ = activationResults[k];
for (int i = 0; i < layer.Length; ++i)
{
var neuron = layer[i];
var error = layer_errs[i];
for (int j = 0; j < neuron.Length; ++j)
{
neuron[j] += learningCoefficient * error * layer_activ[j];
}
}
}
}
Ale wszystkich ABC nie wyeliminujemy. Rozwiązaniem byłoby napisanie kodu... bardziej obiektowo - tzn. rezygnacja z tablic na rzecz większego skupienia się na strukturach i przynależności informacji do nich. Czy to by faktycznie przyśpieszyło program, i jeśli tak to o ile - nie wiem, ale na pewno w tym przypadku pozwoliłoby na eliminację wszystkich checków granic tablicy.
A, czas dalej mocno skacze, ale ta wersja średnio wykonuje się jakieś 870 (zarejestrowane od 830 do 900)
Czas obecnie: 870 ms
Poprawienie ComputeOutputs w tym samym stylu:
private void ComputeOutputs()
{
for (int k = 0; k < network.Length; ++k)
{
var layer = network[k];
var layer_activ = activationResults[k];
var next_layer_activ = activationResults[k + 1];
for (int i = 0; i < layer.Length; ++i)
{
var activRes = 0.0;
var neuron = layer[i];
for (int j = 0; j < neuron.Length; ++j)
{
activRes += neuron[j] * layer_activ[j];
}
next_layer_activ[i] = neuron.Activate(next_layer_activ[i]);
}
}
}
Czasy z 10 powtórzeń: 882, 796, 846, 830. Średnia około 840 - znowu lepiej.
Czas obecnie: 840 ms
Zostało jeszcze ComputeErrors.
Po poprawie, czasy - 620, 606, 616, 626, średnia koło 620 0 już lepiej (ja się pytam, tyle tych 6 to gdzie 666?)!
Czas obecnie: 620 ms
Kod:
private void ComputeErrors(double[] targets)
{
var rmsError = 0.0;
for (int k = lastLayerIndex; k >= 0; --k)
{
int kk = k + 1;
var layer = network[k];
var next_layer = k == lastLayerIndex ? null : network[k + 1];
var layer_errs = errors[k];
var next_layer_errs = k == lastLayerIndex ? null : errors[k + 1];
var next_layer_activ = activationResults[k + 1];
for (int i = 0; i < layer.Length; ++i)
{
if (k == lastLayerIndex)
{
layer_errs[i] = targets[i] - next_layer_activ[i];
rmsError += layer_errs[i] * layer_errs[i];
}
else
{
errors[k][i] = 0.0;
for (int j = 0; j < next_layer.Length; ++j)
{
layer_errs[i] += next_layer_errs[j] * next_layer[j][i];
}
}
layer_errs[i] = layer[i].ComputeDerivative(next_layer_activ[i]) * layer_errs[i];
}
}
RMSError = Math.Sqrt(rmsError);
}
Jeśli porównanie z C++, ma być uczciwe, wyrzuciłem też wszystkie występienia IActivatora - czyli było:
public double Activate(double net)
{
return activator.Activate(net);
}
public double ComputeDerivative(double value)
{
return activator.ComputeDerivative(value);
}
Jest:
public double Activate(double net)
{
return 1.0 / (1.0 + Math.Exp(-net));
}
public double ComputeDerivative(double value)
{
return value * (1.0 - value);
}
Czasy: 578, 587, 580, 576, średnia: 570
Czas obecnie: 570 ms
Zdecydowanie najwięcej czasu schodziło w metodzie ComputeOutputs (prawie 40% całej nauki).
Dlatego jej i neuronowi poświęciłem więcej uwagi. I co się okazało - coś słabo idzie optymalizacja indekserów :<. Dlatego zmieniłem trochę klasę neuron (i wyrzuciłem nieużywaną tablicę booli - była potrzebna?) - ostatecznie wygląda tak:
class Neuron
{
double[] weights; // hack?
public Neuron(int weightCount)
{
CreateTables(weightCount + 1);
}
private void CreateTables(int size)
{
weights = new double[size];
}
public double Activate(double net)
{
return 1.0 / (1.0 + Math.Exp(-net));
}
public double ComputeDerivative(double value)
{
return value * (1.0 - value);
}
public double[] Weights { get { return weights; } }
}
Trochę zmian pojawia się w reszcie kodu, ale obecnie czasy to 510, 531, 486, 518 - średnio koło 520. Jeszcze tylko trochę...
Czas obecnie: 520 ms
Zacząłem od zinlinowania funkcji Activate (/i tak/ nie są razem z Computederivative zbyt object-oriented - równie dobrze mogłyby być statyczne, a wygląda na to że JIT (co znowu JIT? Są krótkie, nie mają for-ów itp - może to był tylko problem u mnie) ich nie inlinował).
next_layer_activ[i] = 1.0 / (1.0 + Math.Exp(activRes));
Czas zmniejszył się o parę ms, do około 510. Ciągle za dużo.
No i /the final hack/.
Naprawdę, nie było nic innego co by się narzucało.
Po prostu, tylko jedno miejsce gdzie się coś faktycznie dzieje w tym momencie w kodzie.
To nie moja wina :(
Math.Exp(activRes);
Aż mi wstyd jak na to patrzę.
next_layer_activ[i] = precomputedActiv[(int)(activRes * 100 + 500)];
Zabijcie mnie, ale to działa.
Czasy: 345, 346, 344, 344. Średnia - 344 ms.
Czas obecnie: 344 ms
Czy da się lepiej? Tak. Pozostaje pytanie czy warto, i jak będzie wyglądał kod po tych wszystkich poprawkach. ;) Mi na razie wystarczy, może się znajdzie ktoś kto podejmie wyzwanie i jeszcze znacznie zmniejszy czas wykonania (procentowo, uruchomić na szybszym komputerze to żadna sztuka ;) ). Zawsze też można zrównoleglić...
===========================================================================
Koniec postu, można już kończyć przewijać.
No więc, na moim komputerze, udało się osiągnąć cel z 940 do 470 ms, a nawet go dość znacząco przebić z wynikiem 344 ms.
Wrzucam kod, niech inni też się nim pobawią (uprzedzam że jest teraz brzydszy, więc trzeba się zastanowić na ile ważna jest wydajność a na ile czytelność...).
Dorzucam też snapshoty z EQUATEC, nie wiem czy się komuś przydadzą ale zawsze można zobaczyć jak zmieniał się czas wykonania.
PS. Tak... Znowu okazuje się że mikrooptymalizacje w C# polegają głównie na omijaniu Tego Wrednego ABC (wrednego jeśli chodzi o takie właśnie optymalizowanie ile się da - w aplikacjach praktycznych (tzn. biznesowych) ma praktycznie żadne znaczenie dla wydajności (dominowane np. przez SQL) a pozwala znacznie przyśpieszyć debugowanie (w porównaniu do np. wskaźników). Cóż, coś za coś. Ale dlaczego nie da się jej wyłączyć :< ) i pilnowania żeby JIT inlinował to, co ma inlinować.
Takie życie, trzeba się z tym pogodzić.
PPS. Mogłem (i to nawet całkiem prawdopodobne) coś zepsuć podczas optymalizacji, podczas podmieniania tablic na lokalne tablice tymczasowe itp. Nie wiem jakie powinno być prawidłowe wyjście, więc nie mogłem sprawdzić czy się za bardzo nie zmienia. W każdym razie, nie wpływa to w żadnym stopniu na wydajność, bo ilość operacji jest tak czy inaczej taka sama - po prostu trzeba poprawić.
PPPS. Widzę że przez cały post rzucałem tajnymi (dwoma) terminami, takimi jak ABC (przedszkolaka) albo ABCE.
Chodzi o Array Bounds Check, oraz jego Eliminację.
Zasadniczo kiedy mamy kod jak
int i = tab[ndx];
albo
tab[ndx] = 2;
CLR zawsze sprawdza czy ndx na pewno nie jest poza tablicą - w uproszczeniu, wygląda to tak jakby zamiast powyższego kodu było:
if (ndx < 0 || ndx >= tab.Length) { throw new ...; }
int i = tab[ndx];
To działanie to właśnie ABC.
Takie sprawdzenie jest bardzo szybkie, mimo wszystko zajmuję trochę cennego czasu jeśli jest wykonywane bardzo wiele razy (jak teraz).
Ale czasami wiadomo że indeks nie może wyjść poza tablicę. Wtedy JIT może wyeliminować sprawdzenie, czyli mamy ABCE.
Pytanie, kiedy JIT wie że nie możemy wyjść poza tablicę i jak sprytny w tym jest.
Na przykład
for (int i = 0; i < arr.Length; i++) {
arr[i] = 0;
}
teraz wie, a
int l = arr.Length;
for (int i = 0; i < l; i++) {
arr[i] = 0;
}
teraz nie wie.
Te zasady są dość magiczne i zmieniają się (prawdopodobnie) co wersję frameworka, więc nigdy nie wiadomo kiedy eliminacja się wykona a kiedy nie :(. Dlatego, kiedy zależy nam na wydajności, możemy wspomóc JIT sprowadzając co sie da do takiej postaci żeby mu było prosciej.
To takie bardzo skrócone wprowadzenie, dla zainteresowanych np.:
http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds-check-elimination-in-the-clr.aspx
PPPPS. O, już ponad dwie godziny minęły?
Wniosek z tego taki że trzeba znać dobrze specyfikę danego języka(wiedzieć jak on działa od środka) by pisać w nim szybkie programy no i po prostu ...umieć programować poprawnie.
Tak /nie/ robimy - to, domyślam się, miała być optymalizacja, ale niestety - kompletnie nietrafiona (dlatego nie warto optymalizować na ślepo ;) ).
Nie robiłem tego na ślepo, każda zmianę sprawdzałem, ta akurat polepszyła mi czas o 20 - 30 ms, dlatego ją zostawiłem.
Rozwiązaniem byłoby napisanie kodu... bardziej obiektowo - tzn. rezygnacja z tablic na rzecz większego skupienia się na strukturach i przynależności informacji do nich.
Jak by takie coś mogło wyglądać, bo nie za bardzo wiem jak by to miało wyeliminować ABC...
Zabijcie mnie, ale to działa.
Ogólnie program po twoich optymalizacjach przestał działać poprawnie, poprawiłem chyba dwie literówki w indeksach, a co do precomputedActiv, to jednak to nie działa, nie wiem dlaczego ale wyniki są całkowicie inne.
Jeśli porównanie z C++, ma być uczciwe
Przepisałem ten kod z C# z nowym algorytmem, teraz dopiero porównanie może być sprawiedliwe. Jak coś to w załączniku jest projekt.
W sumie to ta optymalizacja polegała na wyciągnięciu czego się da z macierzy, nie spodziewałem się ze może przynieść to taka sporo poprawę. Dzięki za wszystko.
Moje czasy:
Bez optymalizacji MSM:
Z pow() = 2.100
Bez pow() = 1.763
Po optymalizacji MSM(bez precomputedActiv):
C++:
GCC 4.8 -o3: 1.587
VS2012: 1.070
C#:
MSM(poprawiony): 1.160
Może i bawię się w archeologa, ale chyba warto spróbować wrzucić kod w tagu unsafe, z tego co pamiętam to GC ignoruje jego zawartość ;)
Inna sprawa, że poza strefą unsafe mogą nam się zepsuć wskaźniki, bo tam GC wraca do gry i przesuwa obiekty w pamięci (ale do tego można posłużyć się tagiem fixed)
Miałem kiedyś robić o tym wpis na blogu, ale rozpłynął się artykuł gdzieś daleko w galaktyce dysku twardego :)
Odkopałem, bo temat chyba dość ciekawy :)