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.

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 47 commits into from
Jul 6, 2016
Merged

Packed arrays #3988

merged 47 commits into from
Jul 6, 2016

Conversation

headius
Copy link
Member

@headius headius commented Jun 30, 2016

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:

  • 41781 RubyArray instances are allocated in total.
  • 8149 RubyArrayOneObject instances are allocated.
  • 20211 RubyArrayTwoObject instances are allocated.

Risks

There are a few risks with this patch:

  • There's additional complexity anywhere we construct a new Array to ensure we're giving it a chance to be packed. I detailed the newBlankArray+store pattern in one of the commits to expand use of packed arrays.
  • Methods overridden by the packed versions can potentially be polymorphic now when they would not have been before. However I suspect most Array call sites will be dealing with the same-sized array each time.
  • New code is risky code. If a packed array is not initialized correctly, or if it does not unpack when it should, it may cause surprising failures.

Future work

  • Explore whether three and four-element packed arrays are worth the additional complexity.
  • Continue improving and expanding our use of packed arrays wherever possible.
  • Begin exploring packed array forms that can handle all-primitive values, to cut down on object boxing for live primitive values on the heap. This will need some analysis to see how frequently large all-Fixnum or all-Float arrays are used in typical libraries and apps.

headius added 19 commits June 30, 2016 16:13
* 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);
Copy link
Member

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)

@kares
Copy link
Member

kares commented Jul 1, 2016

did found the visitAll method at the end, so ignore that.
all 👍 to me esp. like the refactoring of RubyArray's append on loops.

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
@headius headius merged commit 0180583 into master Jul 6, 2016
@headius headius deleted the packed_arrays branch July 6, 2016 19:10
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants