IdentityHashConsidered

=== Top of the Swiki === Attachments ===

IdentityHashConsidered

Some suggestions on generating hash code and minimizing object size.

Technique one is applicable when objects are NOT moved by the garbage collector. Because the address of an object is fixed, the object's address can be used in generating the hash code. For this scheme to work in the presence of snapshots, subtract the base address of the object space from the address. This yields a code whose value ranges over the size of the object space. The hash bits in the object header can be combined with such a value to extend the overall range of the hash code.

Technique two requires a copying garbage collector and assumes that most objects are never asked to reveal their hash code. In this scheme, objects whose hash is used, have an additional 32-bit slot that contains their hash code. Object's are initially created without a hash code and without the slot for holding the hash code. There are two bits in the object header that indicate the hash status of the object. The states that are encoded by these bits are:

No Hash
Lookaside Hash
Hash in Slot

The initial state is No Hash. The #basicHash (#identityHash in X3J20) primitive works as follows, depending upon that hash state:
No Hash: Assign a 32-bit hash value and store it in a hash look-aside table, keyed by the address of the receiver. Set state to Lookaside Hash.
Lookaside Hash: Use the address of the receiver to locate the object's hash in the look-aside table.
Hash in Slot: Return the value in the extended hash slot of the object.

When the garbage collector moves an object, it checks that hash state. If the hash state is Lookaside Hash, the collector allocates the extended hash slot, sets its value from the look-aside table and deletes it from the table, and sets the hash state to Hash in Slot. If a generational collector is used, a look-aside table can be allocated for each generation, and then discarded after its generation is collected.

The fourth state can be used to indicate a special hash computation. Example: the hash code of immutable objects such as symbols can be directly derived from the state of the object and does require an additional hash slot. {See next section}.

In some situations it is useful to be able to set an object's identity hash to a predetermined value. Example: this ability can be used to externalize/internalize hashed data structures without rehashing. But, an object's hash should only be setable if it has never revealed a hash value. The above scheme easily supports this. A "setHash" primitive is allowed to explicitly set an object's hash value if the object's hash state is No Hash. Otherwise the primitive fails. -- AllenWirfsBrock

----

I believe that should be "and does not require an additional hash."

If a hash can be calculated from an object's address or other immutable data, then no look aside table is needed. Each time you get to an object without "Hash in Slot" set, you just recalculate it. When the object moves, you then allocate the slot and store the calculated value. It must be immutable data, not instance variables, or the hash could change at different invocations. -- PatCaudill