Archive for March, 2008

How Rubinius SendSites Work – Part 1

Posted in shotgun with tags , on March 19, 2008 by agardiner

Recently, Rubinius switched from using a simple method dispatch caching mechanism to using a significantly more powerful mechanism known as a SendSite. Over the next couple of posts, we’ll look into the Rubinius SendSite implementation, commencing with an overview of what SendSites are in part 1. In part 2, we’ll examine how SendSites are used in the method dispatch process.

2006-09_042-london-night.jpg

Origins

Before we dive in and start looking at the Rubinius SendSite class, it may be worthwhile reviewing some of the terminology that will be used, and particularly, the origins of the term SendSite.

Ruby and Rubinius draw heavily on the Smalltalk language and implementation; within Smalltalk, perhaps the central concept is the idea of message passing, whereby objects interact via the sending of messages; we talk of objects sending messages to receivers and getting back responses. In practice, this is almost identical to saying that code calls a method and gets back a result, which is how the process is commonly described in most languages.

However, there is one key distinction: message sending makes clearer the concept of duck-typing, and encourages a coding style known as “Tell, Don’t Ask”. In Smalltalk and Ruby, we don’t really care what the type of the receiver is; we only care whether or not it can respond to the message we send. Similarly, in the “Tell, Don’t Ask” coding style, we tell receiver objects what we want them to do based on our internal state, we don’t ask the receiver for details of their state in order to make decisions. The result is that it is easier to replace the receiver object with another object that understands the same message, but perhaps performs the request in a different way.

What is a SendSite?

Ultimately, it is this very capability that complicates method dispatch in Ruby, and makes the use of method caching and other optimisations desirable: if the receiver class can change at any time, resolving exactly which implementation of the message to dispatch to cannot be determined definitively until the actual point-in-time when the message is dispatched. However, it is also true that most times, a given message send (i.e. send site) in a piece of code will resolve at dispatch time to the same receiving code (i.e. method)…

If we could therefore somehow cache the result of this method resolve process, the next time we reach the same send site, we can perform a quick check to determine if the receiving method is still the same as last time, and if so, use an optimised dispatch process. This could could range from the simple, such as jumping directly to the method code via a cached reference, to the complex, such as in-lining and JIT-ing frequently called methods into directly executable machine code at the send site.

The Rubinius SendSite, therefore, is an object that is created for every send site (method call) in the Rubinius bytecode, and facilitates these kinds of optimisations.

With that bit of background behind us, let’s dive in and see how Rubinius defines a SendSite…

SendSite: Half Ruby class, half C struct

We saw above that a SendSite represents a location in code where a message send (aka method call) takes place. At its most basic, a SendSite needs only record the name of the message that is to be sent; indeed, before SendSites were added, a reference to the Ruby symbol identifying the message name was all that was recorded in the Rubinius bytecode. However, by replacing the symbol of the message name with a data structure, we gain the ability to store additional information at the send site, and in particular, information that can be used to speed up method dispatch.

Rubinius SendSites, like a number of other core classes integral to the Shotgun VM, need to be accessible from both Ruby and C code. As most of the use of SendSite is in C code in the VM, and is performance critical, SendSite instance data is stored in the fields of a C struct:

name:
The name of the message (i.e. method) this send site sends (calls)
cm:
A reference back to the CompiledMethod instance in which the send site exists.
selector:
A reference to the Selector instance corresponding to the message name (see Selectors below)
data1:
The receiver class
data2:
The CompiledMethod corresponding to this message on the receiver class, as encountered on the last dispatch. When a message is dispatched, this is the target object that needs to be located; it contains the bytecode for the method on the receiver.
data3:
The module
data4:
The primitive index if the SendSite resolves to a primitive method
c_data:
A pointer to some C data;

  • For an FFI send site, holds the address of the FFI stub function to call.
  • For a primitive send site, holds the address of the primitive function to call.
hits, misses:
Counters for the number of times the SendSite has successfully and unsuccessfully cached the receiver method respectively.
lookup:
A function pointer (functor) to the method lookup function that will be used by the SendSite to perform method dispatch.

Ruby code can access most fields of this C struct via the SendSite#at method, which is implemented as a Rubinius primitive.

The two most important data items in a SendSite are the symbol of the method name to which the SendSite relates, and the address of a lookup function to use to resolve the message name to a method object to which to dispatch. These two fields (and the reference to the containing CompiledMethod) are the only ones populated when a SendSite is initialized, and are sufficient to resolve a message send to a receiver method (albeit, via a slower path).

Selectors

