Skip to content

Commit

Permalink
[Truffle] Tidy up Hash#merge
Browse files Browse the repository at this point in the history
  • Loading branch information
@chrisseaton
chrisseaton committed Jun 13, 2015
1 parent 3d8ecfe commit 6734214
Show file tree
Hide file tree
Showing 2 changed files with 223 additions and 53 deletions.
229 changes: 179 additions & 50 deletions truffle/src/main/java/org/jruby/truffle/nodes/core/hash/HashNodes.java
View file
Original file line number Diff line number Diff line change
Expand Up @@ -868,37 +868,7 @@ public RubyBasicObject replaceBuckets(RubyBasicObject self, RubyBasicObject from
return self;
}

final Entry[] newEntries = new Entry[((Entry[]) getStore(from)).length];

Entry firstInSequence = null;
Entry lastInSequence = null;

Entry entry = getFirstInSequence(from);

while (entry != null) {
final Entry newEntry = new Entry(entry.getHashed(), entry.getKey(), entry.getValue());

final int index = BucketsStrategy.getBucketIndex(entry.getHashed(), newEntries.length);

newEntry.setNextInLookup(newEntries[index]);
newEntries[index] = newEntry;

if (firstInSequence == null) {
firstInSequence = newEntry;
}

if (lastInSequence != null) {
lastInSequence.setNextInSequence(newEntry);
newEntry.setPreviousInSequence(lastInSequence);
}

lastInSequence = newEntry;

entry = entry.getNextInSequence();
}

setStore(self, newEntries, getSize(from), firstInSequence, lastInSequence);
//HashOperations.verySlowSetKeyValues(self, HashNodes.iterableKeyValues(from), isCompareByIdentity(from));
BucketsStrategy.copyInto(from, self);
copyOtherFields(self, from);

assert verifyStore(self);
Expand Down Expand Up @@ -1012,24 +982,80 @@ public abstract static class MergeNode extends YieldingCoreMethodNode {
private final BranchProfile nothingFromSecondProfile = BranchProfile.create();
private final BranchProfile considerResultIsSmallProfile = BranchProfile.create();
private final BranchProfile resultIsSmallProfile = BranchProfile.create();
private final BranchProfile promoteProfile = BranchProfile.create();

public MergeNode(RubyContext context, SourceSection sourceSection) {
super(context, sourceSection);
eqlNode = DispatchHeadNodeFactory.createMethodCall(context);
setNode = SetNodeGen.create(context, sourceSection, null, null, null, null);
}

@Specialization(guards = {"isPackedHash(hash)", "isRubyHash(other)", "isNullHash(other)", "!isCompareByIdentity(hash)"})
public RubyBasicObject mergePackedArrayNull(RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
// Merge with an empty hash, without a block

@Specialization(guards = {
"isNullHash(hash)",
"isRubyHash(other)",
"isNullHash(other)"
})
public RubyBasicObject mergeEmptyEmpty(RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
return createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), null, 0, null, null);
}

@Specialization(guards = {
"isEmptyHash(hash)",
"isRubyHash(other)",
"isPackedHash(other)"
})
public RubyBasicObject mergeEmptyPacked(RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
final Object[] store = (Object[]) getStore(other);
final Object[] copy = PackedArrayStrategy.copyStore(store);
return createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), copy, getSize(hash), null, null);
}

@Specialization(guards = {
"isPackedHash(hash)",
"isRubyHash(other)",
"isEmptyHash(other)"
})
public RubyBasicObject mergePackedEmpty(RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
final Object[] store = (Object[]) getStore(hash);
final Object[] copy = PackedArrayStrategy.copyStore(store);
return createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), copy, getSize(hash), null, null);
}

@Specialization(guards = {
"isEmptyHash(hash)",
"isRubyHash(other)",
"isBucketHash(other)"
})
public RubyBasicObject mergeEmptyBuckets(RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
final RubyBasicObject merged = createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), null, 0, null, null);
BucketsStrategy.copyInto(other, merged);
return merged;
}

@Specialization(guards = {
"isBucketHash(hash)",
"isRubyHash(other)",
"isEmptyHash(other)"
})
public RubyBasicObject mergeBucketsEmpty(RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
final RubyBasicObject merged = createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), null, 0, null, null);
BucketsStrategy.copyInto(hash, merged);
return merged;
}

// Merge non-empty packed with non-empty packed, without a block

