Micro Talk: Why Hashes Will Be Faster in Ruby 2.0

In this micro talk, I'll review the basic theory behind hash functions and hash tables, show you the new internal data structures that Ruby 2.0 uses to save keys and values, and present some performance data that proves this optimization exists and how much time it will actually save you.

GoRuCo 2012

00:00:15.510 Hello, my name is Pat Shaughnessy. I'm thrilled to be here. Thank you for the opportunity. I have only ten minutes to talk, so let me give you a quick two seconds about me. I write a blog, I'm active on Twitter, and I work at McKinsey & Company, which is a management consulting firm. Today, I'm here to discuss why hashes will be faster in Ruby 2.0.

00:00:31.359 Since you are all Ruby developers, you are familiar with hashes and their usage. I won’t go into detail about how to create an empty hash or how to retrieve a value using a key. Instead, I want to focus on how hashes are implemented internally—what occurs inside Ruby when you utilize a hash. My goal today is to put the hash object under a microscope, so to speak, to take a closer look.

00:00:50.350 The closer you examine something, the more you uncover details you may not have known existed. There are really interesting advancements happening with hashes. Interestingly, I discovered how remarkably fast they are. I measured the time it takes to retrieve an element from a hash, regardless of the size of that hash. On the left, I started with a hash of size 1, and I measured the performance as the size increased up to 1 million elements. It took merely microseconds to access an element from a hash, which is akin to having a mini search engine built into the Ruby language.

00:01:10.440 It's astounding how Ruby accomplishes this. At its core, Ruby, like most programming languages, uses a data structure known as a hash table to implement hash objects. A hash table is essentially a collection of bins or buckets, which I'll demonstrate. Initially, Ruby uses 11 bins to store values in a hash, saving the keys and values in something called an 'ST table entry structure.' Today, we won’t dive into the nitty-gritty of C-level programming details, but suffice it to say that the keys are stored in a memory structure.

00:01:35.420 A hash table's functionality relies on assigning each entry to one of the bins—in this case, bin number three. How does Ruby determine which bin to use? It employs a 'hash function.' A hash function is simply a mathematical formula that takes any value and returns an integer. You can experiment with it yourself by running IRB and applying the `.hash` method to any Ruby value or object. You'll receive a seemingly random big number in return; this number is referred to as a hash number or hash value. While they may appear random, they aren't because the same input will always yield the same output.

00:01:55.850 Ruby then divides that hash value by 11 and computes the remainder—which is the modulus operation using the number of bins in the hash table. This result serves as the bin index, determining which bucket the entry will occupy. For example, when I save a key-value pair in a hash, Ruby processes the key through the hash function and the result is a large random-looking number. Upon dividing this number by 11, the remainder might be 3, which indicates where that entry will reside.

00:02:16.070 The essence of a hash function is that it should return numbers that are evenly distributed. As you distribute entries across the hash table, they will ideally be evenly spread out. However, it’s important to note that some entries might collide and yield the same hash value, as illustrated by the fourth entry also resulting in a reminder of 3. That’s completely acceptable because these bins are essentially linked lists.

00:02:40.770 Along the top of the hash table, you will find 11 pointers, each pointing to the first entry within a bucket. Each entry has a pointer to the next entry, forming a linked list. As you add more entries—say 20 or 30—the linked lists can become a bit longer. So, why does Ruby incorporate this structure? The main objective is to optimize performance and make hashes fast. With 30 or 40 entries in a hash, retrieving a value using its key only requires running the key through the hash function again. This returns the same large number, and once again, Ruby will compute the bin index to access the correct bucket without needing to scan all entries.

00:03:01.670 An additional benefit of hash tables is that they automatically expand as more entries are added, accommodating growing data. You can insert thousands or millions of entries into a hash, and Ruby will continuously adjust. The algorithm maintains an average of 5 or fewer entries per bucket, allowing efficient indexing.

00:03:31.380 Now, let's discuss Ruby 2.0 and how hashes are structured. The implementation mechanism of hashes is fascinating already, but what’s particularly noteworthy about Ruby 2.0 is the efficiency improvements introduced by the Ruby core team. They carefully studied the insertion process—the slowest component of which has traditionally been the malloc function, commonly used to allocate memory.

00:03:56.320 As many of you may know, malloc retrieves memory from the operating system when new elements are added to a hash. This process can be comparatively slow because it requires the OS to find available memory, align it, and return a pointer. In Ruby 2.0, the core team made the strategic choice to avoid calling malloc altogether to enhance speed. Furthermore, they simplified the data structures that store these entries.

00:04:16.520 Instead of utilizing separate entry structures, Ruby will now save keys and values directly in the array at the top of the hash. This approach allows storing six key-value pairs in the same memory space that previously accommodated 11 pointers, significantly speeding up the process. These enhancements are simply brilliant and highlight the ingenuity of the Ruby core team.

00:04:40.620 However, an intriguing thought arises: if hashes are now structured this way, do they truly remain hashes? When you upgrade to Ruby 2.0, you will find that your hashes may no longer operate as hashes in the traditional sense. They will, in essence, be arrays when involving up to six elements, since all six fit within that memory space. This process will be entirely seamless, and developers will likely not even notice this transition.

00:05:02.829 So, how will this change affect your lives as Ruby developers? What kind of performance improvement can we expect from this? For me personally, it goes beyond performance; it's just fascinating to dive into the internals of Ruby and understand how it all operates.

00:05:25.420 In terms of performance evaluation, I created a comparison chart for hashes of various sizes. On the left, you’ll see an empty hash, then hashes with one entry, two entries, and so forth. The bars depict the duration required to insert one additional element into these hashes. Notably, in Ruby 2.0, the time to insert the first few elements is faster than in previous versions.

00:05:45.230 There is an observable spike at the sixth entry, which occurs because we can only fit six key-value pairs within that allotted space for the 11 pointers. Upon attempting to insert the seventh element, Ruby must revert to the previous algorithm and reallocate a hash table, thus impacting performance.

00:06:10.700 I experimented further by creating 10,000 database records and loading them all into memory. I ensured that the database table contained six columns or fewer to evaluate optimization. In doing so, I discovered an approximate 6% performance improvement. However, I believed this scenario was contrived; it’s not common to load such a large volume of records into memory in a single operation.

00:06:39.120 Resorting to a practical approach, I generated a Rails application and used a scaffolding generator. I picked one of the specs that had emerged and placed it into a loop to measure the Ruby execution time solely. I found that it was over 2.5% faster, which is quite interesting.

00:07:02.670 I questioned how this performance could be measured since I was primarily using just a handful of hashes—perhaps five at most. There was an attributes hash for the new model, a session hash, and another empty hash for the request parameters. However, I overlooked the frequency with which Rails and Ruby itself utilize hashes internally.

00:07:23.690 While you may see five hashes visually, Rails employs hashes for numerous functions, and Ruby keeps track of various elements with hashes as well. I took it upon myself to implement some additional code in C within Ruby to count the total number of hashes created during a single execution of the loop, and it reported 409 hashes being instantiated.

00:07:44.030 This quantity surprises many when you consider how commonly hashes are used in typical Ruby on Rails applications. Beyond Rails, Ruby itself frequently utilizes hashes for a variety of functions, such as tracking methods, modules, and classes.

00:08:03.690 This exploration has been incredibly exciting for me, and I’m even undertaking a book project titled 'Ruby Under a Microscope'. If you share an interest in Ruby's inner workings and want to delve deeper, feel free to check it out on my website.

00:08:23.500 That's all I have for you today, and I appreciate your time!