Arrays <-> List<T>

Hallo

Was sollte man eurer Meinung nach eher benutzen?
Speziell jetzt beispielsweise bei einer Server<>Client Anwendung.

Sind Arrays tatsächlich schneller als generische Listen?

Grüsse
Regenwurm

Ob sie schneller sind weis ich nicht, aber aufjedenfall sind sie komfortabler!!!!!!! das sollte schon grund genug sein!

Arrays oder Listen?
Ich gehe doch schwer davon aus, dass du jetzt die Listen ansprichst. (:

Arrays gehören in die Mottenkiste, es sollten ab .NET 2.0 nur noch generische Listen verwendet werden, zumindest meiner Meinung nach.

Salute zusammen

Arrays sowie auch Listen haben ihre Daseinsberechtigung.
In die Mottenkiste gehört dieser Datentyp nicht, so elementar wie er ist.

Es gibt Anwendungsfälle die mit einem Array besser / einfacher / schneller zu bewältigen sind (Viele Indexzugriffe, Matrixen, ...) und Anwendungsfälle wo die Liste besser ist.

Allgemein sollte man aber wissen, das Array wenn möglich nicht in eine öffentliche API gehört, sondern ein Interna bleiben soll.
Dasselbe gil auch für List<T>, allerdings weicht das jetzt schon fast wieder vom Thema ab.
Wenn es interessiert, kann hier nachlesen:

• http://www.aspnetzone.de/blogs/peterbucher/archive/2009/11/19/wann-ienumerable-nutzen-wann-icollection-und-wieso-berhaupt-ilist.aspx
• http://blogs.msdn.com/kcwalina/archive/2005/09/23/Collections.aspx

Array sind schneller, weil List<T> intern mit einem Array arbeitet.
Jedoch ist eine Liste viel komfortabler und einfacher in der Nutzung, vorallem wenn man nicht indexbasiert arbeitet.

Der Geschwindigkeitsunterschied sollte praktisch nicht zu merken sein und in den allermeisten Fällen ist IMO List<T> zu bevorzugen.

Gruss Peter

Ist der Geschwindkeitsunterschied spürbar bei einer Client <-> Serveranwendung?

Bis zu 1000 Clients sind an einem Server.

Arrays gehören in die Mottenkiste, es sollten ab .NET 2.0 nur noch generische Listen verwendet werden

ich denke du verwechselst das mit arraylist.

arrays als solche sind elementar. sogar die List<T> ist nur ein wrapper um ein array... so wie alle anderen listenarten, die im framework zu finden sind.

für viele indexzugriffe allerdings eignet sich beides nicht. ohne ein paar umweltbedingungen zu ändern. bei vielen indexzugriffen ist es besser das array zu pinnen und im unsafe kontext per pointer zu arbeiten, da der bounds-check meist die performancebremse ist.

im allgemeinen schließe ich mich Peter Bucher an.

Ist der Geschwindkeitsunterschied spürbar bei einer Client <-> Serveranwendung?

Bis zu 1000 Clients sind an einem Server.

nein.

Vielen Dank für eure Inputs. 😃

Ich werde List<T> benutzen. 😉

Es gibt Anwendungsfälle die mit einem Array besser / einfacher / schneller zu bewältigen sind (Viele Indexzugriffe, Matrixen, ...) und Anwendungsfälle wo die Liste besser ist.

List<T>.Item hat laut MSDN (http://msdn.microsoft.com/de-de/library/0ebtbkkc.aspx) eine Zugriffszeit von O(1).

die aufwandsklasse besagt aber nciht, wie lange es dauert, sondern nur, wieviel aufwand betrieben werden muss. bei vielen indexzugriffen hat man bei einer list<T> nur einen zusätzlichen methodenaufruf zusätzlich im vergleich zu einem array also ist der unterschied nur minimal. der flaschenhals dabei ist dann eher direkt im gewrappten array wegen dem bounds-check zu finden.

Okay, das stimmt natürlich.

Man sollte den Performance-Vorteil von Arrays nicht unterschätzen!
Arrays sind für Performance-Kritische Probleme nach wie vor am schnellsten.

Beispiel:

Ich führ Elementare Operationen auf Arrays und Listen aus.
Mal übergebe ich beides als konkreten Typ, mal als IList.
Mal kopiere ich die Länge in ein lokales Feld, mal frage ich sie jedesmal ab.

    class Program {
        const int count = 5000;
        static int[] arr = new int[count];
        static List<int> list = new List<int>();


        static void Main(string[] args) {
            Init();

            Console.WriteLine("int[] as int[]:A: " + MesaureTime(() => Sum1(arr as int[])).Ticks);
            Console.WriteLine("int[] as IList:A: " + MesaureTime(() => Sum1(arr as IList<int>)).Ticks);
            Console.WriteLine("List as List  :A: " + MesaureTime(() => Sum1(list as List<int>)).Ticks);
            Console.WriteLine("List as IList :A: " + MesaureTime(() => Sum1(list as IList<int>)).Ticks);

            Console.WriteLine("int[] as int[]:B: " + MesaureTime(() => Sum2(arr as int[])).Ticks);
            Console.WriteLine("int[] as IList:B: " + MesaureTime(() => Sum2(arr as IList<int>)).Ticks);
            Console.WriteLine("List as List  :B: " + MesaureTime(() => Sum2(list as List<int>)).Ticks);
            Console.WriteLine("List as IList :B: " + MesaureTime(() => Sum2(list as IList<int>)).Ticks);

            unsafe {
                fixed (int* ptr = arr) {
                    Console.WriteLine("int[] as int* :C: " + MesaureTime(() => Sum3(ptr, count)).Ticks);
                }
            }
        }

        static void Init() {
            for (int i = 0; i < count; i++) {
                arr[i] = i;
                list.Add(i);
            }
        }

        static TimeSpan MesaureTime(Action action) {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            action();
            sw.Stop();
            return sw.Elapsed;
        }


        static int Sum1(int[] a) {
            int sum = 0;
            for (int i = 0; i < a.Length; i++) {
                for (int j = 0; j < a.Length; j++) {
                    sum += a[i]\*a[j];
                }
            }
            return sum;
        }

        static int Sum1(IList<int> a) {
            int sum = 0;
            for (int i = 0; i < a.Count; i++) {
                for (int j = 0; j < a.Count; j++) {
                    sum += a[i] * a[j];
                }
            }
            return sum;
        }

        static int Sum1(List<int> a) {
            int sum = 0;
            for (int i = 0; i < a.Count; i++) {
                for (int j = 0; j < a.Count; j++) {
                    sum += a[i] * a[j];
                }
            }
            return sum;
        }

        static int Sum2(int[] a) {
            int sum = 0;
            int length = a.Length;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    sum += a[i] * a[j];
                }
            }
            return sum;
        }

        static int Sum2(IList<int> a) {
            int sum = 0;
            int length = a.Count;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    sum += a[i] * a[j];
                }
            }
            return sum;
        }

        static int Sum2(List<int> a) {
            int sum = 0;
            int length = a.Count;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    sum += a[i] * a[j];
                }
            }
            return sum;
        }

        static unsafe int Sum3(int* a, int length) {
            int sum = 0;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    sum += a[i] * a[j];
                }
            }
            return sum;            
        }
    }

