Merge branch 'truffle-ropes-2' into truffle-ropes-on-head

jruby · Jan 23, 2016 · b8f19a7 · b8f19a7
2 parents 89451de + 3bda164
commit b8f19a7
Showing 5 changed files with 118 additions and 4 deletions.
diff --git a/truffle/src/main/java/org/jruby/truffle/nodes/core/RopeNodes.java b/truffle/src/main/java/org/jruby/truffle/nodes/core/RopeNodes.java
@@ -13,11 +13,10 @@
 
 import com.oracle.truffle.api.CompilerDirectives;
 import com.oracle.truffle.api.dsl.Cached;
-import com.oracle.truffle.api.dsl.ImportStatic;
 import com.oracle.truffle.api.dsl.NodeChild;
 import com.oracle.truffle.api.dsl.NodeChildren;
 import com.oracle.truffle.api.dsl.Specialization;
-import com.oracle.truffle.api.frame.VirtualFrame;
+import com.oracle.truffle.api.nodes.Node.Child;
 import com.oracle.truffle.api.source.SourceSection;
 import com.oracle.truffle.api.utilities.ConditionProfile;
 import org.jcodings.Encoding;
@@ -118,6 +117,12 @@ private Rope makeSubstringNon7Bit(Rope base, int offset, int byteLength) {
             final int codeRange = StringSupport.unpackArg(packedLengthAndCodeRange);
             final int characterLength = StringSupport.unpackResult(packedLengthAndCodeRange);
 
+            /*
+            if (base.depth() >= 10) {
+                System.out.println("SubstringRope depth: " + (base.depth() + 1));
+            }
+            */
+
             return new SubstringRope(base, offset, byteLength, characterLength, codeRange);
         }
 
@@ -150,6 +155,10 @@ protected static boolean isConcatRope(Rope rope) {
     })
     public abstract static class MakeConcatNode extends RubyNode {
 
+        protected static final int SHORT_LEAF_BYTESIZE_THRESHOLD = 128;
+
+        @Child private MakeLeafRopeNode makeLeafRopeNode;
+
         public MakeConcatNode(RubyContext context, SourceSection sourceSection) {
             super(context, sourceSection);
         }
@@ -176,16 +185,72 @@ public Rope concatEmptyRightDifferentEncoding(Rope left, Rope right, Encoding en
             return RopeOperations.withEncoding(left, encoding);
         }
 
+        @Specialization(guards = { "!left.isEmpty()", "!right.isEmpty()", "left.byteLength() < SHORT_LEAF_BYTESIZE_THRESHOLD", "right.byteLength() < SHORT_LEAF_BYTESIZE_THRESHOLD" })
+        public Rope concatLeaves(LeafRope left, LeafRope right, Encoding encoding,
+                                 @Cached("createBinaryProfile()") ConditionProfile sameCodeRangeProfile,
+                                 @Cached("createBinaryProfile()") ConditionProfile brokenCodeRangeProfile) {
+            if (makeLeafRopeNode == null) {
+                CompilerDirectives.transferToInterpreter();
+                makeLeafRopeNode = insert(RopeNodesFactory.MakeLeafRopeNodeGen.create(getContext(), getSourceSection(), null, null, null));
+            }
+
+            final byte[] bytes = new byte[left.byteLength() + right.byteLength()];
+            System.arraycopy(left.getBytes(), 0, bytes, 0, left.byteLength());
+            System.arraycopy(right.getBytes(), 0, bytes, left.byteLength(), right.byteLength());
+
+            final int codeRange = commonCodeRange(left.getCodeRange(), right.getCodeRange(), sameCodeRangeProfile, brokenCodeRangeProfile);
+
+            return makeLeafRopeNode.executeMake(bytes, encoding, codeRange);
+        }
+
+        @Specialization(guards = { "!right.isEmpty()", "left.byteLength() >= SHORT_LEAF_BYTESIZE_THRESHOLD", "right.byteLength() < SHORT_LEAF_BYTESIZE_THRESHOLD" })
+        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);
+        }
+
+        @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) {
+
+            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, right, encoding, sameCodeRangeProfile, brokenCodeRangeProfile, isLeftSingleByteOptimizableProfile, leftDepthGreaterThanRightProfile);
+        }
+
+        @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);
+        }
+
         @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);
