Skip to content

Commit

Permalink
[Truffle] Switched branching max value check with a bit shift based o…
Browse files Browse the repository at this point in the history 
…ne to avoid branching.
@nirvdrum
nirvdrum committed Feb 4, 2016
1 parent 6b92a92 commit f251975
Showing 1 changed file with 15 additions and 18 deletions.
33 changes: 15 additions & 18 deletions truffle/src/main/java/org/jruby/truffle/core/RopeNodes.java
View file
Original file line number Diff line number Diff line change
@@ -222,42 +222,38 @@ public Rope concatLeaves(LeafRope left, LeafRope right, Encoding encoding,
public Rope concatLeavesGeneral(LeafRope left, LeafRope right, Encoding encoding,
@Cached("createBinaryProfile()") ConditionProfile sameCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile brokenCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile,
@Cached("createBinaryProfile()") ConditionProfile leftDepthGreaterThanRightProfile) {
return concat(left, right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile, leftDepthGreaterThanRightProfile);
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile) {
return concat(left, right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile);
}

@Specialization(guards = { "!left.isEmpty()", "!right.isEmpty()", "right.byteLength() < SHORT_LEAF_BYTESIZE_THRESHOLD" })
public Rope concatWithReduce(ConcatRope left, LeafRope right, Encoding encoding,
@Cached("createBinaryProfile()") ConditionProfile sameCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile brokenCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile,
@Cached("createBinaryProfile()") ConditionProfile leftDepthGreaterThanRightProfile) {
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile) {

if ((left.getRight().byteLength() < SHORT_LEAF_BYTESIZE_THRESHOLD) && (left.getRight() instanceof LeafRope)) {
final Rope compacted = concatLeaves((LeafRope) left.getRight(), right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile);
return concat(left.getLeft(), compacted, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile, leftDepthGreaterThanRightProfile);
return concat(left.getLeft(), compacted, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile);
}

return concat(left, right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile, leftDepthGreaterThanRightProfile);
return concat(left, right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile);
}

@Specialization(guards = { "!left.isEmpty()", "!right.isEmpty()", "right.byteLength() < SHORT_LEAF_BYTESIZE_THRESHOLD" })
public Rope concatSubstringLeaf(SubstringRope left, LeafRope right, Encoding encoding,
@Cached("createBinaryProfile()") ConditionProfile sameCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile brokenCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile,
@Cached("createBinaryProfile()") ConditionProfile leftDepthGreaterThanRightProfile) {
return concat(left, right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile, leftDepthGreaterThanRightProfile);
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile) {
return concat(left, right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile);
}

@Specialization(guards = { "!left.isEmpty()", "!right.isEmpty()" })
public Rope concat(Rope left, Rope right, Encoding encoding,
@Cached("createBinaryProfile()") ConditionProfile sameCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile brokenCodeRangeProfile,
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile,
@Cached("createBinaryProfile()") ConditionProfile leftDepthGreaterThanRightProfile) {
int depth = depth(left, right, leftDepthGreaterThanRightProfile);
@Cached("createBinaryProfile()") ConditionProfile isLeftSingleByteOptimizableProfile) {
int depth = depth(left, right);
/*if (depth >= 10) {
System.out.println("ConcatRope depth: " + depth);
}*/
@@ -291,12 +287,13 @@ private boolean isSingleByteOptimizable(Rope left, Rope right, ConditionProfile
return false;
}

private int depth(Rope left, Rope right, ConditionProfile leftDepthGreaterThanRightProfile) {
if (leftDepthGreaterThanRightProfile.profile(left.depth() >= right.depth())) {
return left.depth() + 1;
}
private int depth(Rope left, Rope right) {
final int x = left.depth();
final int y = right.depth();

int maxChildDepth = x - ((x - y) & ((x - y) >> (Integer.SIZE - 1)));

This comment has been minimized.

Sign in to view

Copy link
@eregon

eregon Feb 4, 2016

Member

How does this work?

This comment has been minimized.

Sign in to view

Copy link
@nirvdrum

nirvdrum Feb 5, 2016

Author Contributor

I got the snippet from the bit twiddling hacks page. The general intuition is (x - y) >> (Integer.SIZE - 1) will end up either 0 or -1 as it fills the int with the MSB from the subtraction. When ANDed, we end up with ((x - y) & 0) if x >= y or ((x - y) & -1) if x < y. Then we either have x - 0 or x - (-y), which gives us the max value in either case.

return right.depth() + 1;
return maxChildDepth + 1;
}

protected static boolean isShortLeafRope(Rope rope) {

0 comments on commit f251975

Please sign in to comment.