Skip to content

Commit

Permalink
[Truffle] Fix hashing for compare_by_identity Hash.
Browse files Browse the repository at this point in the history 
* compare_by_identity hashes also need to get a hash value for choosing the right bucket.
* The hash value is useless for empty/packed hash but we need it when we promote to buckets.
  • Loading branch information
@eregon
eregon committed Oct 20, 2016
1 parent 3af802a commit e7da5df
Show file tree
Hide file tree
Showing 5 changed files with 44 additions and 27 deletions.
2 changes: 1 addition & 1 deletion truffle/src/main/java/org/jruby/truffle/core/hash/HashLiteralNode.java
View file
Expand Up @@ -112,7 +112,7 @@ public Object execute(VirtualFrame frame) {
}
}

final int hashed = hashNode.hash(frame, key);
final int hashed = hashNode.hash(frame, key, false);

final Object value = keyValues[n * 2 + 1].execute(frame);

Expand Down
21 changes: 19 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/core/hash/HashNode.java
View file
Expand Up @@ -9,17 +9,21 @@
*/
package org.jruby.truffle.core.hash;

import com.oracle.truffle.api.CompilerDirectives;
import com.oracle.truffle.api.frame.VirtualFrame;
import com.oracle.truffle.api.profiles.ConditionProfile;
import com.oracle.truffle.api.source.SourceSection;
import org.jruby.truffle.RubyContext;
import org.jruby.truffle.core.ObjectNodes.ObjectIDPrimitiveNode;
import org.jruby.truffle.core.ObjectNodesFactory.ObjectIDPrimitiveNodeFactory;
import org.jruby.truffle.language.RubyBaseNode;
import org.jruby.truffle.language.dispatch.CallDispatchHeadNode;
import org.jruby.truffle.language.dispatch.DispatchHeadNodeFactory;

