Delphi & C#: Vergleich zw. TList und ArrayList

[pajofego]

Hallo Leute,

ich habe das folgendes Problem:

Ich habe meine Matrix und Vektor Bibliothek für Sparse-Matrizen, welche in Delphi geschrieben sind, nach C# übersetzt. Nachdem diese in C# fertig waren wunderte ich mich darüber, dass das ganze in C# deutlich langsamer ist als in Delphi (Faktor 5)! Einen Performancetest mit Prof-It, zeigten mir, dass die Aufrufe von Methoden aus der ArrayList Klasse extrem viel Zeit in Anspruch nehmen (Delphi ist mit seinen Aufrufen in TList ziemlich flott)! Meine Frage an euch wäre, was könnte ich machen, um den Bottleneck einigermaßen vernünftig zu schließen?

Für Anregungen wäre ich euch dankbar..

Danke

Gruß

Paulo

[pajofego]

Bin ich zu ungenau in meiner Formulierung gewesen? :eek:

Wenn ja, dann sagt es ruhig! Mein eigentliches Problem ist; ich kann mir den Performanceunterschied zw. der gleichen Implementierung meiner Klasse in Delphi zu C# (um den Faktor drei) nicht erklären, außer, dass zuviel Zeit in der Klasse ArrayList von .NET verstreicht... :(

Ist dies normal oder eher ungewöhnlich? Verbraucht der GC soviel Zeit?

Gruß und danke

pajofego

[zeckensack]

Nimm lieber Java. Das wurde von kompetenten Leuten implementiert.

[Demirug]

Bin ich zu ungenau in meiner Formulierung gewesen? :eek:

Wenn ja, dann sagt es ruhig! Mein eigentliches Problem ist; ich kann mir den Performanceunterschied zw. der gleichen Implementierung meiner Klasse in Delphi zu C# (um den Faktor drei) nicht erklären, außer, dass zuviel Zeit in der Klasse ArrayList von .NET verstreicht... :(

Ist dies normal oder eher ungewöhnlich? Verbraucht der GC soviel Zeit?

Gruß und danke

pajofego

Der GC kann das nicht sein weil desen Zeit ja nicht bei den Methodeaufrufen anfällt.

Für welchen Zweg brauchst du den die ArrayList genau wenn ich fragen darf?

Es könnte aber auch an der Fliesspunkt Leistung liegen. Da ist der Jitter der aktuellen .Net Version noch nicht sehr gut.

[Jesus]

Naja ArrayLists haben keine indizierung und sehr viel Overhead weil sie für alles benutzt werden können.

Versuch mal ne Hashtable(value, index key), sollte wesentlich schneller sein, falls das für dich in Frage kommt.

Ansonsten kannst du dir auch eine eigene Typ Klasse schreiben, falls dir die Collections zu langsam sind.

[Xmas]

Hallo Leute,

ich habe das folgendes Problem:

Ich habe meine Matrix und Vektor Bibliothek für Sparse-Matrizen, welche in Delphi geschrieben sind, nach C# übersetzt. Nachdem diese in C# fertig waren wunderte ich mich darüber, dass das ganze in C# deutlich langsamer ist als in Delphi (Faktor 5)! Einen Performancetest mit Prof-It, zeigten mir, dass die Aufrufe von Methoden aus der ArrayList Klasse extrem viel Zeit in Anspruch nehmen (Delphi ist mit seinen Aufrufen in TList ziemlich flott)! Meine Frage an euch wäre, was könnte ich machen, um den Bottleneck einigermaßen vernünftig zu schließen?

Für Anregungen wäre ich euch dankbar..
Welche Methoden brauchen konkret am meisten Zeit, welche verwendest du besonders häufig, welche Zugriffsmuster sind üblich?

[pajofego]

Nimm lieber Java. Das wurde von kompetenten Leuten implementiert.
:rolleyes: mmmh...kann ich nicht beurteilen...aber bevor ich mich auf eine neue IDE und neue Sprache - auch wenn C# Java sehr ähnlich ist - bleibe ich lieber bei Delphi... :)

Für welchen Zweg brauchst du den die ArrayList genau wenn ich fragen darf?

Die ArrayList verwaltet einen sehr einfachen Datentpypen Cell

public struct Cell
{
public int Col, Row;
public double Value;
}


Das ganze dient dazu, nur Werte die ungleich NULL sind abzulegen! D.h. es wird jedesmal ein Eintrag vom Typ Cell in die ArrayList gemacht mit der entsprechenden Position in einem Vektor (Row=1) bzw. in einer Matrix!

Es könnte aber auch an der Fliesspunkt Leistung liegen. Da ist der Jitter der aktuellen .Net Version noch nicht sehr gut.

Meine Tests bestanden lediglich aus dem Befüllen und auslesen der Einträge aus den Vektoren bzw. Matrizen


Naja ArrayLists haben keine indizierung und sehr viel Overhead weil sie für alles benutzt werden können.

