Anmerkung: Selbiges gilt auch für den Schlüssel TKey im Dictionary<TKey, TValue>!

Das HashSet<T> stellt eine leistungsstarke Auflistung dar bei Operationen wie Hinzufügen, Prüfung ob ein Element bereits vorhanden ist, etc. einen O(1)-Vorgang dar. Im Vergleich dazu wären diese Operationen bei einer List<T> O(n)-Vorgänge.

Für die .net-Standardtypen kann das HashSet<T> problemlos verwendet werden. Wie schaut die Sache aber mit eigenen Typen aus? Schauen wir uns ein Beispiel an:

Der eigene Typ:

   1: class FooWrong

   2: {

   3:     public int n { get; set; }

   4: }

Der erste Versuch mit dem HashSet<T> zu arbeiten:

   1: FooWrong fooWrong1 = new FooWrong { n = 3 };

   2: FooWrong fooWrong2 = new FooWrong { n = 3 };

   3: int hash1 = fooWrong1.GetHashCode();

   4: int hash2 = fooWrong2.GetHashCode();

   5:  

   6: HashSet<FooWrong> hsWrong = new HashSet<FooWrong>();

   7: bool add1 = hsWrong.Add(fooWrong1);

   8: bool add2 = hsWrong.Add(fooWrong2);

Es werden Instanzen des eigenen Typs erstellt mit den jeweils identen Werten. So erwarten wir dass beide Instanzen ident sind. Werden nun aber diese Instanzen zum HashSet hinzugefügt so sind beide enthalten – komisch denn das HashSet sollte doch nur Elemente haben die einzigartig sind.

Woher kommt das?
Das HashSet vergleicht zuerst die HashWerte der Objekte und falls diese gleich sind wird der Vergleich der Objekte mittels Equals durchgeführt. Dies geschieht indem die Default-Eigenschaft des IEqualityComparers<T> ausgewertet wird. Da wird keine Implementierung bzw. Überschreibung von GetHashCode angegeben haben wird die Methode vom Basistyp (hier: System.Object) verwendet. Dieser liefert korrekt unterschiedliche HashWerte für die beiden Instanzen da sie nicht die gleiche Referenz sind.

Nun kann dem HashSet eine Instanz eines IEqualityComparers<T> übergeben werden oder die Default-Eigenschaft erstellt die Instanz von selbst wenn der Typ die IEquatable<T>-Schnittstelle implementiert. Um obiges Beispiel korrekt zu machen sollte der Code also wie folgt geschrieben werden:

Der eigene Typ (implementiert IEquatable<T>):

   1: class FooCorrect : IEquatable<FooCorrect>

   2: {

   3:     public int n { get; set; }

   4:  

   5:     public override int GetHashCode()

   6:     {

   7:         return n.GetHashCode();

   8:     }

   9:  

  10:     #region IEquatable<FooCorrect> Member

  11:     public bool Equals(FooCorrect other)

  12:     {

  13:         if (other == null)

  14:             return false;

  15:  

  16:         return this.n == other.n;

  17:     }

  18:     #endregion

  19: }

Gewünschte Arbeit des HashSets:

   1: FooCorrect fooCorrect1 = new FooCorrect { n = 3 };

   2: FooCorrect fooCorrect2 = new FooCorrect { n = 3 };

   3: hash1 = fooCorrect1.GetHashCode();

   4: hash2 = fooCorrect2.GetHashCode();

   5:  

   6: HashSet<FooCorrect> hsCorrect = new HashSet<FooCorrect>();

   7: add1 = hsCorrect.Add(fooCorrect1);

   8: add2 = hsCorrect.Add(fooCorrect2);

Da dem HashSet keine Instanz eines Vergleichs übergeben wird verwendet das HashSet eine Instanz des Comparers der über die IEquatable<T>.Default-Eigenschaft erstellt wird. Wie bereits erwähnt wird diese Instanz aus der Schnittstelle IEquatable<T> erstellt.

Happy coding ;)

