Talk Like A Duck

Smalltalk primitives

In Smalltalk-80 and it’s descendants, primitive methods are implemented in a low-level languages like C or Assembler. They are attached to normal Smalltalk methods by a special syntax. For example, here’s a simppet from the Smalltalk-80 Blue Book, this is a method definition for the + method in SmallInteger (Smalltalks analogue to Fixnum in Ruby:

1: + addend
2:   <primitive: 1>
3:   ^ super + addend

The Smalltalk compiler turns method code into CompiledMethod objects which contain the bytecodes implementing the smalltalk code along with other information such as where to find temporary variables. In the case of a method such as the bytecodes would be something like:

   push self
   push addend
   send_super #+, 1  // invoke the inherited + method with 1 argument 
   return_top_of_stack

These are the bytecodes to implement line 3.

The effect of line 2 is to mark the compiled method as being associated with a numbered primitive. A Ruby implementation of a Smalltalk VM might have code like this.

Module VM

  class CompiledMethod

  def execute
      begin
        return exec_prim if has_prim?
      rescue PrimitiveFailed
      end
      return VM.interpret(byte_codes)
  end    

So the idea is that, if a compiled method has an associated primitive method the VM executes it. If it succeeds then that’s the end of this method invocation. If it fails then execution falls through to interpret the byte codes.

In the case of the method we are considering the primitive suceeds if the argument is also a SmallInteger, and the result doesn’t overflow othewise it fails. This allows primitives to quickly handle the 80% cases, and fall back on high-level smalltalk code for the more complicated cases.

User Primitives

Later Smalltalk implementations such as Smalltalk/V and IBM/Smalltalk allowed user written primitives. These were usually referenced by namerather than a number. The same flow allowed fallback to Smalltalk code on failure of a user primitive, either for error recovery, or for balancing implementation complexity against performance.

Ruby Extensions

In contrast, Ruby methods are either wholly normal Ruby code, or wholly extension methods written in C functions registered using ruby api calls like rb_define_method. These methods are somewhat invisible to the ruby programmer. This can be confusing, particularly when you are trying to read code which is partially implemented in C and partially in Ruby. Just this morning I was trying to debug somebody else’s code which was using the eventmachine gem. Looking at the source for eventmachine showed methods being invoked with no definition visible in the ruby source. These methods actually live in a C extension to the class.

Could Ruby Use Something like Smalltalk’s Primitive Methods?

It might be nice if this could be made visible using a mechanism like Smalltalk’s primitive not only to document such cases, but as a way to do th ekind of complexity/performance balancing I’ve described.

It might be interesting to think about combining this with the ideas behind ruby-inline, and to allow the primitives to be written in-line as well. The difference I would see would be the introduction of the idea of failure/recovery and better support for usage of the ruby.h api inside the inlined primitives.

Just a thought.

Postscript – Related Technology

Although I consider the Smalltalk primitive idea as something which might be added to Ruby, Smalltalk and related languages have added more modern techniques for moving the implementation of the core up into the higher-level language.

Squeak smalltalkUses a language called slang (not tobe confused with s-lang), as the source language for the Squeak VM. Slang has a Smalltalk-like syntax but it is easily translated to C. Squeak user primitives are written in slang as plug-ins.

Evan Phoenix’, Rubinius started out as a Ruby VM being written in Ruby or a slang-like language with a ruby-like syntax, but it seems to have changed tack to use a handcoded port of Evan’s earlier Ruby code to C. This ported VM is called Shotgun. Shotgun seems to be taking an approach quite similar to the original Smalltalk-80 numbered primitives to implement the functions of the ruby standard library. I don’t beleive that they are using the primitive failure with fallback idea though.

Java has the Java Native Interface (or JNI) which is similar to ruby’s extensions in that it provides a c-API to the JVM. It differs from Ruby in that Java classes must have declarations of any native functions they provide and are responsibole for loading the load library containing the binary.

I must confess that it’s been a few years since I stopped keeping up with Java evolution, so there may be new things in Java in this area.

An interesting historical sidenote is that the original VisualAge for Java which was written before the advent of JNI used what was called the “UVM” or Universal Virtual Machine. This was a version of the IBM Smalltalk VM extended to support both Smalltalk and Java bytecodes. The UVM used Smalltalk as the language in which Java native methods were written. When Sun came out with the JNI, with requirements for C language primitives, VA/Java moved from a Smalltalk VM to either the Sun or IBM JVMs.

After Dave Ungar cut his teeth (and earned his PhD) working on the UCB implementation of Smalltalk-80, he took on the challenge of implementing a dynamic language completely in itself in the aptly named self language. The philosophy behind self abhored statically optimized techniques, including prmitives written in a low-level language, in favor of dynamically optimizing code at run-time. This was the genesis of the JIT and HotSpot approaches commonly used in Java. It was also the basis of the Strongtalk project which saw members of Dave’s self team taking some of the ideas from Self back to a Smalltalk implementation.

In most Smalltalk implementations #ifTrue;ifFalse: and its ilk are never sent, but are, like in ruby, compiled into test and branch code. Some implementations might have had a fallback if booleanValue wasn’t actually a boolean, but IIRC most would trigger a MustBeBoolean exception.

By the way, those […] are the Smalltalk analog to ruby’s blocks. In Smalltalk, blocks can be used as the value of any argument to a method, and a method could take more than one block argument.

But blocks are also another area where Smalltalk implementations tend to cheat a bit.

Smalltalk maintains the fiction that ifTrue:ifFalse: is really a message, and the methods in True and False are there to see:

in the True class

   ifTrue: trueBlock ifFalse; falseBlock
       ^trueBlock value

   ifTrue: trueBlock ifFalse: falseBlock
        ^falseBlock value

The sending the message value to a Smalltalk block is analogous to sending call to a Proc in ruby, although the actuall message varies with the arity of the block. In the case of ifTrue:ifFalse, the block arguments don’t really bedome block objects, they get compiled as in-line code.

   value
      "return the result of evaluating the receiver"
      ^self value

This certainly looks like it should be an infinite loop, but it isn’t. The trick is that in almost all circumstances, the Smalltalk compiler compiles sending value to a block into either special bytecodes. The only reason that the value method in block needs to be there is to handle cases like:

where perform is the analog to ruby’s send.

Smalltalk VM implementors like to say that it’s okay to cheat as long as they don’t get caught. MustBeBoolean is one area where they do get caught.

Pushing the Envelope

It’s quite a daunting task to fully implement a computation model where everything is a message and get reasonable performance. Smalltalk pushed this model quite far, but bowed to practicality in a few cases.

Ruby, although it’s more dynamic than Smalltalk in a lot of ways, makes more concessions in it’s current implementation.

Dave Ungar’s self language, in the spirit of Nigel Tufnel, turned theknob up to eleven, and eschewed the pre-optimization of even if tests. Instead, the self implementation developed and used sophistacated run-time type inferencing and analysis to generate optimized code at runtime by detecting the common cases of a boolean receiver and converting the message send to tests and branches, while avoiding supporting the less common case.

In common with Ruby, self had a more dynamic object model than Smalltalk, based on delegation rather than inheritance. Something which engendered roaring debates in the early OOPSLA community over how delegation and inheritance are related. The status of that discussion ca. 1989 is captured in “The Treaty of Orlando.” which documented the observation that the differences were really a matter of perception and viewpoint.

The real contribution of self was setting the bar high in terms of the difficulty of implementing a simple and dynamic specification, and then jumping over it. The self team later applied the lessons they had learned to the implementation of Strongtalk, a Smalltalk VM which applied the techniques of the self implementation to both make Smalltalk more dynamic, and better performing.

Many of those sessons should be applicable to implementations of Ruby. I hope to see that unfold over time.

Consider the source

In his day job, paraphrasing his self description John "works for IBM on Java virtual machines and is the lead on the Eclipse tools project management commitee."

But some of my readers might be interested in John's background. John was for a very long time, the lead of the Smalltalk and Java virtual machine team at Object Technology International (OTI) dating from before the time it was acquired by IBM. Among other things John was responsible for the development of embedded Smalltalk virtual machines from OTI, which spawned the VM used in Smalltalk/V Mac, IBM Smalltalk (used in IBM/VisualAge), the 'Universal' Virtual machine which implemented Java on an extended Smalltalk VM, and which was used for the early releases of IBM/VisualAge for Java, and the J9 Java VM. A good deal of what I know about implementing VMs comes from working, lunching, and bar-hopping with John.

John had become OTI's Chief Technology Officer before OTI got assimilated into the IBMborg.

John is a brilliant guy, with a great sense of humor. Two characteristics which seem to have been requirements for a job at OTI. I'm still not sure how I ended up spending several years there.

Dynamically Typed Doesn't Need to Mean Slow

I encourage you to read John's blog post yourself, but to summarize; John ran across another blog item which gave a benchmark written in C++, Ruby and Python. The C++ version runs in under 1/10 of the time needed for either the Ruby or Python versions.

John duplicated the results on his machine, then decided to port the Ruby version of the benchmark to Smalltalk. He then ran it using VisualAge Smalltalk.

And the Smalltalk version runs in the same time as the optimized C++ version!

How can this be?

The Value of Pole Vaulting

Languages like Smalltalk and Self started from the position that a clean object-oriented language was more important than one which makes compromises to make efficient implementation obvious.

Early implementations of Smalltalk used obvious implementations of some features, which were 'fast enough' in many cases, but by no means fast. Two areas which cried for improvement were method dispatch and garbage colection. The obvious techniques were walking up the class hierarchy each time a method was needed, and relatively easy to implement GC techniques like reference counting, and mark-and-sweep. Reference counting has a fairly high cost for each change of an object reference, and also has the drawback of leaking memory because cyclical references lead to garbage which is uncollectable. Mark and sweep delays the overhead until storage is exhausted, but leads to more perceptible pauses when the application gets paused so that the housemaid cleans the room.

Encountering (or having set) this high bar, various implementors of these languages found very clever techniques for both problems. Dave Ungar made measurements of the lifespans of Smalltalk objects and observed that most objects died very shortly after being instantiated, with few living a long life. This led to the invention of generational GC techniques, which quickly dispatched young dead objects, which are the vast majority.

Method dispatching techniques of efficiently implemented dynamically typed languages tend to use clever caching algorithms which can get to what is probably the right method quickly, with a quick test to make sure that the right method was found.

These dispatching techniques turn out to be faster than the virtual function pointer dispatching made possible by strongly-typed languages like C++. In fact, I've heard that more modern implementations of these languages have actually used a more dynamic method dispatch mechanism internally in order to increase performance.

Anoher implementation choice is how to represent executable code. Most efficient implementations use a combination of byte-code representation, and some form of just-in-time translation of byte-codes to machine code. Just how to divide execution between byte-code and machine code is a complicated decision. Back when DIgitalk first produced a version of Smalltalk/V for OS/2, they decided to eschew byte-codes entirely and generate 80286 machine code. The reason was that they were tired of hearing complaints about Smalltalk being an 'interpreted' language.

The surprising result of this experiment was that the resulting implementation was slower. Machine code was bigger, so it took longer to load, and caused more swapping. These costs were paid whether the code in question was executed once or a million times.

Again caching was the basis for getting the best of both worlds. Peter Deutsch of Xerox, later ParcPlace, had introduced the notion of translating byte-codes to machine code into a cache during execution, David Ungar's implementation of Self introduced the notion of using light-weight profiling techniques to avoid the overhhead of translating byte-coded methods which were infrequently executed.

Another area which posed difficulties in implementation was control flow. Smalltalk-80 defines all control flow as methods. Even primitive control flow constructs such as if (ifTrue: in Smalltalk) were implemented as methods on Boolean classes. This is one area where Smalltalk implementations cheated compiling such methods in to testing and branching byte-codes, and requiring the receivers to be boolean instances.

Self eschewed this early optimization. Ungar's team instead relied on run-time type inference in order to dynamicaly generate code which achieved the same or better performance when such a message was sent to a boolean without restricting other cases.

The Current State of Ruby Implementation

Ruby performance today is surprisingly acceptable for a wide range of uses.

This is despite the fact that the implementation is relatively straightforward, almost to the point of being naive. In the current standard implementation of Ruby:

• Method dispatch is done by walking up the 'class' hierarchy looking for methods in a hash table in each class/module.
• Garbage Collection is done by a simple mark and sweep algorithm.
• Executable code is represented by a parse tree which is executed by traversal.

This is not meant to understate the achievements of Matz and the ruby developers. Ruby as it is definitely usable for many production uses.

The point is how much better Ruby performance can get as the implementation matures. A virtual machine, with byte-codes, and better GC is on the roadmap. Ruby virtual machines such as YARV, and JRuby are showing glimmers of the value of implementing Ruby as a virtual machine. If Ruby continues to grow in acceptance, I've no doubt that other clever implementers with experience in efficently implementing dynamically typed languages will provide more implementations.

My prediction is that the future will be so bright that we're going to have to wear (ruby colored) shades!