Ausgabe (Release-Mode, kein Debugging):

int[] as int[]:A: 404179
int[] as IList:A: 37778960
List as List  :A: 1624798
List as IList :A: 7979447
int[] as int[]:B: 775808
int[] as IList:B: 23942406
List as List  :B: 1617253
List as IList :B: 6396561
int[] as int* :C: 400335

Fazit: Array sind (insbesondere wenn durch die Schleife bis "length" die Bereichsprüfung wegfällt) deutlich schneller als alles andere. Die Abstraktion als IList z.B. kostet einen Faktor 100. Auch eine List ist um einen Faktor 4 langsamer.

Das heißt nicht, dass nicht oft dieser Overhead vernachlässigbar ist. Aber er ist da.

EDIT: Unsafe Test hinzugfügt.

Hallo JAck30lena,

die aufwandsklasse besagt aber nciht, wie lange es dauert, sondern nur, wieviel aufwand betrieben werden muss.

... sondern nur, wie sich der Aufwand bei Änderung der Eingabelänge verändert.

Hallo Golo Roden,

aber das wichtige hat JAck30lena natürlich gesagt. Es wird gerade keine Aussage über konstante Faktoren getroffen. So kann es sein, dass eine bestimmte O(1) Operation immer mehrere Sekunden dauert. O(1) bedeutet einfach nur, dass die Dauer der Operation - im Schnitt - unabhängig von der Eingabelänge ist.