Wie bereits im Blog-Eintrag zu INotifyPropertyChanged verwendet und gezeigt können Ausdrucksbäume auch für das Exception-Handling verwendet werden.

Beispiel für eine typische Methode:

   1: public void Foo(object argument)

   2: {

   3:     if (argument == null)

   4:         throw new ArgumentNullException("argument");

   5:     ...

   6: }

Mich stört daran wieder dass ich im Konstruktor für ArgumentNullException der Paramater als String-Literal angegeben werden muss. Vor allem wenn der Code rafactored wird gibt es Probleme.

Durch Verwendung von Lambda-Ausdrücken kann dies sicherer geschrieben werden. Dazu erstelle ich mir eine (statische) Hilfsklasse:

   1: internal static class ExceptionHelper

   2: {

   3:     internal static ArgumentNullException ArgumentNull<T>(Expression<Func<T>> exp)

   4:     {

   5:         return new ArgumentNullException(GetParamName(exp));

   6:     }

   7:     //---------------------------------------------------------------------

   8:     private static string GetParamName<T>(Expression<Func<T>> exp)

   9:     {

  10:         MemberExpression me = exp.Body as MemberExpression;

  11:         return me.Member.Name;

  12:     }

  13: }

In dieser Klasse wird in der Methode GetParamName<T> die Expression “zerlegt” und der Bezeichner des Members als String zurückgegeben.
Über die Methode ArgumentNull<T> wird die Exception erstellt. Der Vorteil der Hilfsklasse ist dass somit alle Exceptions einer Anwendung zentral erstellt werden können (don’t repeat yourself) und weiters ist es somit einfach möglich die Exceptions zu lokalisieren.

Die Methode Foo (das Beispiel) änder sich zu:

   1: public void Foo(object argument)

   2: {

   3:     if (argument == null)

   4:         throw ExceptionHelper.ArgumentNull(() => argument);

   5: }

Es ist ersichtlich dass beim Refactoring die Exception korrekt geworfen wird – eine Änderung des String-Literals (da nicht vorhanden) ist nicht nötig.

Happy coding ;)

Mit .net 4.0 ist es für jeden möglich Parallelverarbeitung durchzuführen ohne dass die grundlegenden Kenntnisse von Threading existieren. Dieses und weitere solcher Probleme werden in Zukunft immer öfter auftreten da es sehr verlockend und als Hype gilt mit mehreren Threads zu arbeiten.

Ich bin dennoch der Meinung dass dieses Werkzeug nur dann sinnvoll eingesetzt werden kann wenn die Grundlagen wie zB Threadsynchronisation verstanden werden - auch wenn das Werkzeug viel von den Mechanismen die im Hintergrund tätig sind wegabstrahiert. Ich habe zB noch keinen Artikel über das Task-Parallel-Library gesehen der bewusst darauf eingeht welche Probleme sich parallelisieren und nicht parallelisieren lassen.

Es ist gut zu überlegen ob die zu verarbeitenden Daten unabhängig voneinander sind - nur dann ist eine Parallelisierung möglich.

Die TPL ist also ein Werkzeug das Fluch und Segen gemeinsam ist – je nachdem ob man die Hintergründe kennt oder nicht.

Happy hacking ;)

   1: static void Main(string[] args)

   2: {

   3:     int i = 0;

   4:     Action myAction = delegate

   5:     {

   6:         Console.WriteLine(i);

   7:     };

   8:  

   9:     myAction();

  10:     i = 666;

  11:     myAction();

  12:  

  13:     Console.ReadKey();

  14: }

In diesem Snippet wird eine anonyme Methode erstellt welche auf den Wert der Variablen i zugreift. Wie kann jedoch auf den Wert zugegriffen werden wenn dieser im Kontext der anonymen Method nicht existiert – er wird ja nicht per Parameter übergeben?

