 |
A generic map container should have fast search by key, which means it should either be implemented via balanced search tree or hash table. Search trees are quite complicated to implement, hash tables are much easier and faster in general. Idlib has several hash tables, each of which has some serious drawbacks compared to std::map. idHashIndex is hash table storing indices. It must be used in conjunction with external array, which actually stores items. It is implemented with separate chaining, although all the chains are stored in a single memory buffer. While it is rather good performance-wise (aside from awful removal), it is very low-level thing. For instance, there are no add/set/remove methods, instead users must write same collision-resolution loop every time. idDict is idStr->idStr map containing array of key/value pairs and idHashIndex. Case-insensitive match is used. This is most used in game code, e.g. for spawnargs. All of its keys are allocated in a global string pool, same applies for values. As the result, it is not threadsafe: it can only be used on the game thread (frontend thread). Also, string-only keys can hardly be called "universal". idHashTable is a standalone hash table with string-only keys. It uses separate chaining with each list node allocated separately. This is very inefficient. Plus string-only keys is not universal again. On top of that, all these three options use hash table of fixed size. So in order to get good performance, one must estimate the number of items in the table before start. There is no automatic exponential rehashing. None of them is suitable for usage in renderer's interaction table, which has integer keys and pointer values (string keys are too slow, separate chaining slow too). That's why idDenseHash was implemented, which is very similar to Google Dense Hash Table (open addressing, all items in single buffer). However, its interface is also fairly low-level. It would be a good idea to extend it to a generally useful data structure. |
|
|
Committed new implementation: r9315. Add idStr::IHashPoly64 --- case-insensitive version of polynomial hash. r9316. Added idHashMap --- generic map container implemented via hash table. r9317. Refactored idInteractionTable to allow on-the-fly between implementations, added idHashMap implementation. r9318. INTERACTION_TABLE_MAX_ENTITYS reduced back from 64K to 8K. The most important commit is indeed r9316: it adds new container and unit tests on it. With r9317, the new map can be used in interaction table, but the default implementation is not switched yet. Had to fix testing framework in order to run tests: r9313. Added /WHOLEARCHIVE:idlib to VC props of TheDarkMod project. r9314. Do not shutdown new backend if it was not initialized. |
|
|
The new container (called idHashMap) can be used for interaction table, where maximum performance is necessary. Thus, it is an extension of idDenseHash (basically the same data structure) . The old interface is still present, but all of its methods are marked as [low-level]. New easy-to-use methods Find, Get, Set, AddIfNew, Remove were added. Also operator[] similar to that of std::map is present. While it is not encouraged, in some cases it is much more convenient. The container has template arguments for hash function and equality operator, aside from key and value types. The hash function and equality operator may have context: the container actually stores objects of these types. Providing hash function is a nuisance in general. Right now 32-bit Knuth hash function is used by default for integer and pointer types. For idStr classes, polynomial hash function (aka djb2) with Knuth hash finalizer is used. For other types std::hash<T> is used it might be a bad fit, but better than not compiling. Generally, user should implement his own hash function for a custom type. The performance might depend a lot on the quality of hash function: it should randomize the higher bits of 32-bit hash well enough. In debug configuration, each idHashMap object maintains statistics of how much probes and queries were done, which makes it easy to detect bad behavior. Also, dense hash table requires some key to designate "empty" cells. Just like hash function and equality operator, it can be set by user. Default "empty" value is: unsigned integer or pointer: -1 = 0xFFFF...F signed integer: INTnn_MIN = 0x8000..0 idStr: "\5" --- string with one character with ASCII code = 5 everything else: default-constructed value (or zero for primitive type) Type alias idHashMapIStr for case-insensitive idStr keys is provided, along with different hash function and equality operator. For case-insensitive idStr -> idStr map similar to idDict, use idHashMapDict. |
|
|
With svn commit 9322, defines for GLSL programs are stored in idHashMapDict instead of idDict. This should fix occasional startup crashes with "com_smp 1". |
|
|
In svn commit 9323, switched default interaction table implementation from idDenseHash to idHashMap. The plan is to remove idDenseHash of course, but I guess I'll do it a bit later. Thus, I'm not closing this issue yet (to not forget about cleanup). |
|
|
Removed idDenseHash in svn rev 9472/ |
- Anonymous
