Truffle ropes #3605

nirvdrum · 2016-01-19T19:55:47Z

This is the initial work in changing the storage strategy for Strings in JRuby+Truffle from ByteList to Rope. There was a fair bit of rote translation work here. I haven't spend any appreciable amount of time on optimizing anything yet. And Symbols are still backed by ByteList.

I tried to make the code work well for both JRuby backends. For simplicity I did pull in some Truffle annotations, but it should be easy to divorce the two.

@chrisseaton @pitr-ch @eregon Please review at your leisure.

@enebo @headius @lopex This work may be of interest to you.

nirvdrum · 2016-01-19T19:58:02Z

I should note that all feedback is appreciated. But please be open to the answer "I didn't get to that yet."

chrisseaton · 2016-01-19T21:49:59Z

test/truffle/compiler/pe/core/string_pe.rb

 tagged_example "'abc' == 'abc'", true # seems to fail sometimes
+example "x = 'abc'; x == x", true
+example "x = 'abc'; x == x.dup", true


This is where the optimisation magic starts! This dup has been completely eliminated by the PE.

How does it work? The rope is only shallow-copied? Then ropes are purely immutable?

Yes, so dup allocates a tiny new wrapper around the same rope node and then the == is just a reference comparison in the fast path, which of course all PEs really well.

chrisseaton · 2016-01-19T22:56:06Z

Looks good to merge to me.

eregon · 2016-01-20T10:21:37Z

truffle/src/main/java/org/jruby/truffle/nodes/core/InterpolatedStringNode.java

        for (Object string : strings) {
            assert RubyGuards.isRubyString(string);

            if (builder == null) {
                builder = dupNode.call(frame, string, "dup", null);
            } else {
-                builder = concatNode.call(frame, builder, "concat", null, string);
+                builder = appendNode.call(frame, builder, "append", null, string);


What is append?

A Rubinius method/primitive. It does much of the same without some of the extra checking that concat needs to perform.

But this means it's a public Ruby method. If it's not needed as such, it could be just a normal node.

Rubinius calls this method. We had it shimmed previously (

jruby/truffle/src/main/ruby/core/shims.rb

Lines 68 to 72 in 18866ad

class String

def append(other)

self << other

end

end

). I just implemented it as a primitive as Rubinius does. The new method lives in bootstrap/string.rb. This was necessary because I moved a lot of String#concat out to Rubinus, which uses String#append to implement the method. Our old shim would have been cyclical.

I could indeed just call the method rather than go through the full dispatch here. I've been avoiding that generally in case we need to run through taint or frozen checks.

I would go for the having an AppendNode and using executeStringAppend here, it's much lighter weight.

I'm going to defer this until after the merge. It's no worse off than what we had before and this PR is already getting rather long.

eregon · 2016-01-20T14:33:44Z

truffle/src/main/java/org/jruby/truffle/runtime/layouts/StringLayout.java

-    int getCodeRange(DynamicObject object);
-    void setCodeRange(DynamicObject object, int codeRange);
+    Rope getRope(DynamicObject object);
+    void setRope(DynamicObject object, Rope byteList);


Rope rope here

Good catch. Thanks.

I'll grep for similar issues.

pitr-ch · 2016-01-20T21:06:46Z

truffle/src/main/java/org/jruby/truffle/runtime/rope/RopeOperations.java

+        }
+    }
+
+    @CompilerDirectives.TruffleBoundary


Didn't we make a convention to use just @TruffleBoundary ?

Probably. I'll fix them. It's just how IntelliJ autocompletes.

pitr-ch · 2016-01-20T22:09:56Z

👍 nice work

…ist.

All Strings are now backed by ropes.

…difies the string being iterated.

…the source string by the iterator.

…n String#setbyte.

… semantics.

Doing a critical operation like this purely in Ruby caused performance regressions that we need to investigate.

…ead of CR_7BIT. While there shouldn't be a difference, it can lead Strings down wrong optimization paths. For now we'll match what MRI and JRuby do to make things simpler.

This should help cases where a byte buffer is pre-allocated using String#* (such as with StringIO). Also, rope links probably cost more than just making a flat array in this case.

…tive.

chrisseaton reviewed Jan 19, 2016
View reviewed changes

eregon reviewed Jan 20, 2016
View reviewed changes

chrisseaton mentioned this pull request Jan 20, 2016

It's time to sizzle whitequark/parser#248

Closed

eregon reviewed Jan 20, 2016
View reviewed changes

nirvdrum force-pushed the truffle-ropes branch from 5244909 to fbebcc4 Compare January 20, 2016 18:45

pitr-ch reviewed Jan 20, 2016
View reviewed changes

nirvdrum added 9 commits January 27, 2016 00:35

[Truffle] Initial work on a rope storage strategy for Strings.

3d1c975

[Truffle] Implemented String#* for ropes.

49b9bfc

[Truffle] Implemented String#slice and String#size for ropes.

a7ef307

[Truffle] Added a method for extracting a byte range from ropes.

987e809

[Truffle] Implemented String#bytesize for ropes.

938b42b

[Truffle] Implemented String#encoding for ropes.

0c7bb5e

[Truffle] Updated String layout to be based on ropes instead of ByteL…

8171f04

…ist.

[Truffle] Removed string_to_rope primitive.

20bc8c3

All Strings are now backed by ropes.

[Truffle] Removed ByteList-based String#+ implementation.

bc07421

nirvdrum added 23 commits January 27, 2016 00:35

[Truffle] Fixed String#each_byte in the event the block yielded to mo…

89dc008

…difies the string being iterated.

[Truffle] Fixed String#each_char in the presence of modifications to …

58ac2e2

…the source string by the iterator.

[Truffle] Fixed a problem with not updating the code range properly i…

268a87b

…n String#setbyte.

[Truffle] Actually update the string on String#downcase!.

aae6ac5

[Truffle] Fixed the byte_append primitive by conforming to its broken…

1e7ee09

… semantics.

[Truffle] Added missing boundaries.

74edda6

[Truffle] Added a missing transfer.

dd24832

[Truffle] Removed some branching in String#*.

47a3b7e

[Truffle] Optimized String#{length,size}.

971f2e3

[Truffle] Reimplemented parts of String#{<<,concat} in Java.

c2defe0

Doing a critical operation like this purely in Ruby caused performance regressions that we need to investigate.

[Truffle] Ensure non-ASCII-compatible empty strings are CR_VALID inst…

74912e1

…ead of CR_7BIT. While there shouldn't be a difference, it can lead Strings down wrong optimization paths. For now we'll match what MRI and JRuby do to make things simpler.

[Truffle] Added a single byte copy implementation of String#*.

faa6614

This should help cases where a byte buffer is pre-allocated using String#* (such as with StringIO). Also, rope links probably cost more than just making a flat array in this case.

[Truffle] Simpler way to clone a byte[].

4ad7b4a

[Truffle] Fixed PE tests with ropes.

beff589

[Truffle] Added more String PE tests.

1a5caa7

[Truffle] Added simple case for rope equality in string_equal primi…

eb91d88

…tive.

[Truffle] Removed support for ropes with unknown code ranges.

c8074ab

[Truffle] Removed an unused import.

f59dd21

[Truffle] Make creating substring ropes more compilation friendly.

b36c2b9

[Truffle] Renamed a method for clarity.

23534f9

[Truffle] Removed more calls to StringOperations.getByteList.

ac10034

[Truffle] Fixed a bad variable name.

f99659f

[Truffle] Use the simpler @TruffleBoundary annotation.

018855f

nirvdrum force-pushed the truffle-ropes branch from 8671dea to 018855f Compare January 27, 2016 05:35

[Truffle] Updated Truffle interop for ropes.

6f1261e

chrisseaton added the truffle label Jan 27, 2016

chrisseaton added this to the truffle-dev milestone Jan 27, 2016

nirvdrum closed this Jan 27, 2016

nirvdrum mentioned this pull request Jan 27, 2016

Truffle ropes #3623

Merged

enebo added this to the Non-Release milestone Dec 7, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

GitHub Sponsors

Truffle ropes #3605

Truffle ropes #3605

nirvdrum commented Jan 19, 2016

nirvdrum commented Jan 19, 2016

chrisseaton Jan 19, 2016

eregon Jan 20, 2016

chrisseaton Jan 20, 2016

chrisseaton commented Jan 19, 2016

eregon Jan 20, 2016

nirvdrum Jan 20, 2016

eregon Jan 20, 2016

nirvdrum Jan 20, 2016

eregon Jan 20, 2016

nirvdrum Jan 20, 2016

eregon Jan 20, 2016

nirvdrum Jan 20, 2016

nirvdrum Jan 20, 2016

pitr-ch Jan 20, 2016

nirvdrum Jan 20, 2016

pitr-ch commented Jan 20, 2016

Truffle ropes #3605

Truffle ropes #3605

Conversation

nirvdrum commented Jan 19, 2016

nirvdrum commented Jan 19, 2016

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

chrisseaton commented Jan 19, 2016

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

pitr-ch commented Jan 20, 2016