Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: jruby/jruby
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: cce2b274bdc4
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 3a4ceac9b5f9
Choose a head ref
  • 5 commits
  • 5 files changed
  • 1 contributor

Commits on Apr 7, 2016

  1. Copy the full SHA
    a8461d7 View commit details
  2. [Truffle] Added specializations for composite ropes in RopeNodes.GetB…

    …yteNode.
    
    Generally we can't optimize much on the structure of a composite rope, as they're
    recursive data structures and we can't PE unbounded recursion. Instead, we must
    find terminal points in the rope that we can optimize on, such as whether the raw
    bytes reference is populated.
    
    This change introduces deconstructing composite ropes for a single level. There
    are various use cases in Ruby that result in a LeafRope being added as a descendant
    to a composite rope, which immediately breaks many fast paths. Examples include:
    
    * Appending "\n" to a LeafRope, resulting in a ConcatRope.
    * Chopping "\n" from a LeafRope, resulting in a SubstringRope.
    * Using a LeafRope as a pattern to fill out a string, resulting in a RepeatingRope.
    
    While this won't make arbitrary rope constructions faster, it will handle a common
    use case.
    nirvdrum committed Apr 7, 2016
    Copy the full SHA
    508b07d View commit details
  3. Copy the full SHA
    e6b5127 View commit details
  4. Copy the full SHA
    1b78b79 View commit details
  5. [Truffle] Special-case substrings of RepeatingRopes that match the ro…

    …pe being repeated exactly.
    nirvdrum committed Apr 7, 2016
    Copy the full SHA
    3a4ceac View commit details
Original file line number Diff line number Diff line change
@@ -0,0 +1,92 @@
/*
* Copyright (c) 2016 Oracle and/or its affiliates. All rights reserved. This
* code is released under a tri EPL/GPL/LGPL license. You can use it,
* redistribute it and/or modify it under the terms of the:
*
* Eclipse Public License version 1.0
* GNU General Public License version 2
* GNU Lesser General Public License version 2.1
*/

package org.jruby.truffle.core.rope;

import org.jcodings.Encoding;

public class RepeatingRope extends Rope {

private final Rope child;
private final int times;

public RepeatingRope(Rope child, int times) {
super(child.getEncoding(), child.getCodeRange(), child.isSingleByteOptimizable(), child.byteLength() * times, child.characterLength() * times, child.depth() + 1, null);
this.child = child;
this.times = times;
}

@Override
public Rope withEncoding(Encoding newEncoding, CodeRange newCodeRange) {
return new RepeatingRope(child.withEncoding(newEncoding, newCodeRange), times);
}

@Override
protected byte getByteSlow(int index) {
return child.getByteSlow(index % child.byteLength());
}

@Override
public byte[] extractRange(int offset, int length) {
assert length <= this.byteLength();

final byte[] ret = new byte[length];

if (getRawBytes() != null) {
System.arraycopy(getRawBytes(), offset, ret, 0, length);
} else {
final int start = offset % child.byteLength();
final byte[] firstPart = child.extractRange(start, child.byteLength() - start);
final int lengthMinusFirstPart = length - firstPart.length;
final int remainingEnd = lengthMinusFirstPart % child.byteLength();

System.arraycopy(firstPart, 0, ret, 0, firstPart.length);

if (lengthMinusFirstPart >= child.byteLength()) {
final byte[] secondPart = child.getBytes();

final int repeatPartCount = lengthMinusFirstPart / child.byteLength();
for (int i = 0; i < repeatPartCount; i++) {
System.arraycopy(secondPart, 0, ret, firstPart.length + (secondPart.length * i), secondPart.length);
}

if (remainingEnd > 0) {
final byte[] thirdPart = child.extractRange(0, remainingEnd);
System.arraycopy(thirdPart, 0, ret, length - thirdPart.length, thirdPart.length);
}
} else {
final byte[] secondPart = child.extractRange(0, remainingEnd);
System.arraycopy(secondPart, 0, ret, length - secondPart.length, secondPart.length);
}
}

return ret;
}

public Rope getChild() {
return child;
}

public int getTimes() {
return times;
}

@Override
public String toString() {
final String childString = child.toString();
final StringBuilder builder = new StringBuilder(childString.length() * times);

for (int i = 0; i < times; i++) {
builder.append(childString);
}

return builder.toString();
}
}
56 changes: 53 additions & 3 deletions truffle/src/main/java/org/jruby/truffle/core/rope/RopeNodes.java
Original file line number Diff line number Diff line change
@@ -120,6 +120,22 @@ public Rope substringSubstringRope(SubstringRope base, int offset, int byteLengt
return makeSubstring(base.getChild(), offset + base.getOffset(), byteLength, is7BitProfile, isBinaryStringProfile);
}

