[Scummvm-devel] Common::HashMap tuning (was: Kyrandia engine loading is slow on the DS)

Max Horn max at quendi.de
Thu Aug 28 11:14:56 CEST 2008


Am 24.08.2008 um 18:59 schrieb Max Horn:

>
> Am 23.08.2008 um 13:34 schrieb Bertrand Augereau:
>
>> Well, if I got it right, the map is expanded when it is 66% full
>> instead of 75% so this might have an impact, no?
>>
>
> You are absolutely right, I forgot about that -- though I *think* it
> should be a rather minor point (I was considering making this more
> easily tunable, too, BTW).

>
>> I doubt this is an issue though.
>>
> Aye ;)
>> Some changes should be done to the memory pool anyway that would
>> have an influence on the hashmaps:
>>
>> * it should grow exponentially instead of linearly
>>
>> * it might have a template size_t parameter that describe in situ
>> storage that is served before heap memory.
>>



FYI, I updated the patch at <https://sourceforge.net/tracker/index.php?func=detail&aid=2062263&group_id=37116&atid=418822 
 >.
Some of the changes:
* You can now easily set it to fill to 75% instead of 66%, for testing.
* MemoryPool supports some in-situ storage
* MemoryPool refactored to make it easier to implement exponential  
instead of linear grow (to match the exp grow of the HashMap)
* Various other tweaks to HashMap to make it perform even better.

With this patch, a fresh StringMap can store up to 10 key/value pairs  
with one single malloc, assuming the strings are at most 32 chars long  
each. Drawback: The StringMap takes 1356 bytes (on a 32bit machine) of  
stack space, instead of the 76 it takes now (note that in total, the  
current StringMap always consumes at least 2772 bytes of *heap*  
storage -- so in total, we save memory, but also shift some of it from  
heap to stack). This could be reduced down to say 476 or 876 bytes of  
stack storage, depending on certain easily tweakable params. See the  
tracker item for some more details.

It would be nice if this would receive some testing / review.

Cheers,
Max




More information about the Scummvm-devel mailing list