<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Ruby X - Medium]]></title>
        <description><![CDATA[Compiling ruby to binary - Medium]]></description>
        <link>https://medium.com/ruby-x?source=rss----5fa4480fdcd9---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Ruby X - Medium</title>
            <link>https://medium.com/ruby-x?source=rss----5fa4480fdcd9---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 03:00:11 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/ruby-x" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Register allocation in a ruby compiler]]></title>
            <link>https://medium.com/ruby-x/register-allocation-in-a-ruby-compiler-9290de3db9dd?source=rss----5fa4480fdcd9---4</link>
            <guid isPermaLink="false">https://medium.com/p/9290de3db9dd</guid>
            <dc:creator><![CDATA[Torsten Ruger]]></dc:creator>
            <pubDate>Mon, 23 Mar 2020 17:37:21 GMT</pubDate>
            <atom:updated>2020-03-23T17:37:21.815Z</atom:updated>
            <content:encoded><![CDATA[<p>I had put off proper register allocation until now, and somehow the 100 commits it took verifies that i wasn’t completely wrong. I think there are quite a few differences to the normal problem and solution, to warrant an explanation, so here it goes: How RubyX does Static Single Assignment and Register Allocation in a ruby compiler.</p><h3>Simple register allocation, the old way</h3><p>To understand the problem, i’ll explain the previous, much simpler, approach and it’s problems. Then i’ll explain the new way, with reference to what i read the “normal” way is and the differences i think we have.</p><p>Simple register allocation is quite simply hard-coding at least some register names into the generation of assembler-like code, and having very simple ways to deal with the rest. In RubyX the assembler-like layer of the code is called Risc, and that is basically a simplified ARM. ARM has registers from r0 through to r15.</p><p>Early on i made two decisions, the current Message object would live in r0. This was one constant hard-coded throughout. The other decision was to design Slot level instructions such, that each instruction had use of all registers. To use registers i implemented a simple stack, but that was reset after every Slot level instruction.</p><h3>Motivation for change</h3><p>There are two major problems with the simple solution outlined above. The first is that it is sub-optimal now, the second that it is restrictive in the future.</p><p>The current problem, is actually many-fold. There is the obvious difficulty of keeping track of registers as they are used and returned. While i thought that the <em>by hand</em> approach was not too bad, after finishing this work, i checked the automatic way uses only half the amount of registers. This is nevertheless peanuts compared to the second problem, which means that the code is forever locked into a subset of the SlotMachine, ie no optimisations can be done across SlotMachine Instruction borders. That is quite serious, and sort of binds in with the third problem. Namely there were some implicit register assumptions being made, but there were implicit, ie could not be checked and would only show up if broken.</p><p>But the real motivation for this work came from the future, or the lack of expandability with this approach. Basically i found from benchmarking that inlining would have to happen quite soon. Even it would <em>only</em> be with more Macros at first. Inlining with this super simple allocation would not only be super hard, but also much less efficient than could be. After all there are 10+ registers that one can keep things in, thus avoiding reloading, and i already noticed constant loading was a thing.</p><h3>SSA and Register Allocation</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/0*CwO2Pr-XctwOc03y.png" /><figcaption>Wikipedia’s description of register allocation</figcaption></figure><p>So then we come to the way that it is coded now. The basic idea (followed by most compilers) is to assign new names for every new usage of a register. I’ll talk about that first. Then the second step is something called liveliness analysis; basically determining when register are not used anymore, and the third is the allocation.</p><h3>Static Single Assignment</h3><p>A <a href="https://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single Assignment form</a> of the Instructions is one where every register name is assigned only once. Hence the <em>Single</em> Assignment. The static part means that this single assignment is only true for a static analysis, so at run time the code may assign many times. But it would be the <em>same</em> code doing several assignments.</p><p>SSA is often achieved by first naming registers according to the variables they hold, and to derive subsequent names by increasing an subscript index. This did not sound very fitting. For one, RubyX does not really have “floating” variables (that later may get popped on some stack), rather every variable is an instance variable. Assigning to a variable does not create a new register value, but needs to be stored in memory. In a concurrent environment it is not safe to bypass that.</p><p>New variables may be created by “traversing” into a instance of the object (if type is known off course). This lead to a dot syntax naming convention, where almost every variable starts off from <strong>message</strong> or as a constant, eg “message.return_value”. This is as “single” as we need it to be (i think), and implementing this naming scheme was about half the work (more than half of that in tests, where register names were and are checked).</p><p>The great benefit from this renaming of registers is that even the risc code is now quite readable, which is great for debugging and tests. This is because the registers now have meaningful names (instance variable names), and it is always clear what a register is used for.</p><h3>Liveliness</h3><p>The next big step was to determine liveliness of registers. This is something i have not found good literature on, and in documents about Register Allocation it is often taken as the starting point.</p><p>Basic reasoning lead me to believe that a simple backward scan is at least a safe estimate. If you imagine going trough the list of instructions and marking the first occurence of any register use. By going backwards through the list you thus get the last usage, and that is the point where we can recycle that register.</p><p>I spent some time trying to figure out if backward branches changes the fact that you can release the register, but could not come to a conclusion (brain melt every time i tried). Intuitively i think that you can, because on the first run through such a loop you could not use results from a register that, because of the ssa, would have had to be created later, but there you go. Even rereading that hurts. My final argument was that a backward jump is a while loop, and a ruby while loop would have to store its data in ruby variables and not new registers, or so i hope).</p><p>I did read about phi nodes in ssa and i did not implement that. Phi nodes are a way to ensure that different branches of an <strong>if</strong> produce the same registers, or the same registers are meaningfully filled after the merge of an <strong>if.</strong> My hope is that the ruby variable argument from above gets us out of that, and for some risc functions i added some transfers to ensure things work as they should.</p><h3>Register Allocation</h3><p>The actual <a href="https://en.wikipedia.org/wiki/Register_allocation">Register Allocation</a> is not substantially more complicated now, than before. But there is a good base now to make more analysis and optimisations.</p><p>So basically we go through the instruction sequence and assign registers in order. But because of the liveliness analysis, we can release registers after their last use, and reuse them immediately off course. I noticed that this results in surprisingly many registers being used only for a single instruction. And the total number of registers used went <strong>down by half.</strong></p><h3>The future</h3><p>As i said that this was mostly for the future, what is the future going to hold? Well, <strong>inlining</strong> is high up, that’s for sure.</p><p>But also there is something called escape analysis. This essentially means reclaiming objects that are created in a method, but never get passed out. A sort of immediate GC, thus not only saving on GC time, but also on allocation. Mostly though it would allow to run larger benchmarks, because there is no GC, and integers get created a lot before a meaningful number of milliseconds has elapsed.</p><p>On the register front, some low hanging fruits are redundant transfer elimination and double load elimination. Since methods have not grown to exhaust registers, unloading register is undone and thus is looming. Which brings with it code cost analysis. So much more fun to be had!!</p><p>I am happy to announce that RubyX is part of <a href="https://railsgirlssummerofcode.org/">Rails Girls Summer of Code</a> and some interest is being show. Since i have enjoyed my last RGSoC summer, i am looking forward to some mentoring, and outside participation.</p><p><em>Originally published at </em><a href="http://ruby-x.org/blog/register-allocation-in-a-ruby-compiler"><em>http://ruby-x.org</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9290de3db9dd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ruby-x/register-allocation-in-a-ruby-compiler-9290de3db9dd">Register allocation in a ruby compiler</a> was originally published in <a href="https://medium.com/ruby-x">Ruby X</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Parsing parfait and other goodies]]></title>
            <link>https://medium.com/ruby-x/parsing-parfait-and-other-goodies-161fac4f5098?source=rss----5fa4480fdcd9---4</link>
            <guid isPermaLink="false">https://medium.com/p/161fac4f5098</guid>
            <category><![CDATA[ruby]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[rubyx]]></category>
            <category><![CDATA[compilers]]></category>
            <dc:creator><![CDATA[Torsten Ruger]]></dc:creator>
            <pubDate>Wed, 21 Aug 2019 17:18:24 GMT</pubDate>
            <atom:updated>2019-08-21T17:18:23.967Z</atom:updated>
            <content:encoded><![CDATA[<p>As rubyx will eventually need to parse and compile itself, i am very happy to report success on the first steps towards that goal. Also better design, benchmarks, and another conference are on the list.</p><h3>Compiling parfait</h3><p>As a recap, Parfait is that part of the core library that we need already during compilation. Ie the compiler creates Parfait objects during compilation and uses Parfait code to do this. This off course is a conundrum, which is solved by using the Parfait Code as is in the compiler (and some ruby module magic to avoid name clashes)</p><p>Naturally any meaningful program that the compiler generates will use Parfait and so Parfait must be available at run-time, ie parsed and compiled. Since i have been busy doing the basics, this has been on the ToDo for a long while.</p><p>Now, finally, most the basics are in place and i have started what feels like a tremendous task. In fact i have successfully compiled <em>three files.</em> Object, DataObject and Integer, to be precise.</p><p>The significance of this is actually much greater (especially since there are no tests yet). Parfait, as part of rubyx, is what one may call ideomatic ruby, ie real world ruby. Off course i had to smoothen out a few bugs before compiling actually worked, but surprisingly little. In other words the compiler is functional enough to compile larger, more feature rich ruby programs, but more on that below.</p><h3>Design improvements</h3><p>The overall design has been like in the picture below for a while already. Alas, the implementation of this architecture was slightly lacking. To be precise, when mom code was generated, it was immediately converted to risc. In other words the layer existed only conceptually, or in transit.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*EZvfhWwLF3fknEX6.png" /></figure><p>Now the code works <em>exactly</em> as advertised. Ruby comes in from the top and binary code out at the bottom. But more than that, every layer is a distinct step, in fact there are methods on the topmost compiler object to create every level down from ruby. This is obviously very handy for testing, and by iself sped up testing by 30%, as risc is not renerated before really needed.</p><h3>Automated binary tests</h3><p>Speaking of testing, we are at over 1600 tests, which is more than 200 up from before the design rewrite. At over 15000 assertions this is still 95% of the code, in other words everything apart from a few fails. And with parallel execution still fast.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Wn4wF0ZFzdhXRET8.png" /></figure><p>But the main achievement a couple of weeks ago was the integration of binary testing into the automated test flow. Specifically on <em>Travis.</em></p><p>This uses a feature of Qemu that i had not know before, namely that one can get qemu to run binaries from a different target on a machine, by simply calling it with qemu-arm.</p><p>Previously i had done testing of binaries via ssh, usually to an qemu emulated pi on my machine. This setup is vastly more complicated, as described <a href="http://ruby-x.org/arm/qemu.html">here</a> and i had shied away from automating that. Meaning they would happen irregularily and all that. My only consolation was that the test would run on the interpreter, but off course that does not test the arm and elf genertion.</p><p>The actual tests that i am talking about are a growing number of “mains” tests, found in the tests/mains directory. These are actual programs that calculate or output stuff. They are complete system tests in the sense that we only test their output (system output and exit code).</p><p>As we usually link to “a.out” files (thus overwriting and avoiding cleanup), the actual invocation of qemu for a binary is really simple:</p><pre>qemu-arm ./a.out</pre><p>but that still leaves you to generate that binary. This can be done by using the rubyxc compiler and linking the resulting object file (see bug #13). But sine i too am a lazy programmer i have automated these steps into the rubyxc compiler, and so one can just compile/link/execute a source file like this:</p><pre>./bin/rubyxc execute test/mains/source/fibo__8.rb</pre><p>This will compile, link and execute this specific fibonacci test. The exit code of this test will be 8, as encoded in the file name. Now this test, and 20 others, will be run as binaries every time travis does its thing.</p><p>BTW, i have also created a rubyxc command to execute a file via the interpreter. This can sometimes yield better errors when things go wrong.</p><pre>./bin/rubyxc interpret test/mains/source/puts_Hello-there_11.rb</pre><p>And as a second btw, i also added an option to the compiler, so one can control the Parfait factory size with the option — parfait.</p><h3>Misc other news</h3><h4>Microbenchmarks</h4><p>At the last conference in Hamburg, someone asked the fair question: So how fast is it? It’s been so long that i did <a href="http://ruby-x.org/misc/soml_benchmarks.html">tests,</a> that i could only mumble. Now i finished updating the tests, but it will be a while before i can answer the question more fully.</p><p>So for starters, because the functionality of the compiler is limited, i did very small benchmarks. Very small means 20 lines or less, loops, string output, fibonacchi, both linear and recursive. I realized too late, that all that will tell about is integer performance.</p><p>Now because it’s early days, i will not go into detail here. In general speed was not as fast as i had hoped for, about the same as mri. I will have to do some work on the calling convention and probably some on integer handling too. I think i can quite easily shave 30–50% off, and that alone should verify the saying that all benchmarks are lies. Like the one where rubyx is doing “hello world” faster than C. Yes, C, not mri. But only because i switched the buffering off, because also rubyx does not buffer (apples and oranges …)</p><p>So i will take this round as inspiration to do some optimisation and performance measuring. And come back to it later.</p><h4>Implicit returns</h4><p>As part of parsing Parfait, i implemented a first version of implicit returns. Low hanging fruits, and in fact most common use cases, included constants and calls. So when a method ends in a simple variable, constant, or a call, a return will be added. More complex rules like returns for if’s or while will have to wait, but i found that i personally don’t tend to use them anyway.</p><p>Since class methods are basically methods (of the meta class), adding the unified return handling to them was easy too.</p><h4>Improved Block handling</h4><p>Block handling, at least the simple implicit kind, has worked for a while, but was in several ways too complicated. The block was unnecessarily assigned to a local, and compiling was handled by looking for blocks statements, not during the normal flow.</p><p>This all stemmed from a misunderstanding, or lack of understanding: Blocks, or should i say Lambdas, are constants. Just like a string or integer. They are created once at compile time and can not change identity. In fact Methods and Classes are also contants, and i reflected this in the Vool level by calling them Expressions, instead of before Statements.</p><p>So now the Lambda Expression is created and just added as an argument to the send. Compiling the Lambda is triggered by the constant creation, ie the step down from vool to mom, and the block compiler added to method compiler automatically.</p><h4>Vool coming into focus</h4><p>I’ve been saying ruby without the fluff, to descibe vool. And while that is true, it is quite vague. Two major things have become clear about vool through the work above.</p><p>Firstly, Vool has no complex or recursive send statements. Arguments must be variables or constants. Calls are executed before and assigned to a temporary variable. In effect recursive calls are flattened into a list, and as such the calling does not rely on a stack as in ruby.</p><p>Secondly, Vool distinguishes between expressions and statements. Like other lower level languages, but not ruby. As a rule of thumb, Statements do things, Expression are things. In other words, only expressions have value, statements (like if or while) do not.</p><h3>Plans</h3><h4>Calling</h4><p>The Calling can do with work and i noticed two mistakes i did. One is that creating a new message for every call is unneccessarily complicated. It is only in the special case that a Proc is created that the return sequence (a mom instruction) needs to keep the message alive.</p><p>The other is that having arguments and local variables as seperate arrays may be handy and easy to code. But it does add an extra indirection for every access _and_ store. Since Mom is memory based, and Mom translates to risc, that does amount to a lot of instructions.</p><h4>Integers</h4><p>I still want to hang on to Integers being objects, though creation is clealy costly. In the future a full escape analysis will help off course, but for now it should be easy enough to figure out wether an int is passed down. If not loops can be made to destructively change the int.</p><h4>Mom instruction invocation</h4><p>I have this idea of being able to code more stuff higher up. To make that more efficient i am thinking of macros or instruction invocation at the vool level. Only inside Parfait off course. The basic idea would be to save the call/return code, and have the compiler map eg X.return_jump to the Mom::ReturnJump Instruction. “Just” have to figure out the passing semantics, or how that integrates into the vool code.</p><h4>Better Builtin</h4><p>The generation of the current builtin methods has always bothered me a bit. It is true that some things just can not be expressed as ruby and so some alternative mechanism is needed (even in c one can embed assembler).</p><p>The main problem i have is that those methods don’t check their arguments and as such may cause core dumps. So they are too high level and hopefully all we really need is that previous idea of being able to integrate Mom code into vool. As Mom is extensible that should take care of any possible need. And we could code the methods normally as part of Parfait, make them safe, and just use the lower level inside them. Lets see!</p><h4>Compiling Parfait tests</h4><p>Since Parfait is part of rubyx, we have off course unit tests for it. The plan is to parse the tests too, and run them as a test for both Prfait and the compiler. Off course this will involve writing some mini version of minitest that the compiler can actually handle (Why do i have the feeling that the real minitest involves too much mmagic).</p><h4>GrillRB conference</h4><p>Last, but not least, i will speak in <a href="https://grillrb.com/">Wrocław</a> in about a week. The plan is to make a comparison with rails and focus on the possibilities, rather than technical detail. See you there :-)</p><p><em>Originally published at </em><a href="http://ruby-x.org/blog/parsing-parfait-and-other-goodies"><em>http://ruby-x.org</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=161fac4f5098" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ruby-x/parsing-parfait-and-other-goodies-161fac4f5098">Parsing parfait and other goodies</a> was originally published in <a href="https://medium.com/ruby-x">Ruby X</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Class methods and a conference]]></title>
            <link>https://medium.com/ruby-x/class-methods-and-a-conference-eeba0a5331f3?source=rss----5fa4480fdcd9---4</link>
            <guid isPermaLink="false">https://medium.com/p/eeba0a5331f3</guid>
            <category><![CDATA[rubyx]]></category>
            <category><![CDATA[ruby]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[metaprogramming]]></category>
            <category><![CDATA[compilers]]></category>
            <dc:creator><![CDATA[Torsten Ruger]]></dc:creator>
            <pubDate>Thu, 28 Feb 2019 18:02:53 GMT</pubDate>
            <atom:updated>2019-02-28T18:02:53.314Z</atom:updated>
            <content:encoded><![CDATA[<p>In short, class methods are working. Plus is some meta stuff that and gotchas that i will explain below. Also i was at presenting rubyx at the first international conference, and there are a couple of misc improvements.</p><h3>Classes are Singleton objects</h3><p>Class methods came up when parsing Parfait. To create objects we usually use new, a class method. After briefly contemplating to hack that and use the global space object, i decided to at least check it out. And since it wasn’t so bad, i continued.</p><p>At some point i thought class methods would be very simple, as they are just methods on another object. After all the way we write code in classes is just a way to define methods on a group of objects. And defining class methods “just” changes which objects we define the methods on. And for the most part, this view is true. The only main difference is that class objects are singletons.</p><h3>Singletons means singleton classes</h3><p>Since we want to define methods on the single object, (and we are not programming javascript) we need a class like object that allows us to define these methods and manages them. There are several ways to do this, and i opted for a rather explicit one for now.</p><p>So i created a class called MetaClass, that is more or less like a Class. It does currently not derive, just implements the same protocol. In the compiler it can be used as a replacement for a class object, and that is exactly what we do. A metaclass instance is created for every class instance and there is a one to one relation with the class object.</p><p>Ruby does this in a more general way, and that off course means that at some point rubyx will have to move there too. In ruby every object has a singleton (meta) class. This must be implemented with lasy creation, otherwise it seems very wasteful. In Ruby the Metaclass is just a class, which means it has a metaclass, and at the moment i have other problems than keeping my brain from melting by thinking in circles like that.</p><h3>Compiling class methods</h3><p>Actual compilation now becomes very simple. Before we were passing the class in when compiling a method. Now we have methods and class methods, and depending on which kind it is, we use a different object. The class object for method, and the classes metaclass object for class methods.</p><p>Sort of surprisingly, none of the code further down had to be changed. But there are no tests yet for all the possible features, so there may be surprises. Also interpreting a class method call worked straight away, no changes needed there.</p><p>Class instance variables also have no tests, and so i don’t know if they work or how much work that would be. I sort of hope not much, but there clearly is an issue with the types changing that will have to be addressed.</p><h3>Change, specifically changing types</h3><p>As Types never change, we always create new instances. This works for normal objects, as we can just use the new type for new objects. Also while compiling a binary (ie not on the fly yet), we can just use the latest type for all existing objects of a class when we create the binary.</p><p>For singletons this hack does not work. Especially when adding class instance variables, the actual type of the existing class object changes. This means we have to change the type reference in the class object. This in turn means the new type has to be binary compatible with the old, which basically means it can’t grow beyond the allocated size.</p><p>This has been on the horizon for objects since the whole type idea was implemented. Just the horizon was always far away, and now i have to see how much of this can be done easily, how much later. We’ll see, tests will tell.</p><h3>Misc other</h3><p>Other things have happened that are maybe worth mentioning.</p><h3>Ruby integer upgrade</h3><p>Since i started before 2.4 there were still uses of Fixnum. In 2.4 Integer and Fixnum were united and later versions created a whole ton of warning. So i had stuck with 2.3 until now.</p><p>Now all Fixnums are gone and i have upgraded to use 2.6.</p><h3>Object creation</h3><p>When doing the Factories i hardcoded some page sizes. Hardcoding always bites you, as they should teach everyone in kindergarten, and so it did. It massively increased the test times, as for every Parfait boot (almost every test) several pages worth of objects were created.</p><p>I have now made the page size configurable and for good measure am passing some config into the compiler. The compiler then passes a parfait key down, a mechanism that could easily be extended to other subsystems.</p><p>The result was that test times have more than halved. Which means my new machine (the one i am just choosing) does not have to be quite as expensive :-)</p><h3>Command Line Interface</h3><p>Since i am hoping that people will start playing with ruby-x at some point i thought to make that easier. This has been out there for a while as well, but since the set of features was so small it just didn’t get done before.</p><p>So now we have a thor based cli in the bin directory. Not that it does so terribly much yet, but at least you can invoke it, get some help, and compile a ruby to binary. Platforms are not supported (as we only have arm) and those Parfait options neither. But a start.</p><h3>Rubyconf talk</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/923/0*20v-22TSZWf6vKEe.jpg" /></figure><p>Last but not least, i had the <a href="https://twitter.com/_swanand/status/1087279289672785920">first talk</a> at a conference. At the RubyConf in India, Goa to be specific. Many people were really interested, and Sherif and the organisers we very friendly. Off course we had a nice holiday too. No video yet, but i put the slides up on the homepage.</p><h3>Work continues</h3><p>When starting two big projects at work last year i didn’t have so much time, and there were months when i had no juice to code. Now i am on part time (physical) work again and am back chipping away at it.</p><p>I am still looking for people to join and will increase the effort a bit now that at least a reasonable subset is working.</p><p>Welcome!</p><p><em>Originally published at </em><a href="http://ruby-x.org/blog/class-methods-and-a-conference"><em>ruby-x.org</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eeba0a5331f3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ruby-x/class-methods-and-a-conference-eeba0a5331f3">Class methods and a conference</a> was originally published in <a href="https://medium.com/ruby-x">Ruby X</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding RubyX through historic decisions]]></title>
            <link>https://medium.com/ruby-x/understanding-rubyx-though-historic-decisions-18a5982a8dce?source=rss----5fa4480fdcd9---4</link>
            <guid isPermaLink="false">https://medium.com/p/18a5982a8dce</guid>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[virtual-machine]]></category>
            <category><![CDATA[rubyx]]></category>
            <category><![CDATA[ruby]]></category>
            <category><![CDATA[performance]]></category>
            <dc:creator><![CDATA[Torsten Ruger]]></dc:creator>
            <pubDate>Wed, 25 Jul 2018 18:46:25 GMT</pubDate>
            <atom:updated>2019-08-21T17:03:22.951Z</atom:updated>
            <content:encoded><![CDATA[<p>Off course the <a href="http://ruby-x.org/rubyx/layers.html">architecture</a> gives a good overview of the system as it is. But it does not explain how we got there. And sometimes knowing the journey makes it easier to understand where one is. So i shall try to highlight the four or five main</p><h3>Macbook + Ruby == Rasperry Pi</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*3WJJusJjOaNfhUL1.png" /></figure><p>When i bought my first 30Euro Pi i noticed that ruby is unusable on it. Looking at how slow ruby actually is, it occurred to me that ruby just about turns the Pi into my first 286 laptop (running at 6MHz), which is the same as turning my MacBook Pro into a Pi.</p><p>Off course, while working on web-apps, which can be parallelized so easily, and with a company paying both developer and hardware, the std ruby argument holds. But since i wanted to use my pi for demanding projects something had to be done.</p><h3>Judy, the importance of cpu cache</h3><p><a href="http://judy.sourceforge.net/">Judy</a> is a really really fast digital tree, kind of hash. I actually built a memory database with it that was also really really fast. When connecting it to rails i ran into the above problem, the niceties of ActiveRecord (ruby) brought performance of my extension © down by a factor of 40.</p><p>But anyway, the point is that Judy’s speed is based on a radical optimisation for cache lines (and key compression). This means all data structures are exactly a cpu cache line big. As i learned, cpu’s do not access memory in word sizes, but instead, always a cache line at a time. This basically lead to ruby-x’s memory model, which is fixed sized objects, multiples of a cache-line.</p><h3>Microkernel</h3><p>As a young engineer, i thought, as my peers, that Linux (then 0.93) was the greatest thing. Only much later did i learn that it is just a copy really, and the reason it got popular was not technical, but licensing (Same reason it is in Android i believe). The reason it stayed popular is inertia, in other words writing device drivers is hard.</p><p><a href="https://en.wikipedia.org/wiki/Self-modifying_code#Massalin%27s_Synthesis_kernel">Synthesis,</a> <a href="https://en.wikipedia.org/wiki/L4_microkernel_family">L4,</a> and <a href="http://www.minix3.org/">Minix,</a> are good proof that the superior architecture is the Microkernel. Eg L4 can run another OS as an application with about 4% performance degradation. Or Minix can recover from a device driver failure.</p><p>This, plus the fact that we have bundler, brought me to the approach that: If you can leave it out, do. Much of the functionality that is in ruby (mri), will never be in RubyX, but rather supplied by gems.</p><h3>System interrupts</h3><p>In the beginning i was off course contemplating how much of c based systems i would use. Like LLVM, which is off course a great tool, though made for c-ish applications. Or libc, which again is really for c apps to access the kernel.</p><p>The sheer size of the functionality one inherits almost swayed me. Even i had long since determined that one of ruby’s biggest flaws, it’s std-lib, came from modelling and using libc.</p><p>Then i learned assembler and looked at libc implementations and learned what i believe made the decision: Kernel calls are not really calls at all. They are software interrupts, which basically means you fill some registers, flick the switch, and the next instruction you can collect the result in a specified register. This may look like a call, and off course, by using libc it is presented as a call, but it is not. It is a very simple set of assembler instructions.</p><p>For me this meant there is very very little benefit in using c, either in it’s libc form, or assembler/linker (i had found a ruby gem to do that easily), or, maybe most importantly, the c calling convention. All of these things are great for c programs, but they are just not made for dynamic languages and that would have brought a whole sloth of problems.</p><h3>Return address is a parameter</h3><p>In C calling (probably other languages too), the return address is determined in the callee, usually by pushing the pc to the stack. But Arm has a different way, an instruction called Branch With Link, that actually stores the pc in a separate register called Link.</p><p>And this made me realise, that really, the return address is always a parameter to a function. Like other parameters it uses a register. It is the C way to hide this implicit parameter, much in the same way it is the oo way of hiding the self parameter.</p><p>By this time i was already coding some rudimentary calling convention and it did not take long to verify this in code. It is in fact quite easy to determine the return address at compile time and pass it explicitly. (Easy if one does not use a c linker that is)</p><h3>OO calling convention</h3><p>Another thing that deterred me from C is the way they use the stack. It is so completely not oo and cryptic. It is in other words very difficult to unwind, and almost impossible to implement closures.</p><p>Since the assembly had progressed easily, i made performance tests with an oo calling convention, and determined that the price would be <a href="http://ruby-x.org/misc/soml_benchmarks.html">about 50%.</a> Since currently the gap is more than an order of magnitude, this seemed ok, given that it would make the compilation process so much easier.</p><p>The resulting calling convention uses normal Message objects that form a linked list, rather than a stack. Since they are completely standard objects, manipulation both at run and compile time is totally integrated.</p><p>Function calling has been working for years, but recently i cracked dynamic method dispatch too, which was not that hard really. Currently the work is progressing to blocks, and the clear structure does help a lot. And while exceptions (or bindings) are not started, i think they will come with relative ease (compared to the c way), since the structures are very simple.</p><h3>Decisions that affect the future</h3><h3>Metasm</h3><p>I gave <a href="https://github.com/jjyg/metasm/">Metasm</a> several long looks. After all it has assembler and disassembler for at least 10 cpu’s, and support for several binary formats, including elf. The reason not to use it was not that it is big (including much we don’t need). But rather that it is unmaintained and unresponsive.</p><p>It would be great to split all that code into several gems, a core and one per cpu / binary format / assembly, disassembly. Only the core would need to be integrated into rubyx, and one could just use the platform specific gems. But I am not the one to do this work, was the decision.</p><h3>Lock free Concurrency</h3><p>Concurrency will have to be part of the core, even if it is just to get a gc working. The work that <a href="http://valerieaurora.org/synthesis/SynthesisOS/abs.html">Massalin did</a> already showed how effective lock free concurrency is, but Dr Cliff took it into the modern (java) world by publishing a <a href="https://www.youtube.com/watch?v=HJ-719EGIts">lock free hash</a> that he later run on some crazy machine with 800 cpus.</p><p>I am not sure whether it will be better to port the java code, or try a <a href="https://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/">diy</a> version. And off course to even get started on this rubyx will need the compare and swap primitives that underly the lock free approach. But all in due time.</p><p>The actual concurrency i am envisioning as two os-threads per core. One for kernel interaction and one for normal operation. Kernel calls would never be executed on the second, but always queued on dedicated kernel threads. The non kernel threads would be used to run fibers. If we insert some little check into the calling, switching could happen very often and because of the linked list approach would be very very fast. And because of the offloading of kennel calls would never stall (completely). This way one can achieve the sort of millions of fibers erlang is known for.</p><h3>House keeping and garbage collection</h3><p>Often, in systems that are designed to be collected, the base object has some field to support this. This was deliberately left out. RubyX only has objects, so the field would have to be an Object, which is too much overhead. Or there would have to be dedicated instruction to deal with a raw data word which is too much overhead in another way.</p><p>Gc will be a completely external gem, so experimenting will be easy and encouraged. Gc implementers will just have to use their own structures to keep track of the state that they need. Judy style digital trees can do this by actually using less memory than a field would use, but handcrafted bitfields will also be good.</p><p>The actual marking phase should be relatively easy, as the world is known completely. There are no grey stack areas where one has to guess, as all objects are typed and the type determines which slots are objects. Not even registers are grey area, as we switch cooperatively; only the Message register is ever valid.</p><p>In fact, all this makes even moving objects relatively easy. Though there is off course the effort of going through the world to find all backlinks. But if that done during a mark, it comes at relatively low cost.</p><p>All in all a very interesting topic, and surely someone will come up with some great idea. And off course we there will have e to be the most rudimentary from the start, just enough to work and give someone motivation to improve it.</p><p><em>Originally published at </em><a href="http://ruby-x.org/blog/understanding-rubyx-though-historic-decisions"><em>ruby-x.org</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=18a5982a8dce" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ruby-x/understanding-rubyx-though-historic-decisions-18a5982a8dce">Understanding RubyX through historic decisions</a> was originally published in <a href="https://medium.com/ruby-x">Ruby X</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[1000 tests and working binaries]]></title>
            <link>https://medium.com/ruby-x/1000-tests-and-working-binaries-5573853366a5?source=rss----5fa4480fdcd9---4</link>
            <guid isPermaLink="false">https://medium.com/p/5573853366a5</guid>
            <category><![CDATA[rubyx]]></category>
            <category><![CDATA[virtual-machine]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[ruby]]></category>
            <dc:creator><![CDATA[Torsten Ruger]]></dc:creator>
            <pubDate>Fri, 22 Jun 2018 19:06:26 GMT</pubDate>
            <atom:updated>2018-06-22T19:06:25.955Z</atom:updated>
            <content:encoded><![CDATA[<p>It was almost going to be working binaries and over 1000 tests. But i am coming more and more to the point where software is measured in number of tests, not lines of code.</p><h3>1000+ Tests</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0ee8BIgj6hXwJzbL.jpg" /></figure><p>It was shortly after the last post that i first noticed that 1k was approaching. A little hard to grasp that i have written all those, kind of: what do they all do?</p><p>A good step thhough: just about 200 tests in 2 months of work. I noticed the couple of times i didn’t have good coverage for new code immediately, i started to have problems and had to write tests later. It seems it is the only way to understand even my own code anymore: by making the assumptions explicit. Some of the bugs where tests were missing are just the classics, +1 or -1 errors. And i feel a real newbie having to debug for 5 hours to find it was “ Off course i tried the next one straight after, “2+2” and …. it worked too. I don’t know if that is just my bad habit or an occupational thing, this being surprised when things work.</p><p>But a little bit about the journey and what how this works.</p><h3>Positioning</h3><p>Since ruby-x approach is oo from the start, we do not rely on the C way of creating binaries. Instead, the binary is a sort of snapshot of a running system, or in other words there is only heap.</p><p>This means we create binaries that look the same as the memory during runtime, which is made up of small fixed sized objects. Currently we only have objects of sizes 2 to the power of 2,3, 4 and 5. Maybe larger later, but with oo complete data hiding it is easy to extend objects transparently.</p><h3>Constant loading</h3><p>Especially for Code (the only objects larger than 16 words currently), this presented a challenge. Maybe even an extra challenge on top of the purely static one, because of the way ARM load constants.</p><p>Constant loading happens when a known object or address is loaded into a register. Arms constant 32bit instruction only allow 10 bit constants to be loaded. So if the constant is larger (eg the object further away) two instructions instead of one are needed. But this only becomes clear when all positions of objects have been determined.</p><h3>Event approach</h3><p>Off course this is not new, and this is in fact the third time i have coded this, finally getting it right. The problem gets hary with the 16 words limit, when the code overlaps the originally assigned length and a new object has to be inserted.</p><p>To keep one methods code continuous, all other methods code has to be moved up, an thus a whole lot of positions change. Off course when some objects position change, a load depending on that may go from 1 to 2 instructions and so on and on. And then there are the branches that load their targets (forward and backward branches) off course, and they need to be updated etc etc.</p><p>I now have position objects which fire events, and about 4 different kind of listeners reacting in different ways when different objects change. The whole thing works, though as with many an event system, it is difficult to say exactly how. (only easy in the small, not the whole i mean)</p><h3>Object continuation</h3><p>As i mentioned, it is quite straightforward to have larger data amounts, made up of 16 word chunks, by having a linked list. This is how the BinaryCode objects, that hold the binary code, do it.</p><p>But with the binaries there is an extra twist to this. The BinaryCode object has a header (the type and next), which are not code. So the code has to jump over this header at every end of an object.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*aqa_DB3dBzR3D36k.jpg" /><figcaption>de-assembled hello world</figcaption></figure><p>This is demonstrated by the object dump above. If the assembly is scary, don’t worry, just look at the top left, address 16260, where the BinaryCode object for the main method starts. You see the first two words are separated, as i said the type and next (see the 162a0 value is the address of the BinaryCode on the right).</p><p>Mainly i wanted to demonstrate the jump, which is the last instruction on the left side. The <strong>b</strong> stands for branch and the address 162a8 is exactly the code of the next BinaryCode, ie just after the header.</p><p>You can just make out on the bottom left, that this is in fact the code for the “Hello World” , as it jumps to the (Word_Type.) putstring.</p><h3>Next steps</h3><p>Hello World is off course a very small step and work will continue on making other things work. On the Interpreter side, many more things, like loops, conditionals, maths and dynamic dispatch already work.</p><p>Luckily, part of this push was to make the Interpreter a platform similar to the Arm. So it too has BinaryCode and works with addresses, not objects as before. In short the differences between Interpreter and Arm have shrunk, and there is good reason to believe that much will work quite soon.</p><p>Next i will build a testing framework to test the same code on Interpreter and Arm and see that both work. And specifically get all those working Interpreter tests working on Arm.</p><p>I think then it is time for some benchmarks. It has been a while since <a href="http://ruby-x.org/misc/soml_benchmarks.html">i made some,</a> and they were quite promising. Especially loops of the Hello World and Fibonacci.</p><p>On the further horizon i was planning for continuations next, probably with a small rework of the return mechanism (unified return sequence).</p><p><em>Originally published at </em><a href="http://ruby-x.org/blog/1000-tests-and-working-binaries"><em>ruby-x.org</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5573853366a5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ruby-x/1000-tests-and-working-binaries-5573853366a5">1000 tests and working binaries</a> was originally published in <a href="https://medium.com/ruby-x">Ruby X</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Four years and going strong]]></title>
            <link>https://medium.com/ruby-x/four-years-and-going-strong-b8174ef2a31e?source=rss----5fa4480fdcd9---4</link>
            <guid isPermaLink="false">https://medium.com/p/b8174ef2a31e</guid>
            <category><![CDATA[virtual-machine]]></category>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[performance]]></category>
            <category><![CDATA[rubyx]]></category>
            <category><![CDATA[ruby]]></category>
            <dc:creator><![CDATA[Torsten Ruger]]></dc:creator>
            <pubDate>Mon, 23 Apr 2018 08:21:43 GMT</pubDate>
            <atom:updated>2018-04-23T08:21:43.577Z</atom:updated>
            <content:encoded><![CDATA[<p>After <a href="http://ruby-x.org/blog/a-dynamic-hello-world">finishing the code,</a> i updated all the docs too!</p><h3>The rewrite</h3><p>Doing anything for the first time is not so easy. I have taught enough by now to see how central <em>guidance,</em> the experience of another, is to the process of learning. <br> I was so much thinking about Vm’s in the beginning that a lot went sideways.</p><p>Now it feels <a href="http://ruby-x.org/blog/rubyx/layers.html">the abstractions</a> are coming into focus, the code is clean and relatively easy to understand.</p><p>During this latest wobble, maybe 500 commits in all, almost everything above the Risc layer was rewritten. At the low point, i was down to just over 400 tests, but now, back strong, at over 800. That’s 94% coverage with a <a href="https://codeclimate.com/github/ruby-x/rubyx/">CodeClimate A</a> so that’s ok.</p><p>In the process i got much closer to the actual goal, which i’ll go into more detail.</p><h3>The docs</h3><p>Now i have also cleaned up all the documentation. This does not mean that everything is documented, but i hope one can get a good idea from the docs, and then just read the code.</p><h3>Architecture</h3><p>The <a href="http://ruby-x.org/rubyx/layers.html">Architecture</a> section given an overview over the new layers.</p><ul><li>Ruby Simplified: Vool</li><li>Mom, a simple machine with object memory</li><li>Risc, the old abstraction of a CPU</li><li>Arm and Elf, to actually generate binaries</li><li>Parfait and Builtin to get the the system up</li></ul><h3>Parfait</h3><p>There is a separate document describing the classes needed to boot the system. A little about the current state of Types and Classes.</p><p>But it should definitely be expanded, and there is nothing about Builtin. Builtin is the way to write methods that can not be expressed in ruby. And since writing them got so messy i wrote a DSL, which is only documented in <a href="https://github.com/ruby-x/rubyx/blob/master/lib/risc/builder.rb">code.</a></p><h3>Calling</h3><p>Since Calling is now done, i documented both the calling convention, and the way method resolution is done.</p><h3>Interpreter</h3><p>Off course the <a href="http://ruby-x.org/blog/rubyx/debugger.html">Interpreter</a> is still working, (since the Risc layer didn’t change much) and is a large part of the testing scheme.</p><p>And i even go the <a href="http://ruby-x.org/debugger">Debugger</a> working again and integrated into the new site (which is now a rails app).</p><h3>Misc</h3><p>Finally i cleaned up the old mumble jumble docs and sorted them a bit into what is ideas, plans and just background info, in the <a href="http://ruby-x.org/misc/index.html">Misc section</a></p><h3>Next Steps</h3><p>The plan for the near future is something like this</p><ul><li>More complicated tests. Whole methods that do something and test containing several methods. All just testing results.</li><li>Better test framework for testing binaries.</li><li>Blocks</li><li>Baby steps towards Stdlib</li></ul><p>As one can see, work happens when i have time and inspiration.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*o6j9Gc_JWN6yzDaK.jpg" /></figure><p>But even after 4 years, i haven’t given up yet :-) Though i may have given up on any time estimates.</p><p><em>Originally published at </em><a href="http://ruby-x.org/blog/four-years-and-going-strong"><em>ruby-x.org</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b8174ef2a31e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ruby-x/four-years-and-going-strong-b8174ef2a31e">Four years and going strong</a> was originally published in <a href="https://medium.com/ruby-x">Ruby X</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>