Extending CRuby With Native Graph Data Type

MountainWest RubyConf 2013

Andy Pliszka

#performance-optimization

Extending CRuby With Native Graph Data Type

by Andy Pliszka

The video titled "Extending CRuby With Native Graph Data Type," presented by Andy Pliszka at MountainWest RubyConf 2013, explores the integration of a native Graph data type into the CRuby language by intercepting the C source code. The discussion begins with an introduction to graphs, emphasizing their significance through a demonstration using social network data, particularly how the connectedness of individuals can reveal groupings or clusters. Pliszka explains fundamental graph representation techniques and highlights how these can be implemented in Ruby using linked lists.

Key points discussed in the presentation include:

Introduction to Graphs: Pliszka introduces graphs and demonstrates their utility with a social network example, showcasing connected components using simple graph algorithms.
Graph Representation: He explains that linked lists serve as an efficient method for representing graphs in memory.
Algorithm Demonstration: The breadth-first search (BFS) algorithm is demonstrated using a grid graph to illustrate how nodes are explored iteratively.
CRuby Source Code Examination: Pliszka shares insights into the CRuby source code, underlining how knowledge of Ruby translates into understanding CRuby and its extensions, particularly in creating a new class in C.
Practical Creation of Graph Class: He walks through the process of defining a graph class in C, including memory allocation, initialization, and method linking, emphasizing the differences in how C handles memory versus Ruby.
Performance Comparison: The video highlights remarkable performance disparities between CRuby and Ruby, showcasing tests where C implementations of graph algorithms significantly outperformed their Ruby counterparts, citing scenarios with extensive datasets.
Conclusions and Insights: Pliszka summarizes that extending CRuby with C not only enhances performance but also provides deeper comprehension of Ruby’s functionality at a fundamental level, demonstrating the feasibility and advantages of integrating low-level programming with high-level abstractions in Ruby.

Overall, the talk demonstrates the broader potential of CRuby to facilitate experimentation and performance optimizations while maintaining the user-friendly aspects of Ruby. The takeaway emphasizes how understanding and extending CRuby can lead to significant performance improvements for algorithms like BFS, Dijkstra, and Minimum Spanning Tree operations, making it a compelling avenue for Ruby developers looking to enhance application performance.

00:00:19.780 Okay, so today I'll briefly introduce graphs, and then we're going to walk through the CRuby source code. At the end, we will try to add a class using CRuby, specifically a native data type directly from C, and use it from Ruby.

00:00:25.850 So, why are graphs important? Let me show you a quick demo. This is my social network, specifically my Facebook network, where I applied a very simple algorithm: connected components and strongly connected components. Because of the way people are connected with each other on Facebook, you can see that it created multiple clusters.

00:00:39.950 For example, you can clearly see the companies I work for because all the individuals associated with those companies are strongly connected among themselves. This is actually a very straightforward algorithm. Essentially, you run the depth-first search algorithm on the graph in two different directions, and in the end, you end up with clearly marked nodes that indicate which network they belong to, such as different companies I work for and my family. This demonstrates how even with trivial routes, you can extract a lot of data from your social networks.

00:01:06.140 So, how do we represent graphs in code? This is just an excerpt from an algorithm book. We have a simple graph with five nodes; it's not fully connected. One of the efficient ways to represent a graph in memory is by using linked lists. Here, you can see a list of lists where each node has a list of nodes that it is connected to. For instance, node one is connected to nodes two and five. You can see that one is connected to two and five, marking the end of the linked list. In Ruby, the same principle applies. You can create a linked list using arrays or hashes.

00:01:45.700 I chose to demonstrate breadth-first search, which is a great algorithm to showcase this concept. This is how a breadth-first search works. Here, you can observe a grid graph, which is an excellent example. It appears that we are flooding the entire graph with red pigment. To start, you take a source node, marked here as red, and the first thing you do is explore all its neighbors and then their neighbors, and so forth. You can observe that we first explore the four directly connected nodes, followed by their neighbors, until we completely explore the graph. Using this approach, you can find nodes containing certain elements, such as identifying people in my social graph who have a large number of followers or specific skills.

00:02:52.890 That wraps up my quick introduction. Now, let's take a look at the CRuby source code. When I started examining Ruby, I appreciated its capabilities as a great language, but I wanted to understand how it actually works. One way to do this is by looking at the CRuby source code. To facilitate this, I thought, 'Why don't I implement a graph data structure similar to how we have an array or hash?' Before doing so, I had to explore CRuby, and I want to show you how easy it is to understand the code. Although it’s in C, our knowledge of Ruby and familiarity with the API helps quickly orient ourselves in the source code.

00:04:02.850 I was able to start experimenting and adding new methods within just a couple of hours. Let's first look at how the array class is defined. In C, each class has an 'init_array' procedure. This is where the class is declared, and in this case, it's the C array class. The code is written in a descriptive manner, making it straightforward to understand. We define the class similarly to Ruby, like 'class Array,' and we declare that this class inherits from 'Object,' just as the array class behaves in our everyday use. Additionally, this class includes the 'Enumerable' module, which you can see has an equivalent code in Ruby.

00:05:10.050 It was very simple for me to add a new class, such as 'Widget', by implementing just a couple of methods. You'll find declaration and initialization in nearly every C Ruby class. Here are two essential methods you’ll notice: the allocation function and the initialization function. The allocation function is vital because, in C, memory must be allocated manually. You cannot rely on the usual Ruby services for this; you must declare and allocate memory on your own. The class then initializes, which is the equivalent of Ruby's 'new,' and you can pass a variable number of parameters, as you can with the Ruby array API.

