Archive for the ‘List<T>’ Category

WinDbg Q&A: Hvorfor er der så mange instanser af string og object[] på heapen?

Wednesday, October 28th, 2009

Når vi debugger .NET applikationer med WinDbg, vil vi almindeligvis have brug for at inspicere heapen med !dumpheap-kommandoen. Den viser antallet af instanser af de forskellige typer på heapen. Listen er sorteret efter summen af størrelsen for instanserne af de enkelte typer på heapen. Dog skal det bemærkes, at der er tale om selve typernes størrelse, så størrelsen af en type med referencer inkluderer altså ikke størrelsen på de refererede objekter.

Det vil typisk sige, at typer med mange instanser vil være at finde mod slutningen af listen, og blandt dem finder vi meget ofte string og object[], men hvorfor er der så mange af disse i stort set alle .NET applikationer?

String

Lad os begynde med string, for her er forklaringen oplangt. For det første opretter CLRen en hel del strings til diverse konstanter, stier og så videre og jo flere assemblies vi refererer, desto flere af disse får vi med i bagagen. Dertil kommer at instanser af string som bekendt er immutable, så hvis applikationen laver en eller anden form for string-behandling, skaber det hurtig mange instanser. Husk at alle konstante tekster samt alle konstruerede tekster havner på heapen, så derfor løber det hurtig op. Med mindre der er tale om meget store instanser, er det sjældent værd at bekymre sig om.

Object[]

Antallet af string-instanser kan virke overvældende, men når vi tænker over det, er det i virkeligheden ikke så underligt, men hvad med object[]?

Var vi ikke lige blevet enige om, at generics og typestærke collections er sådan en god ide? Hvorfor skulle vi så bruge object[]? Og hvis det ikke er vores applikation, der bruger alle disse forældede collections, er det så Microsofts klasser, der endnu ikke er blevet opdateret?

Forklaringen er faktisk mere subtil end som så. Den underliggende type af List<T> er faktisk object[]. Hvordan kan det passe? Når vi fyrer op under Reflector, kan vi jo tydelig se, at List<T> benytter T[] til opbevaring af elementerne. Så hvis vi har List<string>, får vi vel string[] som den underliggende type. Ja, og nej.

Den underliggende type af List<string> er ganske rigtig string[], men måden CLRen implementerer arrays for referencetyper er ved hjælp af object[]. Lad os se et eksempel. Hvis vi har følgende i Main(), kan vi let finde den aktuelle List<string>-instans ved hjælp af !dso.

var Simpsons = new List<string> {
   "Homer", "Marge", "Bart", "Lisa", "Maggie"
};

