Pat Shaughnessy

Ruby’s Missing Data Structure

2013-04-11T00:00:00Z

Have you ever noticed Ruby doesn’t include support for linked lists? Most computer science textbooks are filled with algorithms, examples and exercises based on linked lists: inserting or removing elements, sorting lists, reversing lists, etc. Strangely, however, there is no linked list object in Ruby.

Recently after studying Haskell and Lisp for a couple of months, I returned to Ruby and tried to use some of the functional programming ideas I had learned about. But how do I create a list in Ruby? How do I add or remove an element from a list in Ruby? Ruby contains fast, internal C implementations of the Array and Hash classes, and in the standard library you can find Ruby code implementing the Set, Matrix, and Vector classes among many other things. But no linked lists – why?

The answer is simple: Matz included features you would normally associate with linked lists in the Ruby Array class. For example, you can use Array#push and Array#unshift to add an element to an array, or Array#pop and Array#shift to remove an element from an array.

Today on RubySource.com I wrote about a few common operations you would normally use a linked list for, and then took a look at how you would implement them using an array. I also looked into how Ruby’s array object works internally.

Ruby 2.0 Works Hard So You Can Be Lazy

2013-04-03T00:00:00Z

Lazy enumeration isn’t magic;
it’s just a matter of hard work

Ruby 2.0’s new lazy enumerator feature seems like magic. In case you haven’t tried it yet, it allows you to iterate over an infinite series of values and take just the values you want. It brings the functional programming concept of lazy evaluation to Ruby – at least for enumerations.

For example, in Ruby 1.9 and earlier you would run into an endless loop if you tried to iterate over an infinite range:

Here the call to collect starts an endless loop; the call to first never happens. However, if you upgrade to Ruby 2.0 and use the new Enumerable#lazy method, you can avoid the endless loop and get just the values you need:

But how does lazy evaluation actually work? How does Ruby know I only want ten values, in this example? All I have to do is make the simple call to the lazy method and it just works.

It seems like magic, but actually it’s just a matter of hard work. A lot happens inside of Ruby when you call lazy. To give you just the values you need, Ruby automatically creates and uses many different types of internal Ruby objects. Like heavy equipment at a work site, these objects work together to process the input values from my infinite range in just the right way. What are these objects? What do they do? How do they work together? Let’s find out!

The Enumerable module: many different ways of calling “each”

When I call collect on the range above I’m using Ruby’s Enumerable module. As you probably know, this module contains a series of methods, such as select, detect, any? and many more, that process lists of values in different ways. Internally, all of these methods work by calling each on the target object or receiver:

You can think of the Enumerable methods as a series of different types of machines that operate on data in different ways, all via the each method:

Enumerable is eager

Many of the Enumerable methods, including collect, return an array of values. Since the Array class also includes the Enumerable module and responds to each, you can chain different Enumerable methods together easily:

In my code example above, the Enumerable#first method calls each on the result of Enumerable#collect, an array which was generated in turn by another call to each on the input range.

One important detail to notice here is that both Enumerable#collect and Enumerable#first are eager: this means that they process all of the values returned by each before returning the new array value. So in my example, first collect processes all the values from the range and saves the results into the first array. Then in a second step first processes all the values from the first array, placing the results into the second array:

This is what leads to the endless loop for an infinite range; since Range#each will never stop returning values, Enumerable#collect will never finish, and Enumerable#first will never get a chance to stop the iteration.

The Enumerator object: deferred enumeration

One interesting trick you can use with the Enumerable module’s methods is to call them without providing a block. For example, suppose I call collect on my range, but I don’t provide a block:

Here Ruby has prepared an object you can use later to actually enumerate over the range, called an “Enumerator.” As you can see from the inspect string, Ruby has saved a reference to the receiver (1..10) along with the name of the enumerable method I want to use (collect) inside the enumerator object.

Later when I want to actually iterate through the range and collect the values in an array, I can just call each on the enumerator:

There are a few other ways of using enumerators, such as calling next repeatedly, which I don’t have time to discuss today.

Enumerator::Generator – generating new values for enumeration

In my previous examples I used a Range object to produce a series of values. However, the Enumerator class provides another more flexible way of generating a series of values using a block. Here’s an example:

Let’s take a look at what sort of enumerator this is:

As you can see, Ruby has created a new enumerator object that contains a reference to an internal object called Enumerator::Generator, and has setup to call the each method on that generator. Internally, the generator object converts the block I provided above into a Proc object and saves it away:

Now when I use the Enumerator object, Ruby will call the Proc saved inside the generator to get the values for the enumeration:

In other words, the Enumerator::Generator object is a source of data for an enumeration – it “generates” the values and passes them along.

Enumerator::Yielder – allowing one block to yield to another

If you take a close look at the code above, there’s something strange about it. I first created the Enumerator object using a block:

…which yields values to a second block I provide later when I call each:

In other words, the enumerator somehow allows you to yield values directly from one block to another:

But of course this isn’t how Ruby works. Blocks can’t pass values directly to each other like this. The trick to making this work is another internal object called the Enumerator::Yielder object, passed into the block with the y block parameter:

The y parameter is very easy to miss here. But if you re-read the block’s code, you’ll notice I’m not actually yielding values at all, I’m simply calling the yield method on the y object, which is an instance of the built in Enumerator::Yielder class. You can see and use this class for yourself in IRB as follows:

The yielder catches values I want the enumerator to generate, using the yield method, and then later actually yields them to the target block. As a Ruby developer, aside from calling yield I don’t normally ever need to interact with the generator or the yielder; they are used internally by the enumerator. When I call each on the enumerator, it uses these two objects to generate and yield the values I want:

Enumerators generate data; Enumerable methods consume it

Stepping back for a moment, the pattern we’ve seen so far with enumerations in Ruby is:

Enumerator objects produce data.
Enumerable methods consume data.

From right to left, the enumerable method calls each to request data; later from left to right the enumerator object provides the data by yielding it to a block.

Enumerator::Lazy – putting it all together

Ruby 2.0 implements lazy evaluation using an object called Enumerator::Lazy. What makes this special is that it plays both roles! It is an enumerator, and also contains a series of Enumerable methods. It calls each to obtain data from an enumeration source, and it yields data to the rest of an enumeration:

Since Enumerator::Lazy plays both roles, you can chain them up together to produce a single enumeration. This is what happens in my infinite range example:

The call to lazy produces one Enumerator::Lazy object. Then when I call collect on this first object, the Enumerator::Lazy#collect method returns a second one:

You can see here that the second Enumerator::Lazy, created by the call to Enumerator::Lazy#collect, also calls my block, the x*x code.

How does all of this work? How does Enumerator::Lazy do all of this? To serve both as a data producer and consumer, Enumerator::Lazy uses generator and yielder objects in a special way. The generator first calls each to obtain data, and then it passes each value it obtains immediately into a special block:

