Hashfunktion

Proggen.org - Lernprojekt: Duplikatefinder
Benutzeravatar
Bebu
Beiträge: 562
Registriert: Mi Okt 21, 2009 6:19 pm
Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!

Re: Hashfunktion

Beitrag von Bebu » Fr Jul 15, 2011 9:49 am

cloidnerux hat geschrieben:
So, ich habe heute die aktuelle Branch Version in den Trunk integriert, vielen Dank an cloidnerux für die neue Funktion um die FileStreams verarbeiten zu können. Hat zwar drei Monate gedauert, aber ich habe jetzt auch mal ein bisschen rumgetestet und habe gleich eine Bug für unseren Hashexperten: http://www.bugs.proggen.org/show_bug.cgi?id=9
Mhmm, is mir nicht aufgefallen, hauptsächlich weil ich kein 20Gb Dateien gehasht habe^^
Wird alsbald abgearbeitet^^

p.s: Problem gelöst und das mit nur 8 Zeilen Änderung.
Anscheinend hat aber niemand den Code wirklich validiert oder ich weiß grad selber nicht mehr was ich da geschrieben habe, auf jeden fall waren da ein paar merkwürdige sachen dabei...

p.p.s: Ist nun hochgeladen, bisher aber noch im Falschen Ordner weil mir AnkhSVN ieinen Streich spielen wollte.
Korrigiere ich gleich.
So, ich habe mir das jetzt nur in der Commit Mail angesehen und komme zu dem Schluss, dass mir das was komisch vorkommt ^^
Womit hast du das Kompiliert? So wie der Code da drinnen steht, wird sich mein Kompiler beschweren, oder kompiliert deiner for schleifen, bei denen die Bedingungen mit Komma statt Semikolon getrennt sind? Ich werde trotzdem mal versuchen das ganze in Trunk zu integrieren, aber da sind so ziemlich die selben Fehler enthalten, die mich gestern eine Stunde Suche gekostet haben, damit der Code überhaupt kompiliert hat. Entweder ist der aktuelle GCC extrem lästig, oder dein Kompiler erlaubt Dinge, die nicht erlaubt sind ;)

Ich hege nebenbei die Idee, die Datei jeweils in Blocks einzulesen. Die Blockgröße würde ich folgendermaßen gestalten: 1/3 des vorhanden Arbeitsspeichers geteilt durch die Anzahl der Threads, die für jeden Block den Hash berechnen. Anschließend die Teilhashs zusammenfügen und ausgeben. Das sollte auf einem Mulitcore die Geschwindigkeit bei großen Dateien doch sehr erhöhen. Hab ich was übersehen?
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Fr Jul 15, 2011 10:07 am

Hab ich was übersehen?
Du nicht aber ich. Der Fehler stammt noch von der FileStream integration, da konnte ich es nicht testen weil ich keinen Compilierbaren code des Filestreams hatte, welchen ich gestern auch nicht compilieren konnte.
Ich Bearbeite das ganze nochmal und lade es dann Final in meinen Branch, dann kannst du es nutzen.
Die Blockgröße würde ich folgendermaßen gestalten: 1/3 des vorhanden Arbeitsspeichers geteilt durch die Anzahl der Threads, die für jeden Block den Hash berechnen
Viel zu Aufwendig, du müsstest dann über spezifische Betriebssystemfunktionen die Größe des RAMs auslesen, die aktuelle Auslastung, dann muss immer die Zahl der Threads übergeben werden. Dann ist es so, das der Hash stark von der Reinfolge der Daten abhängt, sprich wenn du "AABB" hashst bekommst du ein anderes Ergebnis als wenn du erst "AA" und "BB" hashst und dann das ganze zusammen.
Ich habe eine andere Lösung, die immer nur 100MB Daten ließt, diese Hasht und dann die nächsten 100MB läd.
Wenn du einen Multicore auslasten willst, hashe mehrere Dateien parallel. Das könnte entweder ich in der Hashklasse Implementieren, da ich ja den FileStream bekomme, oder du regelst das.

Ich sehe, da ist überarbeitungsbedarf am code. Wird wahrscheinlich noch ne Stunde dauern.