0:000> !dso
OS Thread Id: 0x1390 (0)
ESP/REG  Object   Name
0029ed28 01ea2b78 Microsoft.Win32.SafeHandles.SafeFileHandle
0029ed38 01ea2b78 Microsoft.Win32.SafeHandles.SafeFileHandle
0029ed6c 01ea42ac System.Byte[]
0029ed70 01ea2b8c System.IO.__ConsoleStream
0029ed90 01ea4034 System.IO.StreamReader
0029ed94 01ea4034 System.IO.StreamReader
0029edac 01ea4034 System.IO.StreamReader
0029edb0 01ea45c4 System.IO.TextReader+SyncTextReader
0029edd0 01ea45c4 System.IO.TextReader+SyncTextReader
0029ede0 01ea2af4 System.Collections.Generic.List`1[[System.String, mscorlib]] <=== HER!
0029eea4 01ea2a38 System.Object[]    (System.String[])
0029f050 01ea2a38 System.Object[]    (System.String[])
0029f078 01ea2a38 System.Object[]    (System.String[])

Vores instans findes på adressen 01ea2af4, så lad os se nærmere på den. 

0:000> !do 01ea2af4
Name: System.Collections.Generic.List`1[[System.String, mscorlib]]
MethodTable: 5f5f58c8
EEClass: 5f3abf0c
Size: 24(0x18) bytes
 (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
Fields:
      MT    Field   Offset                 Type VT     Attr    Value Name
5f5c4eec  40009d8        4      System.Object[]  0 instance 01ea2b3c _items
5f5eab0c  40009d9        c         System.Int32  1 instance        5 _size
5f5eab0c  40009da       10         System.Int32  1 instance        5 _version
5f5e84dc  40009db        8        System.Object  0 instance 00000000 _syncRoot
5f5c4eec  40009dc        0      System.Object[]  0   shared   static _emptyArray

WinDbg reporterer korrekt, at vi har fat i List<string>, men læg også mærke til, at vi blandt Fields finder _items af typen Object[]. Er det vores data? Lad os se nærmere på indholdet af _items. 

0:000> !dumparray -details -nofields 01ea2b3c
Name: System.String[]
MethodTable: 5f5c4eec
EEClass: 5f3aa8a0
Size: 48(0x30) bytes
Array: Rank 1, Number of elements 8, Type CLASS
Element Methodtable: 5f5e88c0
[0] 01ea2a64
    Name: System.String
    MethodTable: 5f5e88c0
    EEClass: 5f3aa498
    Size: 28(0x1c) bytes
     (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
    String:     Homer
[1] 01ea2a80
    Name: System.String
    MethodTable: 5f5e88c0
    EEClass: 5f3aa498
    Size: 28(0x1c) bytes
     (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
    String:     Marge
[2] 01ea2a9c
    Name: System.String
    MethodTable: 5f5e88c0
    EEClass: 5f3aa498
    Size: 26(0x1a) bytes
     (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
    String:     Bart
[3] 01ea2ab8
    Name: System.String
    MethodTable: 5f5e88c0
    EEClass: 5f3aa498
    Size: 26(0x1a) bytes
     (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
    String:     Lisa
[4] 01ea2ad4
    Name: System.String
    MethodTable: 5f5e88c0
    EEClass: 5f3aa498
    Size: 30(0x1e) bytes
     (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
    String:     Maggie
[5] null
[6] null
[7] null

Der er vist ingen tvivl om, at det object[] indeholder navnene på vores gule familie, men hvor er sammenhængen mellem List<string> og det underliggende object[]? Hvordan ved CLRen, at vores array indeholder instanser af string?

Lad os først få en ting på det rene. Referencer er referencer, så der er ingen forskel på en reference til en instans af object og en reference til en instans af string. Det er blot referencer, så der er intet galt i, at CLRen bruger et object[] til at gemme referencerne, men hvordan holder den styr på det faktiske indhold?

Ovenstående dump giver ikke nogen svar på dette spørgsmål. SOS kan give indtrykket af, at vi ser det hele, men faktisk pakker SOS et par implementeringsdetaljer ind og viser os dem på anden vis. Vi er altså nødt til at gå uden om SOS, for at få svar på det spørgsmål.

Dumper vi hukommelsen for vores object[], får vi de manglende brikker. 

0:000> dd 01c62b3c -4 01c62b3c -4 +0x30 -1
01c62b38  00000000 5f5c4eec 00000008 5f5e88c0
01c62b48  01c62a64 01c62a80 01c62a9c 01c62ab8
01c62b58  01c62ad4 00000000 00000000 00000000

Den noget kryptiske kommando kalder vist på en forklaring. Den instansadresse SOS reporterer, er faktisk forskudt med et enkelt word. Det vil sige, at data for en instans begynder 4 bytes før den viste adresse (på 32 bit forstås). Så for at udskrive indholdet af instansen er vi nødt til at gå 4 bytes tilbage og udskrive til og med instansadressen, minus de fire bytes, plus størrelsen af instansen minus en. Det giver os data for vores object[].

Det første word er instansens SyncBlock, derefter følger instansen egen Method Table, så kommer længden at arrayet (8 i dette tilfælde), og herefter kommer det interessante: Hvad gemmer der sig bag 5f5e88c0? At dømme på værdien kunne det være en Method Table, så lad os se om det skulle være tilfældet.

0:000> !dumpmt 5f5e88c0
EEClass: 5f3aa498
Module: 5f381000
Name: System.String
mdToken: 02000024  (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
BaseSize: 0x10
ComponentSize: 0x2
Number of IFaces in IFaceMap: 7
Slots in VTable: 196

Det er en Method Table for string og dermed har vi kædet vores object[] sammen med den aktuelle type. De efterfølgende otte words er referencerne til vores fem string-instanser, samt tre tommer pladser til yderligere string-referencer.

Det efterlader blot et spørgsmål: Hvis object[] i realiteten er T[], hvad indeholder det mystiske felt så for et rigtig object array? Method Table for object naturligvis og så passer pengene.

Posted in .NET, C#, Debugging, Generics, List<T>, WinDbg, WinDbg Q&A, sos.dll | No Comments »

Når 64 bit < 32 bit

Monday, July 6th, 2009

I en kommentar til mit indlæg om tilgængelig hukommelse i .NET applikationer skriver Jonathan Jørgensen følgende meget relevante kommentar, ”Maks. 2GB per objekt i 64bit applikationer”. Jeg var godt klar over, at denne begrænsning eksisterer i 32 bit .NET, men jeg var faktisk ikke opmærksom på, at den også gælder i 64 bit-verdenen.

Jonathan fortsætter, ”Det er dog de færreste der vil opleve disse problemer da klasser (reference types) som eksempelvis List jo selv referer til flere objekter internt.”

Det kan godt være, at der ikke er mange, der vil opleve problemet, men hvis jeg forstår Jonathan korrekt, tager han desværre fejl med hensyn til List<T>. Problemet er nemlig, at List<T> benytter et array til at gemme sine referencer, og dette array er naturligvis også underlagt 2 GB-grænsen. Ergo er List<T> og andre typer, der benytter arrays begrænset i størrelse.

Det har den ret overraskende effekt, at siden 64 bit referencer er dobbelt så store som 32 bit referencer, kan en instans af List<T> kun rumme halvt så mange referencer under 64 bit .NET i forhold til samme liste under 32 bit .NET. Det er ikke just indlysende, og det vil betyde, at applikationer, der kører fint under 32 bit .NET risikerer at fejle med OutOfMemoryException under 64 bit!

Et array kan i teorien være 2 GB stort på 32 bit .NET. I praksis er den en anelse mindre, da selve array-instansen også har det sædvanlige overhead, der kendes fra referencetyper. Derfor vil List<T> kunne rumme ca. 2 GB / 4 elementer på 32 bit, mens tallet er ca. 2 GB / 8 elementer på 64 bit.

I teorien kan vi derfor have 536.870.897 referencer i en List<T> på 32 bit, men som min forrige artikel illustrerede, kan vi ikke regne med at kunne allokere mere end ca. 1,5 GB sammenhængende hukommelse under 32 bit Windows, og derfor vil vi i praksis ikke kunne oprette en liste med det antal elementer. Det faktiske antal elementer afhænger af det største sammenhængende område i processens adresserum.

På 64 bit er resultatet dog endnu mere begrænset. Her vil vi maksimalt kunne allokere en List<T> med 268.435.448 referencer.

Under 32 bit Windows vil vi i bedste fald kunne oprette et array med ca. 1,5 GB / 4, svarende til ca. 400.000.000 elementer. Det er en del mere end det maksimale antal elementer i et array under 64 bit, og derfor kan vi komme i den bizarre situation, at det faktisk kan give bagslag at flytte sin applikation til 64 bit.

Det er ikke svært, at lave sine egne klasser, der kommer uden om denne begrænsning ved f.eks. at bruge en hægtet liste eller ved at splittet indholdet op i et antal arrays, når det bliver nødvendigt, men det ville have været rart, om standardtyperne under 64 bit .NET havde givet bedre eller i det mindste bare de samme muligheder som under 32 bit.

Posted in .NET, 32 bit, 64 bit, Array, List<T> | 4 Comments »

List<T> under overfladen

Wednesday, December 5th, 2007

Med introduktionen af .NET 2.0 fandt ArrayList en afløser i List<T>. Skønt ordet ”array” ikke længere indgår i navnet, er List<T> faktisk stadig baseret på Array, hvilket vi kan konstatere ved hjælp af Reflector.

De største fordele ved List<T> i forhold til ArrayList er typefastheden og en ganske betydelig performanceforbedring i forbindelse med håndtering af værdityper (value types). Typefastheden leder til simplere kode, da vi undgår at skulle undersøge type på og om nødvendig caste elementer, når vi piller dem ud af listen. Performanceforbedringen kommer af, at vi undgår at box/unboxe i forbindelse med værdityper.

Så for at gøre en lang historie kort: List<T> er langt at foretrække frem for ArrayList, så for at få mest ud af den, er det en god ide at se på, hvordan den er implementeret. Som nævnt er List<T> internt baseret på en Array. Det betyder, at skønt List<T> præsenterer en datastruktur uden fast størrelse, er dette blot en illusion. Når man opretter en List<T>, har den en størrelse, og når der er behov for mere plads, er typen således nødsaget til at oprette en ny, større struktur og flytte alle elementer til denne. Det er selvsagt ikke en billig operation.

Som udgangspunkt afsættes der faktisk ikke plads i en List<T>, hvilket man kan verificere ved at konstatere at Capacity indledningsvis sættes til 0. Så snart der tilføjes et element, afsættes der plads til 4 elementer, og herefter fordobles kapaciteten, hver gang behovet opstår. Det vil sige, at det femte element (og her tænker jeg ikke på filmen) resulterer i at Capacity stiger til 8, det niende element får Capacity til at stige til 16 og så fremdeles. Det betyder, at der for små lister kan spildes meget tid på disse interne omrokeringer, og derfor er det en god ide, at oprette sine List<T>-instanser med en passende kapacitet via den tilhørende constructor.

For meget store lister er dette overhead mindre betydende, men her kan man optimere pladsforbruget ved at sætte en passende kapacitet, så man kan undgå, at der afsættes for meget plads til referencer. Har man f.eks. en liste med 1,1 million navne, vil standardopførelsen gøre, at der afsættes plads til 2^21 eller 2.097.152 elementer. Så uanset hvad er det en god ide at sætte en indledende kapacitet, hvis man på nogen måde har mulighed for at komme med et kvalificeret gæt på den nødvendige kapacitet.

Mange implementeringer af en List-type er baseret på det, man kalder en hægtet listet (linked list), i hvilken brugeren har en reference til det første element i listen, og hvert element desuden har en reference til det efterfølgende element (eller null for sidste element i listen). En sådan implementering vil typisk tilbyde en Insert()- og en Add()-metode ganske som tilfældet er for List<T>. I dette tilfælde vil Insert() almindeligvis være særdeles effektiv, idet det kun kræver justering af to referencer at indsætte et element forrest i listen. Med mindre listen også gemmer en reference til det sidste element, vil det til gengæld være dyrt at indsætte elementer sidst i listen, da dette kræver, at vi løber hele listen igennem via referencerne i de enkelte elementer.

Sådan er det ikke med List<T>. Her forholder det sig faktisk lige omvendt. At tilføje et element via Add() er særdeles effektivt, men vil dog medføre et overhead, hvis kapaciteten skal udvides. Faktisk fremgår det af dokumentationen, at Add() som udgangspunkt er en O(1) operation. Skal listen udvides bliver det dog en O(n) operation.

Insert() er derimod en O(n) operation ifølge dokumentationen, men hvis vi tager et kig på implementeringen ved hjælp af Reflector (se nedenfor), ser vi, at dette faktisk ikke gælder, hvis Insert() resulterer i at elementet indsættes i slutningen af listen. I det tilfælde er Insert() stort set lige så hurtig som Add() – og i realiteten er der tale om O(1).

public void Insert(int index, T item)
{
   if (index > this._size) {
      ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index,
         ExceptionResource.ArgumentOutOfRange_ListInsert);
   }
   if (this._size == this._items.Length) {
      this.EnsureCapacity(this._size + 1);
   }
   if (index < this._size) {
      Array.Copy(this._items, index, this._items, index + 1, this._size - index);
   }
   this._items[index] = item;
   this._size++;
   this._version++;
}

Som det også fremgår af ovenstående, ligger Insert() naturligvis under for de samme restriktioner som Add() i det tilfælde, at kapaciteten skal udvides.

Så hvad kan vi lære af at se på implementeringen af List<T>? For det første, vil det som sagt være en god ide at vælge en passende kapacitet ved oprettelsen af sin liste for at undgå de tunge omallokeringer og det voldsomme overhead ved store lister. Dernæst kan vi konstatere, at i og med at List<T> ikke er implementeret som en hægtet liste, er Add() langt at foretrække frem for Insert(). Faktisk er omkostningerne ved sidstnævnte så store, at man virkelig kun skal bruge den som sidste udvej. Og sidst men ikke mindst, er der ingen grund til fortsat at bruge ArrayList.

Posted in .NET, Array, C#, Generics, List<T>, Performance, Tip | 5 Comments »

Kompakt og hurtig kode med delegates

Thursday, November 22nd, 2007

System definerer et antal delegates, heriblandt to generiske delegates: Predicate<T> og Action<T> til brug for en del af List<T>s metoder. Predicate<T> bruges til at specificere en delegate, der udvælger elementer fra en liste baseret på et eller andet kriterium. Action<T> bruges til at specificere en delegate, der skal udføres på en eller flere af elementerne i en liste.

Predicate<T> kan f.eks. bruges på en List<T> til at udvælge et antal elementer via en anonym delegate. Hvis vi eksempelvis har en liste af ord, kan vi finde alle ord med tre eller flere tegn ved hjælp af FindAll() og en passende anonym Predicate<T> delegate.

List<string> longerthanthree =
   strings.FindAll(delegate(string current) { return current.Length > 3; });

I C# 3.0 kan det tilmed gøres endnu mere elegant ved hjælp af lambda-udtryk:

List<string> longerthanthree =
   strings.FindAll(current => current.Length > 3);

Personligt finder jeg disse former langt mere elegante end den tilsvarende implementering med foreach.

foreach (string s in strings) {
   if (s.Length > 3) {
      longerthanthree.Add(s);
   }
}

Vi kan altså bruge delegates som ovenstående til at skrive meget kompakt og præcis kode. Hvis det giver mening for den pågældende klasse, kan vi tilmed definere delegates til hyppige operationer. Hvis vi eksempelvis har en klasse, der repræsenterer overvågning af forskellige services, kunne vi have en ServiceWatcher-klasse, der definerer en Predicate<T> og en Action<T>, der gør det muligt at skrive kode som nedenstående.

watchers.FindAll(ServiceWatcher.AreRunning).ForEach(ServiceWatcher.StopIt);

watchers er en List<T> af ServiceWatchers, AreRunning er en Predicate<T> og StopIt er en Action<T>. De to delegates er implementeret således:

public static Predicate<ServiceWatcher> AreRunning =
   delegate(ServiceWatcher w) { return w.IsRunning; };
public static Action<ServiceWatcher> StopIt =
   delegate(ServiceWatcher w) { w.Stop(); };

Da de begge udelukkende arbejder på deres argument, kan de med fordel laves static.

(Note: Ovenstående kunne naturligvis også implementeres via en StopAllRunning()-metode, der indkapslede de nødvendige operationer. Har man flere udvælgelseskriterier og flere handlinger, er delegates dog at foretrække, da brugeren derved let kan sammensætte de relevante kombinationer.)

Hvis ovenstående konstruktion skal skrives ved hjælp af et loop, ser det ud som følger:

foreach (ServiceWatcher watcher in list) {
   if (watcher.IsRunning) {
      watcher.Stop();
   }
}

Det er måske en smagssag, hvilken variant man foretrækker, så hvis det bare var et spørgsmål om syntaks, kunne indlægget passende slutte her, men hvis vi ser lidt på performance af de forskellige teknikker, bliver det interessant.

Hvis jeg kører ovenstående igennem i Release mode på en liste med 100 elementer, kører delegate-versionen ca. dobbelt så stærkt som loop-versionen. Ved 10.000 elementer kører delegate-versionen ca. 6 gange så stærkt og ved en million elementer ca. 10 gange så stærkt! Jeg kan ikke på nuværende tidspunkt redegøre for hvilke interne optimeringer, der er årsag til denne forskel, men jeg kan blot konstatere, at dette er et af de få tilfælde, hvor den mest elegante kode også resulterer i den mest effektive ydelse. Derfor er der god grund til at se på disse delegates, når man arbejder med List<T>.

Posted in .NET, C#, C# 3.0, Delegates, List<T>, Performance, Tip | No Comments »

Fleksible grænseflader

Wednesday, May 23rd, 2007

Med introduktionen af generics i .NET 2.0 har vi fået langt bedre muligheder for at lave genbrugelig kode, men som så meget andet kommer det naturligvis ikke af sig selv. Genbrugelig kode kræver, at vi tænker over kodens grænseflader og i den sammenhæng er følgende gode råd at følge:

  1. Parametre til metoder skal være så generelle som mulige
  2. Returparametre fra metoder skal være så specifikke som mulige

I begge tilfælde gælder det naturligvis, at det skal være i forhold til den aktuelle situation og ikke det teoretisk mulige, men lad os se på et par eksempler.

Lad os forestille os, at vi har en metode, der som input tager en liste af vores SomeType-instanser. Den mest nærliggende implementering er:

public static void MostSpecificParameter(List<SomeType> l) {
      foreach (SomeType st in l) {
            st.DoSomething();
         }
      }

Den fungerer, men den er ikke særlig fleksibel, da den kræver at vores samling af SomeType-objekter er samlet i en List<T>. Hvis vi ikke har brug for List<T>s funktionalitet, kan vi gøre metoden lidt mere fleksibel, ved at specificere at input skal være af en type, der implementerer IList<T>.

public static void SpecificParameter(IList<SomeType> l) {
   foreach (SomeType st in l) {
      st.DoSomething();
   }
}

På den måde kan vi nu anvende metoden, uanset om vores SomeType-objeter er opbevaret i en List<T> eller i en array (SomeType[]), men vi kan faktisk gøre det endnu bedre:

public static void LeastSpecificParameter(IEnumerable<SomeType> l) {
   foreach (SomeType st in l) {
      st.DoSomething();
   }
}

Ved at baserer metodens input på typer, der implementerer IEnumerable, har vi gjort det særdeles frit for brugeren, hvordan inputdata skal opbevares. Ovenstående fungerer uændret med blandt andet List<SomeType>, SomeType[] og Stack<SomeType>. Så hvis List<T>s funktionalitet ikke er en nødvendighed for metoden, er alternativerne langt mere anvendelige. Selvfølgelig ville en metode med object som inputargument være endnu mindre specifik, men som nævnt er vi ikke interesseret i den teoretisk mest fleksible grænseflade, men den mest fleksible grænseflade, der passer til den opgave vi forsøger at løse. Da koden ovenfor løber en samling af SomeType-objekter igennem vil det kun give problemer at lave en variant, der tager object som input. Reglen er at input skal være så generel som mulig i forhold til den givne opgave.

Med returtyper forholder det sige lige omvendt. Her er det bedst at anvende en så specifik type som mulig, og derfor er det som udgangspunkt også bedre at returnere typer frem for interfaces, så hvis vi har:

public static SomeDerivedType MostSpecificReturn() {
   return new SomeDerivedType();
}

public static SomeType NotSoSpecificReturn() {
   return new SomeDerivedType();
}

public static object LeastSpecificReturn() {
   return new SomeDerivedType();
}

er førstnævnte langt mere fleksibel for brugerne end de efterfølgende. Førstnævnte understøtter følgende brugsmønstre:

SomeDerivedType SpecificReturn1 = MostSpecificReturn();
SomeType        SpecificReturn2 = MostSpecificReturn();
object          SpecificReturn3 = MostSpecificReturn();

De to andre implementeringer gør det gradvist mere bøvlet for brugerne som nedenstående illustrerer:

SomeDerivedType NotSoSpecificReturn1 = (SomeDerivedType)NotSoSpecificReturn();
SomeType        NotSoSpecificReturn2 = NotSoSpecificReturn();
object          NotSoSpecificReturn3 = NotSoSpecificReturn();

SomeDerivedType LeastSpecificReturn1 = (SomeDerivedType)LeastSpecificReturn();
SomeType        LeastSpecificReturn2 = (SomeDerivedType)LeastSpecificReturn();
object          LeastSpecificReturn3 = LeastSpecificReturn();

Da metoder, der returnerer referencetyper afleverer en reference til en instans af et eller andet, er der som regel ikke noget at vinde ved at returnere et interface i stedet for den faktiske instans.

public static IList<string> ThisIsNotOptimal() {
   return new List<string>();
}

IList<string> l1 = ThisIsNotOptimal ();

Skønt ovenstående fungerer fint, har vi begrænset brugerens anvendelse af den returnerede liste til det interface IList<T> specificerer. Det vil f.eks. sige, at brugeren ikke efterfølgende kan kalde Sort() på listen, da denne metode ikke er en del af IList<T>.

Den eneste fordel ovenstående giver os i forhold til at returnere en List<T> er, at vi på et senere tidspunkt kan ændre implementeringen til f.eks. at returnere en string[]. Da string[] også implementerer IList<T> er det blot en implementeringsdetalje, brugeren ikke behøver at kende. Har man derimod ikke behov for at kunne ændre implementeringen på den måde, giver man brugeren en langt mere fleksibel grænseflade ved at returnere en så specifik type som mulig – i dette tilfælde en List<string>.

Posted in .NET, C#, Generics, List<T> | No Comments »

List, SortedList og en sorteret liste

Friday, May 11th, 2007

Med .NET 2.0 introducerede Microsoft en helt ny samling generic collections. Blandt disse er den meget anvendelige List<T> – en ordnet, men ikke sorteret liste af elementer. List<T> tilbyder en Sort()-metode, der kan sortere indholdet af listen, men det er både bøvlet og ikke særlig effektivt at sortere hele listen hver gang et element indsættes. Har man brug for en liste med sorterede elementer, er List<T> derfor ikke altid det oplagte valg.

Blandt de mange collections er også SortedList<T>, men det er ikke som navnet ellers antyder en liste men derimod et dictionary. Ergo kræver typen, at data er ordnet i et nøgle/værdi-forhold. Derudover kræver SortedList<T>, at alle nøgler er unikke, så alt i alt er den ikke særlig tæt på at være en sorteret udgave af List<T>. Derfor er der ikke umiddelbart noget godt bud på en collection til repræsentation af en sorteret liste, men inden vi fortvivler, er det faktisk en god ide at kaste endnu et blik på List<T>.

List<T> implementerer nemlig BinarySearch(). Metoden returnerer indeks på det søgte element, hvis det findes i listen eller den binære komplementærværdi til det indeks element ville findes på, hvis det var i listen. Den opførsel kan vi bruge til at tilføje elementer til listen, så listen altid er sorteret. BinarySearch() kræver naturligvis, at listen er sorteret, men hvis alle elementer indsættes på deres korrekte plads, er listen sorteret uden, at vi behøver at kalde Sort(). Add() kunne se ud som følger:

public class OrderedList<T> : IList<T> {
   public void Add(T item) {
      int index = list.BinarySearch(item);
      if (index >= 0) {
         list.Insert(index, item);
      } else {
         list.Insert(~index, item);
      }
   }
   ...
}

OrderedList<T> implementerer en Add()-metode, der indsætter elementet på den korrekte plads i listen ved hjælp af BinarySearch(). Det betyder naturligvis, at Add() bliver noget langsommere end List<T>.Add(), men meget hurtigere end List<T>.Add() efterfulgt af List<T>.Sort() og i og med at listen er sorteret, kan vi implementere særdeles effektive udgaver af IndexOf() og Contains().

public int IndexOf(T item) {
   int index = list.BinarySearch(item);
   return index < 0 ? -1 : index;
}

public bool Contains(T item) {
   return list.BinarySearch(item) >= 0;
}

Hvor List<T> er tvunget til at lave en lineær søgning for IndexOf() og Contains(), kan vi nu gøre det samme som en O(log n)-operation. Der er altså store gevinster at hente, hvis man har brug for at slå op i listen.

Hvornår man skal bruge List<T> eller den sorterede variant afhænger meget af omstændighederne. List<T>s Sort()-metode bliver hurtigt meget dyr, så hvis man har brug for at kalde den ofte (i værste fald efter hver tilføjelse af et element), bliver OrderedList<T> hurtig meget mere effektiv. Har man på den anden side en applikation, der ikke har brug for at listen er sorteret, mens elementer bliver tilføjet, er List<T> at foretrække. I så fald kan man indsætte alle elementer og derefter kalde Sort(), for selvom Sort() tager tid opvejes det af at Add() er langt hurtigere for List<T> end den tilsvarende udgave baseret på BinarySearch().

Jeg har lavet en implementering af en sorteret liste, der kan hentes her til fri afbenyttelse.

Posted in .NET, C#, Generics, List<T>, Tip | 1 Comment »