From: Gustaf N. <ne...@wu...> - 2010-02-14 17:20:48
|
Am 11.02.10 01:08, schrieb Alexandre Ferrieux: > Since it appears that timings are tricky, Apparently. It turns out that in the both mini-benchmarks (the two "foo" functions) the hash function for string keys (HashStringKey()) is not called at all (!) in the timed loop (e.g. Tcl variables are compiled locals). Funny enough, just by changing the string hash function one can measure different performance values (maybe due to processor level caching or similar external effects). Two more observations: - At least on x86 Intel, gcc compiles the classical Tcl string hash function pretty well. The loop body if the hash function "result += (result<<3) + c;" results in just two machine instructions (one lea + one add). This is hard to beat by assembly coding (if someone is interested, i have an apparently slighter faster inline assembly version for x86 64bit). So, the classical Tcl hash function appears well suited for modern compilers, and gcc does very well here (i used gcc 4.2.1). FNV needs the slower integer multiply, that's why the FNV is slower (measured by Donals hashes.c test). - For small hash tables, only a few bits of the computed hash values are used. For the initial size, these are only the last two bits. By every hash table resize (RebuildTable) two more bits are added. It is not clear how the properties of hash functions propagate, when only a small fraction (e.g. 2, 4, 6 etc. bits) of the computed hash value are actually used. It looks to me as if the original Tcl hash function has quite good properties for the task it is used. In order to make hashing faster in Tcl, it is most likely more promising to look at the Tcl-hash machinery altogether. The granularity of the functions does not look perfectly suited for the needs of current Tcl. So the current definitions ================================== Tcl_HashKeyType { .... HashKeyProc CompareHashKeysProc AllocHashEntryProc FreeHashEntryProc } Tcl_HashEntry * Tcl_CreateHashEntry(...) { ... if (tablePtr->keyType == TCL_STRING_KEYS) { typePtr = &tclStringHashKeyType; } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) { typePtr = &tclOneWordHashKeyType; } else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS || tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) { typePtr = tablePtr->typePtr; } else { typePtr = &tclArrayHashKeyType; } ... ================================== could become something like ================================== Tcl_HashKeyType { .... CreateHashEntryProc FreeHashEntryProc } #define Tcl_CreateHashEntry(tablePtr,..) (...)tablePtr->type->CreateHashEntryProc(...) ================================== to provide tailored create functions for every hashKeyType. Tcl does not call HashKeyProc, CompareHashKeysProc, or AllocHashEntryProc outside CreateHashEntry. The common "keyType == ..." sermon used in several functions of the hash API does not look perfect either and could be replaced by a macro like the one sketched.... best regards -gustaf neumann |