public class HashNode extends RubyBaseNode {

@Child private CallDispatchHeadNode hashNode;
@Child private ObjectIDPrimitiveNode objectIDNode;

private final ConditionProfile isIntegerProfile = ConditionProfile.createBinaryProfile();
private final ConditionProfile isLongProfile = ConditionProfile.createBinaryProfile();
Expand All @@ -29,8 +33,13 @@ public HashNode(RubyContext context, SourceSection sourceSection) {
hashNode = DispatchHeadNodeFactory.createMethodCall(context, true);
}

public int hash(VirtualFrame frame, Object key) {
final Object hashedObject = hashNode.call(frame, key, "hash");
public int hash(VirtualFrame frame, Object key, boolean compareByIdentity) {
final Object hashedObject;
if (compareByIdentity) {
hashedObject = objectID(key);
} else {
hashedObject = hashNode.call(frame, key, "hash");
}

if (isIntegerProfile.profile(hashedObject instanceof Integer)) {
return (int) hashedObject;
Expand All @@ -41,4 +50,12 @@ public int hash(VirtualFrame frame, Object key) {
}
}

private Object objectID(Object object) {
if (objectIDNode == null) {
CompilerDirectives.transferToInterpreterAndInvalidate();
objectIDNode = insert(ObjectIDPrimitiveNodeFactory.create(null));
}
return objectIDNode.executeObjectID(object);
}

}
32 changes: 18 additions & 14 deletions truffle/src/main/java/org/jruby/truffle/core/hash/HashNodes.java
View file
Expand Up @@ -122,7 +122,7 @@ public Object construct(
final Object key = pairObjectStore[0];
final Object value = pairObjectStore[1];

final int hashed = hashNode.hash(frame, key);
final int hashed = hashNode.hash(frame, key, false);

PackedArrayStrategy.setHashedKeyValue(newStore, n, hashed, key, value);
}
Expand Down Expand Up @@ -206,7 +206,7 @@ public Object getNull(VirtualFrame frame, DynamicObject hash, Object key) {
"!isCompareByIdentity(hash)",
"cachedIndex >= 0",
"cachedIndex < getSize(hash)",
"hash(frame, key) == getHashedAt(hash, cachedIndex)",
"hashNotIdentity(frame, key) == getHashedAt(hash, cachedIndex)",
"eql(frame, key, getKeyAt(hash, cachedIndex))"
}, limit = "1")
public Object getConstantIndexPackedArray(VirtualFrame frame, DynamicObject hash, Object key,
Expand All @@ -228,8 +228,8 @@ public Object getConstantIndexPackedArrayByIdentity(VirtualFrame frame, DynamicO
return PackedArrayStrategy.getValue(store, cachedIndex);
}

protected int hash(VirtualFrame frame, Object key) {
return hashNode.hash(frame, key);
protected int hashNotIdentity(VirtualFrame frame, Object key) {
return hashNode.hash(frame, key, false);
}

protected int getHashedAt(DynamicObject hash, int index) {
Expand All @@ -247,16 +247,14 @@ protected int index(VirtualFrame frame, DynamicObject hash, Object key) {
return -1;
}

int hashed = 0;
if (!HashGuards.isCompareByIdentity(hash)) {
hashed = hashNode.hash(frame, key);
}
boolean compareByIdentity = HashGuards.isCompareByIdentity(hash);
int hashed = hashNode.hash(frame, key, compareByIdentity);

final Object[] store = (Object[]) Layouts.HASH.getStore(hash);
final int size = Layouts.HASH.getSize(hash);

for (int n = 0; n < size; n++) {
if (HashGuards.isCompareByIdentity(hash)) {
if (compareByIdentity) {
if (equal(key, PackedArrayStrategy.getKey(store, n))) {
return n;
}
Expand Down Expand Up @@ -291,7 +289,7 @@ protected boolean equal(Object key1, Object key2) {
public Object getPackedArray(VirtualFrame frame, DynamicObject hash, Object key,
@Cached("create()") BranchProfile notInHashProfile,
@Cached("create()") BranchProfile useDefaultProfile) {
final int hashed = hashNode.hash(frame, key);
final int hashed = hashNode.hash(frame, key, false);

final Object[] store = (Object[]) Layouts.HASH.getStore(hash);
final int size = Layouts.HASH.getSize(hash);
Expand Down Expand Up @@ -509,7 +507,7 @@ public Object deleteNull(VirtualFrame frame, DynamicObject hash, Object key, Dyn
public Object deletePackedArray(VirtualFrame frame, DynamicObject hash, Object key, Object maybeBlock) {
assert HashOperations.verifyStore(getContext(), hash);

final int hashed = hashNode.hash(frame, key);
final int hashed = hashNode.hash(frame, key, false);

final Object[] store = (Object[]) Layouts.HASH.getStore(hash);
final int size = Layouts.HASH.getSize(hash);
Expand Down Expand Up @@ -1357,7 +1355,13 @@ public DynamicObject rehashNull(DynamicObject hash) {
return hash;
}

@Specialization(guards = "isPackedHash(hash)")
@Specialization(guards = "isCompareByIdentity(hash)")
public DynamicObject rehashIdentity(DynamicObject hash) {
// the identity hash of objects never change.
return hash;
}

@Specialization(guards = {"isPackedHash(hash)", "!isCompareByIdentity(hash)"})
public DynamicObject rehashPackedArray(VirtualFrame frame, DynamicObject hash) {
assert HashOperations.verifyStore(getContext(), hash);

Expand All @@ -1366,7 +1370,7 @@ public DynamicObject rehashPackedArray(VirtualFrame frame, DynamicObject hash) {

for (int n = 0; n < getContext().getOptions().HASH_PACKED_ARRAY_MAX; n++) {
if (n < size) {
PackedArrayStrategy.setHashed(store, n, hashNode.hash(frame, PackedArrayStrategy.getKey(store, n)));
PackedArrayStrategy.setHashed(store, n, hashNode.hash(frame, PackedArrayStrategy.getKey(store, n), false));
}
}

Expand All @@ -1376,7 +1380,7 @@ public DynamicObject rehashPackedArray(VirtualFrame frame, DynamicObject hash) {
}

@TruffleBoundary
@Specialization(guards = "isBucketHash(hash)")
@Specialization(guards = {"isBucketHash(hash)", "!isCompareByIdentity(hash)"})
public DynamicObject rehashBuckets(DynamicObject hash) {
assert HashOperations.verifyStore(getContext(), hash);

Expand Down
5 changes: 3 additions & 2 deletions truffle/src/main/java/org/jruby/truffle/core/hash/LookupEntryNode.java
View file
Expand Up @@ -37,7 +37,8 @@ public LookupEntryNode(RubyContext context, SourceSection sourceSection) {
}

public HashLookupResult lookup(VirtualFrame frame, DynamicObject hash, Object key) {
final int hashed = hashNode.hash(frame, key);
final boolean compareByIdentity = byIdentityProfile.profile(Layouts.HASH.getCompareByIdentity(hash));
int hashed = hashNode.hash(frame, key, compareByIdentity);

final Entry[] entries = (Entry[]) Layouts.HASH.getStore(hash);
final int index = BucketsStrategy.getBucketIndex(hashed, entries.length);
Expand All @@ -46,7 +47,7 @@ public HashLookupResult lookup(VirtualFrame frame, DynamicObject hash, Object ke
Entry previousEntry = null;

while (entry != null) {
if (byIdentityProfile.profile(Layouts.HASH.getCompareByIdentity(hash))) {
if (compareByIdentity) {
if (equalNode.executeReferenceEqual(key, entry.getKey())) {
return new HashLookupResult(hashed, index, previousEntry, entry);
}
Expand Down
11 changes: 3 additions & 8 deletions truffle/src/main/java/org/jruby/truffle/core/hash/SetNode.java
View file
Expand Up @@ -66,10 +66,8 @@ public SetNode(RubyContext context, SourceSection sourceSection) {

@Specialization(guards = { "isNullHash(hash)", "!isRubyString(key)" })
public Object setNull(VirtualFrame frame, DynamicObject hash, Object key, Object value, boolean byIdentity) {
int hashed = 0;
if (!byIdentityProfile.profile(byIdentity)) {
hashed = hashNode.hash(frame, key);
}
boolean profiledByIdentity = byIdentityProfile.profile(byIdentity);
final int hashed = hashNode.hash(frame, key, profiledByIdentity);

Object store = PackedArrayStrategy.createStore(getContext(), hashed, key, value);
assert HashOperations.verifyStore(getContext(), store, 1, null, null);
Expand Down Expand Up @@ -99,10 +97,7 @@ public Object setPackedArray(VirtualFrame frame, DynamicObject hash, Object key,

boolean profiledByIdentity = byIdentityProfile.profile(byIdentity);

int hashed = 0;
if (!profiledByIdentity) {
hashed = hashNode.hash(frame, key);
}
int hashed = hashNode.hash(frame, key, profiledByIdentity);

final Object[] store = (Object[]) Layouts.HASH.getStore(hash);
final int size = Layouts.HASH.getSize(hash);
Expand Down

0 comments on commit e7da5df

Please sign in to comment.