[C++] Compile time hash van string

[MisterData]

Een tijd geleden ben ik begonnen met het maken van een eigen scripting-engine. Die werkt op dit moment prima (Spirit Parser genereert bytecode die een VM dan uitvoert). De API om classes scriptbaar te maken is zo simpel mogelijk gehouden en bestaat uit een interface Scriptable die een methode Execute definieert:

C++:

virtual ref<Scriptable> MijnScriptableClass::Execute(std::wstring command, ref<ParameterList> params) {
    if(c==L"toString") {
        return new ScriptString(L"Hello World!");
    }
    return 0; // methode/veld bestaat niet
}

Een en ander met refcounting zodat het allemaal netjes werkt. Zoals je ziet krijgt een Scriptable class bij het uitvoeren van een bepaalde functie op die class gewoon een aanroep naar een methode 'Execute' met als parameters een string met de naam van de gevraagde functie (of veld) en een parameter-lijst.

Dat werkt allemaal prima en het is een hele simpele manier om je classes scriptable te maken. Het probleem is alleen dat het enorm traag is: iedere keer als ik een call maak naar een scriptable class moet hij de functienaam vergelijken met een aantal functienamen (in ifjes, dus slecht voor branch prediction enzo) en daarna pas de functie uitvoeren.

Nou dacht ik: stel dat ik de functienamen ("toString" etc) nou eens zou hashen. Dan krijg ik een int (hopelijk en waarschijnlijk uniek) die ik gewoon met een switch-statement kan 'matchen'. De compiler hasht de functienamen ook meteen en dat zorgt weer voor kleinere bytecode. Kandidaat hiervoor leek me de FNV-hash, omdat die snel en simpel is.

Het probleem: om het programmeren van scriptbare classes makkelijker te maken moet de hash eigenlijk compile-time worden gegenereerd uit een opgegeven functie-naam. Ik wil dus zoiets:

C++:

virtual ref<Scriptable> MijnScriptableClass::Execute(int command, ref<ParameterList> params) {
    switch(c) {
        case HASH(L"toString"):
            return new ScriptString(L"Hello World!");
            break;
    }

    return 0;
} 

Maar hoe maak ik die hash compile-time?

[.oisyn]

Kan niet. Waarom gebruik je niet gewoon een (statische) stdext::hash_map<std::wstring, ref<Scriptable> (MijnScriptableClass::*)(ref<ParameterList>)> ?

C++:

typedef stdext::hash_map<std::wstring, ref<Scriptable> (MijnScriptableClass::*)(ref<ParameterList>)> CommandMap;

void MijnScriptableClass::Init()
{
    s_cmdMap[L"toString"] = &MijnScriptableClass::toString;
}

ref<Scriptable> MijnScriptableClass::toString(ref<ParameterList> params)
{
    return new ScriptString(L"Hello World!"); 
}

virtual ref<Scriptable> MijnScriptableClass::Execute(const std::wstring & command, ref<ParameterList> params)
{
    CommandMap::const_iterator it = s_cmdMap.find(command);
    if (it != s_cmdMap.end())
        return (this->**it)(params);
    else
        throw CommandNotFoundException(); // or whatever
}

[ Voor 71% gewijzigd door .oisyn op 23-01-2007 14:04 ]

[MSalters]

.oisyb, ik zou heel voorzichtig zijn met die opmerking. Maar je oplossing is natuurlijk zinnig. Het kan mogelijk nog handiger: on-demand hashing. Je genereert de hash voor elk input token; heb je die hash nog niet dan check eenmalig je of dat token in de keyword lijst voorkomt. Zo ja, dan voeg je de hash toe aan de known-lijst. Omdat je keyword gelijk is aan je input token is de hash dat ook. Je hash functie wordt dus net zo vaak aangeroepen als je input tokens hebt (ideaal) en je if-statement wordt net zo vaak doorlopen als je keywords gebruikt.

[MisterData]

Ik heb er nooit bij stil gestaan dat function pointers naar class member-functions ook kunnen... Die gebruik je natuurlijk ook niet zo vaak. Het is inderdaad een werkbare optie, maar er is nog steeds per call een lookup nodig in de map met commando's => functies. Ik weet niet precies hoe snel dat is, maar een switch lijkt me sneller (jumptabel?). Zijn er geen hash-achtige functies te maken via Template Metaprogramming?

Wat ook zou kunnen is de hashes at-runtime eenmaal laten berekenen:

C++:

void MijnClass::Execute(int command, ...) {
    static Hash toStringHash(L"toString");

   if(command==toStringHash.hashValue) {
      ...
  }
}

Echter case-expressies moeten constant zijn neem ik aan, dus dan werkt dit weer niet met een switch?

[ Voor 29% gewijzigd door MisterData op 23-01-2007 20:52 ]

[DroogKloot]

Ik denk niet dat je het verschil tussen de O(1) van de hashmap find() operatie en de O(1) van een jumptabel echt zult merken, eerlijk gezegd.

[.oisyn]

MisterData schreef op dinsdag 23 januari 2007 @ 20:48:
maar een switch lijkt me sneller (jumptabel?)

Tenzij jouw hashfunctie n opeenvolgende resultaten geeft voor n hashes, zou ik me daar niet al teveel zorgen over maken