We saw above that a SendSite contains a reference to a Selector object. A Selector is an object that represents a message (i.e. method) name. It consists of the symbol of a message, plus an array of links back to every SendSite that uses the same message. This can be extremely useful, as it provides the ability to locate all direct uses of a particular message (although indirect uses such as via send and the various evals are not caught).

Selectors are not used in the method dispatch process; they exist solely to provide a reverse lookup for a given method name to the SendSites that use it. Nonetheless, this is an extremely useful capability; it is used to find and reset SendSites impacted by a redefinition of a method, and is also extremely handy for finding the messages most often used. In fact, it is this capability that lies behind the -ps and -pss flags that can be used when launching Shotgun; upon exiting, these flags cause a summary to be printed of the most frequently encountered Selectors and SendSites respectively:

ads@ads-kubuntu:~/rubinius$ shotgun/rubinius -ps 10 -e '0'


Total Selectors: 1168
Top 10, by receives:

name receives send sites
at 15694 131
equal? 13074 47
misses 12748 2
hits 12746 2
[] 11842 1180
kind_of? 5865 183
<= 4390 53
size 4293 225
hash 3967 11

Note that this shows the most frequently sent messages, which is not the same as the most frequently executed methods; for that, we need to know the receiver as well. For example, the method #at is the most frequently exexcuted message, but is actually distributed across three different receiver methods (Time#at, Tuple#at, and Array#at).

In Part 2, we’ll look at the lifecycle of a SendSite, and see how it influences the method dispatch process. Continue reading

Shotgun: The Rubinius Virtual Machine

Posted in shotgun with tags , , , , on March 18, 2008 by agardiner

As I stated in my introductory post, I intend with this blog to delve into some of the implementation details of Rubinius. However, as I’ve contemplated various topics to write about, I’ve realised I first need to introduce some of the core underlying concepts and (Ruby) classes unique to Rubinius.

The most important of these (and the topic of this post) are those that relate to the Rubinius execution environment: the Shotgun Virtual Machine, and the various Ruby classes that provide access to Shotgun internals.

louvre.jpg

Shotgun: A Virtual Machine

As mentioned elsewhere, Rubinius is heavily influenced by the implementation of Smalltalk-80, and borrows many of the same concepts and even some of it’s class names from there. Like Smalltalk and Java, Rubinius compiles Ruby source code into a lower-level machine-independent instruction set that is executed on a virtual machine, known as Shotgun.

The Shotgun virtual machine has many similarities to a real computer, such as (virtual) CPUs and an instruction set, but also many higher-level abstractions (such as managed memory and a garbage collector), that make it easier to target as an execution environment for a high-level dynamic language such as Ruby.

Shotgun is currently written in C, although some portions of the source code are actually generated from Ruby (e.g. the opcode and primitive implementations are defined as embedded C code inside Ruby methods). In the future (post-1.0), the plan is to have more of the C code generated from Ruby or a Ruby-like language (Garnet), much as how Squeak (a Smalltalk implementation) implemented a virtual machine in Squeak.

Shotgun Architecture

Shotgun is written in a relatively clean and easy to follow style. It contains no global variables, and consists of a layered architecture: at the root is an environment, within which machines are instantiated. Each machine represents an entire Ruby/Rubinius virtual machine, and runs in its own native (OS) thread. Machines can communicate via an inter-machine message channel, but are otherwise totally separate and isolated.

Within a machine, there exists a virtual CPU, which runs one or more (green) threads. A Shotgun CPU effectively represents a native thread on the underlying hardware, whereas a Shotgun thread represents a Ruby thread. Just like a real CPU, the Shotgun virtual CPU pre-emptively multi-tasks (Shotgun) threads. At present, a Shotgun machine always has a single CPU, so all Shotugn threads within a single machine therefore execute on a single native thread. In the future (again, post-1.0) it is planned to implement what is known as an m:n threading model, whereby a pool of m native threads are used to execute n Ruby threads.

At the next level down from threads are what are known as tasks. Each Shotgun task maintains an operand stack (Shotgun is a stack-based VM) and a reference to the current execution context. Tasks are very similar to threads, but lack pre-emption or scheduling. In practice, they are similar to Ruby 1.9 fibres, although unlike fibres, there is currently no way to co-operatively multi-task (or yield to a co-routine) using Rubinius tasks.

A context represents something similar to a stack frame in C or Java. It represents the current execution context, and as such, it provides:

  • a link back to the caller of the current method;
  • a reference to the compiled method currently being executed;
  • instruction (IP), stack (SP), and frame (FP) pointers for the current instruction, current stack operand, and the operand stack pointer location at the commencement of the current method respectively;
  • the current scope for resolving constant and method lookups; and
  • storage for all local variables in the current scope.

