[VI4] more hash bits? [was: Re: Need an efficient large weak identity key dictionary]

Stephan Rudlof sr at evolgo.de
Mon Aug 12 11:18:00 UTC 2002


Andreas Raab wrote:
> Stephen,
> 
> 
>>I'm thinking about hacking out such a thing (I'm not exactly sure what
>>to name it...suggestions)...also, I'd like to hear opinions on this
>>topic (i.e. is it needed? are there any flaws in my arguments?).
> 
> 
> It sounds good to me - I know that we need such a beast for a variety of
> reasons so making a general thing out of it could help a variety of
> places. Your arguments sound very reasonable to me and since you've been
> to the places where the current stuff really hurts I couldn't think of
> anyone better suited for this task.

> One minor note perhaps: You might
> think about including the object's class identity hash for getting
> better spread - since many of these registries will have highly
> polymorphic keys this may help quite a bit to overcome

We should keep this in mind for a potential later general purpose hashing
function for objects.

> the current
> limitations of the 12 bit hashes.

Is it planned to extend these 12 bits for VI4?


Is it planned to extend the hash bits in the object header of some objects,
e.g. objects not being SmallIntegers or Symbols? Lesser bits for internal
identity hashes (optimized for method dictionaries, 12 bits may be
sufficient here) and more for caching a more sophisticated (slower to
compute) hash for large collections (larger than 2**12 elements)?

Or would it be better to have two hash fields for all objects except
SmallIntegers: the smaller standard one and one larger (since there may be
large Dictionaries/Sets/whatever using Symbols as keys)?


Or is it planned to leave it as it is?


Greetings,

Stephan

> 
> Cheers,
>   - Andreas
> 
> 
>>-----Original Message-----
>>From: squeak-dev-admin at lists.squeakfoundation.org 
>>[mailto:squeak-dev-admin at lists.squeakfoundation.org] On 
>>Behalf Of Stephen Pair
>>Sent: Sunday, August 11, 2002 4:04 PM
>>To: squeak-dev at lists.squeakfoundation.org
>>Subject: Need an efficient large weak identity key dictionary
>>
>>
>>The need to associate extended attributes with potentially very large
>>subsets of the objects in memory seem to me to be a very common
>>occurrence.  It's needed for the DependentsFields and the EventsFields
>>(even though neither of those seem to get heavily used).  It's also
>>needed in virtually any persistence or distributed object 
>>framework.  I
>>could have used it for my Kats transaction service and made 
>>things a bit
>>simpler and more general.
>>
>>The best way of doing this (aside from modifying the VM to 
>>add a special
>>slot) is of course to use a hashed structure.  We have
>>WeakIdentityKeyDictionary, however is suffers from a few problems:
>>
>>A) The optimization to spread the hash when the array grows 
>>larger than
>>4096 slots that is in IdentityDictionary was never added to
>>WeakIdentityKeyDictionary.  A small test that adds 10000 items to the
>>dictionary went from 150 seconds to just 5.5 seconds on my 
>>machine after
>>making that change.
>>
>>B) When such a collection does grow very large, it has to potential to
>>impact incremental GC performance if that collections is in 
>>young space,
>>or if it is marked as a root.
>>
>>I think that without modifying the VM, we could get a reasonably good
>>WeakIdentityKeyDictionary if we add the optimization 
>>mentioned in A, and
>>if we break up the WeakIdentityKeyDictionary's array into a set of
>>smaller arrays.  I have an implementation of a LargeArray that does
>>exactly this that could be used.  The LargeArray simply 
>>breaks an array
>>up into a number of smaller chunks.
>>
>>I'm thinking about hacking out such a thing (I'm not exactly sure what
>>to name it...suggestions)...also, I'd like to hear opinions on this
>>topic (i.e. is it needed? are there any flaws in my arguments?).
>>
>>- Stephen
>>
>>
> 
> 
> 
> 



-- 
Stephan Rudlof (sr at evolgo.de)
   "Genius doesn't work on an assembly line basis.
    You can't simply say, 'Today I will be brilliant.'"
    -- Kirk, "The Ultimate Computer", stardate 4731.3




More information about the Squeak-dev mailing list