@ExplodeLoop
@Specialization(guards = {"isPackedHash(hash)", "isRubyHash(other)", "isPackedHash(other)", "!isCompareByIdentity(hash)"})
public RubyBasicObject mergePackedArrayPackedArray(VirtualFrame frame, RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
// TODO(CS): what happens with the default block here? Which side does it get merged from?
@Specialization(guards = {
"isPackedHash(hash)",
"!isEmptyHash(hash)",
"isRubyHash(other)",
"isPackedHash(other)",
"!isEmptyHash(other)",
"!isCompareByIdentity(hash)"})
public RubyBasicObject mergePackedPacked(VirtualFrame frame, RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
assert verifyStore(hash);
assert verifyStore(other);

Expand All @@ -1039,6 +1065,8 @@ public RubyBasicObject mergePackedArrayPackedArray(VirtualFrame frame, RubyBasic
final Object[] storeB = (Object[]) getStore(other);
final int storeBSize = getSize(other);

// Go through and figure out what gets merged from each hash

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

Expand Down Expand Up @@ -1066,20 +1094,30 @@ public RubyBasicObject mergePackedArrayPackedArray(VirtualFrame frame, RubyBasic
}
}

// If nothing comes from A, it's easy

if (mergeFromACount == 0) {
nothingFromFirstProfile.enter();
return createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), PackedArrayStrategy.copyStore(storeB), storeBSize, null, null);
}

// Cut off here

considerNothingFromSecondProfile.enter();

// If everything in B conflicted with something in A, it's easy

if (conflictsCount == storeBSize) {
nothingFromSecondProfile.enter();
return createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), PackedArrayStrategy.copyStore(storeA), storeASize, null, null);
}

// Cut off here

considerResultIsSmallProfile.enter();

// More complicated case where some things from each hash, but it still fits in a packed array

final int mergedSize = storeBSize + mergeFromACount;

if (storeBSize + mergeFromACount <= PackedArrayStrategy.MAX_ENTRIES) {
Expand Down Expand Up @@ -1110,33 +1148,122 @@ public RubyBasicObject mergePackedArrayPackedArray(VirtualFrame frame, RubyBasic
return createHash(hash.getLogicalClass(), getDefaultBlock(hash), getDefaultValue(hash), merged, mergedSize, null, null);
}

return mergeBucketsBuckets(frame, hash, other, block);
// Most complicated cases where things from both hashes, and it also needs to be promoted to buckets

promoteProfile.enter();

final RubyBasicObject merged = createHash(hash.getLogicalClass(), null, null, new Entry[BucketsStrategy.capacityGreaterThan(mergedSize)], 0, null, null);

for (int n = 0; n < storeASize; n++) {
if (mergeFromA[n]) {
setNode.executeSet(frame, merged, PackedArrayStrategy.getKey(storeA, n), PackedArrayStrategy.getValue(storeA, n), false);
}
}

for (int n = 0; n < storeBSize; n++) {
setNode.executeSet(frame, merged, PackedArrayStrategy.getKey(storeB, n), PackedArrayStrategy.getValue(storeB, n), false);
}

assert verifyStore(hash);

return merged;
}

// TODO CS 3-Mar-15 need negative guards on this
@Specialization(guards = {"!isCompareByIdentity(hash)", "isRubyHash(other)"})

// Merge non-empty buckets with non-empty buckets, without a block