+            /*if (depth >= 10) {
+                System.out.println("ConcatRope depth: " + depth);
+            }*/
+
             return new ConcatRope(left, right, encoding,
                     commonCodeRange(left.getCodeRange(), right.getCodeRange(), sameCodeRangeProfile, brokenCodeRangeProfile),
                     isSingleByteOptimizable(left, right, isLeftSingleByteOptimizableProfile),
-                    depth(left, right, leftDepthGreaterThanRightProfile));
+                    depth);
         }
 
         private int commonCodeRange(int first, int second,
@@ -219,6 +284,13 @@ private int depth(Rope left, Rope right, ConditionProfile leftDepthGreaterThanRi
             return right.depth() + 1;
         }
 
+        protected static boolean isShortLeafRope(Rope rope) {
+            return (rope.byteLength() < SHORT_LEAF_BYTESIZE_THRESHOLD) && isLeafRope(rope);
+        }
+
+        protected static boolean isLeafRope(Rope rope) {
+            return rope instanceof LeafRope;
+        }
     }
 
 

diff --git a/truffle/src/main/java/org/jruby/truffle/runtime/rope/ConcatRope.java b/truffle/src/main/java/org/jruby/truffle/runtime/rope/ConcatRope.java
@@ -99,4 +99,29 @@ public String toString() {
         // This should be used for debugging only.
         return RopeOperations.decodeUTF8(left) + RopeOperations.decodeUTF8(right);
     }
+
+    @Override
+    protected void fillBytes(byte[] buffer, int bufferPosition, int offset, int byteLength) {
+        if (bytes != null) {
+            System.arraycopy(bytes, offset, buffer, bufferPosition, byteLength);
+        } else {
+            final int leftLength = left.byteLength();
+
+            if (offset < leftLength) {
+                // The left branch might not be large enough to extract the full hash code we want. In that case,
+                // we'll extract what we can and extract the difference from the right side.
+                if (offset + byteLength > leftLength) {
+                    final int coveredByLeft = leftLength - offset;
+
+                    left.fillBytes(buffer, bufferPosition, offset, coveredByLeft);
+                    right.fillBytes(buffer, bufferPosition + coveredByLeft, 0, byteLength - coveredByLeft);
+
+                } else {
+                    left.fillBytes(buffer, bufferPosition, offset, byteLength);
+                }
+            } else {
+                right.fillBytes(buffer, bufferPosition, offset - leftLength, byteLength);
+            }
+        }
+    }
 }
diff --git a/truffle/src/main/java/org/jruby/truffle/runtime/rope/LeafRope.java b/truffle/src/main/java/org/jruby/truffle/runtime/rope/LeafRope.java
@@ -49,4 +49,11 @@ public String toString() {
         // This should be used for debugging only.
         return RopeOperations.decodeUTF8(this);
     }
+
+    @Override
+    protected void fillBytes(byte[] buffer, int bufferPosition, int offset, int byteLength) {
+        assert offset + byteLength <= bytes.length;
+
+        System.arraycopy(bytes, offset, buffer, bufferPosition, byteLength);
+    }
 }
diff --git a/truffle/src/main/java/org/jruby/truffle/runtime/rope/Rope.java b/truffle/src/main/java/org/jruby/truffle/runtime/rope/Rope.java
@@ -9,7 +9,6 @@
  */
 package org.jruby.truffle.runtime.rope;
 
-import com.oracle.truffle.api.CompilerDirectives.CompilationFinal;
 import org.jcodings.Encoding;
 import org.jruby.util.ByteList;
 
@@ -123,4 +122,6 @@ public boolean equals(Object o) {
         return false;
     }
 
+    protected abstract void fillBytes(byte[] buffer, int bufferPosition, int offset, int byteLength);
+
 }
diff --git a/truffle/src/main/java/org/jruby/truffle/runtime/rope/SubstringRope.java b/truffle/src/main/java/org/jruby/truffle/runtime/rope/SubstringRope.java
@@ -60,4 +60,13 @@ public String toString() {
         // This should be used for debugging only.
         return RubyEncoding.decodeUTF8(child.getBytes(), offset, byteLength());
     }
+
+    @Override
+    protected void fillBytes(byte[] buffer, int bufferPosition, int offset, int byteLength) {
+        if (bytes != null) {
+            System.arraycopy(bytes, offset, buffer, bufferPosition, byteLength);
+        } else {
+            child.fillBytes(buffer, bufferPosition, offset + this.offset, byteLength);
+        }
+    }
 }