Frage Warum führt die Verwendung von List in IList zu einer reduzierten Leistung?


Ich habe einige Performance-Metriken gemacht und bin auf etwas gestoßen, das mir ziemlich seltsam vorkommt. Ich zeitlich die folgenden zwei Funktionen:

  private static void DoOne()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
          int s=0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < A.Count; c++) s += A[c];
         }

      }

   private static void DoTwo()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
         IList<int> L = A;
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < L.Count; c++) s += L[c];
         }

      }

Selbst beim Kompilieren im Freigabemodus zeigten die Timing-Ergebnisse konsistent, dass DoTwo ~ 100 länger dauert als DoOne:

 DoOne took 0.06171706 seconds.
 DoTwo took 8.841709 seconds.

Angesichts der Tatsache, dass die List IList direkt implementiert, war ich sehr überrascht von den Ergebnissen. Kann jemand dieses Verhalten klären?

Die blutigen Details

Auf Fragen antworten, hier ist der vollständige Code und ein Bild der Build-Präferenzen des Projekts:

  Toter Bildlink

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Collections;

namespace TimingTests
{
   class Program
   {
      static void Main(string[] args)
      {
         Stopwatch SW = new Stopwatch();
         SW.Start();
         DoOne();
         SW.Stop();

         Console.WriteLine(" DoOne took {0} seconds.", ((float)SW.ElapsedTicks) / Stopwatch.Frequency);
         SW.Reset();
         SW.Start();
         DoTwo();
         SW.Stop();

         Console.WriteLine(" DoTwo took {0} seconds.", ((float)SW.ElapsedTicks) / Stopwatch.Frequency);

      }

      private static void DoOne()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
         int s=0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < A.Count; c++) s += A[c];
         }

      }
      private static void DoTwo()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
         IList<int> L = A;
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < L.Count; c++) s += L[c];
         }

      }
   }
}

Danke für all die guten Antworten (besonders @kentaromiura). Ich hätte die Frage geschlossen, obwohl ich denke, dass wir immer noch einen wichtigen Teil des Puzzles vermissen. Warum würde der Zugriff auf eine Klasse über eine von ihr implementierte Schnittstelle so viel langsamer sein? Der einzige Unterschied, den ich sehen kann, ist, dass der Zugriff auf eine Funktion über eine Schnittstelle die Verwendung virtueller Tabellen impliziert, während normalerweise die Funktionen direkt aufgerufen werden können. Um zu sehen, ob das der Fall ist, habe ich ein paar Änderungen am obigen Code vorgenommen. Zuerst stellte ich zwei fast identische Klassen vor:

  public class VC
  {
     virtual public int f() { return 2; }
     virtual public int Count { get { return 200; } }

  }

  public class C
  {
      public int f() { return 2; }
      public int Count { get { return 200; } }

  }

Wie Sie sehen können, verwendet VC virtuelle Funktionen und C nicht. Jetzt zu DoOne und DoTwo:

    private static void DoOne()
      {  C a = new C();
         int s=0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < a.Count; c++) s += a.f();
         }

      }
      private static void DoTwo()
      {
           VC a = new VC();
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < a.Count; c++) s +=  a.f();
         }

      }

Und in der Tat:

DoOne took 0.01287789 seconds.
DoTwo took 8.982396 seconds.

Das ist noch gruseliger - virtuelle Funktionsaufrufe 800 mal langsamer ?? also ein paar Fragen an die Gemeinde:

  1. Kannst du es reproduzieren? (Angenommen Tatsache, dass alle schlechtere Leistung hatten vorher, aber nicht so schlecht wie meins)
  2. Können Sie erklären?
  3. (Dies kann die sein am wichtigsten) - kannst du dir vorstellen eine Möglichkeit zu vermeiden?

Boas


14
2018-05-12 21:30


Ursprung


Antworten:


Ein Hinweis für alle da draußen, die versuchen, so etwas zu bewerten.

Vergiss das nicht Der Code wird erst bei der ersten Ausführung aktiviert. Das bedeutet, dass beim erstmaligen Ausführen einer Methode die Kosten für die Ausführung dieser Methode von der Zeit bestimmt werden können, die für das Laden der IL, das Analysieren der IL und das Jitting in Maschinencode aufgewendet wird, insbesondere wenn es sich um eine triviale Methode handelt.

Wenn Sie versuchen, die "marginalen" Laufzeitkosten von zwei Methoden zu vergleichen, ist es eine gute Idee, sie beide zweimal auszuführen beachte nur die zweiten Läufe zu Vergleichszwecken.


27
2018-05-12 22:04



Profiling eins zu eins:

Testen mit Snippet-Compiler.

Verwenden Sie Ihre Code-Ergebnisse:

0,043s vs 0,116s

Temporäres L eliminieren

0,043s vs 0,116s - Influent

durch Caching von A.count in cmax auf beiden Methoden

0,041 vs 0,076s

     IList<int> A = new List<int>();
     for (int i = 0; i < 200; i++) A.Add(i);

     int s = 0;
     for (int j = 0; j < 100000; j++)
     {
        for (int c = 0,cmax=A.Count;c< cmax;  c++) s += A[c];
     }

Jetzt werde ich versuchen, DoOne zu verlangsamen, zuerst versuchen, Casting zu IList bevor hinzufügen:

for (int i = 0; i < 200; i++) ((IList<int>)A).Add(i);

0,041s 0,076s - so fügen Sie hinzu influent

Es bleibt also nur ein Ort, wo die Verlangsamung stattfinden kann: s += A[c]; also versuche ich das:

s += ((IList<int>)A)[c];

0.075s 0.075s - TADaaan!