Let’s take a closer look at the block from the diagram – this block implements the Enumerator::Lazy#collect method. (The other lazy enumeration methods use slightly different blocks.) Ruby implements it internally using C code, but this is the equivalent Ruby code:

Reading the code, we can see the block takes a yielder and a value. Then it yields the value to another block – this is actually the block I provide to Enumerator::Lazy#collect or x*x in my example. Then the Enumerator::Lazy#collect block calls the yielder, passing the result of my block onto the rest of the enumeration.

This is the key to lazy evaluation in Ruby. Each value from the data source is yielded to my block, and then the result is immediately passed along down the enumeration chain. This enumeration is not eager – the Enumerator::Lazy#collect method does not collect the values into an array. Instead, each value is passed one at a time along the chain of Enumerator::Lazy objects, via repeated yields. If I had chained together a series of calls to collect or other Enumerator::Lazy methods, each value would be passed along the chain from one of my blocks to the next, one at a time:

Lazy evaluation: executing code backwards

Why is this chain lazy evaluation? Why does this allow Ruby to avoid an endless loop and provide me with just the values I need? The answer is that the code at the end of the enumeration chain, in my example the first(10) method call, controls how long the enumeration runs:

At the end of the enumeration chain the values are yielded to the Enumerable#first method:

After the Enumerable#first method receives enough values, 10 in my example, it stops the iteration by raising an exception.

In other words, the code at the right side of my enumeration chain, the code at the end, actually controls the execution flow. The Enumerable#first both starts the iteration by calling each on the lazy enumerators, and ends the iteration by raising an exception when it has enough values.

At the end of the day, this is the key idea behind lazy evaluation: the function or method at the end of a calculation chain starts the execution process, and the program’s flow works backwards through the chain of function calls until it obtains just the data inputs it needs. Ruby achieves this using a chain of Enumerator::Lazy objects, as we’ve seen above. However, functional languages such as Haskell implement this in a deeper, more fundamental way, that encompasses all execution and not just enumeration.

An Interview With Laurent Sansonetti

2013-02-12T00:00:00Z

Laurent Sansonetti created RubyMotion

It was only last April when Laurent Sansonetti captured the imagination of the entire Ruby community with RubyMotion. For the first time Ruby developers were able to write apps directly for the iOS mobile platform using the language we all know and love. Now there is no longer a need to learn the archaic, verbose Objective-C language, or worse yet to learn to navigate the confusing myriad of windows and dialog boxes in the XCode IDE. We can just bring the magic of Ruby to iOS, using our favorite tools: VIM, Sublime or Emacs with our usual command line based workflow.

I was thrilled earlier this month when Laurent agreed to do an interview with me for RubySource. I was able to learn more about RubyMotion directly from its inventor. Since I had so many questions, I’ve divided the interview into two halves. In the first half, I ask Laurent some basic questions: What is RubyMotion, exactly? What does it do? How should we use it? Is writing Ruby for iOS any different from writing a “normal” Ruby app?

The second half of the interview is a bit more technical: How does RubyMotion work, exactly? How does Laurent use the LLVM framework to compile Ruby code into a static executable? How does it differ from the way MacRuby and Rubinius work? I love learning about Ruby internals, and RubyMotion is certainly a unique and fascinating implementation of Ruby.

Ruby MRI Source Code Idioms #3: Embedded Objects

2013-02-08T00:00:00Z

Last year I wrote a post about how the core team optimized Ruby to process shorter strings faster than longer strings. I found that Ruby strings containing 23 or fewer characters are much faster. Why am I bringing this up again now? Well, it turns out this isn’t a single optimization that the core team has added for short strings. Instead, they’ve used the same technique in many other places as well. For example, if you create an array with only one, two or three elements, it’s much faster than if you create an array with four or more elements:

Or if you create a Struct object, it’s much faster when there are three or fewer attributes:

The same pattern also appears if you create large integer values using the Bignum class:

Even your own Ruby objects are faster if they contain three or fewer instance variables:

Finally, here’s the data showing the same optimization for Ruby strings that I wrote about last year – you can see strings containing 23 or fewer characters are faster:

So should you stop and refactor all of your code to use small arrays, short strings, and objects with fewer than four instance variables? Of course not! That’s obviously ridiculous.

Also, I’ve exaggerated the performance difference by running these lines of code in a tight loop, executing the same line of code over and over again. In a more realistic Ruby program the speedup produced by using shorter strings or small arrays would be mixed in with many other types of operations and code. The speed of most Ruby applications has more to do with database connections, network latency and other factors. And, of course, if you’re developing a Rails web site – or more generally using lots of different gems – then your own Ruby code is probably a small fraction of the Ruby code used across your entire application. Bizarre refactoring to use fewer instance variables wouldn’t help you much anyway.

Instead, the reason I’m bringing these optimizations to your attention is:

…to give you a small taste of all the hard work the Ruby core team has done to speed up your code. The core team has put in countless hours of work to squeeze every bit of performance out of Ruby they could to make your code run faster. To make these optimizations work they had to add many lines of complex, additional C code inside of Ruby.
…to make it easier for you to follow the C source code inside of Ruby. If you’re interested in learning how your language actually works internally then you’ll need to understand the coding patterns behind these optimizations.
…because it’s fun to see how these things actually work!

A verbose optimization

There are many places within Ruby’s C source code where small objects – the objects corresponding to the shorter bars in the charts above – are handled differently than larger objects. This is such a common pattern that I consider it an MRI idiom. In order to understand how many of the built in functions in the String, Array, Struct, or Bignum classes work you need to understand the coding pattern behind this optimization. And, as we saw above, Ruby also uses this pattern when handling instance variables in your own classes.

I call these smaller, faster objects “Embedded Objects,” based on the name of certain C constants used inside of Ruby. For example, here’s the C code that Ruby uses to create a new array of a certain size or “capacity:”

As you can see arrays longer than RARRAY_EMBED_LEN_MAX are handled differently than shorter arrays. What’s the value of RARRAY_EMBED_LEN_MAX? It turns out it is 3. This explains the behavior in the chart above.

Here’s another example – whenever you increase the size of a string, for example by calling String#<< or String#insert, Ruby uses this code:

Here again, we can see Ruby handles longer strings differently than shorter strings, using the value RSTRING_EMBED_LEN_MAX. What is this set to? Well, from the performance chart above we know it must be 23.

Finally, here’s the code Ruby uses to create new Struct objects:

Once again you can see structs with fewer than RSTRUCT_EMBED_LEN_MAX members are handled differently than structs with more attributes. What’s the value of RSTRUCT_EMBED_LEN_MAX? It must be 3, based on the chart above.