Der Aufwand muss nicht mal konstant sein (auch wenn man bei O(1) gerne von "konstantem Aufwand" spricht). Da die O-Notation das asymptotische Verhalten angibt, kann es durchaus sein, dass bei bestimmten Eingaben der Aufwand deutlich höher ist als bei anderen. Es ist bei O(1) sogar denkbar, dass der Aufwand für einige (natürlich nur sehr wenige) Eingaben exponentiell ist.

herbivore

Man sollte den Performance-Vorteil von Arrays nicht unterschätzen!

ja, list hat zu dem bounds-check des arrays nochmals einen eigenen bounds-check, da das intern gewrapptes array im normalfall größer ist, als List.Count, der zugriff auf die elemente außerhalb des counts jedoch nicht gestattet ist.

daher der overhead. im konkreten ist das nur eine if-prüfung mit 2 integern und dann der aufruf an das interne array.

Arrays sind für Performance-Kritische Probleme nach wie vor am schnellsten.

nur im unsafe context. der rest ist vernachlässigbar und schadet meist der wartbarkeit.

Arrays sind für Performance-Kritische Probleme nach wie vor am schnellsten.

nur im unsafe context. der rest ist vernachlässigbar und schadet meist der wartbarkeit.

Naja, auch sonst eben in obigem Beispiel einen Faktor 4. Der oft, aber eben nicht immer vernachlässigbar ist.

Der Unterschied kommt im Wesentlichen daher, dass bei einem Array a[4] nur ein Zugriff auf eine Speicherstelle ist, während bei einer Liste a[4] ein Methodenaufruf ist.

Der Unterschied kommt im Wesentlichen daher, dass bei einem Array a[4] nur ein Zugriff auf eine Speicherstelle ist, während bei einer Liste a[4] ein Methodenaufruf ist.

nein. eben nciht. in allen anderen sprachen ja, vielleicht... in den meisten sprachen sogar ganz bestimmt aber nciht in .net
ein array in .net hat auch einen boundscheck. somit ist im safe-context ein buffer-overflow nicht möglich.

ein array in .net hat auch einen boundscheck. somit ist im safe-context ein buffer-overflow nicht möglich.

Der Compiler ist ja doof. Ich vielen Fällen kann und wird der Check wegoptimiert, z.B. bei einer For-Schleife von 0 bis array.length (daher sollte man sich nie die Länge eines Arrays als lokale Variable merken, das verdoppelt in meinem Code oben die Laufzeit). Dort ist ja zur Compilezeit klar, dass die Bounds immer erfüllt sein werden.

demnach dürfte sich die laufzeit im vergleich zu unsafe nicht ändern? probier das doch mal.

demnach dürfte sich die laufzeit im vergleich zu unsafe nicht ändern? probier das doch mal.

Hab das zu dem Test hinzugefügt (siehe oben, habe den Beitrag editiert). Es macht wie erwartet keinen Unterschied.

Ein Unterschied entsteht dann, wenn der Compiler nicht zur Compilezeit erkennen kann, dass der Zugriff korrekt ist, (eben weil es keine Laufvariable einer For-Schleife ist, sondern ein lokales Feld oder sowas). Dann wird er im unsafe Kontext keinen Check machen, im save Kontext hingegen schon.

Da der Compiler für eindimensionale Arrays optimiert, sind übrigens jagged Arrays auch deutlich performanter als mehrdimensionale Arrays

also ich hab mir das mal im detail angesehen. der compiler macht das so wie ich es erwartet habe. die instruktion für den boundscheck ist mit drinn.

    class Program 
    {
       static int[] arr = new int[1];
        
       static void Main(string[] args) {
           arr[0] = int.Parse(Console.ReadLine());

            Console.WriteLine(arr[0]);
        }
    }

