Gem Cutting With Rusty Tools

This is a writeup of a talk I gave internally in SalesMaster, as part of one of our biweekly developer forums. It covers a bit of Rust, Ruby, foreign function interfaces and having the right tools for the job.

Preamble

I am pretty passionate about web application performance: I see it as a usability/accessibility problem, and I’m firmly in Maciej Cegłowski’s school of thought in terms of a solution. However, sometimes you just can’t get away from the need to have interactivity, having some sort of CRUD interface. Even worse, you might even need to do computationally expensive operations while the user waits. To not inconvenience the user too much, we need the right tools for the job.

Ruby is not the fastest language in the world, but this isn’t really a huge deal (at least from my perspective). What Ruby lacks in runtime speed it more than makes up in terms of the time it takes from idea to implementation. Expressive, easy on the eye and has a brilliant toolchain.

There are times when runtime speed matters, and in those cases, it really matters. There are many good examples of this, but for this we’re going to use sorting an array. Array sorting is well-defined problem in computer science, essential for adding floating point numbers. It will serve to illustrate the importance of the right tools for the right jobs.

Sorting

Let’s digress a bit and talk about sorting algorithms for a moment. Generally speaking, quicksort remains a commonly used algorithm to sort arrays. It’s average case performance is O(n log n) – quite close to linear time. It’s this algorithm that we’re going to use going forward.

Without further ado, let’s look at what a quicksort implementation might look like in Ruby:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
##
# Implementation of Quicksort, using a random pivot
# Quicksort is, on average, of O(n log(n)) in time complexity
# and of O(log(n)) space complexity
# @return [Array] the sorted array
module Quicksort
  def quicksort
    return self if length <= 1
    pivot = sample
    partition = group_by { |n| n <=> pivot }
    partition.default = []
    partition[-1].quicksort + partition[0] + partition[1].quicksort
  end
end

We would include this to extend the Array class with a new method, quicksort, returns a new, sorted array. We use the spaceship <=> operator to do the comparison within the block passed to group_by.

However, this is pretty slow. Let’s look at some benchmarks:

1
2
3
4
5
6
7
8
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-darwin15]

Random Data (1m shuffled integers) Benchmark
Warming up --------------------------------------
     Array#quicksort     1.000  i/100ms

Calculating -------------------------------------
Array#quicksort      0.189  (± 0.0%) i/s -   1.000  in   5.299004s

This guy. Only one interation every 5.3s. For comparison, Ruby’s native Array#sort can do about 4.5 iterations per second. This is pretty good, but what if we needed to go faster? Your J. Jonah Jameson-style boss is continually reminding you time is money.

Rust

We can turn to a ‘faster’ language, at least a language that can do the same operation faster. For our purposes we are going to be using Rust. Rust is a general purpose programming languages that is “blazingly fast, prevents segfaults, and guarantees thread safety”, according to the homepage. It’s a statically typed, compiled language, which provides a nice contrast to Ruby’s dynamically typed, interpreted nature.

Let’s take a look at a (truncated) implementation of quicksort in Rust:

1
2
3
4
5
6
7
8
9
10
11
12
13
// OrderFunc is a special type that corresponds to a comparitor function
pub fn quick_sort<T>(v: &mut [T], f: &OrderFunc<T>) {
    let len = v.len();
    if len < 2 {
        return;
    }

    let pivot_index = partition(v, f);
    quick_sort(&mut v[0..pivot_index], f);
    quick_sort(&mut v[pivot_index + 1..len], f);
}

// partition() function omitted for brevity

As you can see, Rust is a little less expressive, but the implementation is very similar: it uses recursion and a comparitor to perform the sort.

Let’s have a look at those benchmarks:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-darwin15]

Random Data (1m shuffled integers) Benchmark
Warming up --------------------------------------
     Array#quicksort     1.000  i/100ms
      Array#rustsort     1.000  i/100ms

Calculating -------------------------------------
     Array#quicksort      0.189  (± 0.0%) i/s -      1.000  in   5.299004s
      Array#rustsort      7.706  (± 0.0%) i/s -     39.000  in   5.082234s

Comparison:
      Array#rustsort:        7.7 i/s
     Array#quicksort:        0.2 i/s - 40.83x slower

The Ruby implementation is almost 41x slower than the rust implementation. Let’s now compare it with Array#sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-darwin15]

Random Data Benchmarks
Warming up --------------------------------------
          Array#sort     1.000  i/100ms
      Array#rustsort     1.000  i/100ms

Calculating -------------------------------------
          Array#sort      4.437  (± 0.0%) i/s -     23.000  in   5.191888s
      Array#rustsort      7.754  (±12.9%) i/s -     39.000  in   5.057555s

Comparison:
      Array#rustsort:        7.8 i/s
          Array#sort:        4.4 i/s - 1.75x slower

Array#sort is 1.75x slower than the Rust implementation! JJJ might stop breathing down our neck, but he has reminded us of one thing: we’re a Ruby shop – we aren’t switching to Rust just because it’s faster for sorting arrays. We need a way of integrating the two.

FFI

A foreign function interface (FFI) will allow us to call the Rust implementation of quicksort from Ruby. In fact, that is what I was doing to generate those benchmarks. There are 2 main ways of writing a foreign function interface in Ruby, plus an extra I will talk briefly about.