These are just three simple examples; if you go and look you’ll find that these “EMBED” constants appear in many places inside Ruby’s implementation of these 4 built-in classes, along with the code that handles instance variables in your objects. Each time one of these constants appears, there will also be code the Ruby core team had to write to handle embedded objects differently – to make your code run a few microseconds faster!

To summarize, here are the 5 C constants Ruby uses as a threshold for embedded objects, and their values:

You can find these values in the include/ruby/ruby.h file. As you can see, each of these corresponds to one of the performance pattern you see in the charts above. For the Bignum class, Ruby uses the RBIGNUM_EMBED_LEN_MAX value to keep track of how many BDIGIT structures will fit into a single RBignum structure. Ruby uses these BDIGIT structures to hold large integer values, and allocates more of them as necessary to represent very large integers.

The C “union” keyword

Above I showed a few places where these “EMBED” constants appear in Ruby’s source code, but the most important places the constant appears is in the C structure definitions for these object types. For example, as I explained two weeks ago, Ruby represents every array object using the RArray structure:

Here I’ve shown the RArray struct separated into two pieces: the top rectangle shows how larger arrays with 4 or more elements save their data, and the lower rectangle shows how shorter array with three or fewer elements work. The key to this is the union keyword, which is a trick you can use in the C language to indicate the same memory segment can be used in more than one way:

By using the union keyword, the C compiler allows you to access either the values on the top via the heap structure, the first member of the union, or the values on the bottom, inside the ary array, the second member of the union.

Accessing embedded objects via macros

As I also wrote about two weeks ago, Ruby uses a series of C macros to access the data inside an array, string or most other built in object types. The Ruby core team, fortunately, also uses these macros to hide some of the complexity around embedded objects.

To see what I mean, here’s the definition of the RARRAY_PTR macro – Ruby uses this to get a pointer to an array’s elements:

Every time Ruby needs access to the contents of an array, it runs the code found inside this macro: First, it uses a second macro, RBASIC, to get access to some internal flags stored inside the inner RBasic structure. One of these flags is called RARRAY_EMBED_FLAG. If RARRAY_EMBED_FLAG is set, then Ruby knows this array is an embedded object, and therefore looks for the array’s elements in as.ary – or the array located right inside the RArray struct. If RARRAY_EMBED_FLAG is not set, then Ruby looks for the array’s elements in the usual way by following the ptr pointer to another memory block in the heap.

Learn the idiom once and use it many times

As I said above, by learning just a few coding patterns, you can quickly start to understand large parts of Ruby’s internal source code. Since the embedded object pattern is used by five different types of objects, it makes a lot of sense to spend some time learning how it works. By learning a few more MRI idioms, you’ll start to think like a member of the Ruby core team! Stay tuned, next time we’ll look at another common coding pattern used by Matz and his colleagues…

Ruby MRI Source Code Idioms #2: C That Resembles Ruby

2013-01-31T00:00:00Z

Reading Ruby’s C source code can be
as easy as reading your own Ruby code

Last week I discussed how Ruby’s C source code uses macros to access data values. I explained that this “MRI Idiom” can make Ruby’s source a bit confusing for C programmers to read, but at the same time can make it easier to follow for Ruby developers who aren’t experienced with C. Today I want to continue this series and talk about another MRI idiom: how Ruby’s C source code frequently resembles Ruby code.

Sounds hard to believe, doesn’t it? At first glance MRI’s C source code looks nothing like Ruby. For example, take a look at the implementation of Array#collect:

This is typical C code: verbose, confusing and hard to understand. Ruby is supposed to be elegant and concise! However, I honestly believe this C code does resemble Ruby, and in fact implements Array#collect just the way you would if you were to implement this in Ruby.

Of course, we don’t need to imagine how we would implement this in Ruby – there already is a Ruby version of Array#collect (actually Enumerable#collect) in Rubinius:

Now let’s take a second look at MRI’s C implementation – if you have a vivid imagination you can see how the MRI C code corresponds to the Ruby used by Rubinius:

My point is that by learning a few of MRI’s idioms and coding patterns, you can begin to read Ruby’s C source code just as easily as you can read Rubinius’s Ruby implementation.

Why would you want to do this? Why not refer to the Rubinius source code base whenever you have a question about how something works? This is actually a great idea; Rubinius is a particularly beautiful implementation of Ruby, and reading its code can give you a lot of insight into what’s going on inside of Ruby. However, most of us don’t run Rubinius in production. If you really need to know how something works at a detailed level… why it is slow, why it is fast, how or when does it allocate memory, etc., then there is no alternative but to read the C code you are actually running in production.

Today I’m going to examine how the C constructs in rb_ary_collect work in detail, and show how we can replace them – in our minds at least – with the corresponding Ruby code. By investing a bit of time to learn just a few of MRI’s coding patterns you’ll be able to understand not only rb_ary_collect, but many of the built in methods from classes such as String, Array, or File that you use everyday in your code. Understanding MRI’s idioms will allow you to follow much of Ruby’s internal source code without being an expert C developer.

First, a review of what Array#collect does

Let’s start by reviewing how the collect method works in Ruby. Here’s the example from the Ruby documentation:

Most of the time we use collect to iterate over an array (or some other Enumerable) and call a block for each element. Later collect pushes the return values from each call to the block into a single new array, and returns it.

However, if you call collect without a block it returns an enumerator object you can use later:

Now let’s see how Ruby implements Array#collect internally. I’ll do this by replacing bits of the confusing C code with Ruby, step by step. As you’ll see, this isn’t that hard to do!

rb_ary_new2 = Array.new

This oddly named C function is actually quite simple: it just creates a new Array with a length of zero, and the given “capacity.” As I explained last week, internally Ruby saves a “capacity” value inside of each array, in the RArray structure, which keeps track of the size of the memory actually allocated for the array. The confusing part of this function is the name: rb_ary_new2 doesn’t create two arrays, or call the “new2” method on the Array class. It’s simply equivalent to calling Array.new in Ruby. MRI uses the number “2” on the function name to distinguish it from other functions that also create arrays in slightly different ways, for example without the internal capacity setting. Let’s take a look what rb_ary_new2 does:

You can see it just calls ary_new with the given capacity value, and by passing in rb_cArray indicates we want to create a new instance of the Array class (sometimes Ruby uses the RArray struct for instances of other classes):

I won’t explain this in detail, but you can see at the top Ruby checks the capacity parameter is valid, and gets a new RArray struct using the ary_alloc function. Finally it sets up this new RArray if necessary. I’ll explain the details around RARRAY_EMBED_LEN_MAX in my next post.

Now let’s return to rb_ary_collect and substitute the Ruby Array.new call into our C code – just as a thought experiment, of course!

for-loop = Array#each

Next, let’s look at how Ruby internally iterates over the array’s elements:

