Nello sviluppo di qualsiasi software non manca di certo l’uso delle stringhe (string litteral detta alla C++) direttamente nel codice sorgente per svariate usi: dal titolo della finestra della nostra applicazione al nome di una texture… Esse sono molto utili anche perchè a noi umani torna molto più facile leggerle. Laddove però abbiamo bisogno di performance non vanno più bene ed è quindi consuetudine convertire la stringa in una chiave hash e usare quest’ultima come indentificartore.
Immaginiamo ad esempio di avere una collezione di suoni e di dover mandare in play il suono hit.wav quando il nostro player viene colpito…il nostro codice assomiglierà a qualcosa del genere:
//...
soundManager->play("hit.wav");
//...
Il soundManager, nella nostra prima e rudimentale implementazione, avrà una semplice mappa con chiave la stringa che identifica il suono e con il valore, ad esempio, l’handle del buffer di openAL del suono. Questo però è poco efficiente poichè ad ogni lookup della mappa equivalgono N comparazioni tra stringhe (strcmp): possiamo e dobbiamo fare di meglio!.
Come ho già detto quindi si converte la stringa in una chiave hash (solitamente uint32) usando una delle tantissime funzioni hash (esempi). La strada più usata sembra essere la seguente: si wrappa la nostra stringa in una classe che si occupa di calcolare il valore di hash e si implementa opportunamente l’operator==. In debug si conserva comunque la stringa per comodità mentre essa “sparisce” in release.
#include <string>
class StringId
{
public:
explicit StringId(const char* const str)
{
#ifdef DEBUG
mString = str;
#endif
mHash = hash(srt,strlen(str));
}
bool operator==(const StringId& other)
{
return mHash == other.mHash;
}
// operatore di conversione, altri operatori, e tutto il resto...
// ... lasciato come esercizio! :)
private:
#ifdef DEBUG
std::string mString;
#endif
uint32 mHash;
};
Tornando al nostro super-complesso esempio potremmo convertire il codice come segue:
/*static storage*/ StringId sound_hit_wav("hit.wav");
//...
soundManager->play(sound_hit_wav);
//soundManager->play(StringId("hit_wav")); // no! evitiamo la costruzioni di inutili oggetti temp e la ri-generazione dell'hash
//...
e ovviamente ri-implemetando in modo opportuno il soundManger: la chiave della nostra mappa sarà ora un StringId o, ancora meglio, uint32. In questo modo ci siamo assicurati ottime performance senza però rinunciare alla comodità delle stringhe per noi comuni mortali.
Ti ricordi quando ti ho detto che in release la stringa sparisce ? bhè non è per niente vero nella maggior parte dei casi e vediamo perchè.
In c++ le stringhe costanti (rvalue string literal) vengono memorizzate nello static storage cioè in un’area di memoria riservata per la sola lettura. Questo vuol dire che nonostante i nostri sforzi per la creazione della classe StringId abbiamo si incrementato le performance in termini di tempo ma non di spazio (anzi, ora abbiamo un uint32 in più 
) In più il calcolo della generazione dell’hash viene eseguita a runtime (comunque prima dell’esecuzione del main se abbiamo variabili con storage statico)
Se infatti apriamo un hex editor e ispezioniamo il nostro eseguibile:
vediamo chiaramente la nostra bella stringa nonostante l’eseguibile sia stato compilato in release con tutte le ottimizzazioni abilitate.
Per evitare cioè abbiamo queste possibilità:
0) Non fare niente visto che si parla di pochi kb anche se abbiamo centinaia di stringhe.
1) Non fare niente fidandoci del compilatore (sembra che gcc riesca a eliminare le string litteral non usate):
// da http://www.gamedev.net/topic/550505-string-names-for-resources/
#include <string.h>
#include <stdio.h>
inline unsigned int hash(const char* str) // cookbook Adler32 sum
{
unsigned int s1 = 1;
unsigned int s2 = 0;
for (unsigned int n = 0; n < strlen(str); ++n)
{
s1 = (s1 + str[n]) % 65521;
s2 = (s2 + s1) % 65521;
}
return (s2 << 16) | s1;
}
int main()
{
printf("%u", hash("SomeTextureName"));
}
This compiles to... HOLY CRAP!
movl $807077383, 4(%esp)
movl $LC0, (%esp)
call _printf
xorl %eax, %eax
leave
ret
($LC0 holds .ascii "%u\0", the format string)
2) Usare il preprocessore con la magia nera delle MACRO
3) Usare lo stesso compilatore con la magia nera dei TEMPLATE (questo risolverebbe solo il problema della generazione a runtime dell’hash)
4) “Hardcodare” a mano o tramite qualche tool oltre alla stringa anche la stessa chiave hash che in release viene scarta grazie ad una semplice macro.
Personalmente preferisco la soluzione 4 anche perchè, escludendo le prime due, la 2 richiede una sintassi orribile:
// da http://bitsquid.blogspot.com/2010/10/static-hash-values.html
uint32 root_point = HASH_STR_10('r','o','o','t','_','p','o','i','n','t'))
e, come la 3, sono difficili da manutenere (se volessi cambiare algoritmo?) e allungano i tempi di compilazione (proporzionalmente con il numero di string literal).
La 4 ha due varianti.
La prima è quella “manuale”: quando il programmatore inserisce una nuova stringa, genera offline l’hash (con un piccolo tool) e l’ “hardcoda” direttamente nel sorgente:
// da http://bitsquid.blogspot.com/2010/10/static-hash-values.html
#ifdef _DEBUG
inline uint32 hash(const char *s, uint32 value) {
assert( hash(s, strlen(s)) == value );
return value;
}
#else
#define hash(s,v) (v)
#end
//...
uint32 root_point = static_hash("root_point", 0x5e43bd96);
da notare che in debug viene controllata la consistenza tra l’hash hardcodato e quello generato a runtime con una assert mentre in release sparisce tutto.
Invece la soluzione automatizzata potrebbe essere quella suggeritaci da Julien Koenen in un commento:
What we do here at keen games is that we have .crc files (text files with one identifier in each line) that run through a ruby script in our maketool (before the compilation starts). This script creates a header file with defines for each symbol in the crc file and the hash (crc32 in our case) value as value. That worked like a charm for all our projects.
In sostanza si ha un file del tipo
//c++ var, string
sound_hit_wav, hit_wav
sound_fire_wav, fire_wav
...
che viene convertito dal tool in un header del tipo:
#ifndef AUTO_GENERATED_IDS_H
#define AUTO_GENERATED_IDS_H
// don't edit this file manually, use XXX tool instead !!!
const uint32 sound_hit_wav = 0x5953e937;
const uint32 sound_fire_wav = 0x701b653a;
//...
#endif
o una sorta di parser del codebase alla ricerca delle stringhe e la sostituzione come ci suggerisce Phil in un’altro commento:
Instead of storing the output in a separate file we just modify the source file in place.
What we do is to place every string in a macro like this:
H(“hello”, 0)
Which gets replaced with the appropriate hash in the second parameter. So immediately after the pre-parser has run on the code file it would look like this:
H(“hello”, 0×263262)
Penso che sia tutto almeno per ora, alla prossima, ciao!
