#8915 closed patch
COMMON: Revised HashMap implementation
| Reported by: | fingolfin | Owned by: | fingolfin |
|---|---|---|---|
| Priority: | normal | Component: | --Other-- |
| Version: | Keywords: | ||
| Cc: | Game: |
Description
Attached you'll find a patch which rewrites Common::HashMap to use some ideas from the very efficient Python dictionary implementation (see also <http://svn.python.org/view/python/trunk/Objects/dictnotes.txt> and <http://svn.python.org/view/python/trunk/Objects/dictobject.c>).
Some of the highlights: * Hashtable sizes are now powers of 2, making it possible to replace expensive MOD operations by binary masking in the lookup code * collisions handling now does not use linear displacement, but rather a more clever strategy -- for details, refer to the Python code * instead of filling the table up to 75%, we reduced this to 2/3=67%, like in Python * the default table size has been reduced to 8, sufficient for up to 5 elements -- a quick test seems to indicate that this accounts for 98%+ of all HashMaps used in ScummVM (of course this may vary depending on what code you test, so take this with a grain of salt) * changed the string hash function to match that used in Python (this one is not mandatory, but since the CPython string hash is proven to work well with the CPython dictionary implementation, this seems like a good idea)
Some shortcoming / possible further improvements: * When there are not enough free slots left, we double the table size; in Python, they quadruple it as long as the table contains less than 5000 elements; that improves performance for tables which grow quickly (say when you have a table and want to insert 100 elements in one go) * Instead of storing _capacity, we could store _capacity-1 (in a new member var _mask), like CPython does; that would save one decrement when doing lookups, moving the cost (an increment) to rarely used functions. * In python, the initial storage for the HashMap is allocated inside the HashMap (i.e. an array of 8 Node pointers); we could do something like that, which would save us a malloc for many many HashMaps, while wasting 8*32 bytes for the rare large HashMaps)
Ticket imported from: #2062263. Ticket imported from: patches/1020.
Attachments (5)
Change History (12)
by , 16 years ago
| Attachment: | hashmap-py.patch added |
|---|
by , 16 years ago
| Attachment: | hashmap-py2.patch added |
|---|
comment:1 by , 16 years ago
Updated patch. It replaces the _capacity member by a _mask member, as suggested; incrases the minimal hashmap storage size from 8 to 16; and quadruples the storage when growing, as long as the table storage has less than 5000 entries.
File Added: hashmap-py2.patch
comment:2 by , 16 years ago
The 3rd revision of the patch also contains an improved MemoryPool implementation: It now provides some in-situ storage, sufficient to keep all elements of a small hashmap -- by default, set to HASHMAP_MIN_CAPACITY=16 elements, which is lower than the current pagesize default of 32. Hence for most hashmaps, one malloc is saved, *and* some heap.
Drawback of in-situ storage: This increases the size of a single HashMap object; for stack allocated HashMaps, this could cause problems on systems with a very small stack. Consider a string-string map: A string object is 40-44 bytes, times two for a String-String map, times 16 for a default pool size of 16, makes 1280-1408 bytes for the pool. On my Intel Mac, sizeof(Common::StringMap) is 1356 with this patch, but only 76 without it.
This problem could be lessened by using less than HASHMAP_MIN_CAPACITY initial elements; e.g. HASHMAP_MIN_CAPACITY * HASHMAP_LOADFACTOR_NUMERATOR / HASHMAP_LOADFACTOR_DENOMINATOR would give us exactly enough elements to completly fill a HashMap before it grows the first time. With the current settings, that would be 10 elements, so 6*40=240 to 6*44=264 bytes saved. And if we use HASHMAP_MIN_CAPACITY = 8 instead of 16 (like Python does), it gets even lower... you get the idea.
Other changes in this patch: * HashMap::clear now calls MemoryPool::freeUnusedPages * the memorypool now stores the size of each "page" it allocates. This should make it trivial to use pages of different sizes in the future. Like, doing exponential growth here, too, to match the HashMap's exponential growth: first time, allocate a 32 chunk page, 2nd page contains 64 chunks, then 128 chunks, etc.. This has not yet been implemented, but would be easy enough to do. File Added: hashmap-py3.patch
comment:3 by , 16 years ago
Rev 4: MemoryPool now grows exponentially. Also fixed a bug in the in-situ storage code, and some other tweaks. File Added: hashmap-py4.patch
comment:4 by , 16 years ago
Rev 5 fixes various bugs in freeUnusedPages. It also makes it possible to to use a FixedSizeMemoryPool with no in-situ storage (by specializing for NUM_INTERNAL_CHUNKS == 0), and reduced the default in-situ storage to HASHMAP_MIN_CAPACITY * HASHMAP_LOADFACTOR_NUMERATOR / HASHMAP_LOADFACTOR_DENOMINATOR which reduces the stack overhead somewhat. File Added: hashmap-py5.patch
comment:5 by , 16 years ago
I downloaded the v5 patch and quickly reviewed it, and tested it a bit and I didn't see any obvious problem (hear "crash", not "subtle leaks" :) ) And it seems flexible enough to integrate it on the trunk and tune the different magic constants later after a bit of stats gathering.
comment:6 by , 16 years ago
| Owner: | set to |
|---|---|
| Status: | new → closed |
comment:7 by , 5 years ago
| Component: | → --Other-- |
|---|
Revised patch