@Specialization(guards = {
"isBucketHash(hash)",
"!isEmptyHash(hash)",
"isRubyHash(other)",
"isBucketHash(other)",
"!isEmptyHash(other)"
})
public RubyBasicObject mergeBucketsBuckets(VirtualFrame frame, RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
CompilerDirectives.transferToInterpreter();
final boolean isCompareByIdentity = isCompareByIdentity(hash);

final RubyBasicObject merged = createHash(hash.getLogicalClass(), null, null, new Entry[BucketsStrategy.capacityGreaterThan(getSize(hash) + getSize(other))], 0, null, null);

for (Map.Entry<Object, Object> keyValue : HashNodes.iterableKeyValues(hash)) {
setNode.executeSet(frame, merged, keyValue.getKey(), keyValue.getValue(), false);
for (Map.Entry<Object, Object> keyValue : BucketsStrategy.iterableKeyValues(HashNodes.getFirstInSequence(hash))) {
setNode.executeSet(frame, merged, keyValue.getKey(), keyValue.getValue(), isCompareByIdentity);
}

for (Map.Entry<Object, Object> keyValue : HashNodes.iterableKeyValues(other)) {
setNode.executeSet(frame, merged, keyValue.getKey(), keyValue.getValue(), false);
for (Map.Entry<Object, Object> keyValue : BucketsStrategy.iterableKeyValues(HashNodes.getFirstInSequence(other))) {
setNode.executeSet(frame, merged, keyValue.getKey(), keyValue.getValue(), isCompareByIdentity);
}

assert verifyStore(hash);

return merged;
}

// Merge combinations of packed and buckets, without a block

@Specialization(guards = {
"isPackedHash(hash)",
"!isEmptyHash(hash)",
"isRubyHash(other)",
"isBucketHash(other)",
"!isEmptyHash(other)"
})
public RubyBasicObject mergePackedBuckets(VirtualFrame frame, RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
final boolean isCompareByIdentity = isCompareByIdentity(hash);

final RubyBasicObject merged = createHash(hash.getLogicalClass(), null, null, new Entry[BucketsStrategy.capacityGreaterThan(getSize(hash) + getSize(other))], 0, null, null);

final Object[] hashStore = (Object[]) getStore(hash);
final int hashSize = getSize(hash);

for (int n = 0; n < PackedArrayStrategy.MAX_ENTRIES; n++) {
if (n < hashSize) {
setNode.executeSet(frame, merged, PackedArrayStrategy.getKey(hashStore, n), PackedArrayStrategy.getValue(hashStore, n), isCompareByIdentity);
}
}

for (Map.Entry<Object, Object> keyValue : BucketsStrategy.iterableKeyValues(HashNodes.getFirstInSequence(other))) {
setNode.executeSet(frame, merged, keyValue.getKey(), keyValue.getValue(), isCompareByIdentity);
}

assert verifyStore(hash);

return merged;
}

@Specialization(guards = {"!isCompareByIdentity(hash)", "isRubyHash(other)"})
@Specialization(guards = {
"isBucketHash(hash)",
"!isEmptyHash(hash)",
"isRubyHash(other)",
"isPackedHash(other)",
"!isEmptyHash(other)"
})
public RubyBasicObject mergeBucketsPacked(VirtualFrame frame, RubyBasicObject hash, RubyBasicObject other, NotProvided block) {
final boolean isCompareByIdentity = isCompareByIdentity(hash);

final RubyBasicObject merged = createHash(hash.getLogicalClass(), null, null, new Entry[BucketsStrategy.capacityGreaterThan(getSize(hash) + getSize(other))], 0, null, null);

for (Map.Entry<Object, Object> keyValue : BucketsStrategy.iterableKeyValues(HashNodes.getFirstInSequence(hash))) {
setNode.executeSet(frame, merged, keyValue.getKey(), keyValue.getValue(), isCompareByIdentity);
}

final Object[] otherStore = (Object[]) getStore(other);
final int otherSize = getSize(other);

for (int n = 0; n < PackedArrayStrategy.MAX_ENTRIES; n++) {
if (n < otherSize) {
setNode.executeSet(frame, merged, PackedArrayStrategy.getKey(otherStore, n), PackedArrayStrategy.getValue(otherStore, n), isCompareByIdentity);
}
}

assert verifyStore(hash);

return merged;
}

// Merge using a block

@Specialization(guards = {"isRubyHash(other)", "!isCompareByIdentity(hash)"})
public RubyBasicObject merge(VirtualFrame frame, RubyBasicObject hash, RubyBasicObject other, RubyProc block) {
CompilerDirectives.transferToInterpreter();
CompilerDirectives.bailout("Hash#merge with a block cannot be compiled at the moment");

final RubyBasicObject merged = createHash(hash.getLogicalClass(), null, null, new Entry[BucketsStrategy.capacityGreaterThan(getSize(hash) + getSize(other))], 0, null, null);

int size = 0;
Expand All @@ -1153,7 +1280,7 @@ public RubyBasicObject merge(VirtualFrame frame, RubyBasicObject hash, RubyBasic

for (Map.Entry<Object, Object> keyValue : HashNodes.iterableKeyValues(other)) {
final HashLookupResult searchResult = lookupEntryNode.lookup(frame, merged, keyValue.getKey());

if (searchResult.getEntry() == null) {
setNode.executeSet(frame, merged, keyValue.getKey(), keyValue.getValue(), false);
size++;
Expand All @@ -1173,7 +1300,9 @@ public RubyBasicObject merge(VirtualFrame frame, RubyBasicObject hash, RubyBasic
return merged;
}

@Specialization(guards = {"!isRubyHash(other)", "!isCompareByIdentity(hash)"})
// Merge with something that wasn't a hash

@Specialization(guards = "!isRubyHash(other)")
public Object merge(VirtualFrame frame, RubyBasicObject hash, Object other, Object block) {
if (fallbackCallNode == null) {
CompilerDirectives.transferToInterpreter();
Expand Down

2 comments on commit 6734214

@bjfish
Copy link
Contributor

@bjfish bjfish commented on 6734214 Jun 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@chrisseaton Just FYI, I think there was one MRI test regression here:

     [exec] Finished tests in 286.887000s, 9.3800 tests/s, 635.4732 assertions/s.
     [exec] 
     [exec]   1) Failure:
     [exec] TestJSONGenericObject#test_json_generic_object_load [   from /home/travis/build/jruby/jruby/test/mri/json/test_json_generic_object.rb:57]:
     [exec] Failed assertion, no message given.

@bjfish
Copy link
Contributor

@bjfish bjfish commented on 6734214 Jun 15, 2015

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also, @chrisseaton I've excluded this failure here: 5ed43e4

Please sign in to comment.