[Scummvm-devel] Common::HashMap tuning

[Max Horn]

Am 28.08.2008 um 13:20 schrieb Kostas Nakos:

> On 08/28/2008 12:14 PM, Max Horn wrote:
>> 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.
>
> This could be a problem. I do not claim proficiency in the inner
> workings of ce's stack and heap handling, but: Currently, the port  
> runs
> with a maximum of 64K stack, and there are serious indications that  
> the
> stack cannot grow too much (perhaps not at all grow bigger than 64K  
> - at
> least for compatibility reasons with older devices). For a cut-down
> operating system like this, conceptually it may be too much to ask to
> juggle memory between stack <-> heap, so there may be some design
> decisions in the spirit of "the stack is from here to there and  
> that's it".
>
> Is it possible for the stringmap use dynamic allocation for the larger
> part of its memory? Perhaps 2 templated varsions for stack and heap
> based allocations? Also, about the malloc call minimization: Is this  
> for
> a reason like "to minimize heap fragmentation"?

Actually, if you look at the patch, it's fully customizable at run  
time. If desired, it can be set to user *0* extra stack space, so that  
in the end it will use the same stack space as it does now (~76 bytes)  
-- just switch the pool from a FixedSizeMemoryPool back to a regular  
MemoryPool (line 102 of common/hashmap.h). Or change the second param  
to a suitable low value, like 4 or 5 or whatever you like (for a  
String-String map, one node takes up 80 to 88 bytes (depending on  
whether you are on 32 or 64 bits). Go figure.

(I guess I could specialize FixedSizeMemoryPool to sen support a value  
of 0 for the second template param, for convenience).

But in general I wonder: How often do we actually allocate HashMaps of  
any kind on the stack?

Bye,
Max