Of course, in Ruby I would never use a for-loop like this; instead I would call Array.each and pass each element to a block. But remember in the C language there is no concept of blocks or enumerators. Instead, you have to code “closer to the metal” and explain to the C compiler exactly how it should iterate through the array. Here’s how this works: first the code above creates a loop and assigns the values 0, 1, 2… to the variable i. Next, Ruby accesses each value of the array using this syntax:

As I explained last week, the RARRAY_PTR returns a pointer to the array’s actual data, and [i] uses C’s array syntax to obtain the proper element of the array.

Now in our thought experiment if we substitute the for-loop with a call to Array#each, passing a block parameter we get:

Now this C code is starting to make more sense!

rb_yield = yield

Now let’s take a look at what happens inside the loop. As you can see, Ruby takes each element of the array and passes it to a C function called rb_yield. As you might guess, this is Ruby’s internal implementation of the Ruby yield keyword. I don’t have time or space today to explain how rb_yield works in detail here – it calls into the internal guts of the YARV virtual machine that runs your Ruby program. For a good explanation of how YARV works and of what Ruby does internally when you call a block, check out chapters 2 and 5 from Ruby Under a Microscope, my eBook on Ruby internals.

Let’s continue the thought experiment and substitute rb_yield with a simple Ruby yield keyword:

rb_ary_push = Array#<<

Next, let’s take a look at the rb_ary_push function call. As you might guess, this simply calls Array#<<. It adds a new value to the end of the array. Let’s take a quick look at the implementation of this, much farther above in the same array.c MRI source code file:

I won’t explain this code carefully, but in a nutshell Ruby uses another C function called rb_ary_push_1 as a optimization when you push a single new element. The related Array#push method can possibly take more than one parameter, so it’s handled slightly differently inside of MRI.

An interesting detail here how Ruby doubles the internal capacity of the array when there’s no room for another value, based on the “capacity” value. This is an optimization to avoid calling malloc to allocate memory over and over again as you push elements onto the array. Allocating (or reallocating) memory can often be an expensive operation.

Following the same pattern, I’ll substitute a call to Array#<< into my original C function – now the C code is looking more and more like the Rubinius implementation:

RETURN_ENUMERATOR = Kernel.to_enum

As you can see, there’s just one last bit of confusing C code left from the original version of rb_ary_collect – the RETURN_ENUMERATOR macro. Let’s take a look at how this macro is written, from include/ruby/intern.h:

Ah yes… typical C verbosity! We have a multiline macro with backslashes, and a needless do…while loop inserted around the actual macro to provide a safe scope for substitution. What in the world does this mean?

Don’t panic! This code isn’t that hard to understand if you take a moment to read it carefully; it essentially means: if a block was not given then call the rb_enumeratorize function, passing in the name of the current C function as a parameter. Then return the result as the return value for rb_ary_collect.

Ruby uses this RETURN_ENUMERATOR macro quite often while implementing methods related to enumeration, such as collect or each. You can find the rb_enumeratorize function in the enumerator.c MRI source code file, but I won’t explain it here. There’s some complex code that eventually does the same thing a call to Kernel.to_enum does – which is to return a new enumerator object that is initialized with the values in the current array.

Replacing this macro with the equivalent call to Kernel.to_enum, I get:

Conclusion

Let’s take a step back and review what I’ve done in this odd thought experiment. Reading the original implementation of rb_ary_collect I recognized some idiomatic C patterns that I was familiar with. This allowed me – in my own head at least – to read the C source code the same way I would read a Ruby function. Notice how similar the code above is to Rubinius’s implementation:

My point today is that by learning a few of the C coding patterns the Ruby core team uses, you can start to read Ruby’s source code just as easily as you can read your own Ruby code. This is especially true for Ruby’s implementation of built-in methods like Array#collect.

Ruby MRI Source Code Idioms #1: Accessing Data Via Macros

2013-01-23T00:00:00Z

From: wiktionary.org

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.

Array#compact!

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.

Wrapping up

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.

Loose ends

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.

Ruby, Smalltalk and Class Variables

2012-12-17T00:00:00Z

Many of the ideas behind Ruby’s object model
were developed for Smalltalk in the 1970s.

A couple weeks ago an article by Ernie Miller got me interested in how class variables work in Ruby. After doing a bit of research, I found that class variables have been a perennial source of confusion. In fact, John Nunemaker wrote an article called Class and Instance Variables In Ruby way back in 2006 that still applies today. The fundamental problem with class variables in Ruby is that they are shared among a class and all of its subclasses – as John explained six years ago, this can lead to confusion and unexpected behavior.

But for me the interesting question here is: “Why?” Why does Ruby share a single value across all of the subclasses? Why have a distinction between “class variables” and “class instance variables?” Where do these ideas come from? It turns out the answer is simple: class variables in Ruby work the same way class variables work in a much older language called Smalltalk. Smalltalk was invented in the early 1970s by the renown computer scientist Alan Kay and a group of his colleagues working at the Xerox PARC laboratory. With Smalltalk, Alan Kay didn’t just invent a programming language; he also conceived of the entire concept of object oriented programming (OOP) and implemented it for the first time. While not in very widespread use now, Smalltalk has influenced many other object oriented programming languages that are used widely today – most importantly Objective C and Ruby.

Today I’m going to look at how class variables work in Smalltalk, and compare and contrast that against how they work in Ruby. As you’ll see, I found that class variables aren’t the only idea Ruby took from Smalltalk. Much of Ruby’s object model design was taken from Smalltalk as well.

Class variables in Ruby

First, let’s quickly review what a class variable is, and how they work in Ruby. Using John Nunemaker’s example from 2006, here’s a simple Ruby class, Polygon, that contains a single class variable, @@sides:

class Polygon
  @@sides = 10
  def self.sides
    @@sides
  end
end

puts Polygon.sides
=> 10

This is simple enough: @@sides is a variable that any class or instance method of Polygon can access. Here the sides class method returns it. At a conceptual level, internally Ruby associates the @@sides variable with the same memory structure used to represent the Polygon class:

The confusion comes in when you define a subclass; again here is another one of John Nunemaker’s examples:

class Triangle < Polygon
  @@sides = 3
end

puts Triangle.sides
=> 3
puts Polygon.sides
=> 3

Notice both class variables, Triangle.sides and Polygon.sides, were changed to 3. In fact, internally Ruby creates a single variable that both classes share:

I may write in more detail about the details of Ruby’s internal implementation of class variables in an upcoming blog post, but for today I’ll just use these very simple diagrams. Instead, now let’s switch gears and learn more about Smalltalk….

What is Smalltalk?

As I said above, Alan Kay invented Smalltalk along with object oriented programming while working at Xerox PARC in the early 1970s. This is the same laboratory that also invented the personal computer, the graphical user interface, and the Ethernet among many other things. Object oriented programming actually seems to be one of their less important inventions!