Dies wird dadurch gelöst dass die Variable i auf dem Heap erstellt wird (statt auf dem Stack). Dazu erzeugt der Compiler eine Klasse (werden DisplayClass…) genannt welche als öffentliches Feld i hat. Somit kann sowohl in der Main-Methode sowie in der anonymen Methode zugegriffen werden. Dieses Prinzip ähnelt dem der Closures.

Definition einer Closure gem. Wikipedia:

Als Closure oder Funktionsabschluss bezeichnet man eine Programmfunktion, die beim Aufruf ihren Definitionskontext reproduziert, selbst wenn dieser Kontext außerhalb der Funktion schon nicht mehr existiert. Closures „konservieren“ also ihren Kontext.

Die Definition wird von C# nicht ganz erfüllt denn wie im obigen Beispiel gezeigt wenn sich der Wert von i ändert so ist der Wert in der anonymen Methode auch geändert - i wurde ja auf dem Heap erstellt. Dieser Umstand ist zu berücksichtigen denn die “äußere Variable wird gefangen”. Die Berücksichtigung dessen erfolgt indem eine lokale Kopie der äußeren Variable angelegt wird.

Inkorrektes Beispiel

   1: static void Incorrect()

   2: {

   3:     for (int i = 0; i < 10; i++)

   4:         ThreadPool.QueueUserWorkItem(delegate

   5:             {

   6:                 Console.WriteLine(i);

   7:             });

   8:     

   9:     Console.ReadKey();

  10: }

Das Beispiel wird in folgenden sinngemäßen Code kompiliert:

   1: static void IncorrectCompiled()

   2: {

   3:     DisplayClass display = new DisplayClass();

   4:     display.i = 0;

   5:     for (display.i = 0; display.i < 10; display.i++)

   6:     {

   7:         ThreadPool.QueueUserWorkItem(delegate

   8:         {

   9:             Console.WriteLine(display.i);

  10:         });

  11:     }

  12:  

  13:     Console.ReadKey();

  14: }

  15: //---------------------------------------------------------------------

  16: private sealed class DisplayClass

  17: {

  18:     public int i;

  19:     //-----------------------------------------------------------------

  20:     public void Action()

  21:     {

  22:         Console.WriteLine(i);

  23:     }

  24: }

Es wird somit immer der Wert 10 ausgegeben da dieser Wert nach Beendigung der Schleife dem Wert des öffentlichen Feldes des DisplayClass-Objektes entspricht.

Korrektes Beispiel

Um ein korrekte Ausgabe der Werte von [0, 10) zu erhalten muss wie oben angemerkt die äußere Variable lokal kopiert werden.

   1: static void Correct()

   2: {

   3:     for (int i = 0; i < 10; i++)

   4:     {

   5:         int j = i;

   6:         ThreadPool.QueueUserWorkItem(delegate

   7:         {

   8:             Console.WriteLine(j);

   9:         });

  10:     }

  11:  

  12:     Console.ReadKey();

  13: }

Dieser Code liefert das korrekte Ergebnis und wird zu folgendem kompiliert:

   1: static void CorrectCompiled()

   2: {

   3:     for (int i = 0; i < 10; i++)

   4:     {

   5:         DisplayClass displayClass = new DisplayClass();

   6:         displayClass.i = i;

   7:         ThreadPool.QueueUserWorkItem(delegate

   8:         {

   9:             Console.WriteLine(displayClass.i);

  10:         });

  11:     }

  12:  

  13:     Console.ReadKey();

  14: }

Es werden also mehrere DisplayClass-Objekte erstellt um den äußeren Zustand gemäß Definition zu fangen. Die Ausgabe ist daher korrekt.

Wichtiger Hinweis

Das Verhalten von Closures muss berücksichtigt werden. Dies gilt auch für LINQ-Abfragen – bei diesen wird ja eine anonyme Methode übergeben und somit müssen Closures berücksichtigt werden.

Im Entwickler-Forum hab ich einen Beitrag zum Thema Visualisieren der Daten einer Matrix verfasst. Der Link zum Thema: http://entwickler-forum.de/showthread.php?p=201316#post201316. Es ist auch das Demo-Projekt angehängt.

