Extending CRuby with native Graph data type
Pliszka, Andy
Reading of the CRuby (MRI) source code provides unparalleled insight into the Ruby language. During the talk we will add new native Graph data type to CRuby. The new Graph data structure will be simple but on par with other native types such as Array or Hash. This talk will demonstrate that it is easy to experiment with CRuby and extend it in C. We will experience the speed advantage of using C to boost Ruby performance. We will implement a few of the greatest hits of graph algorithms: Breath First Search, Dijkstra, and Minimum Spanning Tree.
 My name is Andy. I work at Pivotal Labs in New York City. And today I'm going to show you how to extend Ruby in C. And we're going to concentrate on C Ruby and I'll show you how to build Ruby and extend it. So this is pretty much the agenda. I'm going to explain a couple of problems that I'm trying to solve with this talk. And then we're going to build Ruby, set up the debugger, look at the C Ruby source code, write a couple of simple extensions, and then at the end we're going to write a simple graph implementation in C Ruby. Okay, so what are the problems? If you are addressing a big data, big graph or big data problems, you need a lot of memory, you need speed and write algorithms. And when you think about big data problems and big graph problems, usually you're going to face this, that Ruby is slow. I think everyone faced this kind of question in our professional life. And I do not totally agree with this statement because what I think is that objects are slow, so objects oriented abstractions are slow. So objects actually have a lot of overhead, they require extra memory, they require a lot of indirection, and they result in fragmented memory so you can actually lose some of the performance. And that gets even worse when you work with arrays of objects. So now you, if you have an array, it doesn't really matter if you have, let's say, 10,000 objects, but if you have a million or a billion of objects, that overhead is really substantial and it prevents you from actually solving problems. So when you work with arrays of objects, you have more overhead, more indirection, more memory fragmentation, and then all the CPU caches and all the optimization that you get from the CPUs are pretty much wasted. And it's not only a Ruby problem, it's a problem really with every object oriented language. So that was a problem at the beginning of the small talk, right, that pretty much you had to have the most powerful computer to run small talk. Java had the same problem at the beginning. That's why, that's one of the reasons why Java has primitive types. So you can actually work with bytes and memory instead of arrays of objects. And Python is actually solving it by using Numpy and actually using C extensions. And even C, when you talk to people who are doing high-frequency trading, for example, they also have a lot of tricks that speed up C++. So it's not only Ruby that's slow, but it's a lot of languages that have this problem. So what is the solution? Solution is Ruby plus C. So what you can do, if you can combine Ruby productivity and ecosystem, all the gems and all the tools that we have, especially for testing like RSpec or Minitest, with C efficiency speed and algorithms, because when you really think about it, most of the algorithms are already written in C. The originals were written in C, so why even rewrite them in Ruby if you can use them directly? So what you get is you can put all your high-level abstractions in Ruby. So all the modeling, all the algorithm coordination, all the analysis and scripting, do it in Ruby, but all the low-level operations like algorithm implementation and manipulation of large in-memory data structures, you can do it in C. And in this way, you can also integrate with linear algebra libraries and CUDA and other stuff. So you can make this stuff that matters and that requires speed. You can write it in C, but you can actually control it from Ruby. So my goal for this talk today is to give you a tool set so you can go home and actually experiment with C Ruby on your own at home. And the first step in that journey is actually building your own version of Ruby. And that's what we're going to do. So the first, first we have to check it out from GitHub, right? Set up the, check out the stable version of Ruby. This is Ruby 2.0, built to.47. And then you have to configure it. So if you are running on Mac, you probably want to install OpenSSL because you will need RubyGems. Then you run out the configuration tool, and then you have to configure your Ruby source code. And you can just copy and paste this into terminal, what it does. I'll explain what each element does. So for example, this prefix, it says that the Ruby that you are building, you want to install it in your home folder under MyRuby. You want to use this OpenSSL that comes from, from a, from the root seller. And you want optimization flags set to O0. This is basically no optimization because you want to set up a Ruby version that has no optimization, so it's easier to debug. Because if you set this to a higher level, actually compiler will rearrange the code and it makes debugging much harder. And then you have to specify dash G for, for full debugging for all. And I use disable install docs just to make it faster so we don't install docs. So once you, once you configure it and you run it, this is pretty much what you will get just for your sanity check. This is pretty much the result that you should get. It's going to run for a couple of minutes and then it's going to finish and you will have, you will have a configured version of Ruby. If you are running on Linux, it's slightly different but only a little bit. Instead of using brew, you can use aptitude to install SSL, auto-configure it. And the flags are almost exactly the same except for the debugger because on, on Mac we use LLDB and on Linux you use GDB. So that's the only difference really. So once you configure it, well, you have to compile it and build it. And you can do it with just single command make. The first compile takes a couple of minutes. Incremental compiles are much faster and this is pretty much what you should get on your screen. Basically you should say that it's linking Ruby and you should have your Ruby version built. Once you build your, your, your Ruby, what you want to do is run unit tests. C Ruby actually comes with around 14,000 tests that you can run by running make check. And it will take some time but it will give you confidence that all the configuration and the whole build that you have is actually correct. And one note, if you, if you're going to run into a couple of errors, what's important is make sure that you run this command. This actually fixes some of the security on, on the folder. And what I noticed is without running that command, some of the tests around like 14 tests actually fails and it's a, it's a false negative. Once you run the check and everything is green, well, you can install it. And you can install it by running make install. And you can see here that it actually installed in that my Ruby folder. So this will actually copy all the binaries and put it in the tilde slash my, my Ruby folder. You can, you, you, you can always, you always know that it's there. And it will install a couple of basic gems. And you are almost ready to use it. What do you have to do next? You have to configure the terminal that you are in. You, you set the path to my Ruby path. So it first searches in the build, the, the bin folder under my Ruby. And you also want to configure gem home and gem path. So it includes my Ruby. So my goal here is to give you a single terminal where you have your own version of Ruby for experimentation without actually changing any shell script configuration files. So your RVM, it doesn't really affect your RVM. This is your private sandbox that you can, you can, you can run all your code and experiments. So even if you break your Ruby, you will not break your, your, your, your work setup, et cetera. So once you set up these paths, you can verify that Ruby is installed correctly just by running rich. And you see all these, all these commands actually include my Ruby. And you can even test it with RVR by raising you should, you should see my Ruby in that, in that path. This is pretty much a sanity check for you that everything is set up correctly. Okay. Next thing that you have to verify is make sure that the gem, gems are set up correctly. Because what I want you to do is to be able to use your own compiled version of Ruby to run pretty much any Ruby software that you can imagine. Your production software or, you know, Rails applications, et cetera. So you can experiment with your, with the software that you use every day. So here, if you run gem environment, all this my Ruby should be there. You can verify it that way. These are the gems that are installed by default. And they are stored in this folder. Right. So pretty much we are, we are ready to install Rails now. Actually use our own compiled version of Ruby to install Rails and run a Rails application. So when you run gem install in the same terminal, it will actually install all the required gems. And then you can create a new Rails app and run it. And pretty much this, this Rails app is actually using your own compiled version of Ruby. So within roughly 30 minutes, you have your own sandbox for experimentation with C, C code. If you're using RubyMind, the setup is also easy. Just open RubyMind and set up the SDK to point to my Ruby version of Ruby. And that pretty much completes the level one. So we build our own version of Ruby. So we have all the source code, source code for Ruby. We can actually go there and play with it and modify it and experiment with it. And you, you can, you can even run Rails apps. It's just like any, like, like Ruby that you would install using RVM. And it shouldn't take you longer than 30 minutes. So that's the first step in our journey. The next step is, because we're going to do a lot of C, C coding, well, it's always used, very useful to have a debugger setup. So there are multiple options that you can use. If you're on on Mac, you can use Aldi B. If you're on Linux, you can use GDB. And if you prefer GUIs, you can use Xcode. And of course, Vam and Emacs are also supported. So this is how you would actually debug Ruby, running the upstream Ruby file using Aldi B. So you basically provide the path to the binary, provide a string, provide a, provide the name of the file. And the file is just basically up casing hello. And then when you run, when you enter Aldi B, you would set a break point at the line, at this line in this file. This is the actual, the first line of the up case method that's implemented in C. And then when you run it, it will actually run your code, run Ruby interpreter on that upstream RB file. And it will actually stop. You can see the little arrow here. It was going to stop on the first line of the up case in string, string.c. So this allows you to debug from command line. And if you're on Mac, you can actually use Xcode to debug your C, C Ruby source code. Okay. So now we have, we have Ruby compiled and we can debug it. So the next step is actually take a look. We will take a look at the C Ruby source code and we'll take a look at the folder structure. So this is my, this is pretty much the folder when I downloaded, checked out Ruby from GitHub. Pretty much 99% of the files that you want to worry about are files here. The C files in the main folder, like things like array or big num class. Most of the important files are in the root folder. And the only additional folder that you want to check out at the very beginning is probably the extension folder. So here, for example, you will find things like psych. All the extensions that you probably use, Jason. And these extensions are actually good learning tool because they are usually small. So you can actually see how they were implemented. For example, Jason, Jason maybe is a little bit too big, but find one that has only a few files and just try to understand how it's implemented. It's a good exercise. So let's take a look at a couple of files that we have here. So let's start with, let's see how fixed num is actually implemented in C. So it's going to be in numeric, numeric that C file. So every file that you open, you probably want to go to the bottom of the file and then you scroll up and look for init function. So big file. There we go. You are looking for this init function. And this is the entry point for every class that's defined in C. And here, for example, you can find that, for example, here, there's a definition of an integer class. We're using RB defined class integer and you can see that it actually inherits from numeric. Here are the definitions of all the methods on the integers. So for example, all the methods that we use every day, odd, even, up, to, down, to, times. If you scroll a bit lower, you will actually find the definition of a fixed num. So this is actually where you're using fixed num. You are not really using a class that was defined in Ruby. You are using a class that was defined in C. And all the methods are actually implemented in C. So for example, here you can find a fix. So here's the definition for the fixed num for the plus method. So I can find it here for you. And this is, well, definitely probably this one, this line is what does the actual addition. But there's a lot of wrapping code around it. So for example, what you can do if you want to play a prank on someone, you can just compile your own version of Ruby and just change it. And then you can watch someone try to figure it out for a couple of hours. Yeah, so you can use, you know, this is the first thing that you can do. You want to play with it. It's just that you can play, start with pranking other people. But this is a really good tool to understand how Ruby works, right? How this stuff is implemented, how you can actually extend Ruby, not only in Ruby, but using C and make your code much faster, right? So this is fixed num. Let's actually find another class. Let's say string, right? So string is implemented in string C. And I'm going to do the same thing. I'm going to go all the way to the bottom. I'm going to scroll up and find this init method. There you go. And the pattern is exactly the same. Like once you start looking at a couple of files, one or one, one, three, four files, you see that the patterns are exactly the same. So you first start with definition of a class. You give its name. You basically specify which class it inherits from. And here also, you can see that RB includes modules. So string, string class actually includes comparable, right? There's alloc function. And there are all the functions, string functions like triple equals equals hash. All this stuff is actually implemented here. And the method implementations are actually above. Let's take a look at one more class. Array, right? So here is the array. Yet again, init method, define class. I think you can see the pattern. And it's really easy to understand what's going on because you already have a lot of knowledge about how Ruby works. So you know the method names. So it's very useful actually to, you know, see, for example, how the, where is length, something simple. There you go. Here is the definition of a length method on array, right? So you can actually find it and actually see how it's implemented. Okay, I'm going to find it. There you go. So that's all it takes to implement the array length method. That's the actual C implementation. So that's the folder structure. Fixed on string and array. So how do you actually define classes in C, right? So let's take a look, let's take a look at the array again. Pretty much all you have to do is to create a file. In this case, if I were defining a new array, I would call it array.C, right? Define this method init array and then I would call this Ruby define class, give it the class name and give it the base object, right? Which is Ruby object. And this is pretty much equivalent to this Ruby code, right? You can also see that it references this value, which is RBC array. And that's actually defined at the very top of the file. And you can see, it's defined here. And every time you see this value in C Ruby source code, think about it, it's a reference to an object. It's pretty much an object. So when we define this array here, when you look at this Ruby define class, what it really does, it actually creates an instance of a class, right? If you're interested how meta-programming works in Ruby, actually looking at the C Ruby source code will probably give you the most insight how the meta-programming is actually implemented. Because I think without actually understanding how the C Ruby code works, it's very difficult to understand all the details of meta-programming. So for example, you know that everything in Ruby is an object, right? This pretty much what it does, it creates a class object for Ruby array and stores it in this reference. Then it actually includes a module in that class, right? A numerable module in the array class. And then also specifies the allocation function. And there's, if you're interested in meta-programming in Ruby, so these actually, these methods actually define singleton methods, but they are defined singleton methods not on the instances of an array, but actually on the instance of an array class, right? So, yeah, there's, you can even define aliases. Pretty much you can, just by looking, just by reading these methods and looking at them, you can connect them with Ruby equivalents. So all you really need is create a new file, C file, create init methods, define a method, provide allocation function, and provide defined couple of methods, right? That's all you need, literally six lines of code, okay? So that's define a class, and I'm also going to show you a concrete example in couple of minutes. So what about methods? So to define a method on a class, for example, array class, you have to use this define method, pass in the reference to the object of the class, right? Specify the name, and then pointer to a function, C function, that actually implements it. And the last argument is the number of, number of arguments that this function takes. So for example, it could be minus one if you want to use variable number of arguments. If it's zero, it means that there's no arguments. And then you have to actually implement the C implementation of the function. So here, here is the implementation of array length. And you can see that it's a static function. It returns a value, and every time you see a value, you should think an object. So it returns an object, takes an object, and this object is actually self. It's the reference to the instance of the object that we are calling the length on. So if, if you would write that A equals array new, this would be the reference to A. And then we use, this is using a macro to extract the length of the array as a long. So this is a C, C data type. Because Ruby only knows about objects, every time you have C, C types like length, long integer or float, you have to actually convert it back to a, to a value object, to an object. And you can use these macros. I'm going to, I'm going to talk about a little bit more in a couple of minutes. So you see, pretty much to implement a length method, you, you literally need a couple of lines of code, and you can monkey patch your, your classes in C. Okay. So what's important to understand when you are trying to extend Ruby in C is that there are really two worlds that you have to be aware of. That is the C world where you work directly with memory. There is no garbage collection. And you allocate an, an free memory manually using malloc and free. And there's the other world where, where, where you are in Ruby realm and you work with heap and objects. And everything is done for using garbage collection. And every time you, you switch from one world to the other, you have to make sure that you take precautions and you convert the, the types correctly. So these are the data types that you have access to in, in C. These are pretty much all equivalents to, to the data types that we have in Ruby. And this is how you actually do conversions. So assuming that you have a, let's say a method parameter that's, that's Ruby fixed now, and you want to convert it to C type long, all you have to do is use this macro, num to long, and you're going to get, get the value back. If you want to go the other way, from C long to Ruby fixed them, well, you have to call the log, log to, long to num function and it's going to do it for you. And you have to remember that you call this conversion every time you call C code from Ruby and every time you return values from C back to Ruby. Okay. So at this point, we have compiled version of Ruby. We know how to debug it. We pretty much have a basic understanding of what, what is the folder structure, how to define a class, how to define a method, and how to convert data between C and Ruby. So we can actually take a look at a couple of examples of, of Ruby extensions. Okay. So let's start with something simple, right? So this is how you would monkey patch fixed them in Ruby to add a, a Fibonacci number to fix them, right? So what you would do, you would all reopen the class and you will define the method. And this is equivalent C implementation, right? The algorithm is pretty much the same. It's iterative algorithm. It doesn't really matter that, that the control structures are different. The problem is that you cannot really use C implementations directly because remember that Ruby only knows about objects and C only cares about memory locations and pointers, right? So Ruby doesn't really understand what long is. Ruby only understood those value objects, right? So what you have to do, you have to actually convert the C implementation, the plain C implementation into, I call it C Ruby version, right? The version that's aware of objects. And the way you do it, well, you have to change the signature of the method. So in this case, instead of taking along and then returning along, you're actually taking a value, reading between lines that it's an object, and then you actually return a value. And then when you actually use those values in C, you have to convert them from objects to longs, right? And then when you return a value back to Ruby, you have to also convert V. In this case, as you can see here, that is a long. So you have to long to non-converted into numeric value and return it. And that's all you have to do to pretty much convert a C function into a C Ruby, C Ruby hour function. And then of course, you have to define this method in this case, numeric.c. Okay, let me actually show you this in the editor. So let's open numeric, numeric C. Okay, I'm going to find it's C fib, right? C fib. Okay. So this is pretty much an example of how you would monkey patch fix num directly in C, right? So I, because we have this sandbox that we set up in the step one, we can pretty much modify this whole C source code, and we're not going to break anything. So you can do pretty much whatever you want. And here we define the method, like fib, and here's the implementation, right? That's exactly what we had on the screen. And now if I, I think I have it compiled. So if I run IRB, and let's say I'm going to do 10.cfib, there you go. So this actually, it's already, I didn't have to require any file. So that proves that I actually modified the original Ruby source code. So this is the 10th Fibonacci number, right? And this is calling the C function directly, right? And you can debug it. I showed you before that you can, I can actually debug it in Xcode and experiment with it. So why would you do such a thing as, you know, why, why choose C over, over, instead of monkey patching in Ruby, why would you do it in C? Well, if you need performance, that's, that's going back to the problems that I described at the very beginning of the talk, which is, you know, if you're dealing with a lot of data, well, you need performance, right? So for example, this is a benchmark, just simple benchmark, trivial benchmark of running Fib 80 a million times, right? We run both, both of them directly from Ruby. And the Ruby implementation takes 26 seconds and, and, and, and C implementation takes less than a second. So roughly we are 30 times faster. And this is really trivial. And remember that we actually compiled Ruby without any optimization. So if you would bump optimization to O3, for example, you would probably get even better performance. So what's important here is that it's not that Ruby is slow, but what you can do, you can choose your battles and do the stuff that's high level, high level abstraction. You do, you can do everything in Ruby, but the critical paths, all the algorithms, low level algorithms you can implement in C and make your application much faster, right? If you are, if you are working, let's say, I don't know, with Facebook graphs or Twitter, Twitter feeds, right, that have millions of records, I think it makes a difference if you can do it 20 times, 30 times faster, right? You can be ahead of your competition. You can, and you can really, if, if, if, if you need 30 servers to run something, if you rewrite it in C, you suddenly only need probably two or three, right? So it can even save money. Okay, let's go to the next example. So the next example is prime, right? Testing for prime. Also very simple, simple algorithm. We just go through all the numbers and make sure that we are not divisible by any number below, below the, the, the, the self number. So this is already, this algorithm is pretty much identical. The only thing that we're using, we could use forlub, but just we're using up to here. So this is already converted to C Ruby style. And you can see there's not a lot of differences. It's very easy to rewrite this code into C. That's going from Ruby to C, right? But when you really think about it, most of the algorithms are already written in C. So usually go, you go the other way around, right? So you get the algorithm like in a book or a numerical methods book, you find a C implementation, you try to implement it in Ruby. And you really can avoid that by just interfacing your code directly with, with C. So here again, you monkey patch prime. This is C prime. You define the method. And I think I also have it running here. So I don't know, 11 C prime. There you go. So with a couple of lines of code, you can monkey patch fix num and, and, you know, experiment with it. These are just simple examples, but you can go with, with much more advanced functionality. So yeah, again, we've, we compared the performance in this case. If we test one of the Markov primes, it takes 31 seconds using C, using Ruby, and it takes two seconds using C. So it's 17 times faster, right? And that's even without any optimization. So I think you can see that there are benefits, especially if you, if you're, if, if part of, you definitely don't want to rewrite your GUIs and, and web applications in, in, in, in C. But what do you want to do if there are certain algorithms that you have that are critical for your application? You can rewrite it in C and get a lot of benefits, especially if you operate on a lot, on large arrays of objects or lists of objects. So that was simple monkey patching. But what about if you want to create a completely new class in C, right? This is all it takes. All you have to do is to define init method, specify, define class C longer ray, that it inherits from an object, define a lock function for it, define a constructor for it. And also we, here we're going to demonstrate that, that it's, the quicksort is slightly faster when we are running directly on longs. And we have two accessor methods, right? So if we look at it, the, the lock function is really simple. A couple of lines of code. We use this data make struct macro. What it does, it will actually take this C structure and wrap it in an, in Ruby object. Once you wrap it in a Ruby object, you can return it. So this self is, so we start with this array T, which is the C construct. And we get back by calling this data make struct. We're going to get an C, a C Ruby object that we can re, return and we can use it in a Ruby code. This is the initialization. So this is how we would call it from Ruby, right? C long array new 10. 10 is basically the size of the array. It's really simple implementation of the array with fixed size. So when you initialize it, use this gate, data get struct to get access to the actual array pointer. So basically unwrap the, the Ruby object and get access to the pointer to the memory where the data is stored. And then you can just use a C, a malloc and allocate enough room for, let's say in this case, 10 numbers, right? And you store the size and you can return the object. So at this time, you have enough room to store 10 objects in it. And to access array elements, so it looks, so it works exactly like Ruby, Ruby array. You can just define this square brackets function. And it does the same thing. It extracts the pointer to a, to array, converts the index which comes as a fixed sum, you convert it to a long and then we just access it, accesses through a pointer and we, we convert it back to a, to a fixed sum and then we send it back to Ruby. And this is how we would set the value. It's exactly the same except for this 99 which is the value that we, that we set it to. And it's, the difference is only here. Instead of returning the value at this index, we're actually setting it. Okay. And this is, this is a quick sort implementation, right? I'm doing something different here. So instead of actually converting the C, C example quick sort code to C Ruby convention, actually, I'm using this wrapper function that extracts all the objects, converts all the objects to C data structures and actually calls the C function directly. So you can see it here. This, this function, this quick sort function, it's pretty much, doesn't know anything about Ruby, anything about the object. This function array quick sort actually converts everything for it. So you can, you can get this directly from any website that lists algorithms and you can use it directly in your code. And if you compare performance, when you really think quick sorting stuff is really fundamental feature in a lot of algorithms, right? And just by using this array and this quick sort implementation, you can get a 10 times faster sorting. For example, here we're sorting 1 million numbers and in C it takes 200 milliseconds and, and, and, and Ruby it takes two, two seconds, right? So that's pretty much demonstrates that we can monkey patch fix num in C directly in C. It's 30 times faster, this one is 17. And we can even implement our own classes directly in C. Okay. So that brings us to graphs. So this is really simple implementation. We are, we will work with this grid graph, which is you just, just, just a, just a square, a four by four, so it has 16 nodes. This is the representation that we are using. It's pretty much a list of linked lists, right? So for example, one is just all the elements that we are connected to. So one is connected to two and five. So one is connected to two and five. So we're using linked, basically an array of linked lists. And this is the, the data structure, C data structure that we use for the graph. So it has the side. So it has how many, how many nodes we have on the side and a, a link to this array of linked lists. And this is just a node in linked lists. This is pretty much one of these squares. It has the value of the node and a pointer to the next node. Okay. C graph, although we are implementing pretty complicated data structure like graph, this is not getting much complicated if you compare it to the array, right? We still define a class. We give it a name. It inherits from an object. We still need allocation function. We need a constructor that takes one argument. And in this case, we have three methods. We have breadth first search, depth first search, and, and prims spanning tree. So alloc is exactly, almost exactly the same. The only thing that, that's different is this bolded, bolded text, which is, before we had array, we had array underscore t. Now we have a graph because we are using different data structure. So this is exactly almost the same as in the array example. And in it, it's a little bit more complicated because yet again, we extract the pointer to, to the data. This graph, it points to the, to the, to the location in the memory when the graph is stored. We store this side. We convert it from, from a fixed num to, to a long. And then we call this method implementation of that method basically what it does. It just generates the, the grid graph for us. So it links up all the, all the nodes together. So you will have to do it anyway. So this is the actual, the, the adapter function that we use for calling BFS C implementation. So we have this plain C BFS, which is this code is completely unaware of Ruby. It's just, it's a textbook example of, you know, using a queue to perform a BFS search. And here what we do, we actually first, we get access to those values that are passed in. Right? We get, we get this graph will point to the memory location when that graph is stored. And we actually pass it here directly. We also pass in the long that is the size of the, of the, of the graph. And we also pass the source node. So this, the node where you want to start the BFS search. And you call this method, right? So this method will go through the graph and it will actually return this path. And this path is all the nodes that you explored during the, the, the graph search. And this is, this is a C structure. So what you have to do is create this trace. We create a new array. This is a Ruby array. And we basically go over all the elements in this path. And we push all the elements from path onto a trace by converting it to a, to Ruby objects. Right? So pretty much we are trying to get the, the C structure completely converted into complete Ruby array. And we pass back that array to a calling, calling code. And before that, we also free some memory here. So it's a little bit more complicated, but the complexities here are not really that important. What's important here is how easy it is. Like literally with, with a couple of lines of code, you can, you can start using really complicated graph algorithms directly from Ruby. And you can speed up your Ruby, Ruby code. So for example here, we have a, we have a graph with four million nodes. This is just creation of the graph. And if you want to create it in Ruby, it's going to take you 27 seconds. And if you do it in C, it's going to take you half a second. So it's, in this case, Ruby, C Ruby is actually 50 times faster than, than Ruby. I think that's, that's worth the effort. And all you have to do is just write a couple of lines of C and you can speed up your code 50 times. And if it comes to actual BFS implementation, given a graph with one million nodes, the full BF search on that graph in C takes 200 milliseconds. And then Ruby takes 19, 19 times slower for milliseconds on Mac Pro. So this was just a simple graph example. You can go much deeper than that. But I think for, for presentation, it doesn't really make sense. But what this proves that you can really easily, in couple of lines of code, I think there was like 30 lines of code, you can create your own C Ruby implementation of a graph in Ruby that's going to play really well with Ruby. You can write implementation in BFS and you can make it 20 times faster. So when you really think about it, if you, if you're working with graphs such as, let's say, Facebook, right, all your friends, well, very quickly that graph grows. Like if you have 100 friends and all of your friends have 100 friends, that graph goes into millions really quickly, right? So if you can do something 20 or 50 times faster, that's the difference between not being able to do something or being able to do something, right? If something takes 20 hours, you can, you can get, get it done in an hour, right? So it might be also a base for a business model if you want to, if you want to start a startup. Okay. So what are the conclusions? The conclusions are that you can use C to speed up your Ruby algorithms, especially if they are low level algorithms, like for example, sorting. Like I showed you that really with a simple code, you can speed up your sorting 10 times. You can also go a little bit deeper and, you know, there's a lot of like numerical methods books where you have very elaborate algorithms, so you can actually take them and use them directly in Ruby. Rewrits in C are, I think I showed you that they are not that complicated. Most of them are straightforward. And you can write by using those wrapper functions that convert objects into C data structures and then call the C functions. You can actually use a lot of algorithms directly. So you don't have to worry about the fact that you will break the algorithm. You can just use, use it verbatim and just provide this adapter function. If you do some trivial C Ruby rewrites, like the Fibonacci or prime, you're going to get immediately a 10x to 50x speed performance bump. And if you want better performance, you pretty much, you can go and you can, you know, look what at people who are, let's say, doing a high performance, high frequency trading, right? There's other tricks that you can use. But just with simple rewrite of your crucial algorithms in C, you can get 10 to 50x performance bump. That's pretty much it.
 My name is Andy. I work at Pivotal Labs in New York City. And today I'm going to show  you how to extend Ruby in C. And we're going to concentrate on C Ruby and I'll show you  how to build Ruby and extend it. So this is pretty much the agenda. I'm going to explain  a couple of problems that I'm trying to solve with this talk. And then we're going to build  Ruby, set up the debugger, look at the C Ruby source code, write a couple of simple extensions,  and then at the end we're going to write a simple graph implementation in C Ruby. Okay,  so what are the problems? If you are addressing a big data, big graph or big data problems,  you need a lot of memory, you need speed and write algorithms. And when you think about  big data problems and big graph problems, usually you're going to face this, that Ruby  is slow. I think everyone faced this kind of question in our professional life. And I do  not totally agree with this statement because what I think is that objects are slow, so  objects oriented abstractions are slow. So objects actually have a lot of overhead, they  require extra memory, they require a lot of indirection, and they result in fragmented  memory so you can actually lose some of the performance. And that gets even worse when  you work with arrays of objects. So now you, if you have an array, it doesn't really matter  if you have, let's say, 10,000 objects, but if you have a million or a billion of objects,  that overhead is really substantial and it prevents you from actually solving problems.  So when you work with arrays of objects, you have more overhead, more indirection, more  memory fragmentation, and then all the CPU caches and all the optimization that you  get from the CPUs are pretty much wasted. And it's not only a Ruby problem, it's a problem  really with every object oriented language. So that was a problem at the beginning of  the small talk, right, that pretty much you had to have the most powerful computer to  run small talk. Java had the same problem at the beginning. That's why, that's one  of the reasons why Java has primitive types. So you can actually work with bytes and memory  instead of arrays of objects. And Python is actually solving it by using Numpy and actually  using C extensions. And even C, when you talk to people who are doing high-frequency trading,  for example, they also have a lot of tricks that speed up C++. So it's not only Ruby  that's slow, but it's a lot of languages that have this problem. So what is the solution?  Solution is Ruby plus C. So what you can do, if you can combine Ruby productivity and  ecosystem, all the gems and all the tools that we have, especially for testing like  RSpec or Minitest, with C efficiency speed and algorithms, because when you really think  about it, most of the algorithms are already written in C. The originals were written  in C, so why even rewrite them in Ruby if you can use them directly? So what you get  is you can put all your high-level abstractions in Ruby. So all the modeling, all the algorithm  coordination, all the analysis and scripting, do it in Ruby, but all the low-level operations  like algorithm implementation and manipulation of large in-memory data structures, you can  do it in C. And in this way, you can also integrate with linear algebra libraries and  CUDA and other stuff. So you can make this stuff that matters and that requires speed.  You can write it in C, but you can actually control it from Ruby. So my goal for this  talk today is to give you a tool set so you can go home and actually experiment with C  Ruby on your own at home. And the first step in that journey is actually building your  own version of Ruby. And that's what we're going to do. So the first, first we have to  check it out from GitHub, right? Set up the, check out the stable version of Ruby. This  is Ruby 2.0, built to.47. And then you have to configure it. So if you are running on  Mac, you probably want to install OpenSSL because you will need RubyGems. Then you run out the  configuration tool, and then you have to configure your Ruby source code. And you can just copy  and paste this into terminal, what it does. I'll explain what each element does. So for  example, this prefix, it says that the Ruby that you are building, you want to install  it in your home folder under MyRuby. You want to use this OpenSSL that comes from, from  a, from the root seller. And you want optimization flags set to O0. This is basically no optimization  because you want to set up a Ruby version that has no optimization, so it's easier to  debug. Because if you set this to a higher level, actually compiler will rearrange the  code and it makes debugging much harder. And then you have to specify dash G for, for full  debugging for all. And I use disable install docs just to make it faster so we don't install  docs. So once you, once you configure it and you run it, this is pretty much what you will  get just for your sanity check. This is pretty much the result that you should get. It's  going to run for a couple of minutes and then it's going to finish and you will have, you  will have a configured version of Ruby. If you are running on Linux, it's slightly different  but only a little bit. Instead of using brew, you can use aptitude to install SSL, auto-configure  it. And the flags are almost exactly the same except for the debugger because on, on Mac  we use LLDB and on Linux you use GDB. So that's the only difference really. So once  you configure it, well, you have to compile it and build it. And you can do it with just  single command make. The first compile takes a couple of minutes. Incremental compiles are  much faster and this is pretty much what you should get on your screen. Basically you should  say that it's linking Ruby and you should have your Ruby version built. Once you build  your, your, your Ruby, what you want to do is run unit tests. C Ruby actually comes with  around 14,000 tests that you can run by running make check. And it will take some time but  it will give you confidence that all the configuration and the whole build that you have is actually  correct. And one note, if you, if you're going to run into a couple of errors, what's important  is make sure that you run this command. This actually fixes some of the security on, on  the folder. And what I noticed is without running that command, some of the tests around  like 14 tests actually fails and it's a, it's a false negative. Once you run the check and  everything is green, well, you can install it. And you can install it by running make  install. And you can see here that it actually installed in that my Ruby folder. So this  will actually copy all the binaries and put it in the tilde slash my, my Ruby folder.  You can, you, you, you can always, you always know that it's there. And it will install  a couple of basic gems. And you are almost ready to use it. What do you have to do next?  You have to configure the terminal that you are in. You, you set the path to my Ruby path.  So it first searches in the build, the, the bin folder under my Ruby. And you also want  to configure gem home and gem path. So it includes my Ruby. So my goal here is to give  you a single terminal where you have your own version of Ruby for experimentation without  actually changing any shell script configuration files. So your RVM, it doesn't really affect  your RVM. This is your private sandbox that you can, you can, you can run all your code  and experiments. So even if you break your Ruby, you will not break your, your, your,  your work setup, et cetera. So once you set up these paths, you can verify that Ruby is  installed correctly just by running rich. And you see all these, all these commands actually  include my Ruby. And you can even test it with RVR by raising you should, you should see  my Ruby in that, in that path. This is pretty much a sanity check for you that everything  is set up correctly. Okay. Next thing that you have to verify is make sure that the gem,  gems are set up correctly. Because what I want you to do is to be able to use your own  compiled version of Ruby to run pretty much any Ruby software that you can imagine. Your  production software or, you know, Rails applications, et cetera. So you can experiment with your,  with the software that you use every day. So here, if you run gem environment, all this  my Ruby should be there. You can verify it that way. These are the gems that are installed  by default. And they are stored in this folder. Right. So pretty much we are, we are ready  to install Rails now. Actually use our own compiled version of Ruby to install Rails and  run a Rails application. So when you run gem install in the same terminal, it will actually  install all the required gems. And then you can create a new Rails app and run it. And  pretty much this, this Rails app is actually using your own compiled version of Ruby. So  within roughly 30 minutes, you have your own sandbox for experimentation with C, C code.  If you're using RubyMind, the setup is also easy. Just open RubyMind and set up the SDK  to point to my Ruby version of Ruby. And that pretty much completes the level one. So we  build our own version of Ruby. So we have all the source code, source code for Ruby.  We can actually go there and play with it and modify it and experiment with it. And you,  you can, you can even run Rails apps. It's just like any, like, like Ruby that you would  install using RVM. And it shouldn't take you longer than 30 minutes. So that's the first  step in our journey. The next step is, because we're going to do a lot of C, C coding, well,  it's always used, very useful to have a debugger setup. So there are multiple options that  you can use. If you're on on Mac, you can use Aldi B. If you're on Linux, you can use  GDB. And if you prefer GUIs, you can use Xcode. And of course, Vam and Emacs are also supported.  So this is how you would actually debug Ruby, running the upstream Ruby file using Aldi B.  So you basically provide the path to the binary, provide a string, provide a, provide the name  of the file. And the file is just basically up casing hello. And then when you run, when  you enter Aldi B, you would set a break point at the line, at this line in this file. This  is the actual, the first line of the up case method that's implemented in C. And then when  you run it, it will actually run your code, run Ruby interpreter on that upstream RB file.  And it will actually stop. You can see the little arrow here. It was going to stop on  the first line of the up case in string, string.c. So this allows you to debug from command  line. And if you're on Mac, you can actually use Xcode to debug your C, C Ruby source code.  Okay. So now we have, we have Ruby compiled and we can debug it. So the next step is actually  take a look. We will take a look at the C Ruby source code and we'll take a look at the  folder structure. So this is my, this is pretty much the folder when I downloaded, checked  out Ruby from GitHub. Pretty much 99% of the files that you want to worry about are files  here. The C files in the main folder, like things like array or big num class. Most of  the important files are in the root folder. And the only additional folder that you want  to check out at the very beginning is probably the extension folder. So here, for example,  you will find things like psych. All the extensions that you probably use, Jason. And these extensions  are actually good learning tool because they are usually small. So you can actually see  how they were implemented. For example, Jason, Jason maybe is a little bit too big, but find  one that has only a few files and just try to understand how it's implemented. It's a  good exercise. So let's take a look at a couple of files that we have here. So let's start  with, let's see how fixed num is actually implemented in C. So it's going to be in numeric, numeric  that C file. So every file that you open, you probably want to go to the bottom of the  file and then you scroll up and look for init function. So big file. There we go. You are  looking for this init function. And this is the entry point for every class that's  defined in C. And here, for example, you can find that, for example, here, there's a definition  of an integer class. We're using RB defined class integer and you can see that it actually  inherits from numeric. Here are the definitions of all the methods on the integers. So for  example, all the methods that we use every day, odd, even, up, to, down, to, times. If  you scroll a bit lower, you will actually find the definition of a fixed num. So this  is actually where you're using fixed num. You are not really using a class that was  defined in Ruby. You are using a class that was defined in C. And all the methods are  actually implemented in C. So for example, here you can find a fix. So here's the definition  for the fixed num for the plus method. So I can find it here for you. And this is, well,  definitely probably this one, this line is what does the actual addition. But there's  a lot of wrapping code around it. So for example, what you can do if you want to play  a prank on someone, you can just compile your own version of Ruby and just change it. And  then you can watch someone try to figure it out for a couple of hours. Yeah, so you can  use, you know, this is the first thing that you can do. You want to play with it. It's  just that you can play, start with pranking other people. But this is a really good tool  to understand how Ruby works, right? How this stuff is implemented, how you can actually  extend Ruby, not only in Ruby, but using C and make your code much faster, right? So  this is fixed num. Let's actually find another class. Let's say string, right? So string  is implemented in string C. And I'm going to do the same thing. I'm going to go all  the way to the bottom. I'm going to scroll up and find this init method. There you go.  And the pattern is exactly the same. Like once you start looking at a couple of files,  one or one, one, three, four files, you see that the patterns are exactly the same. So  you first start with definition of a class. You give its name. You basically specify which  class it inherits from. And here also, you can see that RB includes modules. So string,  string class actually includes comparable, right? There's alloc function. And there are  all the functions, string functions like triple equals equals hash. All this stuff is actually  implemented here. And the method implementations are actually above. Let's take a look at one  more class. Array, right? So here is the array. Yet again, init method, define class. I think  you can see the pattern. And it's really easy to understand what's going on because you  already have a lot of knowledge about how Ruby works. So you know the method names.  So it's very useful actually to, you know, see, for example, how the, where is length,  something simple. There you go. Here is the definition of a length method on array, right?  So you can actually find it and actually see how it's implemented. Okay, I'm going to find  it. There you go. So that's all it takes to implement the array length method. That's  the actual C implementation. So that's the folder structure. Fixed on string and array.  So how do you actually define classes in C, right? So let's take a look, let's take a  look at the array again. Pretty much all you have to do is to create a file. In this case,  if I were defining a new array, I would call it array.C, right? Define this method init  array and then I would call this Ruby define class, give it the class name and give it  the base object, right? Which is Ruby object. And this is pretty much equivalent to this  Ruby code, right? You can also see that it references this value, which is RBC array.  And that's actually defined at the very top of the file. And you can see, it's defined  here. And every time you see this value in C Ruby source code, think about it, it's a  reference to an object. It's pretty much an object. So when we define this array here,  when you look at this Ruby define class, what it really does, it actually creates an instance  of a class, right? If you're interested how meta-programming works in Ruby, actually looking  at the C Ruby source code will probably give you the most insight how the meta-programming  is actually implemented. Because I think without actually understanding how the C Ruby code  works, it's very difficult to understand all the details of meta-programming. So for example,  you know that everything in Ruby is an object, right? This pretty much what it does, it creates  a class object for Ruby array and stores it in this reference. Then it actually includes  a module in that class, right? A numerable module in the array class. And then also specifies  the allocation function. And there's, if you're interested in meta-programming in Ruby, so  these actually, these methods actually define singleton methods, but they are defined singleton  methods not on the instances of an array, but actually on the instance of an array class,  right? So, yeah, there's, you can even define aliases. Pretty much you can, just by looking,  just by reading these methods and looking at them, you can connect them with Ruby equivalents.  So all you really need is create a new file, C file, create init methods, define a method,  provide allocation function, and provide defined couple of methods, right? That's all you need,  literally six lines of code, okay? So that's define a class, and I'm also going to show you a  concrete example in couple of minutes. So what about methods? So to define a method on a class,  for example, array class, you have to use this define method, pass in the reference to the object  of the class, right? Specify the name, and then pointer to a function, C function, that actually  implements it. And the last argument is the number of, number of arguments that this function  takes. So for example, it could be minus one if you want to use variable number of arguments. If  it's zero, it means that there's no arguments. And then you have to actually implement the C  implementation of the function. So here, here is the implementation of array length. And you can  see that it's a static function. It returns a value, and every time you see a value, you should  think an object. So it returns an object, takes an object, and this object is actually self. It's  the reference to the instance of the object that we are calling the length on. So if, if you would  write that A equals array new, this would be the reference to A. And then we use, this is using a  macro to extract the length of the array as a long. So this is a C, C data type. Because Ruby  only knows about objects, every time you have C, C types like length, long integer or float, you  have to actually convert it back to a, to a value object, to an object. And you can use these macros.  I'm going to, I'm going to talk about a little bit more in a couple of minutes. So you see, pretty  much to implement a length method, you, you literally need a couple of lines of code, and you  can monkey patch your, your classes in C. Okay. So what's important to understand when you are  trying to extend Ruby in C is that there are really two worlds that you have to be aware of. That  is the C world where you work directly with memory. There is no garbage collection. And you  allocate an, an free memory manually using malloc and free. And there's the other world where,  where, where you are in Ruby realm and you work with heap and objects. And everything is done for  using garbage collection. And every time you, you switch from one world to the other, you have to  make sure that you take precautions and you convert the, the types correctly. So these are the  data types that you have access to in, in C. These are pretty much all equivalents to, to the  data types that we have in Ruby. And this is how you actually do conversions. So assuming that you  have a, let's say a method parameter that's, that's Ruby fixed now, and you want to convert it to C  type long, all you have to do is use this macro, num to long, and you're going to get, get the value  back. If you want to go the other way, from C long to Ruby fixed them, well, you have to call the  log, log to, long to num function and it's going to do it for you. And you have to remember that you  call this conversion every time you call C code from Ruby and every time you return values from C  back to Ruby. Okay. So at this point, we have compiled version of Ruby. We know how to debug it.  We pretty much have a basic understanding of what, what is the folder structure, how to define a  class, how to define a method, and how to convert data between C and Ruby. So we can actually take  a look at a couple of examples of, of Ruby extensions. Okay. So let's start with something simple,  right? So this is how you would monkey patch fixed them in Ruby to add a, a Fibonacci number to  fix them, right? So what you would do, you would all reopen the class and you will define the method.  And this is equivalent C implementation, right? The algorithm is pretty much the same. It's  iterative algorithm. It doesn't really matter that, that the control structures are different.  The problem is that you cannot really use C implementations directly because remember that  Ruby only knows about objects and C only cares about memory locations and pointers, right?  So Ruby doesn't really understand what long is. Ruby only understood those value objects, right?  So what you have to do, you have to actually convert the C implementation, the plain C  implementation into, I call it C Ruby version, right? The version that's aware of objects.  And the way you do it, well, you have to change the signature of the method. So in this case,  instead of taking along and then returning along, you're actually taking a value,  reading between lines that it's an object, and then you actually return a value.  And then when you actually use those values in C, you have to convert them from objects to longs,  right? And then when you return a value back to Ruby, you have to also convert V. In this case,  as you can see here, that is a long. So you have to long to non-converted into numeric value and  return it. And that's all you have to do to pretty much convert a C function into a C Ruby,  C Ruby hour function. And then of course, you have to define this method in this case,  numeric.c. Okay, let me actually show you this in the editor. So let's open numeric, numeric C.  Okay, I'm going to find it's C fib, right? C fib. Okay. So this is pretty much an example  of how you would monkey patch fix num directly in C, right? So I, because we have this sandbox  that we set up in the step one, we can pretty much modify this whole C source code, and we're  not going to break anything. So you can do pretty much whatever you want. And here we define the  method, like fib, and here's the implementation, right? That's exactly what we had on the screen.  And now if I, I think I have it compiled. So if I run IRB, and let's say I'm going to do 10.cfib,  there you go. So this actually, it's already, I didn't have to require any file. So that proves  that I actually modified the original Ruby source code. So this is the 10th Fibonacci number,  right? And this is calling the C function directly, right? And you can debug it. I showed you before  that you can, I can actually debug it in Xcode and experiment with it. So why would you do  such a thing as, you know, why, why choose C over, over, instead of monkey patching in Ruby,  why would you do it in C? Well, if you need performance, that's, that's going back to the  problems that I described at the very beginning of the talk, which is, you know, if you're dealing  with a lot of data, well, you need performance, right? So for example, this is a benchmark,  just simple benchmark, trivial benchmark of running Fib 80 a million times, right? We run both,  both of them directly from Ruby. And the Ruby implementation takes 26 seconds and, and, and,  and C implementation takes less than a second. So roughly we are 30 times faster. And this is  really trivial. And remember that we actually compiled Ruby without any optimization. So if  you would bump optimization to O3, for example, you would probably get even better performance.  So what's important here is that it's not that Ruby is slow, but what you can do, you can choose  your battles and do the stuff that's high level, high level abstraction. You do, you can do everything  in Ruby, but the critical paths, all the algorithms, low level algorithms you can implement in C  and make your application much faster, right? If you are, if you are working, let's say, I don't  know, with Facebook graphs or Twitter, Twitter feeds, right, that have millions of records,  I think it makes a difference if you can do it 20 times, 30 times faster, right? You can be ahead  of your competition. You can, and you can really, if, if, if, if you need 30 servers to run something,  if you rewrite it in C, you suddenly only need probably two or three, right? So it can even  save money. Okay, let's go to the next example. So the next example is prime, right? Testing for  prime. Also very simple, simple algorithm. We just go through all the numbers and make sure that we  are not divisible by any number below, below the, the, the, the self number. So this is already,  this algorithm is pretty much identical. The only thing that we're using, we could use forlub,  but just we're using up to here. So this is already converted to C Ruby style. And you can see there's  not a lot of differences. It's very easy to rewrite this code into C. That's going from Ruby to C,  right? But when you really think about it, most of the algorithms are already written in C. So usually  go, you go the other way around, right? So you get the algorithm like in a book or a numerical  methods book, you find a C implementation, you try to implement it in Ruby. And you really can  avoid that by just interfacing your code directly with, with C. So here again, you monkey patch  prime. This is C prime. You define the method. And I think I also have it running here. So I don't  know, 11 C prime. There you go. So with a couple of lines of code, you can monkey patch fix num  and, and, you know, experiment with it. These are just simple examples, but you can go with,  with much more advanced functionality. So yeah, again, we've, we compared the performance in this  case. If we test one of the Markov primes, it takes 31 seconds using C, using Ruby, and it takes  two seconds using C. So it's 17 times faster, right? And that's even without any optimization.  So I think you can see that there are benefits, especially if you, if you're, if, if part of,  you definitely don't want to rewrite your GUIs and, and web applications in, in, in, in C.  But what do you want to do if there are certain algorithms that you have that are critical for  your application? You can rewrite it in C and get a lot of benefits, especially if you operate on a  lot, on large arrays of objects or lists of objects. So that was simple monkey patching.  But what about if you want to create a completely new class in C, right? This is all it takes. All  you have to do is to define init method, specify, define class C longer ray, that it inherits from  an object, define a lock function for it, define a constructor for it. And also we, here we're going  to demonstrate that, that it's, the quicksort is slightly faster when we are running directly on  longs. And we have two accessor methods, right? So if we look at it, the, the lock function is  really simple. A couple of lines of code. We use this data make struct macro. What it does, it  will actually take this C structure and wrap it in an, in Ruby object. Once you wrap it in a Ruby  object, you can return it. So this self is, so we start with this array T, which is the C construct.  And we get back by calling this data make struct. We're going to get an C, a C Ruby object that we  can re, return and we can use it in a Ruby code. This is the initialization. So this is how we  would call it from Ruby, right? C long array new 10. 10 is basically the size of the array. It's  really simple implementation of the array with fixed size. So when you initialize it, use this  gate, data get struct to get access to the actual array pointer. So basically unwrap the, the Ruby  object and get access to the pointer to the memory where the data is stored. And then you can just  use a C, a malloc and allocate enough room for, let's say in this case, 10 numbers, right? And  you store the size and you can return the object. So at this time, you have enough room to store 10  objects in it. And to access array elements, so it looks, so it works exactly like Ruby, Ruby  array. You can just define this square brackets function. And it does the same thing. It extracts  the pointer to a, to array, converts the index which comes as a fixed sum, you convert it to a  long and then we just access it, accesses through a pointer and we, we convert it back to a, to a  fixed sum and then we send it back to Ruby. And this is how we would set the value. It's exactly  the same except for this 99 which is the value that we, that we set it to. And it's, the difference  is only here. Instead of returning the value at this index, we're actually setting it. Okay. And  this is, this is a quick sort implementation, right? I'm doing something different here. So  instead of actually converting the C, C example quick sort code to C Ruby convention, actually,  I'm using this wrapper function that extracts all the objects, converts all the objects to  C data structures and actually calls the C function directly. So you can see it here. This,  this function, this quick sort function, it's pretty much, doesn't know anything about Ruby,  anything about the object. This function array quick sort actually converts everything for it.  So you can, you can get this directly from any website that lists  algorithms and you can use it directly in your code. And if you compare performance, when you  really think quick sorting stuff is really fundamental feature in a lot of algorithms, right?  And just by using this array and this quick sort implementation, you can get a 10 times faster  sorting. For example, here we're sorting 1 million numbers and in C it takes 200 milliseconds and,  and, and, and Ruby it takes two, two seconds, right? So that's pretty much demonstrates that  we can monkey patch fix num in C directly in C. It's 30 times faster, this one is 17. And we can  even implement our own classes directly in C. Okay. So that brings us to graphs. So this is  really simple implementation. We are, we will work with this grid graph, which is you just,  just, just a, just a square, a four by four, so it has 16 nodes. This is the representation that  we are using. It's pretty much a list of linked lists, right? So for example, one is just all  the elements that we are connected to. So one is connected to two and five. So one is connected  to two and five. So we're using linked, basically an array of linked lists. And this is the, the  data structure, C data structure that we use for the graph. So it has the side. So it has how many,  how many nodes we have on the side and a, a link to this array of linked lists. And this is just  a node in linked lists. This is pretty much one of these squares. It has the value of the node  and a pointer to the next node. Okay. C graph, although we are implementing pretty complicated  data structure like graph, this is not getting much complicated if you compare it to the array,  right? We still define a class. We give it a name. It inherits from an object. We still need  allocation function. We need a constructor that takes one argument. And in this case, we have  three methods. We have breadth first search, depth first search, and, and prims spanning tree.  So alloc is exactly, almost exactly the same. The only thing that, that's different is this bolded,  bolded text, which is, before we had array, we had array underscore t. Now we have a graph because  we are using different data structure. So this is exactly almost the same as in the array example.  And in it, it's a little bit more complicated because yet again, we extract the pointer to, to  the data. This graph, it points to the, to the, to the location in the memory when the graph is  stored. We store this side. We convert it from, from a fixed num to, to a long. And then we call  this method implementation of that method basically what it does. It just generates the, the grid  graph for us. So it links up all the, all the nodes together. So you will have to do it anyway.  So this is the actual, the, the adapter function that we use for calling BFS C implementation. So  we have this plain C BFS, which is this code is completely unaware of Ruby. It's just, it's a  textbook example of, you know, using a queue to perform a BFS search. And here what we do, we  actually first, we get access to those values that are passed in. Right? We get, we get this graph  will point to the memory location when that graph is stored. And we actually pass it here directly.  We also pass in the long that is the size of the, of the, of the graph. And we also pass the source  node. So this, the node where you want to start the BFS search. And you call this method, right?  So this method will go through the graph and it will actually return this path. And this path is  all the nodes that you explored during the, the, the graph search. And this is, this is a C structure.  So what you have to do is create this trace. We create a new array. This is a Ruby array. And we  basically go over all the elements in this path. And we push all the elements from path onto a  trace by converting it to a, to Ruby objects. Right? So pretty much we are trying to get the,  the C structure completely converted into complete Ruby array. And we pass back that array to a  calling, calling code. And before that, we also free some memory here. So it's a little bit more  complicated, but the complexities here are not really that important. What's important here is  how easy it is. Like literally with, with a couple of lines of code, you can, you can start using  really complicated graph algorithms directly from Ruby. And you can speed up your Ruby, Ruby code.  So for example here, we have a, we have a graph with four million nodes. This is just creation of  the graph. And if you want to create it in Ruby, it's going to take you 27 seconds. And if you do  it in C, it's going to take you half a second. So it's, in this case, Ruby, C Ruby is actually  50 times faster than, than Ruby. I think that's, that's worth the effort. And all you have to do  is just write a couple of lines of C and you can speed up your code 50 times. And if it comes to  actual BFS implementation, given a graph with one million nodes, the full BF search on that  graph in C takes 200 milliseconds. And then Ruby takes 19, 19 times slower for milliseconds on  Mac Pro. So this was just a simple graph example. You can go much deeper than that. But I think for,  for presentation, it doesn't really make sense. But what this proves that you can really easily,  in couple of lines of code, I think there was like 30 lines of code, you can create your own C Ruby  implementation of a graph in Ruby that's going to play really well with Ruby. You can write  implementation in BFS and you can make it 20 times faster. So when you really think about it,  if you, if you're working with graphs such as, let's say, Facebook, right, all your friends,  well, very quickly that graph grows. Like if you have 100 friends and all of your friends have 100  friends, that graph goes into millions really quickly, right? So if you can do something 20 or  50 times faster, that's the difference between not being able to do something or being able to do  something, right? If something takes 20 hours, you can, you can get, get it done in an hour, right?  So it might be also a base for a business model if you want to, if you want to start a startup.  Okay. So what are the conclusions? The conclusions are that you can use C to speed up your Ruby  algorithms, especially if they are low level algorithms, like for example, sorting. Like I  showed you that really with a simple code, you can speed up your sorting 10 times. You can also go  a little bit deeper and, you know, there's a lot of like numerical methods books where you have very  elaborate algorithms, so you can actually take them and use them directly in Ruby.  Rewrits in C are, I think I showed you that they are not that complicated. Most of them are  straightforward. And you can write by using those wrapper functions that convert objects into C  data structures and then call the C functions. You can actually use a lot of algorithms directly.  So you don't have to worry about the fact that you will break the algorithm. You can just use,  use it verbatim and just provide this adapter function. If you do some trivial C Ruby rewrites,  like the Fibonacci or prime, you're going to get immediately a 10x to 50x speed performance bump.  And if you want better performance, you pretty much, you can go and you can, you know, look  what at people who are, let's say, doing a high performance, high frequency trading, right? There's  other tricks that you can use. But just with simple rewrite of your crucial algorithms in C,  you can get 10 to 50x performance bump. That's pretty much it.