MfG cloidnerux.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

Re: Hashfunktion

Beitrag von fat-lobyte » Fr Jul 15, 2011 10:09 am

Bebu hat geschrieben:Ich hege nebenbei die Idee, die Datei jeweils in Blocks einzulesen. Die Blockgröße würde ich folgendermaßen gestalten: 1/3 des vorhanden Arbeitsspeichers geteilt durch die Anzahl der Threads, die für jeden Block den Hash berechnen. Anschließend die Teilhashs zusammenfügen und ausgeben. Das sollte auf einem Mulitcore die Geschwindigkeit bei großen Dateien doch sehr erhöhen. Hab ich was übersehen?
a) Wie hast du vor die Größe des "vorhandenen Arbeitsspeichers" auszulesen?
b) Ich kenn die Hash algorithmen nicht, aber ist es normalerweise nicht so dass die Hashfunktionen nicht nur den jeweiligen blöcken operieren, sondern auch auf dem Ergebnis des vorangehenden Blockes? Somit hättest du eine sequenzielle Abhängigkeit drinnen, das macht paralellisierung unmöglich
c) Was aber möglich ist, einfach 2 oder mehr dateien gleichzeitig zu hashen. Das aufwändigste läuft paralell, nur das eintragen des Ergebnisses muss synchronisiert werden.
d) Kuck dir unter Unix fürs "einlesen" der Datei mal die Funktion mmap (3) an. Ich glaube es ist effektiver einfach eine Datei in den Speicher zu mappen und die details dem Kernel zu überlassen als selbst speicher anzufordern und die Dateien mit fread() Blockweise zu kopieren.
Haters gonna hate, potatoes gonna potate.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Fr Jul 15, 2011 10:18 am

d) Kuck dir unter Unix fürs "einlesen" der Datei mal die Funktion mmap (3) an. Ich glaube es ist effektiver einfach eine Datei in den Speicher zu mappen und die details dem Kernel zu überlassen als selbst speicher anzufordern und die Dateien mit fread() Blockweise zu kopieren.
Mache ich, obwohl ich nur ungerne Plattform spezifischen code schreiben möchte, da ich diesen dann Aufwendiger Testen müsste^^(Wäre aber kein Problem)
) Ich kenn die Hash algorithmen nicht, aber ist es normalerweise nicht so dass die Hashfunktionen nicht nur den jeweiligen blöcken operieren, sondern auch auf dem Ergebnis des vorangehenden Blockes? Somit hättest du eine sequenzielle Abhängigkeit drinnen, das macht paralellisierung unmöglich
Das hashen ist nur ein XOR und eine Multiplikation:

Code: Alles auswählen

Ausgangsdaten = (Ausgangsdaten ^NächsteDaten) * Magic
Aber es macht einen Unterschied wenn man die Reinfolge der Daten ändert, bzw Blöcke hasht und dann zusammenfasst. Im schlimmsten Fall gäbe es Unstimmigkeiten bei gleichen Dateien, weil gerade der RAM anders ausgelastet war und damit die Pakete Kleiner ausfielen.
c) Was aber möglich ist, einfach 2 oder mehr dateien gleichzeitig zu hashen. Das aufwändigste läuft paralell, nur das eintragen des Ergebnisses muss synchronisiert werden.
Muss nicht. Die Klasse ist egt nur eine Zusammenfassung der Funktionen und des 32/64-Bit hashes. Die Funktion bei der es Interessant wird, ist die Memberfunktion die einen Filestream bekommt und so mehrere hashes auf einmal Generieren kann. Ich könnte dann jedem Thread eine referenz auf das entsprechende FileInfo Objekt mitgeben, wo er dann den hash reinschreiben kann und wenn der Thread geendet hat, kommt der nächste.

Edit: So neue Version ist in meinem Branch. Die sollte Funktionieren, ich konnte sie aber noch nicht testen weil ich wie gesagt noch keine Compilierbaren Sourcen von Dedupe habe, denn die die ich habe, produzieren mir Fehler.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

Re: Hashfunktion

Beitrag von fat-lobyte » Fr Jul 15, 2011 10:40 am