In Smalltalk, Kay introduced terminology and ideas that we all take for granted today. Every value in Smalltalk, including language constructs such as code blocks, is an object. A Smalltalk program consists of these objects and the way they interact; to call a particular Smalltalk function, you “send a message” to the object that implements that function. In Smalltalk, functions are known as “methods.” An object implements a series of methods. All of this should sound very familiar, of course.

In the 1970s, Alan Kay envisioned a laptop/tablet he called the
“Dynabook” would run Smalltalk. He and his team actually built a
computer called the “Interim Dynabook” and used it to teach
programming to middle school children.

From the very beginning, Kay’s conception of OOP included the idea of an object’s “class.” An object’s class described a series of behaviors (methods) each instance of that class exhibited. Smalltalk also implemented the concept of polymorphism, which allows the developer to define “subclasses” that share the behaviors of their “superclass.” All of these terms we use often today were coined by Kay and his colleagues 40 years ago.

Smalltalk, however, is more than just a programming language; it’s an entire graphical development environment. I think of Smalltalk as a precursor to Visual Studio or XCode, invented before Microsoft or Apple even existed, in a world where computers were found only in academic or government settings! One other impressive goal Alan Kay and the Smalltalk team had from the beginning was to use their visual environment as a teaching tool for school children. It’s a truly amazing story.

To learn more about the history and origin of Smalltalk, I would highly recommend reading The Early History Of Smalltalk (html or original pdf or easier to read pdf, but missing some diagrams), a retrospective account Kay wrote later in the 1990s. It’s a fascinating narrative of how Kay and his colleagues borrowed ideas from even earlier, but with the combination of hard work, creativity and pure talent managed to take a large step forward and revolutionize the computer science world of their day, and ours.

Alan Kay created the first working version of Smalltalk in 1972 – in his own words, here is how it happened:

I had expected that the new Smalltalk would be an iconic language and would take at least two years to invent, but fate intervened. One day, in a typical PARC hallway bullsession, Ted Kaehler, Dan Ingalls, and I were standing around talking about programming languages. The subject of power came up and the two of them wondered how large a language one would have to make to get great power. With as much panache as I could muster, I asserted that you could define the "most powerful language in the world" in "a page of code." They said, "Put up or shut up." Ted went back to CMU but Dan was still around egging me on. For the next two weeks I got to PARC every morning at four o'clock and worked on the problem until eight, when Dan, joined by Henry Fuchs, John Shoch, and Steve Purcell showed up to kibbitz the morning's work. I had originally made the boast because McCarthy's self-describing LISP interpreter was written in itself. It was about "a page", and as far as power goes, LISP was the whole nine-yards for functional languages. I was quite sure I could do the same for object-oriented languages….

Here Kay referred to John McCarthy, who invented LISP about 10 years earlier. It took Kay only eight early mornings of work to finish the first version of Smalltalk:

The first few versions had flaws that were soundly criticized by the group. But by morning 8 or so, a version appeared that seemed to work….

I wish I could be as creative, dedicated and productive as Alan Kay and his Xerox PARC colleagues were 40 years ago!

Class variables in Smalltalk

To find out how class variables actually work in Smalltalk, I installed GNU Smalltalk, a command line based version of the language which is easy to download and run on a Linux box. Initially I found Smalltalk to be very strange and unfamiliar; it’s syntax seems a bit odd and weird at first glance. For example, you need to remember to end each command with a period, and also to define a method you only need to specify a list of arguments… without a method name! I suppose the first argument is the method name or vice-versa. But after a couple of days I became accustomed to the idiosyncratic syntax, and the language began to make more sense to me.

Here is the same Polygon class again – now I have Smalltalk on the left, and Ruby on the right:

Object subclass: Polygon [
  Sides := 10.
]

Polygon class extend [
  sides [ ^Sides ]
]

Polygon sides printNl.
=> 10
class Polygon
  @@sides = 10
  def self.sides
    @@sides
  end
end


puts Polygon.sides
=> 10

Here’s a quick explanation of what the Smalltalk code does:

Object subclass: Polygon – this means send the subclass message to the Object class and pass in the name Polygon. It creates a new class, which is a subclass of the Object class. This is analogous to class Polygon < Object in Ruby. Of course, in Ruby specifying Object as the superclass is unnecessary.
Sides := 10. – this declares a class variable Sides, and assigns it a value. Ruby instead uses the @@sides syntax.
Polygon class extend – this “extends” the Polygon class; i.e., it opens up the Polygon class and allows me to add a class method. In Ruby I use class Polygon; def self.sides.
The printNl method prints a value to the console; it works the same way as puts in Ruby, except printNl is a method of the Sides object. Imagine calling @@sides.puts in Ruby!

Aside from the superficial syntax differences, if you take a step back and think about this, it’s striking how similar Smalltalk and Ruby really are! Not only do both languages share the same class variable concept, but I wrote the Polygon class, declared a class variable and printed it out exactly the same way in both languages. In fact, you can think of Ruby as a newer version of Smalltalk with a simpler, easier to use syntax!

As I said at the top, Smalltalk shares class variables among subclasses the same way Ruby does. Here’s how I would declare the Triangle subclass in Smalltalk and Ruby:

Polygon subclass: Triangle [
]
Triangle class extend [
  set_sides: num [ Sides := num ]
]

Polygon sides printNl.
=> 10 
class Triangle < Polygon
  def self.sides=(num)
    @@sides = num
  end
end

puts Triangle.sides
=> 10

Here I declare the Triangle subclass and a method to set the class variable’s value. Now let’s try changing the value of the class variable from the subclass:

Triangle set_sides: 3.
Triangle sides printNl.
=> 3
Triangle.sides = 3
puts Triangle.sides
=> 3

No surprise; by calling the set_slides class method (sides= in Ruby) I can update the value. But notice since both Polygon and Triangle share the same class variable, it’s changed for Polygon also:

Polygon sides printNl.
=> 3
puts Polygon.sides
=> 3

Again, we’ve seen Ruby and Smalltalk behave in exactly the same way.

One way the two languages differ is that Smalltalk does allow you to create a separate class variable for each subclass, if you want. By repeating the class variable definition and the accessor class method in both classes they become separate variables, at least in GNU Smalltalk which I was using:

Object subclass: Polygon [
  Sides := 10.
]

Polygon class extend [
  sides [ ^Sides ]
]

Polygon subclass: Triangle [
  Sides := 3.
]

Triangle class extend [
  sides [ ^Sides ]
]

Polygon sides printNl.
>= 10

Triangle sides printNl.
>= 3

This isn’t true in Ruby; as we saw above @@sides will always refer to the same value.

Class instance variables