00:06:49.120 Next, we look at the allocation method. The static function returns a value, and most functions for extending CRuby actually return a reference to an object. First, we create a new object, referencing our array structure, a C structure I will show you shortly. We set a couple of flags on the objects, which are essential to the array but may not be necessary for the simple classes you create. This setup creates and allocates memory. Moving on to the initialization function, it's a bit more extensive because the Ruby 'Array.new' accepts a variable number of parameters, as well as an optional block. If the number of arguments passed to 'Array.new' is one, it indicates that we are passing the size of the array to allocate.

00:09:14.500 What happens at this point is that it checks the size of the array but may also replace it with a utility method that reallocates the array with the given size. There are several defined method calls that link C functions to Ruby source code. For instance, if you look at 'first', which we call in Ruby, this links to the actual C implementation via a defined method procedure that connects the array object to the name of the method and to the C function that executes it. This function follows the traditional C convention, where you receive the number of arguments first, followed by an array of those arguments.

00:10:22.760 You can access the number of arguments passed and make decisions accordingly. For instance, when you call 'first' and don’t pass any elements, you expect it to return nil, or if the array is empty, it should behave as expected. You can find all mappings for the methods we use daily when working with array objects if you browse through the C file at the bottom. Additionally, let's explore the structure associated with the Ruby array, found in the Ruby.h include file. Each array indeed has a basic structure indicating which object it belongs to, aiding during garbage collection.

00:12:04.710 The basic object has flags for garbage collection, which mark all objects in use. The array itself contains everything expected, like length, capacity, and a pointer to the array elements. An interesting optimization occurs where a small array can be created directly in the array structure if it contains three or fewer elements. This avoids heap allocation, significantly increasing performance. For typical use-cases where arrays often start empty or are small, this optimization saves time and resources. This covers the declaration and memory allocation of the array.

00:13:59.250 The next concern when creating a new type in C is memory allocation, which happens in ng.c. Ruby is a dynamic language that uses mark-and-sweep garbage collection. If Ruby runs out of memory, it marks all objects in use and sweeps, reclaiming memory from those that have not been marked as in use. For arrays, you'll find a type structure, where we get the length of the array and traverse through all its elements to mark them before proceeding. Thus, you're accountable for manually marking objects as in use to prevent them from being garbage collected.

00:15:20.340 Understanding the implementation of the array in C allowed me to create my own Widget class as a prototype, ensuring it functions correctly under garbage collection requirements. I defined the Widget class that inherits from Object, allocated memory for my object, created methods for construction, inspection, and breadth-first search implementation. The allocation process is rather simple—just three lines of code. My custom struct allows efficient allocation and the initialization manages input arguments, converting them from Ruby objects to C data types.

00:16:43.080 When initializing, I extract parameters from Ruby objects into C types, setting up the graph structure based on the specified length. It also includes error checks and handles memory allocation judiciously. Each time there’s a mark during garbage collection, a print statement indicates the means by which the object was marked. Working with CRuby is complex, especially concerning memory and garbage collection, but it offers an excellent learning opportunity into how Ruby functions beneath the surface.

00:18:38.930 If you clone the Ruby GitHub repository, you will find an interesting 'ext' folder containing classes familiar to us that are implemented as extensions in C. For example, libraries like psych were partially developed in C. The general idea is to simplify the coding experience, allowing for a high-level language to interface smoothly with low-level implementations while maintaining the advantages of both languages. You only need to create two essential files; the first is the 'extension count' file, which you can name according to your class and should match the identifiers used in the second file.

00:20:37.000 This process substantially aids in building a makefile, and the second file is more straightforward than the first, where you define your class's methods. Once you successfully implement the functions needed for breadth-first search in this graph structure, you can utilize Ruby's interaction capabilities with the C code. Tasks like memory management and garbage collection during the 'mark' and 'free' phases can be efficiently handled to ensure your program does not leak precious resources.

00:22:50.590 The high-level function that interfaces your Ruby code with low-level code handles breadth-first search operations. Extracting data involves employing helper functions as part of the Ruby API, allowing you to traverse and manipulate the C data while adhering to Ruby’s standard. The flexibility of transitioning data types makes it easy to bind Ruby objects to C structures. Upon constructing the Ruby array, careful attention to garbage collection is vital to prevent unintentional deletions of data, ensuring smooth operations.

00:24:27.560 Comparative tests demonstrated the significant performance gains realized with CRuby versus pure Ruby implementations of similar algorithms. When comparing C and Ruby across extensive datasets—65,000 nodes in a graph—the results were staggering; C completed the task in roughly ten milliseconds while Ruby took a full minute. As datasets grew larger, the delta in performance widened considerably: C processing one million nodes in hours while Ruby extended to days. This performance gap stems from how Ruby allocates objects, resulting in overhead for thousands of individual object allocations.

00:26:18.320 C's memory management minimizes overhead, utilizing simpler data types versus Ruby's object-oriented model, which inflates both memory footprint and time. The fundamental efficiency of C, when optimized correctly, capitalizes on CPU-level caching and prevents costly memory operations that Ruby's implementation suffers from. Consequently, CRuby offers an appealing methodology for adding performance enhancements to Ruby without sacrificing ease of use. In conclusion, CRuby is not only manageable to comprehend but provides insights into how Ruby operates at a fundamental level. Utilizing data objects helps retain high-level abstractions while achieving the performance gains typical of lower-level programming.