cloidnerux hat geschrieben:obwohl ich nur ungerne Plattform spezifischen code schreiben möchte, da ich diesen dann Aufwendiger Testen müsste^^(Wäre aber kein Problem)
War mir früher auch unangenehm, hab jetzt aber jegliche Scham über Bord geworfen :-) Wenns effektiv und plattformunabhängig geht gerne, wenns spezifisch aber effektiver ist kein Problem.
AAABBER: Mach dir keinen Kopf drum. Das ist ne optimierung. Erstmal funktionalität fertigstellen, und dann optimieren :-)
Das hashen ist nur ein XOR und eine Multiplikation:

Code: Alles auswählen

Ausgangsdaten = (Ausgangsdaten ^NächsteDaten) * Magic
Aber es macht einen Unterschied wenn man die Reinfolge der Daten ändert, bzw Blöcke hasht und dann zusammenfasst.
Genau das meinte ich: der Hash der NächstenDaten ist von den Ausgangsdaten abhängig => Paralellisieren unmöglich.
Edit: So neue Version ist in meinem Branch. Die sollte Funktionieren, ich konnte sie aber noch nicht testen weil ich wie gesagt noch keine Compilierbaren Sourcen von Dedupe habe, denn die die ich habe, produzieren mir Fehler.
Hm... Was kompilierbares wär schon Toll. Mal so ganz allgemein :-)
Haters gonna hate, potatoes gonna potate.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Fr Jul 15, 2011 10:45 am

Hm... Was kompilierbares wär schon Toll. Mal so ganz allgemein
Finde ich auch^^
Aber ich weiß nicht genau woran es liegt, Visual Studio meckert mir an das ein enum in der Klasse neudefiniert wurde und dann noch 50 Fehler, also habe ich mir irgendeinen Code geholt, der so nicht Funktioniert.
Ich muss nochmal testen alles aus Trunk zu auszuchecken und Cmake drüber laufen zu lassen, welches mir aber im Moment noch Ankreidet das ich kein ncurses habe.

Edit:
Genau das meinte ich: der Hash der NächstenDaten ist von den Ausgangsdaten abhängig => Paralellisieren unmöglich
Parallelisierung schon möglich, es muss nur sichergestellt sein, das die Gleichen Daten immer auf die Selbe art und weise gehashst werden. Das heißt, aus mehreren Einzelpaketen die hashes zu generieren und diese am Ende dann zusammenhashen wäre möglich, nur muss dann Wirklich sichergestellt werden, das die selben Daten in die selben Pakete in der selben reinfolge zerlegt werden, was mehr Aufwand als Nutzen darstellen würde.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Bebu
Beiträge: 562
Registriert: Mi Okt 21, 2009 6:19 pm
Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!

Re: Hashfunktion

Beitrag von Bebu » Fr Jul 15, 2011 11:50 am

Ok, lassen wir die Thread momentan noch aus dem Spiel, bzw. implementieren wir das über den Kernel, Geschwindigkeit lässt sich optimieren, wenn die Grundfunktionen vorhanden sind.

Cloidnerux bitte arbeite nur noch im Trunk Verzeichnis und lass den Branch ruhen, im Trunk sind die Flüchtigkeitsfehler schon behoben und es sollte jetzt kompilieren, nur die Änderungen wegen der Einlesegröße fehlen noch.

Um Trunk zu kompilieren sind folgende externe Bibliotheken nötig: Boost_Filesystem, Boost Header für Boost::Function und Boost::Bind, Demnächst wird noch Boost::Thread dazukommen, ist aber noch nicht nötig. Außerdem sqlite3 und für einen Teil der Testsuite noch cppunit, will ich aber wieder über Board werfen und wenn möglich durch Boost::Test ersetzen, muss ich mir aber erst mal in Ruhe ansehen. Achja und für Xin's Ncurses noch Ncurses.

Das aktuelle Target ist dedupe und man könnte Temporär einfach den N-Curses Teil als Exclude from all eintragen, dann kann man sich Ncurses noch sparen.
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Fr Jul 15, 2011 11:58 am