Daher scheint der Zugriff auf Count oder ein Indexelement in der Schnittstellenversion langsamer zu sein:

BEARBEITEN: Nur zum Spaß werfen Sie einen Blick darauf:

 for (int c = 0,cmax=A.Count;c< cmax;  c++) s += ((List<int>)A)[c];

0,041s 0,050s

es ist also kein Besetzungsproblem, sondern eine Reflektion!


9
2018-05-13 09:14



Zuerst möchte ich allen für ihre Antworten danken. Es war wirklich wichtig auf dem Weg, was wir vorfanden. Besonderer Dank geht an @kentaromiura, die den Schlüssel gefunden hat, um den Dingen auf den Grund zu gehen.

Die Ursache für die Verlangsamung der Verwendung von List <T> über eine IList <T> -Schnittstelle ist die fehlende Fähigkeit des JIT-Compilers, die Item-Eigenschaft get-Funktion einzubinden. Die Verwendung von virtuellen Tabellen, die durch den Zugriff auf die Liste über die IList-Schnittstelle verursacht werden, verhindert dies.

Als Beweis habe ich den folgenden Code geschrieben:

      public class VC
      {
         virtual public int f() { return 2; }
         virtual public int Count { get { return 200; } }

      }

      public class C
      {
         //[MethodImpl( MethodImplOptions.NoInlining)]
          public int f() { return 2; }
          public int Count 
          {
            // [MethodImpl(MethodImplOptions.NoInlining)] 
            get { return 200; } 
          }

      }

und modifizierte die DoOne und DoTwo Klassen wie folgt:

      private static void DoOne()
      {
         C c = new C();
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int i = 0; i < c.Count; i++) s += c.f();
         }

      }
      private static void DoTwo()
      {
         VC c = new VC();
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int i = 0; i < c.Count; i++) s += c.f();
         }

      }

Sicherlich sind die Funktionszeiten jetzt sehr ähnlich wie zuvor:

 DoOne took 0.01273598 seconds.
 DoTwo took 8.524558 seconds.

Wenn Sie nun die Kommentare vor dem MethodImpl in der C-Klasse entfernen (wodurch der JIT nicht inline wird), wird das Timing zu:

DoOne took 8.734635 seconds.
DoTwo took 8.887354 seconds.

Voila - die Methoden nehmen fast die gleiche Zeit. Sie können immer noch sehen, dass DoOne Methode immer noch etwas schnell ist, was den zusätzlichen Aufwand einer virtuellen Funktion konsistent ist.


8
2018-05-15 08:22



Ich glaube, dass das Problem in Ihren Zeitmetriken liegt, was verwenden Sie, um die verstrichene Zeit zu messen?

Nur zur Erinnerung, hier sind meine Ergebnisse:

DoOne() -> 295 ms
DoTwo() -> 291 ms

Und der Code:

        Stopwatch sw = new Stopwatch();

        sw.Start();
        {
            DoOne();
        }
        sw.Stop();

        Console.WriteLine("DoOne() -> {0} ms", sw.ElapsedMilliseconds);

        sw.Reset();

        sw.Start();
        {
            DoTwo();
        }
        sw.Stop();

        Console.WriteLine("DoTwo() -> {0} ms", sw.ElapsedMilliseconds);

5
2018-05-12 21:37



Ich sehe eine erhebliche Strafe für die Schnittstellenversion, aber nicht annähernd die Größenordnung, die Sie sehen.

Kannst du ein klein, komplett Programm, das das Verhalten zusammen mit genau zeigt, wie Sie es kompilieren und welche Version des Frameworks Sie verwenden?


4
2018-05-12 21:51



Meine Tests zeigen, dass die Version der Benutzeroberfläche im Freigabemodus etwa 3x langsamer ist. Wenn sie im Debug-Modus kompiliert werden, sind sie fast Kopf an Kopf.

--------------------------------------------------------
 DoOne Release (ms) |  92 |  91 |  91 |  92 |  92 |  92
 DoTwo Release (ms) | 313 | 313 | 316 | 352 | 320 | 318
--------------------------------------------------------
 DoOne Debug (ms)   | 535 | 534 | 548 | 536 | 534 | 537
 DoTwo Debug (ms)   | 566 | 570 | 569 | 565 | 568 | 571
--------------------------------------------------------

BEARBEITEN

In meinen Tests habe ich eine leicht modifizierte Version des DoTwo Methode, so dass es direkt vergleichbar war DoOne. (Diese Änderung hat keinen erkennbaren Unterschied zur Leistung gemacht.)

private static void DoTwo()
{
    IList<int> A = new List<int>();
    for (int i = 0; i < 200; i++) A.Add(i);
    int s = 0;
    for (int j = 0; j < 100000; j++)
    {
       for (int c = 0; c < A.Count; c++) s += A[c];
    }
}

Der einzige Unterschied zwischen der IL generiert für DoOne und (modifiziert) DoTwo Ist das das callvirt Anweisungen für Add, get_Item und get_Count benutzen IList und ICollection eher, als List selbst.

Ich schätze mal, dass die Runtime mehr tun muss, um die eigentliche Methodenimplementierung zu finden, wenn die callvirt ist über eine Schnittstelle (und dass der JIT-Compiler / Optimierer eine bessere Arbeit mit den Nicht-Schnittstellenaufrufen leisten kann, als die Schnittstelle beim Kompilieren im Freigabemodus aufruft).

Kann das jemand bestätigen?


3
2018-05-12 22:08



Ich habe das benutzt Jon Skeets Benchmark Helper und ich sehe nicht die Ergebnisse, die Sie sind, die Ausführungszeit ist ungefähr die gleiche zwischen den beiden Methoden.


2
2018-05-12 21:45