[Vm-dev] Questions about hash

Mariano Martinez Peck marianopeck at gmail.com
Thu Jan 6 17:46:47 UTC 2011


On Thu, Jan 6, 2011 at 6:33 PM, Eliot Miranda <eliot.miranda at gmail.com>wrote:

>
>
>
> On Thu, Jan 6, 2011 at 6:23 AM, Mariano Martinez Peck <
> marianopeck at gmail.com> wrote:
>
>>
>> Hi folks. I am trying to understand a little how hash is assigned and how
>> it works in the SqueakVM. I have a couple of questions:
>>
>> 1) There are 12 bits in the ObjectHeader for the hash. I saw that the
>> value of this hash comes from #newObjectHash. But....this method answers a
>> hash of 16 bit:
>> newObjectHash
>>     "Answer a new 16-bit pseudo-random number for use as an identity
>> hash."
>>
>>     lastHash := 13849 + (27181 * lastHash) bitAnd: 65535.
>>     ^ lastHash
>>
>> Since in the OH we have 12 bits, each place where this method is used,
>> then we have to do something like this:
>>
>> header1 := (classFormat bitAnd: 16r1FF00) bitOr: (hash << HashBitsOffset
>> bitAnd: HashBits).
>>
>> or
>>
>>     hash := self newObjectHash.
>>     header := (self longAt: newOop) bitAnd: 16r1FFFF.
>>     "use old ccIndex, format, size, and header-type fields"
>>     header := header bitOr: ((hash << 17) bitAnd: 16r1FFE0000).
>>
>> ....
>> so, we always need to trim it to 12 bits using (hash << HashBitsOffset
>> bitAnd: HashBits).
>>
>> Now, I wonder, why #newObjectHash  does not answer a 12bits long hash
>> directly ?  is it because of the hash function performance?
>>
>>
>> 2)  It looks to me that not, but can it change the hash of an object? if
>> true, why and where?
>>
>> 3) If #basicIdentityHash is ONLY used for Sets and friends, why not
>> letting the hash assignment as late/lazy as possible? i mean, instead of
>> creating and assigning a hash at object creation, what if we do this in
>> #hashBitsOf: oop
>> where we can check in the hash is empty and if true assign one.
>> Would this make sense or it would be worst?
>>
>
> IMO it is far better and I will implement this in the new object
> representation.  VW has always had lazy hash creation.
>
>
Excellent. Marcus told me about this :)


> Note in Cog the hash is derived from the allocation pointer not from the
> pseudo-random hash generator, avoiding a read-modify-write cycle in object
> allocation.
>
>
Yeah, I saw it:

newObjectHash
    "Derive the new object hash from the allocation pointer.  This is less
costly than
     using lastHash because it avoids the read-modify-write cycle to update
lastHash.
     Since the size of eden is a power of two and larger than the hash range
this provides
     a well-distributed and fairly random set of values."
    <inline: true>
    ^freeStart >> BytesPerWord


> best
> Eliot
>
>
>> Thanks
>>
>> Mariano
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20110106/54d01b05/attachment-0001.htm


More information about the Vm-dev mailing list