Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[Truffle] Iterative implementations for getByteSlow #4201

Closed
wants to merge 1 commit into from
Closed

[Truffle] Iterative implementations for getByteSlow #4201

wants to merge 1 commit into from

Conversation

bjfish
Copy link
Contributor

@bjfish bjfish commented Oct 3, 2016

No description provided.

@bjfish bjfish added the truffle label Oct 3, 2016
@eregon
Copy link
Member

eregon commented Oct 3, 2016

So this is just avoiding recursive calls in case of largely homegeneous ropes, right?
Is it to avoid too deep recursions (which could stack overflow) or is it for performance.
If the latter, do you have numbers?

@bjfish
Copy link
Contributor Author

bjfish commented Oct 3, 2016

@eregon Yes, I did this to avoid stack overflow error. For example, it fixes stack overflow for:
a = "a"; 100000.times { a << "b" }; a[0]

I'm not sure about performance.

nirvdrum
nirvdrum reviewed Oct 3, 2016
View reviewed changes
Copy link
Contributor

@nirvdrum nirvdrum left a comment

Choose a reason for hiding this comment

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

I think the idea is right, but unfortunately you still recurse in various places. If you managed to have a tree made up of alternating ConcatRope and SubstringRope, you'd wind up with as many calls here as you had with the old approach.

And the ConcatRope case only works well for trees that are biased to the left. That happens to be a large number of our trees, but if we have one that goes the other way (i.e., heavy down the right), you'd still recurse.

truffle/src/main/java/org/jruby/truffle/core/rope/SubstringRope.java
return child.getByteSlow(index + offset);
int idx = index + offset;
Rope nextChild = child;
while (nextChild instanceof SubstringRope) {
Copy link
Contributor

Choose a reason for hiding this comment

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

While there's nothing wrong with this check, when we actually create SubstringRope instances we always collapse substrings of substrings (see

jruby/truffle/src/main/java/org/jruby/truffle/core/rope/RopeNodes.java

Lines 119 to 124 in 5c97ec0

@Specialization(guards = { "byteLength > 1", "!sameAsBase(base, byteLength)" })
public Rope substringSubstringRope(SubstringRope base, int offset, int byteLength,
@Cached("createBinaryProfile()") ConditionProfile is7BitProfile,
@Cached("createBinaryProfile()") ConditionProfile isBinaryStringProfile) {
return makeSubstring(base.getChild(), offset + base.getOffset(), byteLength, is7BitProfile, isBinaryStringProfile);
}
for details).

And since you only handle that one case here, I think whatever you were looking to accomplish devolves into the code you replaced.

@bjfish
Copy link
Contributor Author

bjfish commented Oct 7, 2016

Going to decline this for now because: it is not a complete solution, code in this area is expected to change soon, and it is not currently needed for gem installing with a workaround in place.

@bjfish bjfish closed this Oct 7, 2016
@bjfish bjfish deleted the feature/truffle-rope-get-byte-slow branch October 7, 2016 17:32
@enebo enebo modified the milestone: truffle-dev Nov 9, 2016
@bjfish bjfish mentioned this pull request Dec 18, 2016
Closed
@enebo enebo added this to the Invalid or Duplicate milestone Dec 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@nirvdrum nirvdrum nirvdrum left review comments

Assignees

@nirvdrum nirvdrum

Labels
None yet
Projects
None yet
Milestone
Invalid or Duplicate
Development

Successfully merging this pull request may close these issues.

None yet
4 participants
@bjfish @eregon @nirvdrum @enebo