Generic List vs ArrayList

[ marko_81 @ 19.11.2009. 08:51 ] @

Citao sam po netu razne diskusije na temu sta je bolje koristiti Generic List ili ArrayList.
Interesuju me vasa iskustva. Sta mislite?

[ mmix @ 19.11.2009. 09:07 ] @

Moj stav je bar poznat, strong typing je majka. Definitivno List<T>

[ marko_81 @ 19.11.2009. 09:25 ] @

Osim sto je List<T> strong typed, da li postoji razlika u brzini prilikom sortiranja i/ili pretrage?
Koliko sam video na msdn-u i arraylist i generic lista, kod sortiranja, koriste QuickSort algoritam.
Koliko opterecuju procesor i koliko trose memoriju jedna i druga?

[ Dejan Carić @ 19.11.2009. 10:27 ] @

Kod sortiranja manje-više tu su negde.
Međutim, kod ArrayList prilikom iščitavanja vrednosti elemenata niza moraš da radiš unboxing što je procesorski dosta zahtevnije i to radi primetno sporije nego kada koristiš strongly typed kolekcije.

[ marko_81 @ 19.11.2009. 11:58 ] @

Hvala za odgovore. U medjuvremenu nasao sam jedan link gde uporedjuju koliko memorije trose arraylist i genericka lista.
Evo linka: http://blogs.msdn.com/joshwil/archive/2004/04/13/112598.aspx.
Nadam se da ce biti od koristi nekome.

[ mmix @ 19.11.2009. 16:02 ] @

Ne bi trebalo da su blizu ni kod sortiranja upravo zbog unboxinga i pri poredjenju value tipova pozivanja sporijeg IComparer.CompareTo koji radi unobxing umesto ICompare<T>.CompareTo koji direktno poredi value tipove. Sa obzirom da Quicksort u najgorem slucaju ima O(n^2) za veoma velike nizove ovaj eksponencijalni algoritam brzo izgubi korak.

[ mmix @ 19.11.2009. 16:08 ] @

Evo cisto primer za dva compare-a za Int32 (int) tip:

Code:

// ovaj poziva ArrayList.Sort()
public int CompareTo(object value)
{
    if (value == null)
    {
        return 1;
    }
    if (!(value is int))
    {
        throw new ArgumentException(Environment.GetResourceString("Arg_MustBeInt32"));
    }
    int num = (int) value;
    if (this < num)
    {
        return -1;
    }
    if (this > num)
    {
        return 1;
    }
    return 0;
}

// ovaj poziva List<T>.Sort()
public int CompareTo(int value)
{
    if (this < value)
    {
        return -1;
    }
    if (this > value)
    {
        return 1;
    }
    return 0;
}

[ mmix @ 19.11.2009. 16:37 ] @

Evo par rezultata (kad vec volis metriku). Tri prolaza, sva tri generisu List<int> i arraylist sa random intovima unutra, pogledaj kako ArrayList.Sort eksponencijalno ubija performanse sa rastom broja elemenata:

Arrays will have 1,000,000 elements
Initialized List<int> in 00:00:00.0210012
Initialized ArrayList in 00:00:00.0730042
List<int> sorted in 00:00:00.1120065
ArrayList sorted in 00:00:00.9820561

Arrays will have 10,000,000 elements
Initialized List<int> in 00:00:00.2020116
Initialized ArrayList in 00:00:01.0440597
List<int> sorted in 00:00:01.2170696
ArrayList sorted in 00:00:15.7349000

Arrays will have 50,000,000 elements
Initialized List<int> in 00:00:01.0450598
Initialized ArrayList in 00:00:07.4094238
List<int> sorted in 00:00:06.8963944
ArrayList sorted in 00:01:42.1138406

Na 100mil elemenata moj sistem vec pocinje da trokira sa ArrayList zato sto svaki od tih intova boxuje na heap.

[ Dejan Carić @ 19.11.2009. 18:37 ] @

U pravu si.
My mistake.

[ mmix @ 19.11.2009. 20:05 ] @

Ma opusteno, ovo testiranje me je bilo interesovalo vec neko vreme i nikako da odradim, sad se bas poklopilo sa pauzom za rucak :)

[ Shadowed @ 19.11.2009. 20:50 ] @

A pri svemu tome je i lakse koristiti List<T> :)

[ Goran Arandjelovic @ 19.11.2009. 23:37 ] @

A i što se tiče memorijskog zauzeća (ako su elementi value tipovi), razlika je značajna na 32-bitnoj platformi, a da ne pominjemo na 64-bitnoj...

[ mmix @ 20.11.2009. 09:03 ] @

Memorijsko zauzece u generic List je isto na x64 i x86, List<T> koristi interno T[] niz za smestanje elemenata a alokacija value type niza se bar na MS implementaciji CLRa obavlja kao single chunk, tako da new List<int>(1000000); zauzima 4MB i na jednom i na drugom sistemu. Jedina razlika je referenca na List[T]._items koja je 4 bajta duza ali ona je samo jedna bez obzira na velicinu niza

Sa druge stranenew ArrayList(1000000) popunjen intovima zauzimace oko 32Mb na x64 platformi (24 byte za boxovani int + 8 byte za object reference za svaki element) dok ce na x86 platformi zauzimati duplo manje (12 byte za boxovani int + 4 byte reference).

U svim slucajevima je payload int-a 32 bita.

[ Goran Arandjelovic @ 20.11.2009. 17:41 ] @

Da, to sam ukratko i hteo da kažem. E da, da ne ostane nedorečeno, overhead boxinga potiče od dodavanja VTable i SyncBlock (odgovornog za monitoring lockovanja ako se ne varam?) pointera.