Das Originalprogramm macht beim Lookup ohne Kollissionen folgende Speicherzugriffe, die wahrscheinlich Cache misses verursachen: Viele Gruppen haben den zweiten Zugriff wegoptimiert, aber erstaunlicherweise hat sich keine wirklich mit dem Zugriff auf den String befasst. Meine Version versucht, diese Cache misses auf einen zu reduzieren, indem ein Knoten den Wert und den String enthält, und 64 Bytes gross ist: 
struct hashnode {
  int value;
  char keylen;
  char key[59];
};
Diese Knoten sind direkt in der Hash-Tabelle abgespeichert, und es wird open addressing mit linear probing verwendet (das koennte moeglicherweise die Prefetch-Hardware gut ausnutzen). Damit es wenig Kollisionen gibt, die bei dieser Methode mit diesem Load-Faktor schon problematisch sein könnten, wurde die Anzahl der Tabelleneinträge verdoppelt; 10 Extra-Einträge am Ende sollten für Kollisionen am Ende ausreichen (ein ordentliches Programm würde das prüfen und abfangen, aber dieser proof-of-concept ist nur für den vorgegebenen Input geschrieben). Als Nachteil des Ganzen schwillt der Speicherverbrauch auf 128MB allein für die Hash-Tabelle an. Eigentlich sollte man auch sicherstellen, dass die Tabelle 64-Byte-aligned anfängt, aber mit der verwendeten gcc-Version geschieht das offenbar automatisch. Performance: 
[g0:~/hash/opt:32440] gcc -O3   -fno-builtin-memcmp hash.c
[g0:~/hash/opt:32441] perf stat -e instructions -e cycles -e cache-misses a.out input input2
8879313950759542027, ht=0x601400

 Performance counter stats for 'a.out input input2':

     1287430511  instructions             #      0.602 IPC  
     2140055224  cycles                   #      0.000 M/sec
       19923194  cache-misses             #      0.000 M/sec

    0.647701299  seconds time elapsed
Ca. 8M der Cache Misses kommen von den 11*724129 Zugriffen auf Einträge in der Hash-Tabelle, einige mehr von Kollissionen, 2M von der Initialisierung der Hash-Tabelle, ca. 1.7M vom Lesen der Dateien. Die restlichen 8M müßten noch nachgeforscht werden. Unten finden Sie den Code der verbesserten Variante.
[ICO]NameLast modifiedSizeDescription
[PARENTDIR]Parent Directory  -  
[TXT]hash.c2013-01-25 13:44 3.5K 
Apache/2.4.62 (Debian) OpenSSL/3.0.15 Server at www.complang.tuwien.ac.at Port 80