haha interessant...das macht sie ja aber so atraktiv für mein Problem :-)

Versuch mal ne Hashtable(value, index key), sollte wesentlich schneller sein, falls das für dich in Frage kommt.

Prinzipiell schon, nur fehlt mir die Methode Insert(int index, object value) in der Klasse ggf. müsste ich sie selbst nachbauen, aber dann wäre ich doch wieder bei ArrayList oder?

Welche Methoden brauchen konkret am meisten Zeit, welche verwendest du besonders häufig, welche Zugriffsmuster sind üblich?


Den größten Bottleneck hat eindeutig die Methode Insert() aus der ArrayList Klasse...am häufigsten werden die Index-Eigenschaften von ArrayList aufgerufen...diese verbraten aber lange nicht so viel Zeit wie die o.g. Methode Insert().

Danke,

Gruß

pajofego

[Xmas]

Die ArrayList verwaltet einen sehr einfachen Datentpypen Cell

public struct Cell
{
public int Col, Row;
public double Value;
}

Probier mal bitte class statt struct. Ich glaube das ist eher was du willst, wenn du von Delphi/TList ausgehst.
Die Verwendung von .Capacity sollte bei beiden ja eigentlich gleich sein.

[pajofego]

Probier mal bitte class statt struct. Ich glaube das ist eher was du willst, wenn du von Delphi/TList ausgehst.
Die Verwendung von .Capacity sollte bei beiden ja eigentlich gleich sein.

Hatte ich auch so schon in meiner Anfangsversion...war aber auch nicht schneller als mit einem struct!

[Trap]

Ohne Code oder zumindest Zugriffsmuster ist das alles blindes rumraten. Entweder du sagst konkret was du mit ArrayList machst, dann kann man dir helfen, oder du sagst es nicht, dann kann man nur raten.

[pajofego]

Ohne Code oder zumindest Zugriffsmuster ist das alles blindes rumraten. Entweder du sagst konkret was du mit ArrayList machst, dann kann man dir helfen, oder du sagst es nicht, dann kann man nur raten.

äh, ich personlich habe kein Problem den Code hier zu veröffentlichen...ist eigentlich auch nich wirklich viel! Nur ich habe den Delphi Code vor ca. 5 Jahren von jedem via PN aus einem englischsprachingen Forum exclusiv bekommen...das dumme ist, da war nie ein Copyright drauf und ich habe jetzt auch nicht die e-mail Adresse geschweige den Name von dem Ur-Autor :confused:

Deswegen meine Bedenke hier alles zu veröffentlichen...könnten wir das irgendwie etwas einschränken? Evt. schicke ich das euch via Mail? Ginge das? Oder habt ihr andere Vorschläge?

Gruß

pajofego

[Trap]

Ich hab kein Delphi installiert, mich würde sowieso nur der C#-Code interessieren. Kannst du nicht einfach den Teil reinstellen, den du gebencht hast? Muss nichtmal compilierbar sein, es reicht völlig wenn erkennbar ist was passiert.

Ansonsten kannst du es auch gern per mail schicken.

[Trap]

Hast du im Delphicode genau den gleichen Code laufen lassen?

Du füllst deine Matrix im Benchmark in einer ungünstigen Reihenfolge. Deine Matrix ist zeilenorientiert, aber du füllst die Spalten der Reihe nach. Ist das im Delphibench genauso? Wenn nicht kann das sicher die Ursache sein, hab es noch nicht ausprobiert...

Außerdem hast du selbst eine binäre Suche implementiert anstatt .binarySearch von Arraylist zu benutzten, keine gute Idee normalerweise.

[Trap]

