RVM

System identity hashcodes aren't very random

Details

  • Type: Improvement Improvement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: 1000
  • Component/s: Runtime
  • Labels:
    None
  • Number of attachments :
    0

Description

The identity hashcodes of objects is their initial address. This means the bottom bits of the hashcode will always be 0 and for a generational GC hashcode collisions are quite likely. We should probably do a better job and have a more random identity hash code that will result in fewer hashtable collisions and the like.

This is inspired by analysis performed Jimmy, Jing Lv on the use of the Harmony HashMap:
http://mail-archives.apache.org/mod_mbox/harmony-dev/200707.mbox/raw/%3c5c8e69f0707032218i159b99cbu84b29a5d469469eb@mail.gmail.com%3e

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Daniel Frampton added a comment - - edited

Why anyone would return a raw address as a hashcode I can only guess..

Our address based hashing function is

ADDRESS >>> LOG_BYTES_IN_ADDRESS

As we sometimes 8 byte align objects, the distribution of our hash will be uneven and give more even numbers than odd..

We should improve it by making it:

ADDRESS >>> LOG_MAX_ALIGNMENT

where LOG_MAX_ALIGNMENT is currently 8 for intel I believe.

J9 appears to have made a similar mistake in that all values are even. Perhaps they didn't keep their hash in sync with their minimum alignment?

Show
Daniel Frampton added a comment - - edited Why anyone would return a raw address as a hashcode I can only guess.. Our address based hashing function is ADDRESS >>> LOG_BYTES_IN_ADDRESS As we sometimes 8 byte align objects, the distribution of our hash will be uneven and give more even numbers than odd.. We should improve it by making it: ADDRESS >>> LOG_MAX_ALIGNMENT where LOG_MAX_ALIGNMENT is currently 8 for intel I believe. J9 appears to have made a similar mistake in that all values are even. Perhaps they didn't keep their hash in sync with their minimum alignment?
Hide
Permalink
Daniel Frampton added a comment -

To clarify the situation with J9, with a silly test program I wrote, the hash values have a remainder of 0 or 2 when divided by 4.

We and Sun have a reasonably even distribution of 0 1 2 and 3

If they were just returning addresses we would expect always 0.

For info:

hash % x = 0 / 1 / 2 / 3
------------------------------------------------
IBM1.5.0 280 / 0 / 288 / 0
JDK1.6.0 141 / 176 / 124 / 127
JikesRVM 142 / 143 / 142 / 141

Show
Daniel Frampton added a comment - To clarify the situation with J9, with a silly test program I wrote, the hash values have a remainder of 0 or 2 when divided by 4. We and Sun have a reasonably even distribution of 0 1 2 and 3 If they were just returning addresses we would expect always 0. For info: hash % x = 0 / 1 / 2 / 3 ------------------------------------------------ IBM1.5.0 280 / 0 / 288 / 0 JDK1.6.0 141 / 176 / 124 / 127 JikesRVM 142 / 143 / 142 / 141

People

  • Assignee:
    Unassigned
    Reporter:
    Ian Rogers
Vote (0)
Watch (0)

Dates

  • Created:
    Updated: