Skip to content

Commit

Permalink
[Truffle] Work on Hash.
Browse files Browse the repository at this point in the history
@chrisseaton
chrisseaton committed Mar 9, 2015
1 parent c3662bc commit 1bed0dc
Showing 7 changed files with 107 additions and 150 deletions.
8 changes: 0 additions & 8 deletions spec/truffle/tags/core/hash/constructor_tags.txt
View file

This file was deleted.

1 change: 1 addition & 0 deletions spec/truffle/tags/core/hash/element_reference_tags.txt
View file
Original file line number Diff line number Diff line change
@@ -1,2 +1,3 @@
fails:Hash#[] calls subclass implementations of default
fails:Hash#[] finds a value via an identical key even when its #eql? isn't reflexive
fails:Hash#[] does not compare keys with different #hash values via #eql?
1 change: 1 addition & 0 deletions spec/truffle/tags/core/hash/eql_tags.txt
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
fails:Hash#eql? does not compare keys with different hash codes via eql?
1 change: 1 addition & 0 deletions spec/truffle/tags/core/hash/equal_value_tags.txt
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
fails:Hash#== does not compare keys with different hash codes via eql?
1 change: 1 addition & 0 deletions spec/truffle/tags/core/hash/rehash_tags.txt
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
fails:Hash#rehash reorganizes the hash by recomputing all key hash codes
201 changes: 59 additions & 142 deletions truffle/src/main/java/org/jruby/truffle/nodes/core/HashNodes.java
View file
Original file line number Diff line number Diff line change
@@ -117,135 +117,10 @@ public boolean equalNonHash(RubyHash a, Object b) {

}

@CoreMethod(names = "[]", onSingleton = true, argumentsAsArray = true, reallyDoesNeedSelf = true)
public abstract static class ConstructNode extends HashCoreMethodNode {

private final BranchProfile singleObject = BranchProfile.create();
private final BranchProfile singleArray = BranchProfile.create();
private final BranchProfile objectArray = BranchProfile.create();
private final BranchProfile smallPackedArray = BranchProfile.create();
private final BranchProfile largePackedArray = BranchProfile.create();
private final BranchProfile otherArray = BranchProfile.create();
private final BranchProfile singleOther = BranchProfile.create();
private final BranchProfile otherHash = BranchProfile.create();
private final BranchProfile keyValues = BranchProfile.create();

public ConstructNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
}

public ConstructNode(ConstructNode prev) {
super(prev);
}

@ExplodeLoop
@Specialization
public RubyHash construct(RubyClass hashClass, Object[] args) {
if (args.length == 1) {
singleObject.enter();

final Object arg = args[0];

if (arg instanceof RubyArray) {
singleArray.enter();

final RubyArray array = (RubyArray) arg;

if (array.getStore() instanceof Object[]) {
objectArray.enter();

final Object[] store = (Object[]) array.getStore();

// TODO(CS): zero length arrays might be a good specialisation

if (store.length <= HashOperations.SMALL_HASH_SIZE) {
smallPackedArray.enter();

final int size = array.getSize();
final Object[] newStore = new Object[HashOperations.SMALL_HASH_SIZE * 2];

for (int n = 0; n < HashOperations.SMALL_HASH_SIZE; n++) {
if (n < size) {
final Object pair = store[n];

if (!(pair instanceof RubyArray)) {
CompilerDirectives.transferToInterpreter();
throw new UnsupportedOperationException();
}

final RubyArray pairArray = (RubyArray) pair;

if (!(pairArray.getStore() instanceof Object[])) {
CompilerDirectives.transferToInterpreter();
throw new UnsupportedOperationException();
}

final Object[] pairStore = (Object[]) pairArray.getStore();

newStore[n * 2] = pairStore[0];
newStore[n * 2 + 1] = pairStore[1];
}
}

return new RubyHash(hashClass, null, null, newStore, size, null);
} else {
largePackedArray.enter();

final List<KeyValue> keyValues = new ArrayList<>();

final int size = array.getSize();

for (int n = 0; n < size; n++) {
final Object pair = store[n];

if (!(pair instanceof RubyArray)) {
CompilerDirectives.transferToInterpreter();
throw new UnsupportedOperationException();
}

final RubyArray pairArray = (RubyArray) pair;

if (!(pairArray.getStore() instanceof Object[])) {
CompilerDirectives.transferToInterpreter();
throw new UnsupportedOperationException();
}

final Object[] pairStore = (Object[]) pairArray.getStore();
keyValues.add(new KeyValue(pairStore[0], pairStore[1]));
}

return HashOperations.verySlowFromEntries(hashClass, keyValues, false);
}
} else {
otherArray.enter();
throw new UnsupportedOperationException("other array");
}
} else if (arg instanceof RubyHash) {
otherHash.enter();

return HashOperations.verySlowFromEntries(hashClass, HashOperations.verySlowToKeyValues((RubyHash) arg), false);
} else {
singleOther.enter();
throw new UnsupportedOperationException("single other");
}
} else {
keyValues.enter();

final List<KeyValue> entries = new ArrayList<>();

for (int n = 0; n < args.length; n += 2) {
entries.add(new KeyValue(args[n], args[n + 1]));
}

return HashOperations.verySlowFromEntries(hashClass, entries, false);
}
}

}

@CoreMethod(names = "[]", required = 1)
public abstract static class GetIndexNode extends HashCoreMethodNode {


@Child private CallDispatchHeadNode hashNode;
@Child private CallDispatchHeadNode eqlNode;
@Child private BasicObjectNodes.ReferenceEqualNode equalNode;
@Child private YieldDispatchHeadNode yield;
@@ -259,6 +134,7 @@ public abstract static class GetIndexNode extends HashCoreMethodNode {

public GetIndexNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
hashNode = DispatchHeadNodeFactory.createMethodCall(context, true);
eqlNode = DispatchHeadNodeFactory.createMethodCall(context, false, false, null);
equalNode = BasicObjectNodesFactory.ReferenceEqualNodeFactory.create(context, sourceSection, null, null);
yield = new YieldDispatchHeadNode(context);
@@ -267,6 +143,7 @@ public GetIndexNode(RubyContext context, SourceSection sourceSection) {

public GetIndexNode(GetIndexNode prev) {
super(prev);
hashNode = prev.hashNode;
eqlNode = prev.eqlNode;
equalNode = prev.equalNode;
yield = prev.yield;
@@ -280,6 +157,8 @@ public GetIndexNode(GetIndexNode prev) {
public Object getNull(VirtualFrame frame, RubyHash hash, Object key) {
notDesignedForCompilation();

hashNode.call(frame, key, "hash", null);

if (undefinedValue != null) {
return undefinedValue;
} else if (hash.getDefaultBlock() != null) {
@@ -294,6 +173,8 @@ public Object getNull(VirtualFrame frame, RubyHash hash, Object key) {
@ExplodeLoop
@Specialization(guards = {"!isNull", "!isBuckets"})
public Object getPackedArray(VirtualFrame frame, RubyHash hash, Object key) {
hashNode.call(frame, key, "hash", null);

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

@@ -302,9 +183,9 @@ public Object getPackedArray(VirtualFrame frame, RubyHash hash, Object key) {
final boolean equal;

if (byIdentityProfile.profile(hash.isCompareByIdentity())) {
equal = equalNode.executeReferenceEqual(frame, store[n * 2], key);
equal = equalNode.executeReferenceEqual(frame, key, store[n * 2]);
} else {
equal = eqlNode.callBoolean(frame, store[n * 2], "eql?", null, key);
equal = eqlNode.callBoolean(frame, key, "eql?", null, store[n * 2]);
}

if (equal) {
@@ -360,7 +241,6 @@ public Object getBuckets(VirtualFrame frame, RubyHash hash, Object key) {

public void setUndefinedValue(Object undefinedValue) {
this.undefinedValue = undefinedValue;

}

}
@@ -391,6 +271,7 @@ public Object getOrUndefined(VirtualFrame frame, RubyHash hash, Object key) {
@CoreMethod(names = "[]=", required = 2, raiseIfFrozenSelf = true)
public abstract static class SetIndexNode extends HashCoreMethodNode {

@Child private CallDispatchHeadNode hashNode;
@Child private CallDispatchHeadNode eqlNode;
@Child private BasicObjectNodes.ReferenceEqualNode equalNode;

@@ -400,28 +281,43 @@ public abstract static class SetIndexNode extends HashCoreMethodNode {

public SetIndexNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
hashNode = DispatchHeadNodeFactory.createMethodCall(context, true);
eqlNode = DispatchHeadNodeFactory.createMethodCall(context, false, false, null);
equalNode = BasicObjectNodesFactory.ReferenceEqualNodeFactory.create(context, sourceSection, null, null);
}

public SetIndexNode(SetIndexNode prev) {
super(prev);
hashNode = prev.hashNode;
eqlNode = prev.eqlNode;
equalNode = prev.equalNode;
}

@Specialization(guards = "isNull")
public Object setNull(RubyHash hash, Object key, Object value) {
@Specialization(guards = {"isNull", "!isRubyString(arguments[1])"})
public Object setNull(VirtualFrame frame, RubyHash hash, Object key, Object value) {
final Object[] store = new Object[HashOperations.SMALL_HASH_SIZE * 2];
hashNode.call(frame, key, "hash", null);
store[0] = key;
store[1] = value;
hash.setStore(store, 1, null, null);
return value;
}

@Specialization(guards = "isNull")
public Object setNull(VirtualFrame frame, RubyHash hash, RubyString key, Object value) {
notDesignedForCompilation();
if (hash.isCompareByIdentity()) {
return setNull(frame, hash, (Object) key, value);
} else {
return setNull(frame, hash, ruby(frame, "key.dup.freeze", "key", key), value);
}
}

@ExplodeLoop
@Specialization(guards = {"!isNull", "!isBuckets"})
@Specialization(guards = {"!isNull", "!isBuckets", "!isRubyString(arguments[1])"})
public Object setPackedArray(VirtualFrame frame, RubyHash hash, Object key, Object value) {
hashNode.call(frame, key, "hash", null);

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

@@ -430,9 +326,9 @@ public Object setPackedArray(VirtualFrame frame, RubyHash hash, Object key, Obje
final boolean equal;

if (byIdentityProfile.profile(hash.isCompareByIdentity())) {
equal = equalNode.executeReferenceEqual(frame, store[n * 2], key);
equal = equalNode.executeReferenceEqual(frame, key, store[n * 2]);
} else {
equal = eqlNode.callBoolean(frame, store[n * 2], "eql?", null, key);
equal = eqlNode.callBoolean(frame, key, "eql?", null, store[n * 2]);
}

if (equal) {
@@ -463,15 +359,25 @@ public Object setPackedArray(VirtualFrame frame, RubyHash hash, Object key, Obje
hash.setStore(new Entry[HashOperations.capacityGreaterThan(newSize)], newSize, null, null);

for (KeyValue keyValue : entries) {
HashOperations.verySlowSetInBuckets(hash, keyValue.getKey(), keyValue.getValue(), false);
HashOperations.verySlowSetInBuckets(hash, keyValue.getKey(), keyValue.getValue(), hash.isCompareByIdentity());
}

HashOperations.verySlowSetInBuckets(hash, key, value, false);

return value;
}

@Specialization(guards = "isBuckets")
@Specialization(guards = {"!isNull", "!isBuckets"})
public Object setPackedArray(VirtualFrame frame, RubyHash hash, RubyString key, Object value) {
notDesignedForCompilation();
if (hash.isCompareByIdentity()) {
return setPackedArray(frame, hash, (Object) key, value);
} else {
return setPackedArray(frame, hash, ruby(frame, "key.dup.freeze", "key", key), value);
}
}

@Specialization(guards = {"isBuckets", "!isRubyString(arguments[1])"})
public Object setBuckets(RubyHash hash, Object key, Object value) {
notDesignedForCompilation();

@@ -482,6 +388,12 @@ public Object setBuckets(RubyHash hash, Object key, Object value) {
return value;
}

@Specialization(guards = "isBuckets")
public Object setBuckets(VirtualFrame frame, RubyHash hash, RubyString key, Object value) {
notDesignedForCompilation();
return setBuckets(hash, ruby(frame, "key.dup.freeze", "key", key), value);
}

}

@CoreMethod(names = "clear", raiseIfFrozenSelf = true)
@@ -792,10 +704,11 @@ public RubyHash initialize(RubyHash hash, UndefinedPlaceholder defaultValue, Rub
return hash;
}

@Specialization
@Specialization(guards = "!isUndefinedPlaceholder(arguments[1])")
public RubyHash initialize(RubyHash hash, Object defaultValue, UndefinedPlaceholder block) {
notDesignedForCompilation();
hash.setDefaultValue(defaultValue);
hash.setDefaultBlock(null);
return hash;
}

@@ -1029,18 +942,21 @@ public RubyHash mergePackedArrayPackedArray(VirtualFrame frame, RubyHash hash, R
final int storeASize = hash.getSize();

final Object[] storeB = (Object[]) other.getStore();
final int storeBSize = hash.getSize();
final int storeBSize = other.getSize();

final boolean[] mergeFromA = new boolean[storeASize];
int mergeFromACount = 0;

int conflictsCount = 0;

for (int a = 0; a < HashOperations.SMALL_HASH_SIZE; a++) {
if (a < storeASize) {
boolean merge = true;

for (int b = 0; b < HashOperations.SMALL_HASH_SIZE; b++) {
if (b < storeBSize) {
if (eqlNode.callBoolean(frame, storeA[a * 2], "eql?", null, storeB[b * 2])) {
conflictsCount++;
merge = false;
break;
}
@@ -1062,9 +978,9 @@ public RubyHash mergePackedArrayPackedArray(VirtualFrame frame, RubyHash hash, R

considerNothingFromSecondProfile.enter();

if (mergeFromACount == storeB.length) {
if (conflictsCount == storeBSize) {
nothingFromSecondProfile.enter();
return new RubyHash(hash.getLogicalClass(), hash.getDefaultBlock(), hash.getDefaultValue(), Arrays.copyOf(storeB, HashOperations.SMALL_HASH_SIZE * 2), storeBSize, null);
return new RubyHash(hash.getLogicalClass(), hash.getDefaultBlock(), hash.getDefaultValue(), Arrays.copyOf(storeA, HashOperations.SMALL_HASH_SIZE * 2), storeASize, null);
}

considerResultIsSmallProfile.enter();
@@ -1096,7 +1012,8 @@ public RubyHash mergePackedArrayPackedArray(VirtualFrame frame, RubyHash hash, R
}

CompilerDirectives.transferToInterpreter();
throw new UnsupportedOperationException();

return mergeBucketsBuckets(hash, other, block);
}

// TODO CS 3-Mar-15 need negative guards on this
44 changes: 44 additions & 0 deletions truffle/src/main/ruby/core/rubinius/common/hash.rb
View file
Original file line number Diff line number Diff line change
@@ -368,4 +368,48 @@ def ==(other)
true
end

def self.[](*args)
if args.size == 1
obj = args.first
if hash = Rubinius::Type.check_convert_type(obj, Hash, :to_hash)
new_hash = allocate.replace(hash)
new_hash.default = nil
return new_hash
elsif associate_array = Rubinius::Type.check_convert_type(obj, Array, :to_ary)
return new_from_associate_array(associate_array)
end
end

return new if args.empty?

if args.size & 1 == 1
raise ArgumentError, "Expected an even number, got #{args.length}"
end

hash = new
i = 0
total = args.size

while i < total
hash[args[i]] = args[i+1]
i += 2
end

hash
end

def self.new_from_associate_array(associate_array)
hash = new
associate_array.each do |array|
next unless array.respond_to? :to_ary
array = array.to_ary
unless (1..2).cover? array.size
raise ArgumentError, "invalid number of elements (#{array.size} for 1..2)"
end
hash[array.at(0)] = array.at(1)
end
hash
end
private_class_method :new_from_associate_array

end

0 comments on commit 1bed0dc

Please sign in to comment.