Cloidnerux bitte arbeite nur noch im Trunk Verzeichnis und lass den Branch ruhen, im Trunk sind die Flüchtigkeitsfehler schon behoben und es sollte jetzt kompilieren, nur die Änderungen wegen der Einlesegröße fehlen noch.
Man sollte immer erst in branch comitten, bevor man den trunk ändert, nicht umgekehrt, sonst wird das ein nur noch größeres Chaos.
Wie gesagt, alle Änderungen lagen in meinem Branch und die habe ich schnell rüber kopiert.
Ist jetzt alles eingebaut.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Bebu
Beiträge: 562
Registriert: Mi Okt 21, 2009 6:19 pm
Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!

Re: Hashfunktion

Beitrag von Bebu » Fr Jul 15, 2011 12:31 pm

Stopp! - Zu spät.
cloidnerux hat geschrieben:
Cloidnerux bitte arbeite nur noch im Trunk Verzeichnis und lass den Branch ruhen, im Trunk sind die Flüchtigkeitsfehler schon behoben und es sollte jetzt kompilieren, nur die Änderungen wegen der Einlesegröße fehlen noch.
Man sollte immer erst in branch comitten, bevor man den trunk ändert, nicht umgekehrt, sonst wird das ein nur noch größeres Chaos.
Wie gesagt, alle Änderungen lagen in meinem Branch und die habe ich schnell rüber kopiert.
Ist jetzt alles eingebaut.
Du hast leider vergessen, dass die Hash Dateien aus deinem Branch schon ziemlich alt sind und auch einige Fehler enthalten haben, die nicht kompliert haben. Die waren in Trunk schon gefixt. Jetzt hast du deine Änderung in den alten Hashdateien eingepflegt, sie in deinen Branch commited und nach Trunk kopiert. Folge: Die schon gefixten Fehler liegen wieder in Trunk und der Build ist gebrochen. Keine Sorge, ich versuche das schnell zu fixen, aber bitte in Zukunft auf den aktuellen Dateien arbeiten, das spart doppelte Arbeit.
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Fr Jul 15, 2011 12:39 pm

Du hast leider vergessen, dass die Hash Dateien aus deinem Branch schon ziemlich alt sind und auch einige Fehler enthalten haben, die nicht kompliert haben. Die waren in Trunk schon gefixt. Jetzt hast du deine Änderung in den alten Hashdateien eingepflegt, sie in deinen Branch commited und nach Trunk kopiert. Folge: Die schon gefixten Fehler liegen wieder in Trunk und der Build ist gebrochen. Keine Sorge, ich versuche das schnell zu fixen, aber bitte in Zukunft auf den aktuellen Dateien arbeiten, das spart doppelte Arbeit.
Wir erleben hier ein sehr typisches Problem: Mangelnde Kommunikation!
Ich bin verantwortlich für die hashklasse, werde also selber dort Änderungen einführen und Fehler korrigieren.
Wenn du etwas änderst im Trunk und ich davon nichts weiß, kann ich sie auch nicht übernehmen.
Im gegenteil, wie jetzt geschehen habe ich meine neue Version vom branch nach Trunk kopiert.
Ich habe aber in der aktuellen Version alle Fehler beseitigt und die Quellen im Branch sind neu, die habe ich erst vorhin hochgeladen.
Ich Denke, wir sollten uns über einem kürzeren Kommunikationskanal verständigen, sprich ICQ/Skype sonstige Chats und Videokonferenzen.
Keine Sorge, ich versuche das schnell zu fixen, aber bitte in Zukunft auf den aktuellen Dateien arbeiten, das spart doppelte Arbeit.
SVN hat extra einen Branch und Trunk. Man soll immer eine Stabile Version im Trunk und alles Instabile und "Work in progress" im branch lassen, das alle die Möglichkeit haben immer eine Funktionierende Version aus dem trunk zu ziehen.
Im gegenteil: du schadest wenn du im Trunk arbeitest! Dadurch das die Dateien im Trunk neuer sind, wird jeder der in seinem Branch weitermachen will auf alte Dateien stoßen, die nur wieder Probleme hervorrufen.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Antworten