Extending_CRuby_0_47.png Extending_CRuby_48_95.png Extending_CRuby_96_191.png Extending_CRuby_192_251.png Extending_CRuby_252_407.png Extending_CRuby_408_1235.png Extending_CRuby_1236_1931.png Extending_CRuby_1932_3347.png Extending_CRuby_3348_3395.png Extending_CRuby_3396_3587.png Extending_CRuby_3588_3683.png Extending_CRuby_3684_3923.png Extending_CRuby_3924_4019.png Extending_CRuby_4020_4187.png Extending_CRuby_4188_6059.png Extending_CRuby_6060_9287.png Extending_CRuby_9288_9971.png Extending_CRuby_9972_10235.png Extending_CRuby_10236_11123.png Extending_CRuby_11124_12155.png Extending_CRuby_12156_17075.png Extending_CRuby_17076_17543.png Extending_CRuby_17544_19451.png Extending_CRuby_19452_19583.png Extending_CRuby_19584_19775.png Extending_CRuby_19776_21491.png Extending_CRuby_21492_22067.png Extending_CRuby_22068_22931.png Extending_CRuby_22932_22991.png Extending_CRuby_22992_23951.png Extending_CRuby_23952_24167.png Extending_CRuby_24168_25559.png Extending_CRuby_25560_25607.png Extending_CRuby_25608_25679.png Extending_CRuby_25680_32159.png Extending_CRuby_32160_33347.png Extending_CRuby_33348_34259.png Extending_CRuby_34260_37823.png Extending_CRuby_37824_37883.png Extending_CRuby_37884_39071.png Extending_CRuby_39072_39491.png Extending_CRuby_39492_44075.png Extending_CRuby_44076_44219.png Extending_CRuby_44220_45647.png Extending_CRuby_45648_48287.png Extending_CRuby_48288_50363.png Extending_CRuby_50364_51515.png Extending_CRuby_51516_54695.png Extending_CRuby_54696_57443.png Extending_CRuby_57444_57995.png Extending_CRuby_57996_58055.png Extending_CRuby_58056_62495.png Extending_CRuby_62496_62555.png Extending_CRuby_62556_62603.png Extending_CRuby_62604_62651.png Extending_CRuby_62652_62699.png Extending_CRuby_62700_62747.png Extending_CRuby_62748_62807.png Extending_CRuby_62808_62867.png Extending_CRuby_62868_62915.png Extending_CRuby_62916_63023.png Extending_CRuby_63024_63041.png
My name is Andy. I work at Pivotal Labs in New York City. And today I'm going to show you how to extend Ruby in C. And we're going to concentrate on C Ruby and I'll show you how to build Ruby and extend it. So this is pretty much the agenda. I'm going to explain a couple of problems that I'm trying to solve with this talk. And then we're going to build Ruby, set up the debugger, look at the C Ruby source code, write a couple of simple extensions, and then at the end we're going to write a simple graph implementation in C Ruby. Okay, so what are the problems? If you are addressing a big data, big graph or big data problems, you need a lot of memory, you need speed and write algorithms. And when you think about big data problems and big graph problems, usually you're going to face this, that Ruby is slow. I think everyone faced this kind of question in our professional life. And I do not totally agree with this statement because what I think is that objects are slow, so objects oriented abstractions are slow. So objects actually have a lot of overhead, they require extra memory, they require a lot of indirection, and they result in fragmented memory so you can actually lose some of the performance. And that gets even worse when you work with arrays of objects. So now you, if you have an array, it doesn't really matter if you have, let's say, 10,000 objects, but if you have a million or a billion of objects, that overhead is really substantial and it prevents you from actually solving problems. So when you work with arrays of objects, you have more overhead, more indirection, more memory fragmentation, and then all the CPU caches and all the optimization that you get from the CPUs are pretty much wasted. And it's not only a Ruby problem, it's a problem really with every object oriented language. So that was a problem at the beginning of the small talk, right, that pretty much you had to have the most powerful computer to run small talk. Java had the same problem at the beginning. That's why, that's one of the reasons why Java has primitive types. So you can actually work with bytes and memory instead of arrays of objects. And Python is actually solving it by using Numpy and actually using C extensions. And even C, when you talk to people who are doing high-frequency trading, for example, they also have a lot of tricks that speed up C++. So it's not only Ruby that's slow, but it's a lot of languages that have this problem. So what is the solution? Solution is Ruby plus C. So what you can do, if you can combine Ruby productivity and ecosystem, all the gems and all the tools that we have, especially for testing like RSpec or Minitest, with C efficiency speed and algorithms, because when you really think about it, most of the algorithms are already written in C. The originals were written in C, so why even rewrite them in Ruby if you can use them directly? So what you get is you can put all your high-level abstractions in Ruby. So all the modeling, all the algorithm coordination, all the analysis and scripting, do it in Ruby, but all the low-level operations like algorithm implementation and manipulation of large in-memory data structures, you can do it in C. And in this way, you can also integrate with linear algebra libraries and CUDA and other stuff. So you can make this stuff that matters and that requires speed. You can write it in C, but you can actually control it from Ruby. So my goal for this talk today is to give you a tool set so you can go home and actually experiment with C Ruby on your own at home. And the first step in that journey is actually building your own version of Ruby. And that's what we're going to do. So the first, first we have to check it out from GitHub, right? Set up the, check out the stable version of Ruby. This is Ruby 2.0, built to.47. And then you have to configure it. So if you are running on Mac, you probably want to install OpenSSL because you will need RubyGems. Then you run out the configuration tool, and then you have to configure your Ruby source code. And you can just copy and paste this into terminal, what it does. I'll explain what each element does. So for example, this prefix, it says that the Ruby that you are building, you want to install it in your home folder under MyRuby. You want to use this OpenSSL that comes from, from a, from the root seller. And you want optimization flags set to O0. This is basically no optimization because you want to set up a Ruby version that has no optimization, so it's easier to debug. Because if you set this to a higher level, actually compiler will rearrange the code and it makes debugging much harder. And then you have to specify dash G for, for full debugging for all. And I use disable install docs just to make it faster so we don't install docs. So once you, once you configure it and you run it, this is pretty much what you will get just for your sanity check. This is pretty much the result that you should get. It's going to run for a couple of minutes and then it's going to finish and you will have, you will have a configured version of Ruby. If you are running on Linux, it's slightly different but only a little bit. Instead of using brew, you can use aptitude to install SSL, auto-configure it. And the flags are almost exactly the same except for the debugger because on, on Mac we use LLDB and on Linux you use GDB. So that's the only difference really. So once you configure it, well, you have to compile it and build it. And you can do it with just single command make. The first compile takes a couple of minutes. Incremental compiles are much faster and this is pretty much what you should get on your screen. Basically you should say that it's linking Ruby and you should have your Ruby version built. Once you build your, your, your Ruby, what you want to do is run unit tests. C Ruby actually comes with around 14,000 tests that you can run by running make check. And it will take some time but it will give you confidence that all the configuration and the whole build that you have is actually correct. And one note, if you, if you're going to run into a couple of errors, what's important is make sure that you run this command. This actually fixes some of the security on, on the folder. And what I noticed is without running that command, some of the tests around like 14 tests actually fails and it's a, it's a false negative. Once you run the check and everything is green, well, you can install it. And you can install it by running make install. And you can see here that it actually installed in that my Ruby folder. So this will actually copy all the binaries and put it in the tilde slash my, my Ruby folder. You can, you, you, you can always, you always know that it's there. And it will install a couple of basic gems. And you are almost ready to use it. What do you have to do next? You have to configure the terminal that you are in. You, you set the path to my Ruby path. So it first searches in the build, the, the bin folder under my Ruby. And you also want to configure gem home and gem path. So it includes my Ruby. So my goal here is to give you a single terminal where you have your own version of Ruby for experimentation without actually changing any shell script configuration files. So your RVM, it doesn't really affect your RVM. This is your private sandbox that you can, you can, you can run all your code and experiments. So even if you break your Ruby, you will not break your, your, your, your work setup, et cetera. So once you set up these paths, you can verify that Ruby is installed correctly just by running rich. And you see all these, all these commands actually include my Ruby. And you can even test it with RVR by raising you should, you should see my Ruby in that, in that path. This is pretty much a sanity check for you that everything is set up correctly. Okay. Next thing that you have to verify is make sure that the gem, gems are set up correctly. Because what I want you to do is to be able to use your own compiled version of Ruby to run pretty much any Ruby software that you can imagine. Your production software or, you know, Rails applications, et cetera. So you can experiment with your, with the software that you use every day. So here, if you run gem environment, all this my Ruby should be there. You can verify it that way. These are the gems that are installed by default. And they are stored in this folder. Right. So pretty much we are, we are ready to install Rails now. Actually use our own compiled version of Ruby to install Rails and run a Rails application. So when you run gem install in the same terminal, it will actually install all the required gems. And then you can create a new Rails app and run it. And pretty much this, this Rails app is actually using your own compiled version of Ruby. So within roughly 30 minutes, you have your own sandbox for experimentation with C, C code. If you're using RubyMind, the setup is also easy. Just open RubyMind and set up the SDK to point to my Ruby version of Ruby. And that pretty much completes the level one. So we build our own version of Ruby. So we have all the source code, source code for Ruby. We can actually go there and play with it and modify it and experiment with it. And you, you can, you can even run Rails apps. It's just like any, like, like Ruby that you would install using RVM. And it shouldn't take you longer than 30 minutes. So that's the first step in our journey. The next step is, because we're going to do a lot of C, C coding, well, it's always used, very useful to have a debugger setup. So there are multiple options that you can use. If you're on on Mac, you can use Aldi B. If you're on Linux, you can use GDB. And if you prefer GUIs, you can use Xcode. And of course, Vam and Emacs are also supported. So this is how you would actually debug Ruby, running the upstream Ruby file using Aldi B. So you basically provide the path to the binary, provide a string, provide a, provide the name of the file. And the file is just basically up casing hello. And then when you run, when you enter Aldi B, you would set a break point at the line, at this line in this file. This is the actual, the first line of the up case method that's implemented in C. And then when you run it, it will actually run your code, run Ruby interpreter on that upstream RB file. And it will actually stop. You can see the little arrow here. It was going to stop on the first line of the up case in string, string.c. So this allows you to debug from command line. And if you're on Mac, you can actually use Xcode to debug your C, C Ruby source code. Okay. So now we have, we have Ruby compiled and we can debug it. So the next step is actually take a look. We will take a look at the C Ruby source code and we'll take a look at the folder structure. So this is my, this is pretty much the folder when I downloaded, checked out Ruby from GitHub. Pretty much 99% of the files that you want to worry about are files here. The C files in the main folder, like things like array or big num class. Most of the important files are in the root folder. And the only additional folder that you want to check out at the very beginning is probably the extension folder. So here, for example, you will find things like psych. All the extensions that you probably use, Jason. And these extensions are actually good learning tool because they are usually small. So you can actually see how they were implemented. For example, Jason, Jason maybe is a little bit too big, but find one that has only a few files and just try to understand how it's implemented. It's a good exercise. So let's take a look at a couple of files that we have here. So let's start with, let's see how fixed num is actually implemented in C. So it's going to be in numeric, numeric that C file. So every file that you open, you probably want to go to the bottom of the file and then you scroll up and look for init function. So big file. There we go. You are looking for this init function. And this is the entry point for every class that's defined in C. And here, for example, you can find that, for example, here, there's a definition of an integer class. We're using RB defined class integer and you can see that it actually inherits from numeric. Here are the definitions of all the methods on the integers. So for example, all the methods that we use every day, odd, even, up, to, down, to, times. If you scroll a bit lower, you will actually find the definition of a fixed num. So this is actually where you're using fixed num. You are not really using a class that was defined in Ruby. You are using a class that was defined in C. And all the methods are actually implemented in C. So for example, here you can find a fix. So here's the definition for the fixed num for the plus method. So I can find it here for you. And this is, well, definitely probably this one, this line is what does the actual addition. But there's a lot of wrapping code around it. So for example, what you can do if you want to play a prank on someone, you can just compile your own version of Ruby and just change it. And then you can watch someone try to figure it out for a couple of hours. Yeah, so you can use, you know, this is the first thing that you can do. You want to play with it. It's just that you can play, start with pranking other people. But this is a really good tool to understand how Ruby works, right? How this stuff is implemented, how you can actually extend Ruby, not only in Ruby, but using C and make your code much faster, right? So this is fixed num. Let's actually find another class. Let's say string, right? So string is implemented in string C. And I'm going to do the same thing. I'm going to go all the way to the bottom. I'm going to scroll up and find this init method. There you go. And the pattern is exactly the same. Like once you start looking at a couple of files, one or one, one, three, four files, you see that the patterns are exactly the same. So you first start with definition of a class. You give its name. You basically specify which class it inherits from. And here also, you can see that RB includes modules. So string, string class actually includes comparable, right? There's alloc function. And there are all the functions, string functions like triple equals equals hash. All this stuff is actually implemented here. And the method implementations are actually above. Let's take a look at one more class. Array, right? So here is the array. Yet again, init method, define class. I think you can see the pattern. And it's really easy to understand what's going on because you already have a lot of knowledge about how Ruby works. So you know the method names. So it's very useful actually to, you know, see, for example, how the, where is length, something simple. There you go. Here is the definition of a length method on array, right? So you can actually find it and actually see how it's implemented. Okay, I'm going to find it. There you go. So that's all it takes to implement the array length method. That's the actual C implementation. So that's the folder structure. Fixed on string and array. So how do you actually define classes in C, right? So let's take a look, let's take a look at the array again. Pretty much all you have to do is to create a file. In this case, if I were defining a new array, I would call it array.C, right? Define this method init array and then I would call this Ruby define class, give it the class name and give it the base object, right? Which is Ruby object. And this is pretty much equivalent to this Ruby code, right? You can also see that it references this value, which is RBC array. And that's actually defined at the very top of the file. And you can see, it's defined here. And every time you see this value in C Ruby source code, think about it, it's a reference to an object. It's pretty much an object. So when we define this array here, when you look at this Ruby define class, what it really does, it actually creates an instance of a class, right? If you're interested how meta-programming works in Ruby, actually looking at the C Ruby source code will probably give you the most insight how the meta-programming is actually implemented. Because I think without actually understanding how the C Ruby code works, it's very difficult to understand all the details of meta-programming. So for example, you know that everything in Ruby is an object, right? This pretty much what it does, it creates a class object for Ruby array and stores it in this reference. Then it actually includes a module in that class, right? A numerable module in the array class. And then also specifies the allocation function. And there's, if you're interested in meta-programming in Ruby, so these actually, these methods actually define singleton methods, but they are defined singleton methods not on the instances of an array, but actually on the instance of an array class, right? So, yeah, there's, you can even define aliases. Pretty much you can, just by looking, just by reading these methods and looking at them, you can connect them with Ruby equivalents. So all you really need is create a new file, C file, create init methods, define a method, provide allocation function, and provide defined couple of methods, right? That's all you need, literally six lines of code, okay? So that's define a class, and I'm also going to show you a concrete example in couple of minutes. So what about methods? So to define a method on a class, for example, array class, you have to use this define method, pass in the reference to the object of the class, right? Specify the name, and then pointer to a function, C function, that actually implements it. And the last argument is the number of, number of arguments that this function takes. So for example, it could be minus one if you want to use variable number of arguments. If it's zero, it means that there's no arguments. And then you have to actually implement the C implementation of the function. So here, here is the implementation of array length. And you can see that it's a static function. It returns a value, and every time you see a value, you should think an object. So it returns an object, takes an object, and this object is actually self. It's the reference to the instance of the object that we are calling the length on. So if, if you would write that A equals array new, this would be the reference to A. And then we use, this is using a macro to extract the length of the array as a long. So this is a C, C data type. Because Ruby only knows about objects, every time you have C, C types like length, long integer or float, you have to actually convert it back to a, to a value object, to an object. And you can use these macros. I'm going to, I'm going to talk about a little bit more in a couple of minutes. So you see, pretty much to implement a length method, you, you literally need a couple of lines of code, and you can monkey patch your, your classes in C. Okay. So what's important to understand when you are trying to extend Ruby in C is that there are really two worlds that you have to be aware of. That is the C world where you work directly with memory. There is no garbage collection. And you allocate an, an free memory manually using malloc and free. And there's the other world where, where, where you are in Ruby realm and you work with heap and objects. And everything is done for using garbage collection. And every time you, you switch from one world to the other, you have to make sure that you take precautions and you convert the, the types correctly. So these are the data types that you have access to in, in C. These are pretty much all equivalents to, to the data types that we have in Ruby. And this is how you actually do conversions. So assuming that you have a, let's say a method parameter that's, that's Ruby fixed now, and you want to convert it to C type long, all you have to do is use this macro, num to long, and you're going to get, get the value back. If you want to go the other way, from C long to Ruby fixed them, well, you have to call the log, log to, long to num function and it's going to do it for you. And you have to remember that you call this conversion every time you call C code from Ruby and every time you return values from C back to Ruby. Okay. So at this point, we have compiled version of Ruby. We know how to debug it. We pretty much have a basic understanding of what, what is the folder structure, how to define a class, how to define a method, and how to convert data between C and Ruby. So we can actually take a look at a couple of examples of, of Ruby extensions. Okay. So let's start with something simple, right? So this is how you would monkey patch fixed them in Ruby to add a, a Fibonacci number to fix them, right? So what you would do, you would all reopen the class and you will define the method. And this is equivalent C implementation, right? The algorithm is pretty much the same. It's iterative algorithm. It doesn't really matter that, that the control structures are different. The problem is that you cannot really use C implementations directly because remember that Ruby only knows about objects and C only cares about memory locations and pointers, right? So Ruby doesn't really understand what long is. Ruby only understood those value objects, right? So what you have to do, you have to actually convert the C implementation, the plain C implementation into, I call it C Ruby version, right? The version that's aware of objects. And the way you do it, well, you have to change the signature of the method. So in this case, instead of taking along and then returning along, you're actually taking a value, reading between lines that it's an object, and then you actually return a value. And then when you actually use those values in C, you have to convert them from objects to longs, right? And then when you return a value back to Ruby, you have to also convert V. In this case, as you can see here, that is a long. So you have to long to non-converted into numeric value and return it. And that's all you have to do to pretty much convert a C function into a C Ruby, C Ruby hour function. And then of course, you have to define this method in this case, numeric.c. Okay, let me actually show you this in the editor. So let's open numeric, numeric C. Okay, I'm going to find it's C fib, right? C fib. Okay. So this is pretty much an example of how you would monkey patch fix num directly in C, right? So I, because we have this sandbox that we set up in the step one, we can pretty much modify this whole C source code, and we're not going to break anything. So you can do pretty much whatever you want. And here we define the method, like fib, and here's the implementation, right? That's exactly what we had on the screen. And now if I, I think I have it compiled. So if I run IRB, and let's say I'm going to do 10.cfib, there you go. So this actually, it's already, I didn't have to require any file. So that proves that I actually modified the original Ruby source code. So this is the 10th Fibonacci number, right? And this is calling the C function directly, right? And you can debug it. I showed you before that you can, I can actually debug it in Xcode and experiment with it. So why would you do such a thing as, you know, why, why choose C over, over, instead of monkey patching in Ruby, why would you do it in C? Well, if you need performance, that's, that's going back to the problems that I described at the very beginning of the talk, which is, you know, if you're dealing with a lot of data, well, you need performance, right? So for example, this is a benchmark, just simple benchmark, trivial benchmark of running Fib 80 a million times, right? We run both, both of them directly from Ruby. And the Ruby implementation takes 26 seconds and, and, and, and C implementation takes less than a second. So roughly we are 30 times faster. And this is really trivial. And remember that we actually compiled Ruby without any optimization. So if you would bump optimization to O3, for example, you would probably get even better performance. So what's important here is that it's not that Ruby is slow, but what you can do, you can choose your battles and do the stuff that's high level, high level abstraction. You do, you can do everything in Ruby, but the critical paths, all the algorithms, low level algorithms you can implement in C and make your application much faster, right? If you are, if you are working, let's say, I don't know, with Facebook graphs or Twitter, Twitter feeds, right, that have millions of records, I think it makes a difference if you can do it 20 times, 30 times faster, right? You can be ahead of your competition. You can, and you can really, if, if, if, if you need 30 servers to run something, if you rewrite it in C, you suddenly only need probably two or three, right? So it can even save money. Okay, let's go to the next example. So the next example is prime, right? Testing for prime. Also very simple, simple algorithm. We just go through all the numbers and make sure that we are not divisible by any number below, below the, the, the, the self number. So this is already, this algorithm is pretty much identical. The only thing that we're using, we could use forlub, but just we're using up to here. So this is already converted to C Ruby style. And you can see there's not a lot of differences. It's very easy to rewrite this code into C. That's going from Ruby to C, right? But when you really think about it, most of the algorithms are already written in C. So usually go, you go the other way around, right? So you get the algorithm like in a book or a numerical methods book, you find a C implementation, you try to implement it in Ruby. And you really can avoid that by just interfacing your code directly with, with C. So here again, you monkey patch prime. This is C prime. You define the method. And I think I also have it running here. So I don't know, 11 C prime. There you go. So with a couple of lines of code, you can monkey patch fix num and, and, you know, experiment with it. These are just simple examples, but you can go with, with much more advanced functionality. So yeah, again, we've, we compared the performance in this case. If we test one of the Markov primes, it takes 31 seconds using C, using Ruby, and it takes two seconds using C. So it's 17 times faster, right? And that's even without any optimization. So I think you can see that there are benefits, especially if you, if you're, if, if part of, you definitely don't want to rewrite your GUIs and, and web applications in, in, in, in C. But what do you want to do if there are certain algorithms that you have that are critical for your application? You can rewrite it in C and get a lot of benefits, especially if you operate on a lot, on large arrays of objects or lists of objects. So that was simple monkey patching. But what about if you want to create a completely new class in C, right? This is all it takes. All you have to do is to define init method, specify, define class C longer ray, that it inherits from an object, define a lock function for it, define a constructor for it. And also we, here we're going to demonstrate that, that it's, the quicksort is slightly faster when we are running directly on longs. And we have two accessor methods, right? So if we look at it, the, the lock function is really simple. A couple of lines of code. We use this data make struct macro. What it does, it will actually take this C structure and wrap it in an, in Ruby object. Once you wrap it in a Ruby object, you can return it. So this self is, so we start with this array T, which is the C construct. And we get back by calling this data make struct. We're going to get an C, a C Ruby object that we can re, return and we can use it in a Ruby code. This is the initialization. So this is how we would call it from Ruby, right? C long array new 10. 10 is basically the size of the array. It's really simple implementation of the array with fixed size. So when you initialize it, use this gate, data get struct to get access to the actual array pointer. So basically unwrap the, the Ruby object and get access to the pointer to the memory where the data is stored. And then you can just use a C, a malloc and allocate enough room for, let's say in this case, 10 numbers, right? And you store the size and you can return the object. So at this time, you have enough room to store 10 objects in it. And to access array elements, so it looks, so it works exactly like Ruby, Ruby array. You can just define this square brackets function. And it does the same thing. It extracts the pointer to a, to array, converts the index which comes as a fixed sum, you convert it to a long and then we just access it, accesses through a pointer and we, we convert it back to a, to a fixed sum and then we send it back to Ruby. And this is how we would set the value. It's exactly the same except for this 99 which is the value that we, that we set it to. And it's, the difference is only here. Instead of returning the value at this index, we're actually setting it. Okay. And this is, this is a quick sort implementation, right? I'm doing something different here. So instead of actually converting the C, C example quick sort code to C Ruby convention, actually, I'm using this wrapper function that extracts all the objects, converts all the objects to C data structures and actually calls the C function directly. So you can see it here. This, this function, this quick sort function, it's pretty much, doesn't know anything about Ruby, anything about the object. This function array quick sort actually converts everything for it. So you can, you can get this directly from any website that lists algorithms and you can use it directly in your code. And if you compare performance, when you really think quick sorting stuff is really fundamental feature in a lot of algorithms, right? And just by using this array and this quick sort implementation, you can get a 10 times faster sorting. For example, here we're sorting 1 million numbers and in C it takes 200 milliseconds and, and, and, and Ruby it takes two, two seconds, right? So that's pretty much demonstrates that we can monkey patch fix num in C directly in C. It's 30 times faster, this one is 17. And we can even implement our own classes directly in C. Okay. So that brings us to graphs. So this is really simple implementation. We are, we will work with this grid graph, which is you just, just, just a, just a square, a four by four, so it has 16 nodes. This is the representation that we are using. It's pretty much a list of linked lists, right? So for example, one is just all the elements that we are connected to. So one is connected to two and five. So one is connected to two and five. So we're using linked, basically an array of linked lists. And this is the, the data structure, C data structure that we use for the graph. So it has the side. So it has how many, how many nodes we have on the side and a, a link to this array of linked lists. And this is just a node in linked lists. This is pretty much one of these squares. It has the value of the node and a pointer to the next node. Okay. C graph, although we are implementing pretty complicated data structure like graph, this is not getting much complicated if you compare it to the array, right? We still define a class. We give it a name. It inherits from an object. We still need allocation function. We need a constructor that takes one argument. And in this case, we have three methods. We have breadth first search, depth first search, and, and prims spanning tree. So alloc is exactly, almost exactly the same. The only thing that, that's different is this bolded, bolded text, which is, before we had array, we had array underscore t. Now we have a graph because we are using different data structure. So this is exactly almost the same as in the array example. And in it, it's a little bit more complicated because yet again, we extract the pointer to, to the data. This graph, it points to the, to the, to the location in the memory when the graph is stored. We store this side. We convert it from, from a fixed num to, to a long. And then we call this method implementation of that method basically what it does. It just generates the, the grid graph for us. So it links up all the, all the nodes together. So you will have to do it anyway. So this is the actual, the, the adapter function that we use for calling BFS C implementation. So we have this plain C BFS, which is this code is completely unaware of Ruby. It's just, it's a textbook example of, you know, using a queue to perform a BFS search. And here what we do, we actually first, we get access to those values that are passed in. Right? We get, we get this graph will point to the memory location when that graph is stored. And we actually pass it here directly. We also pass in the long that is the size of the, of the, of the graph. And we also pass the source node. So this, the node where you want to start the BFS search. And you call this method, right? So this method will go through the graph and it will actually return this path. And this path is all the nodes that you explored during the, the, the graph search. And this is, this is a C structure. So what you have to do is create this trace. We create a new array. This is a Ruby array. And we basically go over all the elements in this path. And we push all the elements from path onto a trace by converting it to a, to Ruby objects. Right? So pretty much we are trying to get the, the C structure completely converted into complete Ruby array. And we pass back that array to a calling, calling code. And before that, we also free some memory here. So it's a little bit more complicated, but the complexities here are not really that important. What's important here is how easy it is. Like literally with, with a couple of lines of code, you can, you can start using really complicated graph algorithms directly from Ruby. And you can speed up your Ruby, Ruby code. So for example here, we have a, we have a graph with four million nodes. This is just creation of the graph. And if you want to create it in Ruby, it's going to take you 27 seconds. And if you do it in C, it's going to take you half a second. So it's, in this case, Ruby, C Ruby is actually 50 times faster than, than Ruby. I think that's, that's worth the effort. And all you have to do is just write a couple of lines of C and you can speed up your code 50 times. And if it comes to actual BFS implementation, given a graph with one million nodes, the full BF search on that graph in C takes 200 milliseconds. And then Ruby takes 19, 19 times slower for milliseconds on Mac Pro. So this was just a simple graph example. You can go much deeper than that. But I think for, for presentation, it doesn't really make sense. But what this proves that you can really easily, in couple of lines of code, I think there was like 30 lines of code, you can create your own C Ruby implementation of a graph in Ruby that's going to play really well with Ruby. You can write implementation in BFS and you can make it 20 times faster. So when you really think about it, if you, if you're working with graphs such as, let's say, Facebook, right, all your friends, well, very quickly that graph grows. Like if you have 100 friends and all of your friends have 100 friends, that graph goes into millions really quickly, right? So if you can do something 20 or 50 times faster, that's the difference between not being able to do something or being able to do something, right? If something takes 20 hours, you can, you can get, get it done in an hour, right? So it might be also a base for a business model if you want to, if you want to start a startup. Okay. So what are the conclusions? The conclusions are that you can use C to speed up your Ruby algorithms, especially if they are low level algorithms, like for example, sorting. Like I showed you that really with a simple code, you can speed up your sorting 10 times. You can also go a little bit deeper and, you know, there's a lot of like numerical methods books where you have very elaborate algorithms, so you can actually take them and use them directly in Ruby. Rewrits in C are, I think I showed you that they are not that complicated. Most of them are straightforward. And you can write by using those wrapper functions that convert objects into C data structures and then call the C functions. You can actually use a lot of algorithms directly. So you don't have to worry about the fact that you will break the algorithm. You can just use, use it verbatim and just provide this adapter function. If you do some trivial C Ruby rewrites, like the Fibonacci or prime, you're going to get immediately a 10x to 50x speed performance bump. And if you want better performance, you pretty much, you can go and you can, you know, look what at people who are, let's say, doing a high performance, high frequency trading, right? There's other tricks that you can use. But just with simple rewrite of your crucial algorithms in C, you can get 10 to 50x performance bump. That's pretty much it.
the C Ruby source code, write a couple of simple experiment with your, with the software that you not only in Ruby, but using C and make your code really easy to understand what's going on because this is a C, C data type. Because Ruby only knows the very beginning of the talk, which is, you algorithms you can implement in C and make your to demonstrate that, that it's, the quicksort is we will work with this grid graph, which is you data structure that we use for the graph. So it if you, if you're working with graphs such as, conclusions are that you can use C to speed up