It's no secret that Crystal's standard library looks almost exactly the same as Ruby. Ruby's one has a very well designed API, with lots of useful things in it, so why not have a similar API in Crystal? Why rethink names and other things from scratch?

So a few years ago we started adding these methods as we needed them for the compiler, or just for fun and completeness. While doing that, we would always compare Ruby's performance with Crystal. The idea was that, because Crystal is statically typed and compiled, relying on LLVM optimizations, it would always beat Ruby. It turns out, that wasn't always the case! We would think "How can Ruby be faster here? What's this magic?." Well, looking at Ruby's source code we found so many beautiful and performant algorithms. And they are all hidden. Most people don't know about them.

So here I will talk about some of them.

Multiplying strings or arrays

In Ruby you can do this:

"hello" * 3 # => "hellohellohello"

What's the most obvious way to implement this? Like this:

The string consists of 5 bytes
We are multiplying it by 3, so we'll need a string of 15 bytes
Iterate 3 times by copying those 5 bytes over and over (for efficiency, we can use something like memcpy)

And that was the first implementation we did in Crystal. And Ruby was faster!

So what does Ruby do? Let's say we need to multiply the string by 16. We can do this:

The string consists of 5 bytes
We are multiplying it by 16, so we need 80 bytes total
First we copy 5 bytes from the original string. Great! 75 to go
Next we copy 5 bytes more. Great! 70 to go.
Now that we have 10 bytes ("hellohello"), we can copy those 10 bytes in the next position. Now we copied 20 bytes. 60 to go.
Now that we have 20 bytes ("hellohellohellohello") let's copy those over. Now we copied 40 bytes! 40 to go.
Next we copy the 40 bytes we have to the next position. Done! All 80 bytes copied.

This doesn't look like an optimization at all, right? After all we end up copying 80 bytes in any case. However, copying 40 bytes with a single memcpy call is more efficient than doing 8 memcpy calls copying 5 bytes. memcpy is really well optimized! I don't know what tricks it does, but it can copy large memory portions very fast.

Of course this works great when the amount with are multiplying by is a power of two. If that's not the case we can fill the remaining bytes by using the simpler algorithm.

Because I haven't read many algorithm books, maybe this is a well known algorithm? I don't know. But here's something. Ruby introduced this optimization 14 years ago, while Go introduced it 8 years ago. In both cases the first algorithm to use was the simplest one, so at least it doesn't look like this optimization is immediately obvious.

There's more!

Ruby also has another optimization, which I didn't see in Go. This isn't to prove Ruby is better than Go or anything like that, it's just to show how much care there is in every single Ruby method in the standard library, and to show that this isn't like that in every language out there.

If we are doing something like this:

"a" * 100

Ruby will notice that the string we are multiplying occupies only one byte. In that case, it does the following optimization:

Create a new string of size 100 bytes
Call memset to fill those 100 bytes with the single byte from the original string.

Arrays

Before meeting Ruby I was mainly coding in Java and C#. If you need some sort of collection in those languages you have many choices. Let's see Java:

This is also similar in Rust:

The reason there are many collection types is that each one of them has better performance in some use cases, but worse performance in others. Depending on your use case you should choose one or another.

So, before you just start collecting elements somewhere, you have to think about how that collection of elements is going to be used, by you and potentially others! Maybe you need to document "Do this, but please don't do that because it could be inefficient," and so on.

Where are all these collection types in Ruby?

One type to rule them all

In one of my many trips to Rubyland I found an old sheet that contained ancient writing. I didn't understand the meaning, so I copied the contents to a foo.rb file and ran it with ruby. This was the output:

Three Types for the Java-kings under the beans,
Seven for the Rust-lords in their halls of stone,
Nine for Mortal Men doomed to use C++,
One for the Happy Lord on his shiny throne
In the Land of Ruby where Happiness lies.
One Type to rule them all, One Type to find them,
One Type to bring them all, and in the bliss bind them,
In the Land of Ruby where Hapiness lies.

In Ruby, there's only one type for this: Array. And it's implemented in a way that covers a lot of uses cases. When you need a collection of elements you don't need to think what to use: the answer is to use Array. Simplifying users lives is what Ruby is all about.

First, it's implemented like Java's ArrayList and never like a LinkedList. A linked list looks nice in paper, but having to allocate memory for every node when you want to insert an element is very expensive! Then traversing the list is also not great, when the memory for these nodes can be scattered, so cache locally can't be used.

I don't want to get too technical, but Array is implemented by allocating some memory, let's say with an initial capacity of 10 elements, but it starts empty. Whenever you insert an element, as long as the current size didn't reach the current capacity, you do it. If not, you ask a bit more memory (let's say, 20 elements), copy what you had before into this new space, and then put the new element.

Array has methods like push and pop that let you use it like a stack, and that's easy to do with the structure described above. But then it has methods like shift and unshift that let you use it as a queue or dequeue too! Normally if you want to insert an element right at the beginning of an array you would have to move all the existing contents forward, then put an element. I'm not sure what Ruby does here, but that's definitely not what it does. It looks like Ruby knows where the array starts, so when you shift, it just moves that pointer forward. It's really efficient!

A lot more

There are a lot more operations you can do on an Array, so many that it's a lot to cover in a blogpost, and they are all handled with extreme care and thought, so you can use arrays however you need them and have a good guarantee that things will work well and fast.

Coming up next...

I don't know! I thought this post was going to be the final part, but it seems I still have many nice things to say about Ruby, so we'll see :-)

Blog

Why I love Ruby: the secret algorithms

Ary Borenszweig