Finally, each context has an associated compiled method, which contains the instruction bytecodes to be executed for the method to which the context relates. Compiled methods are the result of compiling Ruby source into Shotgun bytecode, and are the units of execution in Shotgun. A compiled method contains:

  • the bytecode instruction sequence that tells Shotgun what actions to take;
  • the number and names of any local variables used in the bytecode;
  • the static scope, used for resolving constant and method lookups; and
  • a tuple containing the literals contained in the source code that cannot be represented directly as opcode arguments (e.g. strings, symbols, method calls etc).

Key Rubinius Classes

Without further ado, let’s look at the Ruby classes that correspond to the concepts above… but this time, we’ll work from the bottom up.

InstructionSequence

In Rubinius, Ruby code is compiled down to bytecode , which is then executed by Shotgun, the Rubinius virtual machine. The compilation process is reasonably complex (see here for a detailed overview), but the end result is that Ruby code is converted into a sequence of integers, representing the VM opcodes and any arguments they take. The class that represents this bytecode in Rubinius is InstructionSequence, which is a sub-class of ByteArray.

The InstructionSequence class does not have many useful instance methods, since it is essentially a representation of the Shotgun machine language. However, the class source file defines a number of related classes for working with InstructionSequences that are useful, including:

InstructionSet

Defines the full set of Shotgun instructions or opcodes, and includes useful metadata about each instruction. This includes information about the number and purpose of any opcode arguments, whether the opcode changes the flow of execution, the number of stack operands consumed and produced, etc.

Encoder

This class is used to encode and decode an instruction sequence between symbolic and bytecode representations. It is used by the compiler, to convert a generated instruction sequence consisting of opcode symbols and arguments into the actual bytecode executed by Shotgun and saved to disk in .rbc files. It is also used by tools such as the debugger to disassemble the bytecode of a CompiledMethod into something that can be displayed on screen, or to modify bytecode to support debugging.

CompiledMethod

A CompiledMethod represents the compiled source code for a Ruby method (or top-level script, i.e. Ruby code that is not part of a method body). As such, a CompiledMethod contains an InstructionSequence instance containing the compiled bytecode for the method source, the number and names of any local variables used in the method, details of the method scope, and a whole bunch of other attributes.

A CompiledMethod is the main executable unit in a Rubinius program. It is the output created by the Rubinius compiler that is then passed to Shotgun for execution and/or persisted to disk. CompiledMethod instances can be obtained from any method definition using the #compiled_method accessor on a Method or UnboundMethod object.

CompiledMethod objects are also nested; each Ruby source file that is compiled by Rubinius creates a single top-level CompiledMethod object named __script__, which is then run when the (compiled) file is loaded. Any CompiledMethod can contain other CompiledMethod objects as literals; so when a Ruby script is executed that contains, for example, a def statement, the bytecode for the new method will be compiled into its own CompiledMethod object, and this CompiledMethod will then be added to the literals tuple of the containing CompiledMethod. From there, it can then be referenced by opcodes such as add_method, which hook a CompiledMethod up to a symbol in a method table.

MethodContext and BlockContext

The next level up from a CompiledMethod is an execution context, in the form of either a MethodContext or a BlockContext (depending upon whether we are dealing with the execution of a method or a block). Where a CompiledMethod represents the executable instructions for a given method or top-level script, an execution context represents the actual execution of Rubinius code.

MethodContext and BlockContext instances provide a way to inspect and modify the execution environment. Not surprisingly, they are therefore a key component enabling the Rubinius debugger to do its thing. However, they also make implementation of eval bindings and continuations almost trivial, since an execution context contains all the necessary details to resolve binding references relative to some other context (e.g. a caller’s context), and to save and restore execution state.

Task

As we saw earlier, a Shotgun task maintains an operand stack and a reference to the current execution context. Tasks are also the building blocks for Ruby threads, and provide a way to transfer an execution context from one Ruby thread to another.

The Task class provides access to a the current execution contex, via Task#current_context, and to the operand stack (the latter being of interest primarily to the debugger).

Thread

The Thread class provides an implementation of the Ruby Thread class semantics using a combination of Ruby code, Tasks, and Rubinius (Shotgun) primitives: the execution context for a thread is maintained via an associated Task, and methods that control thread scheduling and execution are implemented as primitives.

Conclusion

In this post, we’ve introduced the Shotgun virtual machine, and looked at how it models an execution environment through the concepts of machines, cpus, tasks, etc. However, there is a good deal more to Shotgun that we’ve not even touched on, and which will have to be saved for a future post.

I hope you’ve found this post informative; feel free to ask questions, provide feedback, or indicate the areas you’d like to know more about using the comments facility below.