DoubleSource - Duplikate im Source finden v0.4.1

[Motzi]

Hi,

erstmal vorweg - ich weiß, dass es so ein Programm vor kurzem schonmal hier gab (DupeChecker). Tatsächlich hat mich dieses Programm sogar dazu inspiriert meine eigene Version zu schreiben, da ich in einigen Punkten nicht ganz glücklich damit war (siehe dazu mein Posting im Thread zu dem Programm).
Ich habe daher beschlossen mein eigenes Programm zu schreiben und versucht die von mir kritisierten Punkte zu verbessern.

Features:

• Sehr schnelle Duplikatssuche
• Kommentare werden vor dem Vergleichen entfernt -> unterschiedliche Kommentare in identischen Codeblöcken spielen keine Rolle mehr; auskommentierter Code wird nicht als Duplikat erkannt
• "Überflüssige" Leerzeichen werden vor dem Vergleichen ebenfalls entfernt (aus "i : integer ;" wird "i:integer;") -> Unterschiede in der Formatierung werden ignoriert
• Übersichtliche Aufbereitung der Ergebnisse in einem Treeview

Anmerkung: Treeview Einträge die kursiv sind sind "Subduplikate", sie sind also ein Teil eines größeren Duplikats. Diese werden nur dann angezeigt, wenn sie identisch mit anderen gefundenen Dupliakten sind, die selbst keine Subdupliakte sind.

v0.4.1

• Speicherverbrauch wurde drastisch gesenkt
• Geschwindigkeit wurde um das 4-5 fache gesteigert
• Rekursive Suche in Unterordnern kann optional deaktiviert werden
• Comboboxen wurden durch "erweiterte" Versionen ersetzt
• Es wird nun überall der volle Pfad als Hint angezeigt

v0.3.1

• Analyse findet nun in einem eigenen Thread statt und kann abgebrochen werden
• Geschwindigkeit wurde nochmals gesteigert
• Speicherverbrauch wurde deutlich reduziert
• Splitter-Problem beseitigt
• Die Schriftart des Treeview wurde auf Verdana umgestellt - damit gibt es keine Probleme mit den kursiven Zahlen mehr.

v0.2.2

• Es gibt jetzt eine SettingsForm - die Einstellungen werden in einer ini-Datei und einer txt-Datei gespeichert (siehe weiter unten)
• Alle Sources eines Duplikats können nun in einem eigenen Fenster direkt verglichen werden
• Sowohl im "Compare-Fenster" als auch in der MainForm werden die Duplikate im Source durch eine eigene Hintergrundfarbe gekennzeichnet
• Duplikate die nur aus Keywords bestehen können ignoriert werden
• Geschwindigkeit wurde um das bis zu 4-fache beschleunigt

Folgende Einstellungen sind möglich:

• Minimale Zeilenanzahl
• Extensions der Files die beim Durchsuchen von Ordnern berücksichtigt werden sollen
• Ignorieren von Duplikaten die nur aus Keywords bestehen
• Es sollen nur Zeilen gezählt werden die nicht nur aus einem Keyword bestehen (betrifft minimale Zeilenanzahl)
• Liste der Keywords die ignoriert werden sollen - betrifft die beiden obigen Einstellungen (diese List wird in keywords.txt gespeichert)

v0.1.2

• Das Programm kann jetzt auch für ganze Ordner angewendet werden. Dabei werden alle pas und dpr Files aus dem gewählten Ordner und allen Unterordnern zur Duplikatssuche herangezogen.
• Die Duplikatsanzeige wurde korrigiert, es sollten jetzt immer die korrekten Zeilen angezeigt werden
• Das Ergebnis kann nach Files gefiltert werden, dabei werden nur jene Duplikate angezeigt die in dem ausgewählten File vorkommen. Wenn zusätzlich noch "strict" aktiviert ist werden alle Sources aus anderen Files ebenfalls ausgeblendet.
• Optional kann nun das gesamte File im Edit angezeigt werden, das Duplikat wird dabei markiert.
• Während der Duplikatssuche wird jetzt ein Dialog mit Progressbar angezeigt. Im Moment verwende ich noch Application.ProcessMessages damit das UI upgedatet wird was sich natürlich auf die Laufzeit auswirkt. In Zukunft wird das per Multithreading gelöst.

TODO:

• Einstellungsmöglichkeiten - Kommentare beim Preprocessing entfernen, Compiler-Schalter als Kommentar behandeln, ...
• Subduplikate mit "Eltern"-Duplikat verknüpfen
• Eventuell noch bessere Anpassung während des preprocessing um unterschiedliche Formatierungen noch besser auszugleichen
• ...

Gruß, Motzi

[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

[Union]

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 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 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 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