@Specialization(guards = { "byteLength > 1", "!sameAsBase(base, offset, byteLength)" })
public Rope substringMultiplyRope(RepeatingRope base, int offset, int byteLength,
@Cached("createBinaryProfile()") ConditionProfile is7BitProfile,
@Cached("createBinaryProfile()") ConditionProfile isBinaryStringProfile,
@Cached("createBinaryProfile()") ConditionProfile matchesChildProfile) {
final boolean offsetFitsChild = offset % base.getChild().byteLength() == 0;
final boolean byteLengthFitsChild = byteLength == base.getChild().byteLength();

// TODO (nirvdrum 07-Apr-16) We can specialize any number of children that fit perfectly into the length, not just count == 1. But we may need to create a new RepeatingNode to handle count > 1.
if (matchesChildProfile.profile(offsetFitsChild && byteLengthFitsChild)) {
return base.getChild();
}

return makeSubstring(base, offset, byteLength, is7BitProfile, isBinaryStringProfile);
}

@Specialization(guards = { "byteLength > 1", "!sameAsBase(base, offset, byteLength)" })
public Rope substringConcatRope(ConcatRope base, int offset, int byteLength,
@Cached("createBinaryProfile()") ConditionProfile is7BitProfile,
@@ -646,9 +662,43 @@ public int getByte(Rope rope, int index) {
}

@Specialization(guards = "rope.getRawBytes() == null")
@TruffleBoundary
public int getByteSlow(Rope rope, int index) {
return rope.get(index) & 0xff;
public int getByteSubstringRope(SubstringRope rope, int index,
@Cached("createBinaryProfile()") ConditionProfile childRawBytesNullProfile) {
if (childRawBytesNullProfile.profile(rope.getChild().getRawBytes() == null)) {
return rope.getByteSlow(index) & 0xff;
}

return rope.getChild().getRawBytes()[index + rope.getOffset()] & 0xff;
}

@Specialization(guards = "rope.getRawBytes() == null")
public int getByteRepeatingRope(RepeatingRope rope, int index,
@Cached("createBinaryProfile()") ConditionProfile childRawBytesNullProfile) {
if (childRawBytesNullProfile.profile(rope.getChild().getRawBytes() == null)) {
return rope.getByteSlow(index) & 0xff;
}

return rope.getChild().getRawBytes()[index % rope.getChild().byteLength()] & 0xff;
}

@Specialization(guards = "rope.getRawBytes() == null")
public int getByteConcatRope(ConcatRope rope, int index,
@Cached("createBinaryProfile()") ConditionProfile chooseLeftChildProfile,
@Cached("createBinaryProfile()") ConditionProfile leftChildRawBytesNullProfile,
@Cached("createBinaryProfile()") ConditionProfile rightChildRawBytesNullProfile) {
if (chooseLeftChildProfile.profile(index < rope.getLeft().byteLength())) {
if (leftChildRawBytesNullProfile.profile(rope.getLeft().getRawBytes() == null)) {
return rope.getLeft().getByteSlow(index) & 0xff;
}

return rope.getLeft().getRawBytes()[index] & 0xff;
}

if (rightChildRawBytesNullProfile.profile(rope.getRight().getRawBytes() == null)) {
return rope.getRight().getByteSlow(index - rope.getLeft().byteLength()) & 0xff;
}

return rope.getRight().getRawBytes()[index - rope.getLeft().byteLength()] & 0xff;
}

}
Original file line number Diff line number Diff line change
@@ -147,7 +147,18 @@ public static String decodeRope(Ruby runtime, Rope value) {
final ConcatRope concatRope = (ConcatRope) value;

return decodeRope(runtime, concatRope.getLeft()) + decodeRope(runtime, concatRope.getRight());
} else {
} else if (value instanceof RepeatingRope) {
final RepeatingRope repeatingRope = (RepeatingRope) value;

final String childString = decodeRope(runtime, repeatingRope.getChild());
final StringBuilder builder = new StringBuilder(childString.length() * repeatingRope.getTimes());
for (int i = 0; i < repeatingRope.getTimes(); i++) {
builder.append(childString);
}

return builder.toString();
}
else {
throw new RuntimeException("Decoding to String is not supported for rope of type: " + value.getClass().getName());
}
}
@@ -348,6 +359,33 @@ public static byte[] flattenBytes(Rope rope) {
substringLengths.push(adjustedByteLength);
}
}
} else if (current instanceof RepeatingRope) {
final RepeatingRope repeatingRope = (RepeatingRope) current;

// In the absence of any SubstringRopes, we always take the full contents of the MultiplyRope.
if (substringLengths.isEmpty()) {
// TODO (nirvdrum 06-Apr-16) Rather than process the same child over and over, there may be opportunity to re-use the results from a single pass.
for (int i = 0; i < repeatingRope.getTimes(); i++) {
workStack.push(repeatingRope.getChild());
}
} else {
final int bytesToCopy = substringLengths.peek();
int loopCount = bytesToCopy / repeatingRope.getChild().byteLength();

// Fix the offset to be appropriate for a given child. The offset is reset the first time it is
// consumed, so there's no need to worry about adversely affecting anything by adjusting it here.
offset %= repeatingRope.getChild().byteLength();

// Adjust the loop count in case we're straddling a boundary.
if (offset != 0) {
loopCount++;
}

// TODO (nirvdrum 06-Apr-16) Rather than process the same child over and over, there may be opportunity to re-use the results from whole sections.
for (int i = 0; i < loopCount; i++) {
workStack.push(repeatingRope.getChild());
}
}
} else {
CompilerDirectives.transferToInterpreter();
throw new UnsupportedOperationException("Don't know how to flatten rope of type: " + rope.getClass().getName());
@@ -401,6 +439,28 @@ public static int hashForRange(Rope rope, int startingHashCode, int offset, int
}

return hashForRange(right, hash, offset - leftLength, length);
} else if (rope instanceof RepeatingRope) {
final RepeatingRope repeatingRope = (RepeatingRope) rope;
final Rope child = repeatingRope.getChild();

int remainingLength = length;
int loopCount = length / child.byteLength();

offset %= child.byteLength();

// Adjust the loop count in case we're straddling a boundary.
if (offset != 0) {
loopCount++;
}

int hash = startingHashCode;
for (int i = 0; i < loopCount; i++) {
hash = hashForRange(child, hash, offset, remainingLength >= child.byteLength() ? child.byteLength() : remainingLength % child.byteLength());
remainingLength = child.byteLength() - offset;
offset = 0;
}

return hash;
} else {
throw new RuntimeException("Hash code not supported for rope of type: " + rope.getClass().getName());
}
Original file line number Diff line number Diff line change
@@ -87,6 +87,7 @@
import org.jruby.truffle.core.encoding.EncodingNodes;
import org.jruby.truffle.core.encoding.EncodingOperations;
import org.jruby.truffle.core.rope.CodeRange;
import org.jruby.truffle.core.rope.RepeatingRope;
import org.jruby.truffle.core.rope.Rope;
import org.jruby.truffle.core.rope.RopeConstants;
import org.jruby.truffle.core.rope.RopeNodes;
@@ -1370,33 +1371,49 @@ public StringPatternPrimitiveNode(RubyContext context, SourceSection sourceSecti
makeLeafRopeNode = RopeNodesFactory.MakeLeafRopeNodeGen.create(context, sourceSection, null, null, null, null);
}