Verwendung findet es im konkreten Anwendungsfall in der Visualisierung von Messdaten eines Sensors.

Nachfolgend dargestellt ist einmal die Graustufendarstellung und die Darstellung mit Verwendung einer Farbskala.

Happy visualizing ;)

Ich merke immer wieder dass vielen das Verständnis von Gleitkommazahlen fehlt und deshalb oft eine Vergleich mit == durchgeführt wird. Dies ist aber nicht korrekt.

Beispiel:

double d1 = 3.3;
double d2 = 1.1 + 2.2;
if (d1 == d2)
    Console.WriteLine("gleich");
else
    Console.WriteLine("ungleich");

Beim Ausführen des Code wird die korrekte Ausgabe “gleich” erwartet, es erscheint jedoch “ungleich”. Wie ist das möglich? Ist meine CPU defekt?

Die Begründung in diesem Verhalten liegt darin dass Gleitkommazahlen (float, double) im Rechner nur als Näherung einer reellen Zahl dargestellt werden. Es treten also Rundungsfehler auf. In der Numerik gibt es ganze Kapitel über die Behandlung von Fehlern und der Fortpflanzung. So weit gehe ich hier aber nicht.

Durchläuft man obigen Code mit dem Debugger und schaut sich die Werte von d1 und d2 an so kann festgehalten werden:

d1    3.3    double
d2    3.3000000000000003    double

Also existiert nur ein kleiner Unterschied in beiden Werten, der Vergleich mit == liefert somit korrekt das falsche Ergebnis.

Wie werden Gleitkommazahlen verglichen?

Es liegt somit Nahe einen Vergleich mit einer Toleranz durchzuführen. Dieses Toleranz wird in der Numerik üblicherweise als Epsilon bezeichnet.

Somit muss obiger Code geändert werden zu:

if (Math.Abs(d1 - d2) < epsilon)
    Console.WriteLine("gleich");
else
    Console.WriteLine("ungleich");

Dies stellt allerdings nur die einfachste (und oft auch falsche Variante) dar. Eine detailliertere Betrachtung hab ich in diesem Foren-Beitrag gegeben.

Wie groß soll Epsilon gewählt werden?

Die Datentypen System.Single (float) und System.Double (double) bietet eine Konstante namens Epsilon an. Diese entspricht aber nicht der Definition von Epsilon im Sinne der Numerik. Dieses Epsilon stellt die kleinste positive von 0 verschiedene Zahl dar.

Epsilon im Sinne der Numerik wird wie folgt berechnet:

public static double Epsilon()
{
    double tau = 1.0;
    double walt = 1.0;
    double wneu = 0.0;

    while (wneu != walt)
    {
        tau *= 0.5;
        wneu = walt + tau;
    }

    return 2.0 * tau;
}

Es wird die Schleife so lange durchgeführt bis zwei Gleitkommazahlen als gleich erachtet werden. Dieses Epsilon (kann natürlich auch für float errechnet werden) sollte für Vergleiche von Gleitkommazahlen verwendet werden.

Epsilon für float: 1,192093E-07
Epsilon für double: 2,22044604925031E-16

Happy coding ;)

Ein sagenhaftes Tool von Microsoft Research. PEX – ein Blick für jeden Unit-Tester - und die es werden wollen lohnt - sich.

Geht auch im CommandLine-Modus super.

Da ich mich gerade mit diesem Tool spiele kann ich noch keine Beispiele posten – ist aber auch nicht nötig denn die Dokumention beschreibt alles ausführlich (oder im Getting Started ausreichend) so dass durch “spielendes Lernen” keine Anleitung nötig sein sollte.

Das einzige was ich schade finde ist dass ich jetzt auf NUnit verzichten kann – welch ein schönes Tool das war….;)

Happy testing ;)

In heutigen PCs steckt mit der Grafikkarte gewaltiges Rechenpotential das nicht nur für Computergrafik verwenden werden kann. Nachfolgend wird beispielhaft gezeigt wie mit der Grafikkarte Matritzen multipliziert werden können.