In Ruby if you want to keep a separate value for each class, then you need to use a class instance variable instead of a class variable. What does this mean? Let’s take a look at another one of John Nunemaker’s examples:

class Polygon
  def self.sides
    @sides
  end
  @sides = 8
end

puts Polygon.sides
=> 8

Now since I used the @sides notation instead of @@sides, Ruby created an instance variable instead of a class variable:

Conceptually there’s no difference, until I create the Triangle subclass again:

class Triangle < Polygon
  @sides = 3
end

Now each class has its own copy of the value @sides:

Now let’s try the same thing in Smalltalk. In Smalltalk to declare an instance variable you call the instanceVariableNames method on a class:

Object subclass: Polygon [
]

Polygon instanceVariableNames: 'Sides '!

Polygon extend [
  sides [ ^Sides ]
]
class Polygon
  def sides
    @sides
  end
end

Here I’ve created a new class Polygon, a subclass of Object. Then I send the instanceVariableNames message to this new class, telling Smalltalk to create a new instance variable called Sides. Finally, I reopen the Polygon class and add the sides method to it. Again I show the corresponding Ruby code on the right.

However, here Sides and @sides are instance variables of Polygon objects, and not of the Polygon class. To create a class instance variable in Smalltalk, you instead have to send the class message to Polygon first before calling instanceVariableNames or extend, like this:

Object subclass: Polygon [
]

Polygon class instanceVariableNames: 'Sides '!

Polygon class extend [
  sides [ ^Sides ]
]
class Polygon
  def self.sides
    @sides
  end
end