@Specialization(guards = "value == 0")
@Specialization(guards = "value >= 0")
public DynamicObject stringPatternZero(DynamicObject stringClass, int size, int value) {
ByteList bytes = new ByteList(new byte[size]);
return allocateObjectNode.allocate(stringClass, StringOperations.ropeFromByteList(bytes, CodeRange.CR_UNKNOWN), null);
final Rope repeatingRope = new RepeatingRope(RopeConstants.ASCII_8BIT_SINGLE_BYTE_ROPES[value], size);

return allocateObjectNode.allocate(stringClass, repeatingRope, null);
}

@Specialization(guards = "value != 0")
public DynamicObject stringPattern(DynamicObject stringClass, int size, int value) {
final byte[] bytes = new byte[size];
Arrays.fill(bytes, (byte) value);
return allocateObjectNode.allocate(stringClass, StringOperations.ropeFromByteList(new ByteList(bytes), CodeRange.CR_UNKNOWN), null);
@Specialization(guards = { "isRubyString(string)", "patternFitsEvenly(string, size)" })
public DynamicObject stringPatternFitsEvenly(DynamicObject stringClass, int size, DynamicObject string) {
final Rope rope = rope(string);
final Rope repeatingRope = new RepeatingRope(rope, size / rope.byteLength());

return allocateObjectNode.allocate(stringClass, repeatingRope, null);
}

@Specialization(guards = "isRubyString(string)")
@Specialization(guards = { "isRubyString(string)", "!patternFitsEvenly(string, size)" })
@TruffleBoundary
public DynamicObject stringPattern(DynamicObject stringClass, int size, DynamicObject string) {
final Rope rope = rope(string);
final byte[] bytes = new byte[size];

// TODO (nirvdrum 21-Jan-16): Investigate whether using a ConcatRope would be better here.
// TODO (nirvdrum 21-Jan-16): Investigate whether using a ConcatRope (potentially combined with a RepeatingRope) would be better here.
if (! rope.isEmpty()) {
for (int n = 0; n < size; n += rope.byteLength()) {
System.arraycopy(rope.getBytes(), rope.begin(), bytes, n, Math.min(rope.byteLength(), size - n));
}
}

// TODO (nirvdrum 21-Jan-16): Verify the encoding and code range are correct.
return allocateObjectNode.allocate(stringClass, makeLeafRopeNode.executeMake(bytes, encoding(string), CodeRange.CR_UNKNOWN, NotProvided.INSTANCE), null);
// If we reach this specialization, the `size` attribute will cause a truncated `string` to appear at the
// end of the resulting string in order to pad the value out. A truncated CR_7BIT string is always CR_7BIT.
// A truncated CR_VALID string could be any of the code range values.
final CodeRange codeRange = rope.getCodeRange() == CodeRange.CR_7BIT ? CodeRange.CR_7BIT : CodeRange.CR_UNKNOWN;
final Object characterLength = codeRange == CodeRange.CR_7BIT ? size : NotProvided.INSTANCE;

return allocateObjectNode.allocate(stringClass, makeLeafRopeNode.executeMake(bytes, encoding(string), codeRange, characterLength), null);
}

protected boolean patternFitsEvenly(DynamicObject string, int size) {
assert RubyGuards.isRubyString(string);

final int byteLength = rope(string).byteLength();

return byteLength > 0 && (size % byteLength) == 0;
}

}
Loading