führt zu:

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       30 (0x1e)
  .maxstack  8
  IL_0000:  ldsfld     int32[] ConsoleApplication4.Program::arr
  IL_0005:  ldc.i4.0
  IL_0006:  call       string [mscorlib]System.Console::ReadLine()
  IL_000b:  call       int32 [mscorlib]System.Int32::Parse(string)
  IL_0010:  stelem.i4
  IL_0011:  ldsfld     int32[] ConsoleApplication4.Program::arr
  IL_0016:  ldc.i4.0
  IL_0017:  ldelem.i4
  IL_0018:  call       void [mscorlib]System.Console::WriteLine(int32)
  IL_001d:  ret
} // end of method Program::Main

ldelem (das i 4 ist die bytegröße) ist die instruktion für den zugriff inklusive boundscheck. bei unsafe zugriffen verwendet er die instruktion ldind

daher macht der compiler hier keine optimierung. evtl hat aber dein JITTER optimiert.....

edit: kannst du mal einen lauf mit ngen optimierten code machen?

Da scheint der Compiler es zur Compilezeit nicht zu erkennen.

Gegenbeispiel:

     class Programm {
        static int[] arr = new int[10];

        static void Main(string[] args) {            
            for (int i = 0; i < arr.Length; i++) {
                arr[i] = i;
            }
        }
    }

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       27 (0x1b)
  .maxstack  3
  .locals init ([0] int32 i)
  IL_0000:  ldc.i4.0
  IL_0001:  stloc.0
  IL_0002:  br.s       IL_0010
  IL_0004:  ldsfld     int32[] Performance_Test.Programm::arr
  IL_0009:  ldloc.0
  IL_000a:  ldloc.0
  IL_000b:  stelem.i4
  IL_000c:  ldloc.0
  IL_000d:  ldc.i4.1
  IL_000e:  add
  IL_000f:  stloc.0
  IL_0010:  ldloc.0
  IL_0011:  ldsfld     int32[] Performance_Test.Programm::arr
  IL_0016:  ldlen
  IL_0017:  conv.i4
  IL_0018:  blt.s      IL_0004
  IL_001a:  ret
} // end of method Programm::Main

stelem.i4

setzt im array einen wert inklusive dem boundscheck. oder übersehe ich etwas?

Oh je, jetzt sind meine IL-Kenntnisse überfragt. Ich meine, nach Definition müsse nur sichergestellt sein, dass die Bounds OK sind, nicht, dass wirklich zur Laufzeit ein Check durchgeführt wird. Aber meine Hand lege ich dafür nicht ins Feuer.

Habe noch folgenden Link gefunden.
http://blogs.msdn.com/clrcodegeneration/archive/2009/08/13/array-bounds-check-elimination-in-the-clr.aspx

Ist der Geschwindkeitsunterschied spürbar bei einer Client <-> Serveranwendung?

Bis zu 1000 Clients sind an einem Server.

premature optimization is the root of all evil

Trifft voll zu, hier wird in 99% der Fälle die meiste Performance nicht im List<T> verloren gehen sondern am Kabel.

@Uwe81:

sehr sehr interessanter link. witzig, das der x86 JIT komplett anders läuft als der X64 JIT.

wie ich vermutet habe beruht diese optimierung auf dem JIT und nicht dem c# compiler und der JIT kann hier nur nach einem bestimmten pattern optimieren, was gerade in den komplexen fällen nicht mehr greift. zum initialisieren eines arrays ist das schnell und gut aber wirkliche optimierung für mehrfache zugriffe und komplexen operationen ist das wiederrum nichts.

Ich meine, nach Definition müsse nur sichergestellt sein, dass die Bounds OK sind, nicht, dass wirklich zur Laufzeit ein Check durchgeführt wird.

jain... die CLR kennt wie gesagt den checked-zugriff und den unchecked-zugriff. was die CLR letzendlich aus diesen instruktionen macht (ob sie nun prüft oder nciht) ist eine andere geschichte. ab da ist das die domäne des JIT.