DoubleSource - Duplikate im Source finden v0.4.1

[toms]

Hallo Motzi

Einige Anmerkungen:

1. Kursive Zahlen werden z.T abgeschnitten (Siehe Bild)

2. Der Focus sollte im Progress Fenster auf dem Button sein.
So kann das Fenster mit Enter resp. per Leertaste direkt geschlossen werden.
Es stellt sich die Frage, ob ein Progress Fenster überhaupt nötig ist.
Eine Progressbar würde es doch auch tun.

3. Verwendest du einen Splitter zwischen SynEdit und VST? Dieser funktioniert nicht
richtig.

4. Mögliche Erweiterung: Bei Rechtsklick auf eine Unit im VST ein Kontextmenü anzeigen
mit der Möglichkeit, die Unit (in Delphi, Editor) zu öffnen.


Ansonsten :thumb:

[Union]

Zitat:

Zitat von Motzi

Hab gerade einen Hardcore-Test gemacht:
Files: 947
Original lines: 292.041
Preprocessed lines: 152.783
Comparisons: 665.512.367
Duplicates: 544
Duplicates sources: 1675
Time: 52.250ms

Hallo Motzi,

die neue Version ist schick, auch der Optionendialog gefällt mir sehr. Allerdings habe ich einen "Extrem" Hardcore-Test gemacht, woraufhin ich den Rechner neu starten musste (per Hardware!).

Der Hauptspeicherbedarf ging auf fast 400 MB und dann kam Out of Memory. Vorher kam eine Meldung "Creating datastructures" für mehrere Minuten, dann fing er an zu analysieren, aber nur bis ca. 10% des Progressbars.

Dateien: 5.260
Zeilen: 4.956.663

[Motzi]

Wow.. ok, so einen Hardcore-Test hab ich noch nicht gemacht! Es wundert mich aber auch nicht wirklich, dass da dann irgendwann der Speicher ausgeht! Pro "preprocessed line" wird ein 48-Byte großes Objekt erzeugt, und außerdem noch eine sortierte Liste ohne Duplikate in die alle Zeilen eingefügt werden und über die verkettete Listen erstellt werden (die TPreprocessedLine Instanzen werden untereinander verknüpft).
Und pro gefundenes Duplikat werden dann noch mal 1-2 TDuplicateSource Instanzen erzeugt (ebenfalls 48 Bytes groß) und eventuell auch noch eine TDuplicate Instanz (24 Bytes groß). Noch nicht berücksichtigt sind dabei diverse Listen die die Instanz-Zeiger enthalten und natürlich auch nicht die Strings (sowohl Original code als auch preprocessed code)...

Schafft es dein Programm diese Datenmengen zu bewältigen?

[Union]

Zitat:

Pro "preprocessed line" wird ein 48-Byte großes Objekt erzeugt, und außerdem noch eine sortierte Liste ohne Duplikate in die alle Zeilen eingefügt werden und über die verkettete Listen erstellt werden

Bei mir sind das 38-58 Byte, ich habe das mit einem Pointer-Array gemacht (18 Byte) und einer sortierten Liste die das Pointer-Array indiziert (20 Byte). Dann kommt noch eine nicht näher definierbare sortierte Hashliste dazu, die wiederum die Startposition eines Hashblocks indiziert (auch 20 Byte, Anzahl der Einträge ist abhängig von der Anzahl der unterscheidlichen Hashes).

Zitat:

Und pro gefundenes Duplikat werden dann noch mal 1-2 TDuplicateSource Instanzen erzeugt (ebenfalls 48 Bytes groß) und eventuell auch noch eine TDuplicate Instanz (24 Bytes groß).

