Array-Grenzen überprüfen die Effizienz in .net 4 und höher
Ich bin daran interessiert, wie effizient Low-Level-Algorithmen in .net sein können. Ich möchte es uns ermöglichen, in Zukunft mehr Code in C # als in C ++ zu schreiben, aber ein Stolperstein ist das Einchecken von .net, das bei Schleifen und wahlfreiem Zugriff auf Arrays auftritt.
Ein motivierendes Beispiel ist eine Funktion, die die Summe der Produkte der entsprechenden Elemente in zwei Arrays berechnet (dies ist das Skalarprodukt zweier Vektoren).
static void SumProduct(double[] X, double[] Y)
{
double sum = 0;
int length = X.Length;
if (length != Y.Length)
throw new ArgumentException("X and Y must be same size");
for (int i = 0; i < length; i++) // Check X.Length instead? See below
sum += X[i] * Y[i];
}
Nach allem, was ich sagen kann und nicht genug IL oder x86 weiß, um es zu überprüfen, wird der Compiler die Überprüfung der Grenzen nicht optimierenX
und Y
. Liege ich falsch und / oder gibt es eine Möglichkeit, meinen Code zu schreiben, damit der Compiler mir helfen kann?
Weitere Details
Es gibt viele Effizienzargumente für und gegen die Verwendung bestimmter Sprachen, nicht zuletzt, dass es besser ist, sich auf die algorithmischen Kosten von "Big O" zu konzentrieren, als auf die Proportionalitätskonstante, und Sprachen höherer Ebenen helfen Ihnen dabei. Was das Einchecken von .net angeht, ist der beste Artikel, den ich gefunden habeArray Bounds Check Elimination in der CLR auf MSDN (auch in aStapelüberlauf Antwort über die Bedeutung der Optimierung).
Dieses Datum stammt aus dem Jahr 2009, daher frage ich mich, ob sich die Dinge seitdem erheblich geändert haben. Außerdem enthüllt der Artikel einige echte Feinheiten, die mich überrascht hätten. Allein aus diesem Grund würde ich mich über einen kompetenten Rat freuen.
Zum Beispiel scheint es, dass ich in meinem obigen Code besser dran wäre, zu schreibeni< X.Length
eher, alsi < length
. Außerdem hatte ich naiv angenommen, dass für einen Algorithmus mit einem einzigen Array einforeach
loop würde Ihre Absicht besser dem Compiler erklären und ihm die beste Chance geben, die Überprüfung der Grenzen zu optimieren.
Gemäß dem MSDN-ArtikelSumForBAD
, unten, von dem ich dachte, dass es sicher optimiert werden würde, wäre es nicht. WohingegenSumFor
würde einfach optimiert werden, undSumForEach
würde auch optimiert werden, aber nicht trivial (und könnte überhaupt nicht optimiert werden, wenn das Array in eine Funktion als übergeben würdeIEnumerable<int>
)?
static double SumForBAD(double[] X)
{
double sum = 0;
int length = X.Length; // better to use i < X.length in loop
for (int i = 0; i < length; i++)
sum += X[i];
return sum;
}
static double SumFor(double[] X)
{
double sum = 0;
for (int i = 0; i < X.Length; i++)
sum += X[i];
return sum;
}
static double SumForEach(double[] X)
{
double sum = 0;
foreach (int element in X)
sum += element;
return sum;
}
Ich habe einige Nachforschungen angestellt, die auf der Antwort von doug65536 basierten. In C ++ habe ich die Zeiten eines SumProducts verglichen, das einen Bounds-Check durchführt
for(int i=0; i<n; ++i) sum += v1[i]*v2[i];
gegen eine andere Version, die zwei Bounds-Checks durchführt
for(int i=0; i<n1 && i <n2; ++i) sum += v1[i]*v2[i];
Ich fand, dass die zweite Version langsamer war, aber nur um ca. 3,5% (Visual Studio 2010, optimierte Erstellung, Standardoptionen). Mir ist jedoch aufgefallen, dass es in C # möglicherweise drei Grenzprüfungen gibt. Eine explizite (i < length
in der Funktionstatic void SumProduct(double[] X, double[] Y)
am Anfang dieser Frage) und zwei implizite (X[i]
undY[i]
). Also habe ich eine dritte C ++ - Funktion mit drei Grenzwertprüfungen getestet
for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i];
Dies war 35% langsamer als die erste, was es wert ist, beachtet zu werden. Ich habe weitere Nachforschungen zu dieser Frage angestellt.Warum macht das Hinzufügen einer zusätzlichen Check-in-Schleife auf einigen Computern einen großen Unterschied und auf anderen einen kleinen Unterschied?. Interessanterweise scheinen die Kosten für die Prüfung der Schranken auf verschiedenen Maschinen erheblich zu variieren.