Fiddle

Fiddle is part of Ruby’s standard library, and provides a simple, reasonably low level way of creating an FFI (it is just a wrapper for libffi. However, as far as I understand it there is no native support for boolean-type returns (as stdbool.h isn’t used). For our purposes, this is no good – we are probably going to want to return booleans from some functions.

ruby-ffi

ruby-ffi is a gem that implements it’s own FFI library, along with a great DSL. It also provides memory managment assistance.

We now have our weapon of choice, but we need to do some prep work first. We need to make sure our Rust functions can be called from Ruby.

Rust Prep

In order for Ruby to be able to call the Rust functions, we need to do three things:

  • Stop the compiler from mangling the function symbol
  • Make the function C ABI compatible
  • Return a value that Ruby understands

The compiler will mangle the function symbols to ensure uniqueness, but we want to be able to call the function by name. Our lingua franca will be C, as both Ruby and Rust ‘understand’ the C ABI. Finally, in Ruby all instances of the core classes (and beyond) (Array, Fixnum, Float etc) are represented by a VALUE pointer, which points to an instance of RObject, a specialised C structure. Rust has no idea about that, so we need to cross the bridge.

Here is what this looks like: The assert! macro here is unsafe, and is a bit of legacy from the original implementation. This also isn’t the most idiomatic Rust, but will do for illustration purposes.

1
2
3
4
5
6
7
8
9
10
11
#[no_mangle]
pub extern "C" fn rustsort(n: *const libc::int32_t, len: libc::size_t) -> RubyArray {
    let numbers = unsafe {
        assert!(!n.is_null());
        slice::from_raw_parts(n, len as usize)
    };
    let mut mutable_numbers = numbers.to_owned();
    quick_sort(&mut mutable_numbers, &is_less);

    RubyArray::from_vec(mutable_numbers)
}

So what’s going on here? First of all, we have the #[no_mangle] compiler directive, which instructs the compiler to not mangle the following function symbol. We then declare the function as a public external function, that is compatible with the C ABI. Finally, we return a structure that Ruby can understand (the details of which you can see in one of the repositories at the end). *const libc::int32_t declares that this function expects a pointer containing data that corresponds to the int32 type – we’re passing it an array of integers.

Ruby Prep

We now need to hook the Rust up to Ruby. Again, we need to do three things:

  • Allow Ruby to call the Rust function
  • Pass the Rust function the right datatype
  • Handle the returned data

We will set up our FFI to allow Ruby to call the Rust function, and use the ruby-ffi gem to handle our data types, along with the returned data.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
##
# Contains a link to the Rust library and
# a struct to aid in marshalling data across
module Rust
  ##
  # Give Rust library access to modules/classes
  # this module is included in
  def self.included(base)
    base.extend FFI::Library
    base.ffi_lib begin
      pre = Gem.win_platform? ? '' : 'lib'
      suffix = FFI::Platform::LIBSUFFIX
      dirname = File.dirname(__FILE__)
      target = '../../target/release/'
      "#{File.expand_path(target, dirname)}/#{pre}rustsort.#{suffix}"
    end
  end

  ##
  # Struct to handle marshalling data from Rust
  class RustArray < FFI::Struct
    layout :len,  :size_t,
           :data, :pointer

    def to_a
      self[:data].get_array_of_int(0, self[:len]).compact
    end
  end
end

##
# Implementation of Quicksort, but in Rust!
# Uses FFI to cross the boundaries
# @return [Array] the sorted array
module Rustsort
  include Rust
  ##
  # Attach a function that hooks into the Rust library
  attach_function :rust_sort,           # Name
                  :rustsort,            # Rust function
                  [:pointer, :size_t],  # Args
                  RustArray.by_value    # Return

  ##
  # Dup the array, create a pointer containing the array data
  # then pass the pointer over to Rust to let the magic happen
  def rustsort
    arr = dup
    buf = FFI::MemoryPointer.new :int32, arr.size
    buf.write_array_of_int32(arr)
    rust_sort(buf, arr.size).to_a
  end
end

The comments explain much of what’s going on, except the part where we compile our Rust library. cargo build --release will create a compiled dynamic library for us (if we specified it as a dylib crate), which we then link to using FFI::Library.

Wrapup

JJJ is happy – the library written in Rust is integrated into our Ruby code and he now has precious extra seconds to look for pictures of Spiderman. What have we achieved?

  • Wrote an implemention of quicksort in Rust and Ruby
  • Benchmarked them using benchmarks-ips
  • Used ruby-ffi to call Rust from Ruby.
  • We used the right tool, for the right job.

Examples

I’ve got a few examples of hooking into Rust with ruby-ffi, along with an implementation that uses the Rust crate ruru on my Github page. Look for sorting_algorithms, ffi_example and ruru_experiment.

There are also some interesting projects that are working on either using Rust as an extension in a Ruby gem, or working on integrating Ruby and Rust:


Ruby Logo © 2006, Yukihiro Matsumoto, CC BY-SA 2.5
Rust Logo © Mozilla, CC BY 4.0. Modified for use in the leader image