Ich lege die Duplikate in Paaren ab (2 x (24 byte + String(DateiName)).

Zitat:

Noch nicht berücksichtigt sind dabei diverse Listen die die Instanz-Zeiger enthalten und natürlich auch nicht die Strings (sowohl Original code als auch preprocessed code)...

Den Sourcecode und den preprocesseden Code werfe ich nach dem Einlesen der Files weg. Wenn ich den anzeigen muss, mache ich das durch erneuten Zugriff auf die Dateien.

Zitat:

Schafft es dein Programm diese Datenmengen zu bewältigen?

In der Version die ich jetzt gerade am Testen bin, ja. Vorher gab es auch EOutOfMemory. Dieser Test ist aber auch wirklich schon hart an der Grenze: Er umfasst die komplette Program files\Borland Struktur, mit D7, D2006 und allen möglichen Fremdkomponenten drin. Aber es dauert dann auch ziemlich lange (47 Mrd. Vergleiche):

Code:

Files     Zeilen Duplikate Vergleiche      Dauer sek. Minuten  Vergleiche/Sek.
5.260   4.956.663   39167   47.218.981.168  6803,02   113,38   6.940.885,25

Wie berechnest Du eigentlich die Laufzeit? Ich habe den Eindruck, es ist nur die Analyse Zeit. Bei mir fängt die Zählung an, sobald der User "Start" gedrückt hat.

[Motzi]

Zitat:

Zitat von Union

Zitat:

Pro "preprocessed line" wird ein 48-Byte großes Objekt erzeugt, und außerdem noch eine sortierte Liste ohne Duplikate in die alle Zeilen eingefügt werden und über die verkettete Listen erstellt werden

Bei mir sind das 38-58 Byte, ich habe das mit einem Pointer-Array gemacht (18 Byte) und einer sortierten Liste die das Pointer-Array indiziert (20 Byte). Dann kommt noch eine nicht näher definierbare sortierte Hashliste dazu, die wiederum die Startposition eines Hashblocks indiziert (auch 20 Byte, Anzahl der Einträge ist abhängig von der Anzahl der unterscheidlichen Hashes).

Zitat:

Und pro gefundenes Duplikat werden dann noch mal 1-2 TDuplicateSource Instanzen erzeugt (ebenfalls 48 Bytes groß) und eventuell auch noch eine TDuplicate Instanz (24 Bytes groß).

Ich lege die Duplikate in Paaren ab (2 x (24 byte + String(DateiName)).

Ja, wir haben unterschiedliche Systeme mit Duplikaten umzugehen. Ich hab zwei verschiedene Klassen: TDuplicate und TDuplicateSource, wobei ein Duplikat mehrere Sources haben kann. Wenn ein Duplikat gefunden wurde, dann wird geschaut ob es bereits eine TDuplicate-Instanz mit demselben preprocessed code gibt, ansonsten wird eine neue Instanz erzeugt.

Zitat:

Zitat:

Noch nicht berücksichtigt sind dabei diverse Listen die die Instanz-Zeiger enthalten und natürlich auch nicht die Strings (sowohl Original code als auch preprocessed code)...

Den Sourcecode und den preprocesseden Code werfe ich nach dem Einlesen der Files weg. Wenn ich den anzeigen muss, mache ich das durch erneuten Zugriff auf die Dateien.

Das wollte ich eigentlich vermeiden, wäre aber natürlich eine Möglichkeit..

Zitat:

Zitat:

Schafft es dein Programm diese Datenmengen zu bewältigen?

In der Version die ich jetzt gerade am Testen bin, ja. Vorher gab es auch EOutOfMemory. Dieser Test ist aber auch wirklich schon hart an der Grenze: Er umfasst die komplette Program files\Borland Struktur, mit D7, D2006 und allen möglichen Fremdkomponenten drin. Aber es dauert dann auch ziemlich lange (47 Mrd. Vergleiche):

Code:

Files     Zeilen Duplikate Vergleiche      Dauer sek. Minuten  Vergleiche/Sek.
5.260   4.956.663   39167   47.218.981.168  6803,02   113,38   6.940.885,25

Nicht schlecht! Mal schaun ob ich eine Möglichkeit finde den Speicherbedarf ein wenig zu senken..

Zitat:

Wie berechnest Du eigentlich die Laufzeit? Ich habe den Eindruck, es ist nur die Analyse Zeit. Bei mir fängt die Zählung an, sobald der User "Start" gedrückt hat.

Die ProgressBar wird im Moment aber nur für Analyse benutzt, es wird aber die gesamte Zeit genommen - Startzeit = vor dem Einlesen der Dateien, Endzeit = nach dem finalisieren der Ergebnisse (es ist nur eine ganz simple Messung per GetTickCount).

Gruß, Motzi

[Motzi]

Eine neue Version mit einigen kleinen Änderungen ist online - siehe erstes Posting!

[Union]

Super, das ist ja jetzt 3 Mal so schnell wie vorher. Allerdings ist die Anzahl der Duplikate knapp 3 Mal so groß wie bei der vorherigen Version, bei den gleichen Testfiles.

Was mir noch fehlt ist eine Pfadanzeige der Dateien. Da Du ja standardmäßig alle Unterverzeichnisse durchsuchst, findet man die Dateien sonst schwer.

Bei der Anzeige der Sourcen nebeneinander wird beim Öffnen des Fensters nichst angezeigt (Comboboxen sind nicht vorbelegt). Dort sollten dann vielleicht die ersten beiden Duplikate voreingestellt sein. Oder Du läßt in dem VST eine Mehrfachauswahl der Duplikate zu und zeigst dann die selektierten an.

[Motzi]

Zitat:

Zitat von Union

Super, das ist ja jetzt 3 Mal so schnell wie vorher.

Danke, deine letzte Version ist aber auch echt nicht schlecht! :) Einen nicht zu verachtenden Teil dieser Geschwindigkeitssteigerung macht der Thread, da jetzt keine ständigen Application.ProcessMessages Aufrufe mehr notwendig sind! Auf diese Weise könntest du sicher auch noch einiges rausholen.

Zitat:

Allerdings ist die Anzahl der Duplikate knapp 3 Mal so groß wie bei der vorherigen Version, bei den gleichen Testfiles.

Wie meinst du das? Bei meinen Tests haben die neue und die alte Version die komplett gleichen Ergebnisse geliefert (außer bei den Comparisons - die fallen bei der neuen Version durch ein paar Optimierungen niedriger aus).

Zitat:

Was mir noch fehlt ist eine Pfadanzeige der Dateien. Da Du ja standardmäßig alle Unterverzeichnisse durchsuchst, findet man die Dateien sonst schwer.

Ja, nur weiß ich noch nicht wie bzw. wo, da die Pfade ja auch recht lang ausfallen können...

Zitat:

Bei der Anzeige der Sourcen nebeneinander wird beim Öffnen des Fensters nichst angezeigt (Comboboxen sind nicht vorbelegt). Dort sollten dann vielleicht die ersten beiden Duplikate voreingestellt sein. Oder Du läßt in dem VST eine Mehrfachauswahl der Duplikate zu und zeigst dann die selektierten an.

Ja, sowas in der Richtung hab ich mir auch schon gedacht und werd ich wohl in einer der nächsten Versionen einbauen.

Gruß, Motzi

[Union]

Ich habe heute Nacht nochmal den Monstertest gefahren. Diesmal wurde er zwar fertig, hat aber mit 1,7 GB Hauptspeicherverbrauch meinen Virenscanner Service zum Absturz gebracht. Die "Fertig" Meldung mit Anzahl und Dauer kam noch, aber dann auch Out of Memory.

Code:

Dateien Zeilen    Duplikate Vergleiche     Dauer    Minuten Vergleiche/Sek. 
5.260   4.952.663 N/A       20.142.551.061 3.084,94 51,42   6.529.316,96

Du solltest Dir mal anschauen, wie Du den Speicher anforderst. Teilweise merkt man das richtig, dass er in Intervallen realloziert und anhält.

Wegen des Threads hatte ich mir auch schon überlegt. Man kann ja auch Update statt Prozessmessages einsetzen. Und ob das so viel bringt, weil man ja ständig synchronize für die VCL-Zugriffe aufrufen muss? Aber ich hatte eine andere Idee, nämlich die Analyse selber in mehreren Threads parallel laufen zu lassen, die sich die Arbeit teilen (z.B. 5 Threads, jeder nimmt sich 25% der Dateien nach der Vorbereitung).

[Motzi]

Zitat:

Zitat von Union

Du solltest Dir mal anschauen, wie Du den Speicher anforderst. Teilweise merkt man das richtig, dass er in Intervallen realloziert und anhält.

Ich alloziere den Speicher nicht direkt, sondern erzeuge einfach nur Instanzen von Objekten - den Rest überlass ich dem Delphi MemoryManager. Ich könnte mir aber überlegen ob es sinnvoll wäre gleich ganze Objekt-Pools anzulegen...

Zitat:

Wegen des Threads hatte ich mir auch schon überlegt. Man kann ja auch Update statt Prozessmessages einsetzen. Und ob das so viel bringt, weil man ja ständig synchronize für die VCL-Zugriffe aufrufen muss? Aber ich hatte eine andere Idee, nämlich die Analyse selber in mehreren Threads parallel laufen zu lassen, die sich die Arbeit teilen (z.B. 5 Threads, jeder nimmt sich 25% der Dateien nach der Vorbereitung).

Nein, nur "Update" funktioniert auch nicht, da dann zB der Cancel-Button nicht mehr gedrückt werden kann. Und ich verwende kein Synchronize! ;) Ich schicke stattdessen per PostMessage Nachrichten an das Fenster - so wird der Thread nicht unnötig lange blockiert.
Mehrere Threads zu Erzeugen die sich die Arbeit teilen wäre natürlich eine Idee, fragt sich nur ob das wirklich viel bringt und den ganzen Aufwand rechtfertigt.

Gruß, Motzi