Again, notice that the Smalltalk and Ruby code snippets are really just two different ways of expressing the same commands. In Smalltalk you say Polygon class extend [ sides… while in Ruby you say class Polygon; def self.sides. To me Ruby seems to be a more succinct version of Smalltalk.

Metaclasses in Smalltalk and Ruby

This diagram, taken from Alan Kay’s fascinating article The Early
History Of Smalltalk, resembles the class hierarchy Ruby would
use 20 years later!

Let’s take another look at the line of code I used above to create an instance variable in Smalltalk:

Polygon instanceVariableNames: 'Sides '!

Translating from Smalltalk into English, this means:

Take the Polygon class,
send it a message called instanceVariableNames,
and pass the string Sides as a parameter.

Again, this is how you define instance variables in Smalltalk. That is, now when I create instances of the Polygon class, they will each have a Sides instance variable. Saying the same thing in a different way, to give all polygon instances an instance variable, I call a method on the Polygon class.

As I explained above, to create a class instance variable in Smalltalk you have to use the class keyword, like this:

Polygon class instanceVariableNames: 'Sides '!

This code literally means: call the instanceVariableNames method on the Polygon class’s class. Following the same pattern, now all instances of the Polygon class will contain a class instance variable. But what is the “class of the Polygon class” in Smalltalk? What does this mean? Spending just a moment at the GNU Smalltalk REPL we can find out:

$ gst
GNU Smalltalk ready

st> Polygon printNl.
=> Polygon

st> Polygon class printNl.
=> Polygon class

I first display the Polygon class object, and I get “Polygon”. Displaying the class of the Polygon class, I get “Polygon class.” But what type of object is this? Let’s call class on it:

st> Polygon class class printNl.
=> Metaclass

Ah… so the class of a class is a Metaclass. Above, when I called instanceVariableNames to create a class instance variable, I was actually using the Polygon metaclass, an instance of the Metaclass class.

Here’s a diagram showing how these classes are all related in Smalltalk:

By now, it should be no surprise if I tell you internally Ruby uses the same model. Here’s how classes work inside of Ruby:

In Ruby whenever you create a class, Ruby internally creates a corresponding new class called the “metaclass.” Unlike Smalltalk, Ruby doesn’t use this for class instance variables, but only to keep track of class methods. Also, Ruby doesn’t have a Metaclass class, but instead all metaclasses are simply instances of the Class class.

In Ruby the metaclass is a hidden, mysterious concept. Ruby silently creates it without telling you and doesn’t expose the metaclass in the language directly. In Smalltalk, however, the metaclasses are not hidden at all and instead play a large role in the language. Creating a class instance variable, as I did above, is just one example of using a metaclass in Smalltalk. Another good example is the way you add class methods by calling extend.

When you ask for a class’s class in Ruby, you simply get Class. Ruby doesn’t tell you about the metaclass:

$ irb
> class Polygon; end
> Polygon.class
Class

To see a Ruby metaclass, you have to use a trick instead:

$ irb
> class Polygon
>   def self.metaclass
>     class << self
>       self
>     end
>   end
> end
=> nil
> Polygon.metaclass
=> #<Class:Polygon>

“#<Class:Polygon>” is the metaclass of Polygon. This syntax means the metaclass is “an instance of Class for the Polygon class,” or the metaclass for Polygon.

* Quoted text and images from: The Early History Of Smalltalk, by Alan Kay, © 1993 Association for Computing Machinery

An Interview With Jim Weirich

2012-12-13T00:00:00Z

This appeared on RubySource.com last week; just getting around to posting a link to the interview here also….

Jim Weirich is the Chief Scientist at Neo

I’ve been familiar with Jim Weirich’s name for a while; among other things he wrote the “rake” tool which most of us use on a daily basis. Then I was lucky enough to see Jim do a presentation at GoRuCo this June, when he explained some of the more advanced features of rake. I was immediately struck by how Jim was able to explain a very complex topic in a natural, straightforward way. Later this Fall at RubyConf I saw Jim gave an amazing keynote address that derived the Y-Combinator from first principles, explaining some of the basic ideas behind Lambda Calculus along the way. This time he not only clearly explained an even more difficult topic, but was able to make what would normally be a dry, mathematical subject very entertaining.

This month I was thrilled had the chance to interview Jim for RubySource; it was a great opportunity for me to learn more about him and how he approaches public speaking. We also had a chance to talk about how he got started as a computer programmer, why he learned Ruby, functional programming, Ruby’s threading model and also his new RSpec-Given framework. I’ve typed in the interesting parts of our conversation and posted them on RubySource.com.

A High Level Code Walk Through Ruby MRI

2012-12-03T00:00:00Z

Watch it now on rubyinside.com!

Have you ever thought about taking at look at Ruby’s internal C source code, but weren’t quite sure where to get started? Well, this weekend Peter Cooper and I recorded a screencast that is just for you. We went on a tour through the MRI source code tree, and recorded it in a 33 minute screencast called: A High Level Code Walk Through Ruby MRI. We’ll give you a “lay of the land,” a sense of what is where inside the MRI C source code tree and suggest places to get started reading the C source code yourself.

Special thanks to Peter for taking time out of his busy schedule to record and edit the video, and for being such a big fan of my book, Ruby Under a Microscope! I’m sure you all know Peter as the editor of Ruby Inside and Ruby Weekly, but he’s also recorded a number of great screencasts. Just this June he produced the fantastic Ruby 1.9 Walkthrough, and earlier in February he did the fun Ruby Trick Shots piece. In fact, Peter’s new Kickstarter project, The Ruby 2.0 Walkthrough, was backed just last week – keep an eye out for that in the coming months! This is the first screencast I’ve ever done; having the chance to do it with Peter was a bit like stepping onto a tennis court for the first time and getting a private lesson from John McEnroe – or maybe Andy Murray would be a better analogy.

Let us know if you like this; if enough people are interested we may do some more screencasts on Ruby internals, diving into more detail that we had time for this week. Enjoy!

My eBook build process and some PDF, EPUB and MOBI tips

2012-11-27T00:00:00Z

Ruby Under a Microscope is an illustrated guide to
Ruby internals. No C programming required!

In case you missed it, last month I self-published an eBook about Ruby internals called Ruby Under a Microscope. To date I’ve sold over 600 copies – thanks everyone! I’ve never written anything so ambitious before, and I’m grateful for your support. I hope it’s been a fun read, and that you come away with a better appreciation for the amazing work Matz and the rest of the core team have done to create such a beautiful language. It was certainly a lot of fun to write!

In the spirit of “sharing is caring,” and to follow in the footsteps of some Ruby self-publishers like Jesse Storimer (see 4 Months of ebook Sales and Lessons Learned Getting Other People to Sell My Ebook) and Avdi Grimm (see My authoring tools) who have been generous with their knowledge, I’d like to try to pass along whatever information I can about how to publish an eBook. This post contains a high level description of my build process for Ruby Under a Microscope, and also a few tips for dealing with the PDF, EPUB and MOBI file formats that I learned along the way. If anyone would like actual code or more technical detail about my build process, or if there’s any other way I can help you self-publish something, please let me know!

My authoring tools

To write Ruby Under a Microscope I used Apple Pages on a Mac laptop. While I love VIM for writing code, I find it easier and more natural to use a traditional word processor to write English text. Also, Apple’s spelling autocorrect feature works nicely; I prefer to use the “Automatically use spell checker suggestions” option in Preferences –> Auto-Correction.

As you might know, Ruby Under a Microscope contains a large number of diagrams – a picture is worth 1000 words, and often I find visual aids are the only way to communicate the complex ideas, algorithms and data structures Ruby uses internally. To draw these I used the Omnigraffle product from The Omni Group. This is an amazing tool that allows you to produce professional looking diagrams very quickly. It also integrates very nicely with Apple Pages; I can copy/paste a diagram from Omnigraffle right into Pages and immediately see something that will closely resemble my final document. As I’ll explain below, I also ended up purchasing a license for Omnigraffle Pro, in order to be able to export my diagrams as SVG vector image files, a feature the standard version does not contain.

The Bookshop gem

Once I had the bulk of my writing done, I copied my text into a series of HTML/ERB files and used a gem called Bookshop to manage the process of creating the PDF, EPUB and MOBI target files from them. Bookshop, in turn, uses a tool called PrinceXML to create the PDF file:

As you can see, Bookshop is essentially a Ruby static site generator like Jekyll or Middleman: you use it to run a series of ERB transformations that produce static HTML and CSS. Then Bookshop launches PrinceXML to convert the HTML to PDF. PrinceXML is not cheap ($495 US), but has been worth every penny to me. It does a remarkable job rendering the PDF, allowing you to use really any CSS styling/design code you you would like to. With PrinceXML, creating a beautiful PDF file is as simple as – or as hard as – creating a beautiful web site.

PrinceXML also supports a number of print-only related CSS directives you may not be familiar from web development, such as the “page-break-before” attribute or the @page directive. For example, I used this CSS code to indicate I wanted page numbers in the lower left corner for left side pages:

@page :left {
  @bottom-left {
    font: 8pt "Helvetica Neue", serif;
    content: counter(page);
    padding-top: 2em;
    vertical-align: top;
    color: #880000;
  }
}

One of the nicest features of Bookshop was that out of the box it provided a series of CSS templates to get me started, containing a series of example CSS styles I could use for page numbers, the table of contents and more.

Next, here’s how Bookshop creates the EPUB file:

You can see here that the EPUB is essentially a ZIP file containing the static HTML/CSS source code, along with a few mysterious XML files (content.opf, toc.ncx, etc.) that contain the book’s table of contents, a list of your HTML and other source codes files with their mime types, and other meta data. Bookshop also automatically runs the EpubCheck utility on the finished EPUB file to help you be sure you got everything correct in those XML files.

If you’re really interested in learning the details of the EPUB format, this fun, practical video by Paul Salvette might be worth watching: http://www.youtube.com/watch?v=RSc7XZzMkq0

Finally, Bookshop launches Amazon’s KindleGen utility to generate the MOBI file from the EPUB file:

Customizing Bookshop

To make my life easier, I ended up customizing Bookshop to support code syntax highlighting (using Coderay) and to allow Markdown as the source file format (using Redcarpet). I also customized it to be able to manage the large number of diagram images files I created in special ways. If anyone is interested in these details, let me know. In a nutshell, I used SVG to represent the diagrams for the PDF, but PNG for the diagrams in the EPUB/MOBI files; using two different file formats for the same images required some code changes to Bookshop.

I’ve also heard good things about the Kitabu gem, which seems to function in largely the same way as Bookshop. I haven’t tried it, but if I write another eBook I’ll probably look at using Kitabu instead, since it already contains support for code syntax highlighting and Markdown. It’s also encouraging that Jesse Storimer, a prolific eBook author, is a maintainer on that project.

PDF tip: use vector image file formats

PDF is the the Mercedes of eBook file formats. I’m guessing most people who read technical eBooks use a PDF file on a laptop: it just works, it looks the same on every platform, and we all have the confidence that the rendered document will appear the same as the original document did. After spending months crafting a PDF file, I’m amazed at what Adobe’s software can do – why read a book using any other file format?

One important but easily overlooked property of the PDF file format is that it is vector based. That means that, like SVG and related image file formats, all of the text and other rendering information in a PDF document is saved as a series of vector commands: “go here, draw this, move there, draw that, etc.” But since the Adobe’s PDF file format is more or less a black box, this doesn’t normally matter: who cares how the PDF file format works internally?

I certainly didn’t, until I tried to render some of the many diagrams in Ruby Under a Microscope in a PDF file. For my first attempt, I rendered my diagrams as PNG images and then included them in my HTML using <img> tags, as I normally do for blog posts. PrinceXML then produced a PDF file that looked like this:

While this isn’t horrible, you can see the “YARV internal stack,” “rb_control_frame_t” and other text in my diagram at the bottom is blurry and somewhat disappointing to look at. The text above, which originally came from the HTML source code of my book, looks fine. It almost looks as if you were viewing the diagram through a thick piece of glass, while viewing the rest of the document directly with the naked eye.

The problem here is that the end user PDF viewer software, for me Apple’s Preview app, has to resize the original PNG image for the diagram, scaling the text as necessary along the way. This produces the blurriness. It’s also possible the scaling is performed by PrinceXML when the PDF file is generated.

It took me a few days of research, trial and error to stumble upon the solution: since PDF is internally a vector based format, why not render my diagrams using a vector based image file format? After paying some extra money to upgrade to Omnigraffle Pro, I was able to use the “File –> Export” command:

… and then select the “SVG vector drawing” file type (the standard version of Omnigraffle doesn’t support this):

Now the real magic happens: when I include an SVG image in my HTML using a standard <img> tag, PrinceXML generates a PDF file that includes the vector commands to render the diagram! In fact, I also noticed that PrinceXML includes whatever font I used in the Omnigraffle diagram right inside the PDF file:

prince: loading image: builds/pdf/assets/images/ch01/process.svg
prince: used font: Menlo, Bold
prince: used font: Menlo, Regular

Here’s what same diagram looks like in the final version of Ruby Under a Microscope:

The reason this looks better is that the end user PDF viewer app, Apple Preview, Adobe Reader, iBooks or whatever software your reader has, draws the diagram text at the proper size at the moment the reader opens the page, using the font that PrinceXML embedded into the PDF file.

EPUB tip: package many small HTML files, not one large one

While writing Ruby Under a Microscope I also became familiar with the EPUB file format. It’s a useful file format because it’s become an open standard shared by a large number of eBook reader devices. You can read EPUBs on a high end device like an iPad, on a variety of Android tablets, and also on cheaper eBook readers.

An EPUB file is really just a ZIP file that contains a HTML/CSS web site, along with a few confusing, bizarre XML files. In fact, in hindsight I’ve realized that an EPUB file closely resembles a J2EE web application – but without the Java! You might remember J2EE from the early 2000s and 1990s – it was how we created web sites before Rails came along in 2004 and made all our lives easier.

Unzipping my EPUB file, here’s what you’ll see:

$ unzip ruby-under-a-microscope.epub 
Archive:  ruby-under-a-microscope.epub
 extracting: mimetype                
  inflating: META-INF/container.xml  
  inflating: OEBPS/assets/css/page-template.xpgt  
  inflating: OEBPS/assets/css/stylesheet.epub.css  
  inflating: OEBPS/assets/images/canvas-ana.png  
  inflating: OEBPS/assets/images/ch01/ast-compile1.png  
  inflating: OEBPS/assets/images/ch01/ast-compile2.png  
  inflating: OEBPS/assets/images/ch01/ast-compile3.png  
  inflating: OEBPS/assets/images/ch01/ast1.png  

… etc …

  inflating: OEBPS/ch04-part6.html   
  inflating: OEBPS/ch05-part1.html   
  inflating: OEBPS/ch05-part2.html   
  inflating: OEBPS/ch05-part3.html   
  inflating: OEBPS/ch05-part4.html   
  inflating: OEBPS/ch05-part5.html   
  inflating: OEBPS/ch05-part6.html   
  inflating: OEBPS/conclusion.html   
  inflating: OEBPS/content.opf       
  inflating: OEBPS/cover.html        
  inflating: OEBPS/preface.html      
  inflating: OEBPS/title.html        
  inflating: OEBPS/toc.html          
  inflating: OEBPS/toc.ncx

It really does look like a committee of Java programmers designed the EPUB spec! We have something called “META-INF/container.xml,” a directory called “OEBPS,” and there are lots of confusing XML files with names like content.opf and toc.ncx. These all need to contain the proper information in precisely the correct format. Fortunately, as I mentioned above, the Bookshop gem runs the EpubCheck tool to validate that all the information in these files is correct.

On of the drawbacks of the Bookshop gem was that I had to write some Ruby code myself to generate the table of contents information stored in the “toc.ncx” file, and also the list of HTML and image files contained in the “content.opf” file. In hindsight the Kitabu gem might have taken care of this detail for me. Ideally the TOC info should be autogenerated from the <h1> or <h2> tags I use in my text.

One other important detail here: you’ll notice my HTML content is split up into a series of different HTML files: “ch04-part6,” “ch05-part1,” etc. Originally Bookshop created a single, large HTML file containing the entire text of the book and included that in the EPUB file. However, then I heard from Avdi Grimm and other readers than it was slow on some EPUB reader devices. The problem was that the reader device would hang while opening up the large HTML file, trying to render 100s of pages all at once.

With some help from Mike Cook I was able to fix this by splitting my text up into smaller HTML files. I did this by further customizing Bookshop, but I suspect Kitabu or other tools out there can do this automatically for you.

MOBI tip: use relative font sizes and Amazon CSS media types

Finally, to produce a book you can read on all of the different Kindle devices, the most popular eBook reader in the U.S., you need to create a MOBI file. Ironically, the MOBI format wasn’t even invented by Amazon, but now Amazon is the only reason this format continues to be relevant. As I explained above, Bookshop does this by running the KindleGen utility, from Amazon. I’ve heard rumors Amazon might directly support EPUB in the future, which would make all of our lives easier.

Be sure to download and use the Kindle Previewer app. This allows you to see how your MOBI file will render on seven or more different varieties of the Kindle. eBooks appear somewhat differently on each version of the Kindle and without this app there’s no way to know what will happen.

Using the Kindle Previewer with Ruby Under a Microscope I ran into trouble rendering fonts on some versions of the Kindle. Newer versions of Kindle, like the Kindle Fire, worked well, while older Kindles had trouble when I used certain fonts. More trial and error revealed that I could use only relative font sizes in my CSS code: font-size: 50% instead of font-size: 10pt, for example. I was also able to distinguish between newer and older Kindles using this special CSS media type directive invented by Amazon:

@media  amzn-mobi
{

.section-caption {
  text-align: left;
  font-style: italic;
  font-size: 50%;
}

}

@media  amzn-kf8
{

.section-caption {
  text-align: center;
  font-style: italic;
  font-size: 75%;
}

}

Why go to all this trouble?

If you made it this far, then you must really be interested in self-publishing. I have to admit that the technical work involved with producing an eBook myself was far more tedious and difficult than I had ever thought it would be. I can imagine that partnering with a publishing company would make this all a lot easier – probably you would be able to work within an established, proven technical publishing pipeline. But one of the joys of self-publishing is being able to have full control over the final product. There’s something thrilling and fun about controlling every last detail yourself. I hope this post saves you a few hours of frustration when it comes time to produce your eBook, or that it provides you a bit of encouragement to take the first step!