-
-
Notifications
You must be signed in to change notification settings - Fork 925
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.
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
Packed arrays #3988
Merged
Merged
Packed arrays #3988
+2,058
−1,020
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This is not yet running properly.
* Reduce #unpack logic. * Pull a couple more methods up to RubyArray with accessors. * Document specialized array classes. * Eliminate flag; null values field is good enough (maybe better).
This new mechanism passes in state that makes most Visitor construction unnecessary: thread context, currently-visiting Hash, and a generic state object.
Nearly all of these are now allocated once, like a lambda. A few require more state to be passed in than is reasonable for a generic visitor, or require state to be calculated during visit and retrieved at the end. These cases were at least reduced to only allocate a visitor, rather than a visitor and a state-holding object.
See MapJavaProxy's RubyHashMap subclass; it previously override the old visitAll, which broke Map instances returned from Java because that visitAll was not being used. This will help ensure no subclasses are overriding the wrong method. I don't expect there's many (or maybe any) other cases in the wild.
This commit includes a pass over our code to improve places where we are creating one or two-element arrays via the IRubyObject[] paths, so they will use packed arrays when possible. I did this survey by applying the patch (below) and running ruby/spec, various gem commands, and starting up and hitting a blank rails application. The pattern used for most of these changes is as follows: * Allocate a new "blank" array with RubyArray.newBlankArray(size). * Popululate at least the first 'size' elements. This is necessary since the packed arrays can only represent exactly one or two elements, and must be unpacked to represent other sizes. Most cases found in the survey were updated to this new pattern and now will create packed forms. Notable exceptions that I skipped (usually due to algorithms that had unpredictable sizing) were: * RubyString.enumerate[chars,codepoints] - Because of the variable width of characters in multibyte, this logic was difficult to connect up to an "exactly this size" array. It should be possible to use packed arrays for 7-bit cases, or to be smarter about small strings with one or two codepoints, but I have not attempted that here. * RubyArray.values_at - Because the incoming arguments may not represent exactly how many items will be pulled from the array (e.g if you pass in a Range). * RubyStruct.values_at - Same reasons as for RubyArray.values_at. * SelectExecutor's construction of result arrays - Because some or all of the expected channels may not be ready, it would require more logic to right-size the arrays. This is a heavily- hit piece of logic and such an improvement may be warranted, but there's significantly more overhead in SelectExecutor that needs a rewrite before packed arrays would show any significant improvement. The patch mentioned above follows. ```diff diff --git a/core/src/main/java/org/jruby/RubyArray.java b/core/src/main/java/org/jruby/RubyArray.java index d2bc419..180af8f 100644 --- a/core/src/main/java/org/jruby/RubyArray.java +++ b/core/src/main/java/org/jruby/RubyArray.java @@ -160,26 +160,30 @@ public class RubyArray extends RubyObject implements List, RandomAccess { /** rb_ary_new2 * */ public static final RubyArray newArray(final Ruby runtime, final long len) { + if (len == 1 || len == 2) Thread.dumpStack(); checkLength(runtime, len); return newArray(runtime, (int)len); } public static final RubyArray newArrayLight(final Ruby runtime, final long len) { + if (len == 1 || len == 2) Thread.dumpStack(); checkLength(runtime, len); return newArrayLight(runtime, (int)len); } public static final RubyArray newArray(final Ruby runtime, final int len) { + if (len == 1 || len == 2) Thread.dumpStack(); RubyArray array = new RubyArray(runtime, len); Helpers.fillNil(array.values, 0, len, runtime); return array; } public static final RubyArray newArrayLight(final Ruby runtime, final int len) { + if (len == 1 || len == 2) Thread.dumpStack(); RubyArray array = new RubyArray(runtime, len, false); Helpers.fillNil(array.values, 0, len, runtime); return array; } ```
} | ||
|
||
public static RubyArray newArrayLight(Ruby runtime, IRubyObject obj) { | ||
return new RubyArray(runtime, new IRubyObject[] { obj }, false); | ||
return new RubyArrayOneObject(runtime, obj); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
so it might show up in ObjectSpace now ... thus not really "light" (not sure it matters at all)
did found the |
This commit introduces a few new RubyArray.newArray factory methods that are aware of packed forms and can produce the most memory-efficient RubyArray possible. RubyArray.newArrayMayCopy takes an array and will either construct a packed copy of the first one or two elements or a COW-shared array viewing the original. The expectation is that the given array is "effectively read-only", so it can be owned or discarded by the factory method at will. There are new RubyArray.newArray forms for three and four elts. Only the one and two-elt versions use packed forms. Several calls through Ruby.newArray utility methods were moved to new or existing RubyArray factory methods. All specs pass with these changes, and many cases that created "heavy" arrays before will now create packed arrays. This is particularly useful for splatting one or two arguments into an array. A quick benchmark of "def foo(*a); a; end" five times in a 1M iteration loop shows 15-20% improved performance for both one and two-argument calls.
…om cexts as otherwise we may not notice if the monkey patching doesn't work
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This branch is an implementation of packed arrays for one and two-element Array instances.
Basics
There are three new classes: RubyArraySpecialized, a superclass for all the specialized instances, and RubyArrayOneObject and RubyArrayTwoObject, one and two-elt versions of RubyArray. Generally these are used when constructing a new array known to be one or two elements. If the size of the array needs to change from the packed size, it "unpacks" into an array and proceeds to use normal array-based RubyArray logic.
Background
This work was prompted in part by explorations into the heap of a very large application in #3941 as detailed here: #3941 (comment)
In addition to the many small arrays used by RubyGems, there are many pieces of code in stdlib and other libraries that create small arrays as transient data carriers. We also use small arrays in many places in the JRuby runtime for passing block arguments, splatted arguments, and so on. These cases all can benefit from the packing.
Benefits
The two primary benefits of this work are reduced memory usage for one and two-element arrays, and reduced dereferencing requirements for those arrays (since we don't have to hop through an IRubyObject[] to get them).
Memory-wise, the packed arrays add one and two references to the size of RubyArray, but eliminate the much-larger IRubyObject[] header required for arbitrarily-sized arrays. This translates to 60% savings in the one object case and around 40% savings in the two-object case.
Analysis of a Rails app
An analysis of a blank Rails app in development mode shows me the following, after this patch:
There are 909 live RubyArrayOneObject instances and 565 RubyArrayTwoObject instances, consuming about 102KB of memory. If these were all regular RubyArray with a perfectly-sized IRubyObject[], that would be about doubled. If those RubyArray instances had the usual "base" size of 16 elements, it would be considerably higher.
Of the 3046 remaining RubyArray instances, 1626 have one element and 1045 have two elements. These are opportunities to improve our use of packing, but they will require deeper analysis. There are many ways to produce an Array, and the packing logic I've written here can't handle resizes...so many of these arrays may have started out as a different size. In the future we may look at speculatively allocating arrays we know will eventually be packable and adding a way to go from unpacked form to packed form (only the reverse exists now).
Of the 909 RubyArrayOneObject instances, only 2 ended up having to unpack. Of the 565 RubyArrayTwoObject instances, 37 unpacked. This tells me we're doing a good job deciding when to use a packed version that won't just end up unpacking.
There are only 190 three-element RubyArray and 229 four-element RubyArray in the remaining pool. The benefit of packing drops of quickly after one and two-element arrays.
A large app with more "data" may show greater benefit from this patch, especially if it uses many small arrays to represent any data (e.g. a large binary tree).
Doing an allocation profile of that same Rails app, booting up the server and hitting the info page and an error page, I see the following results:
Risks
There are a few risks with this patch:
Future work