039
22.01.2009, 10:11 Uhr
~raps
Gast
|
| Zitat von Guybrush Threepwood: |
Das mag ja so sein, aber das heißt ja nicht das das für jeden alles so selbstverständlich ist. Ich kann da zum Beispiel vom eigentlichen Thema nicht mitreden,
|
dann bekommst du gerne von mir die grundausbildung in Hash.
"A hash function is any well-defined procedure or mathematical function which converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index into an array." (quelle wikipedia).
und auf gut deutsch: ein hash algorithmus mapt auf einen n-dimensionalen raum von einem >n dimensionalem raum z.b. einen string von 200byte auf 32bit.
aus diesem grund kann es mehrere werte geben die den selben hash-wert erhalten (nennt man dann Hash collision).
Ein guter hash algorithmus nutz den ganzen raum voll aus, bei 32bit kann also bei einem 32bit input jeder wert wieder rauskommen, das heisst auch dass keine hashcollision enstehen kann.
Was bedeutet ein hash algorithmus, angewendet auf werte der selben und von kleineren dimensionen, nur eine permutation der werte erzeugt und man erhaelt keine Collision, was aber auch bedeutet dass man die dimension nicht verkleinert.
eine schluesseleigenschaft von hashes ist, dass sie irreversibel sind, du kannst von einem hash nicht mehr die ursprungsdaten errechnen, dazu:
"Hash Functions take a block of data as input, and produce a hash or message digest as output. The usual intent is that the hash can act as a signature for the original data, without revealing its contents. Therefore, it's important that the hash function be irreversible" (quelle: www.lincoln.edu/math/rmyrick/ComputerNetworks/InetReference/142.htm)
das heisst auch, ein (guter) hash von 32bit auf eine 32bit zahl bringt nichts, das ist soviel wert wie ein hash auf einen hash, du erhaellt keine dimensionsverkleinerung und kannst deswegen auch ein inverses mapping erstellen, von hash zu ursprungs-wert.
Es waere also nur eine zeitverschwendung. nun ein kleiner blick in die hash implementierung von STL_PORT (die nicht sonderlich anders ist als andere)
| C++: |
template <class _Key> struct hash { };
inline size_t __stl_hash_string(const char* __s) {
_STLP_FIX_LITERAL_BUG(__s)
unsigned long __h = 0;
for ( ; *__s; ++__s)
__h = 5*__h + *__s;
return size_t(__h);
}
_STLP_TEMPLATE_NULL struct hash<char*> {
size_t operator()(const char* __s) const
{ _STLP_FIX_LITERAL_BUG(__s) return __stl_hash_string(__s); }
};
_STLP_TEMPLATE_NULL struct hash<const char*> {
size_t operator()(const char* __s) const
{ _STLP_FIX_LITERAL_BUG(__s) return __stl_hash_string(__s); }
};
_STLP_TEMPLATE_NULL struct hash<char> {
size_t operator()(char __x) const { return __x; }
};
_STLP_TEMPLATE_NULL struct hash<unsigned char> {
size_t operator()(unsigned char __x) const { return __x; }
.
.
.
_STLP_TEMPLATE_NULL struct hash<size_t> {
size_t operator()(size_t __x) const { return __x; }
};
|
du siehst, die fachwelt gibt einfach wieder den eingangswert zurueck fuer char,short, unsigned int (bei 32bit systemen size_t genannt).
nun einmal in meinem beispielcode die hier von "beefy" vorgeschlagene " vernünftige Hash-Funktion z.B. Jenkin's one-at-a-time hash" eingebaut, ergebniss: statt >18s hat man nun 25s laufzeit. Die anzahl der collisions in der hashtable veraendert sich nicht, es kommt lediglich die zeit hinzu die du fuers hashing brauchst.
----------------------------------------------------------------
soviel zu hashes, nun zu hashtables: (ich hoffe ich bin verstaendlich  ).
wieso dann ueberhaupt eine hashtable? ganz einfach, das eigentliche "hashing" was dann auch die kollisionen verursacht erzeugt man indem man den 32bit index auf die hash-table laenge mapt. also entweder ein modulo (%size ) oder bei power of two groessen eine und verknuepfung (&(size-1)). wenn also die hashtable eine groesse von 400 000 hat und du pruefst ob 50 oder ob 400 050 in der hashtable ist, hast du eine hash collision. das ist auch der ganze grund fuer die langsammkeit, man muss diese collisions aufwendig behandeln.
Die hier grundlangenlos in den raum gestellte aussage "Natürlich ist das so langsam, was erwartest du denn? Wahrscheinlich kopiert das hash_set dauernd seine Daten hin und her und hasht die halbe Zeit neu." kann man leicht wiederlegen indem man die hashtable in einem ersten durchgang fuellt und in einem zweiten dann das eigentliche rausfiltern der daten durchfuehrt (Weil die hashmap voll ist, werden natuerlich _alle_ werte als schon vorhanden erachtet und somit nicht in den vector kopiert, aber fuer die validierung ist das ok). das ergebnis ist: von 18.8ms -> 18.3ms. (ich erspar dir mal die details weshalb das schon so effizient ist, aber falls du es dennoch wissen willst, frage ruhig ).
nun meine behauptung, es liegt an hash collision die man immer aufloesen muss. wie du vielleicht in meinem sourcecode sehen kannst, nutz ich so ziemlich den ganzen 32bit raum aus um die 400 000 werte einzufuegen, diese sind in immer gleichen intervalen (das ist beim thread starter nicht so, das ist ja nur mein worst-case fuer bit-table szenario). entsprechend kann man mit ein paar weiteren operationen einfach durch die intervallaenge teilen und erhaellt einen perfect hash (fuer diesen konstruierten fall). das mal in meine beispiel applikation eingebaut und die zeiten aendern sich folgendermassen: 18ms -> 10ms.
Ist aber immer noch nicht so schnell wie die 8ms der bittable, wieso? weil es noch overhaed gibt. auch wenn es keine collision gibt, stl_port rechnet modulo und da sie nicht weiss dass es ein perfect hash ist, prueft sie natuerlich immer ob eine collision vorliegt.
q.e.d.
----------------------------------------------------------------
nun zur vorab analyse des problems bevor wir eine loesung vorschlagen koennen.
es gibt 400 000 werte die 100Mio mal angefasst werden. kritisch ist also jeder lookup und sollte moeglichst schnell sein, also ohne collisions.
perfect hashing ist in der realen welt leider nicht moeglich, also lass uns die alternative checken. BitTables.
wieviel ist das an daten? 512MB? oder 400 000/8 Byte? wieviel schaufelt man schlussendlich?
antwort: das haengt davon ab auf welcher architektur. einzelne bits kannst du nicht laden, was du laden kannst sind cachelines, bottleneck ist dabei entweder der cache zugriff falls die daten reinpassen, ansonsten ramzugriff.
amd xp: 32byte(cacheline groesse) * 400 000 = ca 12MB
intel core2duo: 64byte -> 24mb
PowerPC (z.b. cell): 128byte -> 48MB
ergo, die limitation ist der main memory zugriff. du kannst _ganz_grob_ mit ca 75cycles bis 150cycles rechnen die ein zugriff kostet. 100Mio -> 15Gigacycles, bei 2.4 Ghz sind das bei 0 cachehits 6.25s. (nebenbei, der modulo alleine bei einer hashtable kostet ca 40cycles)
mit der simplen implementierung von mir kommen wir bei >8.9s raus. es gibt ja auch die moeglichkeit noch prefetching einzubauen um waehrend der aktuellen berechnungen die latenz auszunutzen, sodass man vom cahe noch was hat. mit diesen zwei zeilen
| C++: |
_mm_prefetch((const char*)&rVec[a+16],_MM_HINT_NTA);
_mm_prefetch((const char*)&RBitTable[rVec[a+4]>>5],_MM_HINT_NTA);
|
erhaellt man schliesslich ca 4.5s an laufzeit -> 108 cycles pro test.
so, ich hoffe ich hab dich alten piraten nicht zu sehr gelangweilt. danke  |