Grundsätzlich würde ich eine andere Datenstruktur wählen, eine std::map(std::pair<int,int>,double> in C++. Aber die gibt es in .NET nicht und außerdem ist das kein Grund dafür dass es 5 mal langsamer in .NET läuft.

Außer der binären Suche ist nix drin was ich als falsch sehen würde und die verbraucht nur einen kleinen Teil der Zeit. Die Zugriffsreihenfolge macht viel weniger aus als ich gedacht hab, nämlich fast garnichts.

Fazit: .NET ist da einfach langsamer als Delphi

[pajofego]

mmmh! Danke für deine Mühen! Ich wollte eigentlich für meine zukünftigen Projekte C# und VS nehmen...aber die Performanceeinbußen sind einfach zu hoch.

Zwar gibt es für .NET eine effiziente Bibliothek, die Sparse Matrizen verwaltet (NMath Matrix CenterSpace), aber die ist mir ehrlich gesagt viel zu teuer...da würde ich lieber beim guten alten Delphi bleiben!

Gruß

pajofego

[Shink]

Jetzt weisst Du, warum ich mich mit Fortran 95 herumplage.
Für Java gäb es ja Sachen wie MTJ, dass man sogar mit nativem LAPACK verwenden kann. Ist es nicht möglich, Java-Klassen in die .NET-CLI (oder wie das heisst) zu übersetzen oder geht dass nicht, wenn man JNI-Aufrufe dabeihat?

[pajofego]

Jetzt weisst Du, warum ich mich mit Fortran 95 herumplage.
Für Java gäb es ja Sachen wie MTJ, dass man sogar mit nativem LAPACK verwenden kann. Ist es nicht möglich, Java-Klassen in die .NET-CLI (oder wie das heisst) zu übersetzen oder geht dass nicht, wenn man JNI-Aufrufe dabeihat?

Ooooooh Fortran!!! So eine Kacksprache...Ich habe mich an der Uni strickt gegen Fortran geweigert...jedesmal wenn's hieß ich soll dann mal in Fortran coden, habe ich dankend abgelehnt! Das schlimme daran, finde ich, gar nicht mal so sehr die Sprach...die könnte man notfalls noch über sich ergehen lassen...sondern der Umstand, dass man das ganze Zeug in eine Art Notepad programmiert! Auf meine Nachfrage ob's einen Debugger gibt, gabs als Antwort, dass man alles per Output auf die Shell ausgeben kann :eek: ...und das in den heutigen Zeiten mit diesem geilen VS Debugger!

BTW: Für was steht MTJ? Hab dazu nichts im Netz gefunden?

Gruß

pajofego

[Shink]

MTJ = Matrix Toolkit for Java: http://www.math.uib.no/~bjornoh/mtj/
Enthält u.a. SMT (Sparse Matrix Toolkit). Hab ich selbst keine Erfahrung damit, aber sollte eigentlich schneller sein als was selbst gebasteltes.
Zu Fortran: Gerade im Bereich Matrizen/Numbercrunching finde ich, die Sprache hat (v.a. seit Version 95) ein paar nette Befehle. Wegen Notepad Programmierung: Uhm... keine Ahnung was du damit meinst. IDE in dem Sinn von Borland oder Microsoft-IDEs kenn ich keine, geben wirds wohl welche (Netbeans vermutlich?), aber es gibt ja auch ein paar nette Editoren wie z.B. JEdit. Zu Debugging: Bei GNU Fortran ist natürlich der gdb dabei.

[Trap]

Hab was gefunden, warum der Code so lahm ist:
Boxing Issues

If you use a collection such as an ArrayList to store value types such as integer or float, every item is boxed (a reference type is created and the value copied) when it is added to the collection. If you are adding many items to the collection, the overhead can be excessive. The problem is illustrated by the following code snippet.

ArrayList al = new ArrayList();
for (int i=0; i<1000;i++)
al.Add(i); //Implicitly boxed because Add() takes an object
int f = (int)al[0]; // The element is unboxed

To prevent this problem, consider using an array instead, or creating a custom collection class for your specific value type.

Note The .NET Framework 2.0, at the time of this writing, introduces generics to the C# language which will avoid the boxing and unboxing overhead.

[pajofego]

Hab was gefunden, warum der Code so lahm ist:

Coooool, danke, dass du dich noch daran erinnerst...hatte selbst schon die Idee das ganze in ein Array zu packen...war mir aber nicht ganz sicher ob sich wirklich lohnt... :rolleyes:

Das werde ich wohl einmal demnächst ausprobieren... :)

Gruß

Paulo

[Trap]

Würde ich nicht probieren, bald kommt .NET 2.0 , da lohnt es nichtmehr 1.1 Performancetests zu machen...

[Shink]

Nun ja, ich würd mal sagen, ein Array dürfte generell die schnellere Lösung sein, wenn Du die Vorteile einer Liste nicht benötigst.

[pajofego]

Würde ich nicht probieren, bald kommt .NET 2.0 , da lohnt es nichtmehr 1.1 Performancetests zu machen...

Ich habe meinen Code unter .NET 1.1 und .NET 2.0 laufen lassen...das war zwar dann schneller als unter .NET 1.1, aber im Vergleich zu Delphi immer noch ziemlich langsam...

Da ich, ganz gerne weiterhin ArrayList verwende möchte und das Boxing und Typumwandlung Zeit kostet...wäre mein nächster Gedanke meine eigene Custom ArrayList zu schreiben, d.h. eine, die nicht von .NETs ArrayList erbt, sondern von neu auf meine eigene, die anstatt object verwaltet, meine o.g. struktur Cell... Add(Cell value)!

Das müsste (sollte, wenn ich das vernünftig hinbekomme) doch jetzt schneller gehen, oder?

Gruß

pajofego

[-xenonite-]

ich glaube das Boxing/Unboxing kostet nur viel Zeit, wenn man keinen Referenzdatentyp speichert, also z.B. int. Deine Cell-Objekte sind eh schon Referenzen.
Besser wäre es wohl, entweder generics zu verwenden oder aber alles in "kleinen" Variablen zu speichern, also int, long etc. und dafür ne eigene Liste schreiben.
Wenn es irgendwie geht nimm ein Array.