Opened 12 years ago

Closed 12 years ago

Last modified 2 years ago

#8915 closed patch

COMMON: Revised HashMap implementation

Reported by: fingolfin Owned by: fingolfin
Priority: normal Component: --Other--
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)

hashmap-py.patch (10.7 KB ) - added by fingolfin 12 years ago.
hashmap-py2.patch (14.8 KB ) - added by fingolfin 12 years ago.
Revised patch
hashmap-py3.patch (19.0 KB ) - added by fingolfin 12 years ago.
3rd revision
hashmap-py4.patch (21.0 KB ) - added by fingolfin 12 years ago.
4th revision
hashmap-py5.patch (21.6 KB ) - added by fingolfin 12 years ago.
5th revision

Download all attachments as: .zip

Change History (12)

by fingolfin, 12 years ago

Attachment: hashmap-py.patch added

by fingolfin, 12 years ago

Attachment: hashmap-py2.patch added

Revised patch

comment:1 by fingolfin, 12 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

by fingolfin, 12 years ago

Attachment: hashmap-py3.patch added

3rd revision

comment:2 by fingolfin, 12 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

by fingolfin, 12 years ago

Attachment: hashmap-py4.patch added

4th revision

comment:3 by fingolfin, 12 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

by fingolfin, 12 years ago

Attachment: hashmap-py5.patch added

5th revision

comment:4 by fingolfin, 12 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 tramboi, 12 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 fingolfin, 12 years ago

Owner: set to fingolfin
Status: newclosed

comment:7 by digitall, 2 years ago

Component: --Other--
Note: See TracTickets for help on using tickets.