Echter case-expressies moeten constant zijn neem ik aan, dus dan werkt dit weer niet met een switch?

Waarom zou een if/else anders zijn dan een switch, behalve de syntax? Denk je niet dat een compiler een hele if/else boom niet precies hetzelfde kan optimaliseren?

[MisterData]

DroogKloot schreef op dinsdag 23 januari 2007 @ 21:17:
Ik denk niet dat je het verschil tussen de O(1) van de hashmap find() operatie en de O(1) van een jumptabel echt zult merken, eerlijk gezegd.

Ik denk niet dat de hashmap O(1) is? Maar ik begrijp wat je zegt: met weinig entries is de hashmap nagenoeg even snel. Denk dat dat 'em dus ook wordt, is ook wel handig voor een stukje reflection in de scripting-engine natuurlijk (handig om uit te zoeken welke functies een bepaald object aanbiedt). Ik ga dan wel voor een std::map<int, functie> en niet voor de stdext::hashmap<string, functie>, omdat ik anders nog steeds strings over en weer aan het schieten ben (in iedere opcode zit dan een string met functienaam) en er bij iedere call nog steeds gehasht moet worden

[.oisyn]

Maar waarom dan een binaire boom ipv een hashtable? Je kunt natuurlijk ook gewoon een stdext::hashmap<int, functie> gebruiken. De hashfunctie van een int is redelijk simpel, namelijk gewoon die int

[Soultaker]

Eerst ging het over strings, maar nu heb je ints in je opcodes staan. Kun je dan niet direct die functies aan getallen van 0..N koppelen? Dan kun je gewoon een array (of std::vector) van functie-pointers gebruiken en heb je helemaal geen speciale datastructuren meer nodig. Lijkt me nog wat compacter (en daarom efficiënter) dan een hashtable.

(Dit alles vanuit de aanname dat het gaat om performanceproblemen bij het interpreteren van de bytecode, niet het genereren daarvan.)

[ Voor 16% gewijzigd door Soultaker op 24-01-2007 12:38 ]

[.oisyn]

Als het een early-bound scripttaal is is dat natuurlijk een betere oplossing, maar voor late-bound talen is dat natuurlijk geen optie, en die indruk kreeg ik van de TS.

[DroogKloot]

MisterData schreef:
[...]


Ik denk niet dat de hashmap O(1) is?

Als elke functienaam een unieke hashcode heeft (wat je wel mag aannemen), dan is de lookup-tijd natuurlijk constant. Het enige O(1)-'intensieve' aan de lookup is het berekenen van die hash, maar veel zal het echt niet schelen.

[MisterData]

Late-bound inderdaad Denk dat het inderdaad een stdext::hashmap<int, functie> moet gaan worden

[Hackykid]

Ik kan me herinneren dat ik ooit iets soortgelijks had waarvoor ik compile-time string hashes nodig had.
Het is me toen ook nog gelukt, met C macro's als ik me het goed herinner.
Ik zal eens kijken of ik die code nog kan vinden.

---

Edit: heb iets gevonden

code:

// some typedefs i used to use
typedef unsigned char uint8;
typedef unsigned int uint32;

/* The FNV-la Hashing algo stuff: (http://www.isthe.com/chongo/tech/comp/fnv/) */
#define FNV_32_I ((uint32)0x811C9DC5)
#define FNV_32_P ((uint32)0x1000193)
#define FNV_32A_OP(hash, oct) (((uint32)(hash) ^ (uint8)(oct)) * FNV_32_P)
/* Hash stuff for handling strings */
#define FNH_LEN(s) (sizeof(s)-1)
#define FNH_CHR(s, i) ((i) < FNH_LEN(s) ? (uint8)((s)[i]) : (uint8)(FNH_LEN(s) - (i)))
/* Hash stuff calculating the hash */
#define FNH01(s,h,i) FNV_32A_OP((h), FNH_CHR((s),(i)))
#define FNH02(s,h,i) FNH01((s), FNH01((s), (h), (i)), (i) + 1 )
#define FNH04(s,h,i) FNH02((s), FNH02((s), (h), (i)), (i) + 2 )
#define FNH08(s,h,i) FNH04((s), FNH04((s), (h), (i)), (i) + 4 )
#define FNH16(s,h,i) FNH08((s), FNH08((s), (h), (i)), (i) + 8 )
#define FNH32(s,h,i) FNH16((s), FNH16((s), (h) ,(i)), (i) + 16)
/* The actual hash we are using */
#define FNV_HASH(s) FNH32((s), FNV_32_I, 0)

int main(int argc, char* argv[])
{
    uint32 x = FNV_HASH("thestring");

    printf("%u",x);
}

Kijkt naar de eerste 32 characters van de string, en pad er nummers achteraan als hij korter is

Let op: optimalisaties moeten wel aanstaan (met GCC -O1 minimaal) anders berekent hij toch een deel at runtime.

Trouwens best grappig om de preprocessor output hiervan te bekijken.

Als vindt dat dit niet C++ genoeg is, ben ik vrij zeker dat je iets soortgelijks kan doen in C++ met template metaprogramming.

[ Voor 78% gewijzigd door Hackykid op 24-01-2007 21:06 ]