Don’t be afraid of reading Ruby’s C source code. If you’re a Ruby developer, it can be a lot of fun to see how things work “under the hood,” and studying Ruby internals can give you a deeper understanding of what Ruby really is and how to use it. A good way to get started looking at Ruby’s source code, to get a “lay of the land,” would be to watch Peter Cooper and I walk through some code in a screencast we recorded last month. However, you might be reluctant to read Ruby’s source code on your own since it’s written in C, a verbose, confusing low-level language that most of us don’t have time to learn.
But is Ruby really written in C? I find Ruby’s C code to be very idiomatic; at times it almost resembles another dialect or language. To see what I mean, take a look at this snippet from MRI’s array.c file, which implements the Array#compact! method:
Most of the code in this function is composed of C macros; these appear in capital letters. Macros are text formulas that C developers can use to make their code more concise and easier to read. The Ruby core team very often uses macros to access data, which is what most of the code in the function above is doing. This is an example of what I call an “MRI idiom.”
Today I’m going to take a close look at this method, Array#compact!, and explain how it works at a C programming level. I’ll do this by explaining what these different macros do. Beyond understanding this one method, learning this MRI idiom of accessing data via macros will help you understand many, many different functions in the Ruby C source code. In a series of upcoming blog posts, I’ll look at some different MRI idioms as well.
Before we get to the C code, let’s review what the compact! method does in Ruby. Here’s the example used in the Ruby docs, the C comment that appears just above this code in array.c:
The rb_ary_compact_bang C function I showed above actually implements this behavior. Whenever you use the compact! method in your code, Ruby internally calls this function and passes in the target array. Somehow it has to identify and remove the nil values. Also, it has to update the target array, or the receiver of the compact! message - the normal compact method would return a new array instead and leave the original unchanged. Finally, it should return nil if there were no changes made to the array.
Array data in MRI
To understand how MRI accesses data via macros, let’s first look at how it stores data, at least for array objects. Ruby stores all arrays and their contents using the RArray C struct, like this:
I won’t cover all the details here today; in fact, you can see some other MRI idioms at work here, such as the ary[RARRY_EMBED_LEN_MAX] struct member which is used for space optimization, or the shared value, which is used for copy-on-write optimization. I wrote about these how these idioms work in the String class last year; see: Never create Ruby strings longer than 23 characters, and Seeing double: how Ruby shares string values.
The details to learn for today are that: Ruby stores the Array data values in a C memory array, tracked by the VALUE *ptr pointer. Ruby (usually) tracks the length of the array in len, and Ruby keeps a capacity value in capa. The capacity records the size of the allocated C memory array (as a count of VALUEs, not as bytes). Ruby frequently allocates more memory for an array than what is actually needed.
By taking some time to first study the RArray C structure, you can quite easily understand large parts of the Ruby C source code in the array.c file… and understand how Ruby arrays actually work!
Accessing array data via macros
However, as I explained above if you read array.c you’ll immediately notice that Ruby doesn’t use the RArray struct directly. Instead, it accesses values such as ptr, len and capa using macros. If you’re not a C programmer, macros are formulas that the C “pre-processor” evaluates and substitutes into the C code just before the C compiler runs.
So let’s just take a look at these macros and see what they do - should be simple, right?
Oops! C programming isn’t that simple! One of the most challenging parts of reading and understanding Ruby’s code is figuring out what these macros mean and do. But this is essential, since they are used so frequently across the code base. Most of the complexity in these particular formulas has to do with Ruby’s embedded data idiom, which I’ll cover in one of my upcoming blog posts.
But don’t despair, normally these macros just boil down to something very simple:
- RARRAY_PTR(ary) - this returns a pointer to the array’s actual data, normally the same as the ptr value. In rb_ary_compact_bang, Ruby initializes the p and t pointers using RARRAY_PTR:
- RARRAY_LEN(ary) - this returns the length of the array, normally just the
len value. rb_ary_compact_bang initializes the end pointer using
RARRAY_LEN, by adding the length to p:
In this diagram, I assume the length of the array is 3, and the capacity of the array is 5.
- ARY_CAPA(ary) - the returns the capacity of the array, or the amount of memory Ruby actually allocated for the array’s elements. Ruby allocates more memory than necessary to avoid repeated memory allocations when an array changes size. This normally just returns capa (except when Ruby is using certain optimizations):
- ARY_SET_LEN(ary, n) - this updates the array length, which is normally the len value:
Putting it all together
Now that we understand how MRI accesses data values via macros, it’s not hard to follow most of the code in rb_ary_compact_bang:
Let’s walk through it, starting with this loop:
This C pointer arithmetic loop actually does the compact operation - if you’re not familiar with C, here’s a 5 second lesson on how pointers work:
If p is a pointer, then *p means to return the value that p points to, and:
*p++ means return the value p points to, but also increment p by one after obtaining this value, so it points to the next value.
Let’s walk through this loop visually, to get a sense of how it works. I’ll use the example from the Ruby docs:
First, Ruby checks whether the first value in the array is nil, using another macro: NIL_P(*t):
Since it is not nil, Ruby copies the “a” onto itself:
This has no effect, but both p and t move forward to the next element:
Now NIL_P(*t) is true, so Ruby just increments t and not p:
Now t points to the “b”, while p remains the same:
This time, NIL_P(*t) is false, so Ruby copies the value “b” back, and increments both pointers:
Continuing through the loop again, NIL_P(*t) will be true this time:
And Ruby will again only increment t:
Iterating again, t points to the “c”, and so Ruby will copy it back:
And again now both pointers will be incremented:
Finally, Ruby increments t past the last nil value, and exits the loop when t == end. This leaves us with the compacted array, which ends at the current location of p.
Now the compacting operation is done, and Ruby just needs to wrap things up and leave the array’s internal values in a self consistent state.
First, Ruby calculates the new length, using the p pointer and RARRAY_PTR which returns the start of the array again:
You can see if the new length is the same as the original length was Ruby will return nil and exit immediately. Otherwise, Ruby uses ARY_SET_LEN to save the new length back in the RArray struct. In the example above, the new length would be 3.
The last bit of confusing code in rb_ary_compact_bang updates the array’s capacity, using the ARY_CAPA macro:
This code is still very confusing, but at least we know now that ARY_CAPA(ary) returns the current capacity of the array. Remember the capacity is the actual size of the memory allocated to hold the array data, measured as an element count. Here Ruby calls the ary_resize_capa method if the new size of the smaller, compacted array is less than half of the current capacity, which will free up some memory. The condition about ARY_DEFAULT_SIZE enforces a minimum capacity - this constant is set to 16 at the top of array.c:
Note: this doesn’t mean that all new, empty arrays allocate enough memory to have a capacity of at least 16; things aren’t so simple. I’ll explain how new arrays look in my next post.
I glossed over a few details here. First of all, as I said above sometimes RARRAY_PTR and RARRY_LEN sometimes work differently. I’ll cover this in my next blog post, on Ruby’s “embedded data” idiom. Second, I didn’t explain the call to rb_ary_modify, which is used for Ruby’s copy-on-write optimization, another MRI idiom. While these are optimizations Ruby uses internally to speed up your programs, I consider them to be idioms also since they have a broad, widespread impact on the way MRI’s C code was written.