Warum mit der Grafikkarte rechnen?

Beim Vergleich der Leistungdaten einer Grafikkarte wie zB die Geforce GTX 285 mit einer Leistung von 1062,7 GigaFLOPS [1] und einem Pentium 4 mit 3,2 GHz der “nur” auf 6,4 GigaFLOPS kommt wird klar dass dieses Potential genutzt werden kann.

Warum ist die Grafikkarte (GPU – graphics processing unit) so schnell?

Eine CPU ist universell ausgelegt und kann prinzipiell alles berechnen während GPUs auf Computergrafik optimiert sind. Zudem arbeiten GPUs als Vektorprozessoren und sind somit hochgradig parallel.

Wie kann mit der Grafikkarte gerechnet werden?

In den Anfängen von GPGPU wurden Float-Arrays in Bitmaps verpackt um somit eine beliebige Anwendung als Grafikproblem zu tarnen. Wie man sich leicht vorstellen kann ist das Tarnen als Bitmap eine eher schwierige Aufgabe denn das Ergebnis wieder korrekt aus dem Bitmap zu entpacken ist schon eine Kunst.

Mit dem Projekt Accelerator von Microsoft Research wird dieses Verfahren verwendet.

Firmen wie zB Nvidia haben erkannt dass GPGPU ein neues Geschäftsfeld sein kann und bieten eine Programmierschnittstelle (API) an. Im Falle von Nvidia ist dies die Compute Unified Device Architecture [2]. CUDA ist eine Erweiterung für die Programmiersprache C aber es gibt glücklicherweise einen Wrapper für C# – CUDA.net. Diese Variante kann nur verwendet werden wenn eine Nvidia-Grafikkarte vorhanden ist. Zusätzlich muss das SDK dazu während der Entwicklung vorhanden sein.

Mit diesen zwei Projekten steht die Möglichkeit für GPGPU für jeden zur Verfügung. Es liegt aber beim Entwickler abzuwägen ob die Aufgabe für GPGPU geeignet ist.

Ich finde die Verwendung von Accelerator angenehmer da diese auf DirectX aufsetzt und somit keine Bindung zu einer spezifischen Grafikkarte existiert. Bei CUDA ist es außerdem nachteilig dass in einer C++-ähnlichen Syntax mit der Grafikkarte interagiert werden muss.

Beispiel

Als Beispiel sei der “Klassiker” für die Parallelisierung – die Matritzenmultiplikation – mit dem Accelerator-Projekt implementiert. Das Projekt besteht nur aus einer DLL und ist somit einfach zu verwenden – es braucht nur die Assembly eingebunden werden (Verweis hinzufügen).
Der Code ist relativ einfach:

   1: public float[,] MatMul(float[,] a, float[,] b)

   2: {

   3:     // GPU aktivieren:

   4:     ParallelArrays.InitGPU();

   5:  

   6:     // Die Matritzen für die GPU erstellen:

   7:     DisposableFloatParallelArray x = new DisposableFloatParallelArray(a);

   8:     DisposableFloatParallelArray y = new DisposableFloatParallelArray(b);

   9:  

  10:     // Matrix Multiplikation durchführen:

  11:     FloatParallelArray z = ParallelArrays.Multiply(x, y);

  12:  

  13:     // Das Ergebnis der GPU-Berechnung "greifbar" machen:

  14:     float[,] c;

  15:     ParallelArrays.ToArray(z, out c);

  16:  

  17:     // Speicher freigeben:

  18:     x.Dispose();

  19:     y.Dispose();

  20:  

  21:     // GPU deaktivieren:

  22:     ParallelArrays.UnInit();

  23:  

  24:     return c;

  25: }

Siehe auch

• General Purpose Computation on Graphics Processing Unit
• CUDA – Compute Unified Device Architecture

Quellenverzeichnis:

[1] Nvidia-GeForce-200-Serie (Leistungdaten)

Die klassische Verwendung von INotifyPropertyChanged sieht exemplarisch so aus:

   1: class Foo : INotifyPropertyChanged

   2: {

   3:     private string _name;

   4:     public string Name

   5:     {

   6:         get { return _name; }

   7:         set {

   8:             if (_name == value)

   9:                 return;

  10:  

  11:             _name = value;

  12:             OnPropertyChanged("Name");

  13:         }

  14:     }

  15:     //-------------------------------------------------------------------------

  16:     protected void OnPropertyChanged(string propertyName)

  17:     {

  18:         // Threadsicherheit:

  19:         PropertyChangedEventHandler tmp = PropertyChanged;

  20:         if (tmp != null)

  21:             tmp(this, new PropertyChangedEventArgs(propertyName));

  22:     }

  23:     //-------------------------------------------------------------------------

  24:     public event PropertyChangedEventHandler PropertyChanged;

  25: }

Darin gefällt mir nicht dass ich beim Aufruf von OnPropertyChanged ein String-Literal übergeben muss. Dies kann beim Refactoring zu Fehlern führen.

Seit es Lambda-Expressions gibt kann folgendes umgesetzt werden:

   1: protected void OnPropertyChanged<T>(Expression<Func<T>> exp)

   2: {

   3:     MemberExpression memberExpression = exp.Body as MemberExpression;

   4:     OnPropertyChanged(memberExpression.Member.Name);

   5: }

Darin wird der Name der Eigenschaft aus dem Ausdrucksbaum extrahiert (Lambda-Expression-Tree).

Die Verwendung wäre somit:

   1: set {

   2:     if (_name == value)

   3:         return;

   4:  

   5:     _name = value;

   6:     OnPropertyChanged(() => this.Name);

   7: }

Siehe da – es wird kein String mehr verwendet. Der korrekte Aufruf von OnPropertyChanged(string) ist auch nach einem Refactoring gegeben.

Es ist allerdings immer noch der Lambda-Ausdruck zu schreiben. Wenn ich jetzt besonders schreibfaul bin und für viele Eigenschaften Copy & Paste verwenden will muss ich mein Hirn anstrengen und versuchen den Namen der Eigenschaft zur Laufzeit zu ermitteln. Aber wie geht das?

Im Namespace System.Diagnostics gibt es Klassen mit denen der Aufruf-Stack geholt werden kann und daraus auch die Methode welche den Aufruf getätigt hat. Für Eigenschaften werden vom Compiler Getter- und Setter-Methoden generiert sodass die Setter-Methode einen Namen wie “set_EigenschaftsName” hat. Daraus den Namen der Eigenschaft zu extrahieren ist kein Problem.

   1: protected void OnPropertyChanged()

   2: {

   3:     // Methode des Aufrufers dieser Methode holen:

   4:     MethodBase mb = new StackFrame(1).GetMethod();

   5:         

   6:     string propertyName = mb.Name.Substring(4);    // set_ auslassen.

   7:  

   8:     OnPropertyChanged(propertyName);

   9: }

Der Aufruf vereinfacht sich jetzt zu einem OnPropertyChanged();

Der Compiler (genau genonommer der JITer) hat die Möglichkeit Optimierungen durchzuführen und dazu gehört auch das Inlining. Eigenschaften sind somit typische Kanditaten für Inlining. Daher muss für die Property das MethodImpl-Attribute mit NoInlining gesetzt werden.

Super!

Anmerkungen zur Leistung

Die zuletzt gezeigte Variante verwendet Reflektion und ist daher im Laufzeitverhalten um etliche Ticks langsamer als die vorletzte Variante die ihrerseits wiederum langsamer ist als der dirkete Aufruf mit dem String-Literal.

Am idealsten wäre natürlich wenn der Compiler den Code für OnPropertyChanged genieren würde. Dann wäre das auch mit den "automatic properties" möglich.
Könnte doch von Mircosoft berücksichtigt werden. Es gibt ja schon so vieles was [CompilerGenerated] ist.

Happy coding ;)