C++/Rubyで基数木をつかって高速なHTTPルーティングを実現する

はじめに

数年にわたり、PadrinoやGrapeといったWebアプリケーションフレームワークのルーティングを改善してきた自分が、今年の11月頃から、従来とは異なるアプローチでHTTPルーティングの高速化について検証したので、その結果について解説する。

なおこの記事では、その過程でC++で基数木を実装し、それを用いることにより、Rubyで高速なHTTPルーティングを実現した事例について、順を追って解説する。

tl;dr

• C++で基数木(Radix Tree)を表現するr2reeというライブラリを書いた。
• r2reeのRuby向けバインディングであるr2ree-rubyを書いた。
• r2ree-rubyを用いてRuby上でHTTPルーティングを行う pendragon-radixを書いた。
  • 多分、Rack準拠のルーティングライブラリでは最速。

結果、Sinatraなどで用いられる正規表現+線形探索と比較して最大25倍ほど高速化できた。

あらまし

この記事では、routeとrootを区別するため、基本的にrouteをルートと呼び、rootは根と呼ぶことにする。

基数木というデータ構造がある。
このデータ構造は、トライ木に非常によく似ているものの、トライ木が各ノードを単一の文字でラベル付けするところを、
文字の並びによってそのラベルを表現するデータ構造を持つことが特筆すべき性質として挙げられる。
文字の並びといっても実際には様々で、たとえばそれはIPアドレスを表現する数値でもよいし、あるいは文字列でもよいといった具合である。
IPルーティングを行うルーターなどでの採用事例が多いように思う。

この記事の根幹は、この基数木を用いたHTTPルーティングの高速化、ということになる。

パフォーマンス面での基数木の優位性

以下、wikipediaより引用

以下の比較では、キーの長さを k、格納している要素数を n としている。

衡2分探索木では、検索・挿入・削除には O(log n) の時間がかかるが、基数木では O(k) である。一般に k ≥ log n であるから、これは利点とは見なされないが、平衡2分探索木での比較は常に文字列の比較であり、最悪で O(k) の時間がかかる。特に長い接頭部が共通な文字列を多数格納していると遅くなる。一方、トライ木では比較は文字の比較で定数時間で済み、長さ m の文字列なら m 回の比較が必要となる。基数木は比較回数も少なく、走査するノード数も少ない。

ただし、基数木にはトライ木と同じ欠点がある。これらは、文字列や文字列に写像できるデータしか扱えない。それに対して平衡2分探索木は、順序関係のある任意のデータ型を扱える。これは例えば、大小比較だけが可能だが、シリアライズできないデータ型で問題となる。

ハッシュテーブルは一般に挿入・削除に O(1) の時間しかかからないとされているが、これはキーの操作を定数時間とみなしているためであって、キーの構造を考慮すると変わってくる。キーの長さが k なら、ハッシュテーブルでの挿入・削除には O(k) の時間がかかり、衝突が発生すると処理方式によってはさらに時間がかかる。基数木は最悪でも O(k) で挿入・削除できる。また、基数木では可能な辞書式順序の前後を取り出す操作もハッシュテーブルでは不可能である。

引用中にもある通りk ≥ log nであるため、どの用途においても基数木が平衡二分探索木よりも優位であるということにはならない。
しかしながら、今回はHTTPルーティング、しかもSinatraやGrape、RailsといったWebアプリケーション向けのルーティングを高速化することが目的であり、
それらの実装においてはしばしば、/archivesや/usersなどといった共通接頭辞を持つ複数個のルートが利用される。

したがって、HTTPルーティングにおける基数木の優位性については一定の期待が持てるということで、今回の取り組みに至った次第である。

それに、Golangで実装されたhttprouterは評判いいし…。

実装

実装といっても、「C++によるピュアな基数木の実装」、そして「それに対するRuby向けのバインディングの実装」、「そのバインディングを用いたHTTPルーティングの実装」の三つについて解説する必要がある。

今回の最終的な到達目標は、Ruby用 HTTPルーティングライブラリであるpendragonを高速化することであるため、そこに到達するまでの過程を追っていく。
pendragonについての詳細は後述。

C++で基数木を実装する

今回は高速化が主な目的のため、速度面での優位性という観点から、C++を用いて実装する。
Cでもよかったのだが、C++を最近仕事で使う必要があったため、勉強という意味も兼ねてC++を採用した。
実際のところ基数木の実装はgithub上に多く転がっているため、それらを参考に書き下すことはC++初学者の自分でもそんなに難しくはない。

すでにWeb上には基数木の実装についての解説などは大量に存在しているので、この項では基数木のデータ構造やデータの追加・探索についての考え方についてを簡単に解説するにとどめたい。

基数木のデータ構造

前述のように基数木は各ノードに文字の並びよってそのラベルを表現できる。
例えば、以下のようなルートが存在すると仮定する。

• /
• /foo
• /bar
• /baz
• /boo

これを基数木で表現すると、以下の図のように表せる。

この図では、入力されたパスで根(/)から基数木を辿っていき、辿った先が白色のノードであれば探索は成功、黒色であれば、そのノードはルート群の各文字列の終端ではないため、失敗ということになる。

さらに今回の基数木には、HTTPルーティングをアプリケーション側で制御する際によく用いられる*と:をメタ文字として、特別な意味をもつラベルとして扱うことにする。

*

*は*以降の全ての文字にマッチする。
たとえば、/foo/*は/foo/hogeや/foo/fuga/fugoにマッチする。

:id

:idは、:id以降の/以外の全ての文字にマッチする。
たとえば、/foo/:idは/foo/1234や/foo/hogeにはマッチするが、/foo/bar/bazにはマッチしない。

これらの前提条件を踏まえ、ルートの追加と検索について解説する。

ルートの追加

基数木はその特性上、ルートを追加するごとにすでにあるデータ構造を変更する必要が生じる。

たとえば、以下の二つのルートをもつ基数木があったとする。

• /foo
• /bar

この二つのルートをもつ基数木は以下のように表せる。

この基数木に対し、/bazというルートを追加すると、barとラベル付けられたノードはbar・bazともに共通しているbarという共通部分のみを辺として新たに作成し、r・zという新たなノードを派生させる。以下の図の通りである。

ルートの検索

前項のようにして作成したデータについて、入力されたパスから一致するかどうかを探索する。
*や:などが含まれると、説明にあるようなことを考慮した探索に切り替えるが、それ以外は基本的に子ノードに対する二分探索を行っている。

後述のr2ree-rubyのために、一致するノードが見つかったときにはそのルートの番号を返すようにしている。
ルート番号というのはそのノードを終端とするルートが追加された順序のことで、3番目に追加されたルートについては2、といった値を返す。
基本的にString#indexのような挙動と思えば良いかと思う。

ルートの削除

目的がRuby上でのルーティング高速化を狙うことであり、現状のユースケースだとルートを削除する必要はなかったので実装していない。

成果物

以上の内容を踏まえてC++を用いて実装し、一応のライブラリの体裁を整えたものが以下のリンクにあるr2reeである。

namusyaka/r2ree

一応、Travis ci上でgoogletestを用いてテストが走るようになっている。
C++でライブラリを作ってCMakefile.txtを書いてci上でビルド・テストを走らせる、という経験ができただけでも勉強になったと思う。

C++で実装した基数木のRuby向けバインディングを実装する

C++で開発したr2reeを次はRubyから呼び出せるようにしたい。
最小の機能だけで十分のため、r2ree全ての機能を網羅したバインディング、というよりかは自分自身が必要なものだけを取り揃えたい。

r2ree-ruby

追加系のメソッドがあるわけではなく、constructorに必要なルートを全部渡してやることで動くという簡易仕様である。

ソースコードも非常に小さく、実装は以下の数十行だけである。

#include "libr2ree.hh" // r2reeをvendoringしたもの
#include "string"
#include "iostream"
#include "ruby.h"

#define R2REE_VERSION "0.0.1"

using std::ignore;
using std::tie;

static VALUE rb_r2ree;

static void r2ree_free(r2ree::radix_tree *tree);
static r2ree::radix_tree *get_r2ree_radix_tree(VALUE klass);
static r2ree::parse_result match(VALUE klass, const char *path);
static VALUE r2ree_size(VALUE self); 
static VALUE r2ree_s_new(int argc, VALUE *argv, VALUE self); 
static VALUE r2ree_find(int argc, VALUE *argv, VALUE self); 
static VALUE r2ree_exist(int argc, VALUE *argv, VALUE self); 
static VALUE r2ree_size(VALUE self); 

static void r2ree_free(r2ree::radix_tree *tree) {
  tree->~radix_tree();
  ruby_xfree(tree);
}

static r2ree::radix_tree *get_r2ree_radix_tree(VALUE klass) {
  r2ree::radix_tree *tree;
  return Data_Get_Struct(klass, r2ree::radix_tree, tree);
}

static r2ree::parse_result match(VALUE klass, const char *path) {
  r2ree::radix_tree *tree = get_r2ree_radix_tree(klass);
  return tree->get(path);
}

static VALUE r2ree_s_new(int argc, VALUE *argv, VALUE self) {
  int i = 0;
  VALUE paths, path;
  r2ree::radix_tree *tree = new r2ree::radix_tree();
  rb_scan_args(argc, argv, "1", &paths);

  if (TYPE(paths) == T_ARRAY) {
    while (!NIL_P(path = rb_ary_entry(paths, i))) {
      if (TYPE(path) != T_STRING)
        rb_raise(rb_eArgError, "wrong argument type, expected String");
      tree->insert(StringValuePtr(path));
      ++i;
    }
  }

  return Data_Wrap_Struct(self, NULL, r2ree_free, tree);
};

static VALUE r2ree_size(VALUE self) {
  r2ree::radix_tree *tree = get_r2ree_radix_tree(self);
  int cid = tree->cid;
  return INT2NUM(cid >= 0 ? cid + 1 : 0);
};

static VALUE r2ree_exist(int argc, VALUE *argv, VALUE self) {
  VALUE path;
  bool existence, leaf;

  rb_scan_args(argc, argv, "1", &path);

  if (TYPE(path) == T_STRING) {
    tie(existence, ignore, ignore, leaf) = match(self, StringValuePtr(path));
    return (existence && leaf) ? Qtrue : Qfalse;
  } else {
    return Qfalse;
  }
};

static VALUE r2ree_find(int argc, VALUE *argv, VALUE self) {
  int cid;
  VALUE path;
  bool existence, leaf;

  rb_scan_args(argc, argv, "1", &path);

  if (TYPE(path) == T_STRING) {
    tie(existence, cid, ignore, leaf) = match(self, StringValuePtr(path));
    return (existence && leaf) ? INT2NUM(cid) : INT2NUM(-1);
  } else {
    rb_raise(rb_eArgError, "wrong argument type, expected String");
  }
};

extern "C" void Init_r2ree() {
  VALUE tmp;

  rb_r2ree = rb_define_class("R2ree", rb_cObject);

  tmp = rb_str_new2(R2REE_VERSION);
  rb_obj_freeze(tmp);
  rb_const_set(rb_r2ree, rb_intern("VERSION"), tmp);

  rb_define_singleton_method(rb_r2ree, "new",        RUBY_METHOD_FUNC(r2ree_s_new), -1);
  rb_define_method(rb_r2ree,           "exist?",     RUBY_METHOD_FUNC(r2ree_exist), -1);
  rb_define_method(rb_r2ree,           "find",       RUBY_METHOD_FUNC(r2ree_find),  -1);
  rb_define_method(rb_r2ree,           "size",       RUBY_METHOD_FUNC(r2ree_size),   0);
  rb_define_alias(rb_r2ree, "length", "size");
};

r2ree-ruby

使い方は以下のコードの通り。

require 'r2ree'

tree = R2ree.new(['/foo', '/bar', '/baz'])
tree.size #=> 3
tree.find('/foo') #=> 0
tree.find('/bar') #=> 1
tree.find('/baz') #=> 2
tree.find('/boo') #=> -1

ベンチマーク

ここで、Sinatra-2.0から正式に組み込まれたMustermannを比較対象として、単純なRoute探索についてのベンチマークをとってみる。
Mustermannは/foo/:idや/hoge/*などのルーティングによく用いられるパターン文字列を渡すと、正規表現にコンパイルしてくれるライブラリであり、つまるところ正規表現によるマッチング+線形探索とr2reeの比較検証、ということになる。

ベンチマークをとる方法としては、ruby標準添付のbenchmarkやbenchmark-ipsがよく用いられる選択肢かと思う。
今回は同じようなコードを何度も書く羽目になったので、シンプルに書けるようにするためのモジュールを以下のようにして書いてみた。

require 'benchmark'
require 'benchmark/ips'

module BenchmarkSpec
  def describe(target, &block)
    Describer.new(&block).run
  end
  alias_method :context, :describe

  class Report
    attr_reader :desc

    def initialize(desc, &block)
      @desc = desc
      instance_eval(&block)
    end

    def let(key, &block)
      unless respond_to?(key)
        self.class.class_eval do
          define_method(key) { instance_variable_get(:"@#{key}") }
        end
      end
      instance_variable_set(:"@#{key}", block.call)
    end

    def setup(&block)
      @setup ||= block
    end

    def measure(&block)
      @measure ||= block
    end
  end

  class Describer
    attr_accessor :benchmarker

    def initialize(&context)
      self.benchmarker = -> (&block) { Benchmark.bm(&block) }
      instance_eval(&context)
    end

    def run
      benchmarker.call do |x|
        @startup.call(x) if @startup
        reports.each do |report|
          report.setup.call if report.setup
          _measure = report.measure || measure
          x.report(report.desc) do
            report.instance_eval(&_measure)
          end
        end
        @teardown.call(x) if @teardown
      end
    end

    def startup(&block)
      @startup = block
    end

    def teardown(&block)
      @teardown = block
    end

    def measure(&block)
      @measure ||= block
    end

    def report(desc, &block)
      reports << Report.new(desc, &block)
    end

    def reports
      @reports ||= []
    end
  end
end

上記ベンチマークスクリプトを用いて、まずは以下のようにシンプルなベンチマークスクリプトを実装した。

require_relative 'benchmark_spec'
require 'r2ree'

include BenchmarkSpec

describe '/0 .. /999' do
  self.benchmarker = -> (&block) { Benchmark.ips(&block) }
  startup { |x| x.config time: 5, warmup: 2 }
  teardown { |x| x.compare! }

  paths = 1000.times.to_a.map { |n| "/#{n}" }

  report 'mustermann' do
    let(:routes) do
      paths.each_with_object([]) { |path, _routes| _routes << Mustermann.new(path) }
    end

    measure do
      paths.each do |path|
        routes.find { |pattern| pattern === path }
      end
    end
  end

  report 'string' do
    let(:routes) do
      paths.each_with_object([]) { |path, _routes| _routes << path }
    end

    measure do
      paths.each do |path|
        routes.find { |pattern| pattern == path }
      end
    end
  end

  report 'r2ree' do
    let(:routes) { R2ree.new(paths) }
    measure { paths.each { |path| routes.find(path) } }
  end
end

それぞれ、正規表現・文字列・r2reeの順でベンチマークをとっている。
特にこのケースだと、/0から/999までの正規表現不要なルートしか用いないため、文字列も比較対象として加えている。
実行結果は以下の通りである。

Warming up --------------------------------------
          mustermann     1.000  i/100ms
              string     1.000  i/100ms
               r2ree   126.000  i/100ms
Calculating -------------------------------------
          mustermann      2.592  (± 0.0%) i/s -     13.000  in   5.051368s
              string     25.160  (± 7.9%) i/s -    125.000  in   5.027413s
               r2ree      1.382k (± 4.3%) i/s -      6.930k in   5.024613s

Comparison:
               r2ree:     1381.8 i/s
              string:       25.2 i/s - 54.92x  slower
          mustermann:        2.6 i/s - 533.18x  slower

結果として、文字列によるマッチングと比較して54倍、正規表現によるマッチングと比較して533倍高速に動作していることがわかる。

ただし、上記のベンチマークは1000個のRouteが存在しているケースの話であり、現実ではウェブアプリケーションの実装でその数のRouteが存在することはほとんどないと言っていい。そこで、より現実のパターンに則ったベンチマークを以下のスクリプトでとってみた。

require_relative 'benchmark_spec'
require 'r2ree'
require 'mustermann'

include BenchmarkSpec

describe '/0 .. /999' do
  self.benchmarker = -> (&block) { Benchmark.ips(&block) }
  startup { |x| x.config time: 10, warmup: 2 }
  teardown { |x| x.compare! }

  paths = %w[
    /
    /users/:id
    /articles/:id
    /articles/:id/comments
    /articles/:id/comments/:comment_id
    /search/:keyword
    /support
  ]

  arguments = %w[
    /
    /users/1234
    /articles/1234/9
    /articles/5678/comments
    /articles/9999/comments/1
    /search
    /search/hello
    /search/boooooo
    /support
  ]

  report 'mustermann' do
    let(:routes) do
      paths.each_with_object([]) { |path, _routes| _routes << Mustermann.new(path) }
    end

    measure do
      arguments.each do |argument|
        routes.find { |pattern| pattern === argument }
      end
    end
  end

  report 'r2ree' do
    let(:routes) { R2ree.new(paths) }
    measure { arguments.each { |argument| routes.find(argument) } }
  end
end

今回は単純な文字列による比較は意味をなさないため、正規表現とr2reeの比較となっている。
結果は以下の通りである。

Warming up --------------------------------------
          mustermann     2.134k i/100ms
               r2ree    12.617k i/100ms
Calculating -------------------------------------
          mustermann     22.472k (± 4.2%) i/s -    226.204k in  10.084881s
               r2ree    122.344k (±18.8%) i/s -      1.148M in  10.037832s

Comparison:
               r2ree:   122344.2 i/s
          mustermann:    22471.8 i/s - 5.44x  slower

登録されているRouteは7個だが、それでも5倍ほどの高速化が見込めるという結果となった。
実際、追加するRouteの数を増やしていけばいくほど、r2reeの方が優位であることを示す結果となっていった。

全てのケースにおいてそうであるとは言えないものの、少なくともウェブアプリケーションにおけるルーティングでは、r2reeは既存のものと比較しても非常に高速に動作すると言えそうだ。

Rubyで基数木を用いたHTTP ルーティングを実装する

前項で紹介したr2reeを用い、次は実際のHTTPルーターを作成する。

Pendragon gemがその役目を終えて生まれ変わった話

r2reeを用いたHTTPルーターを作成する前に、Ruby製HTTPルーティングライブラリであるpendragonについて、簡単に説明したい。

このgemはもともと、Padrinoのルーティング高速化のために開発されたものであり、つい最近まではPadrinoのルーティング高速化のためのプラグインとしての役割も果たしていた。
pendragonはそれ単体でも、Rackアプリケーションに準拠する形でルーターを開発できる機能を備えていたが、もっぱらPadrinoプラグインとして使われることの方が多かったように思う。
しかしながら、このpendragonのコンセプトはすでにPadrinoのmasterにmerge済みのため、このgemはお役御免となっていた。

そこで、v1.0.0というメジャーバージョンアップを契機に、ルーティングに関わる設計やデザインを一から作り直したものが、現在のpendragonである。

今回のr2reeを用いたHTTPルーターは、この新しく生まれ変わったpendragonをベースに開発した。

HTTPルーター ToolkitとしてのPendragon

現在のpendragonは、それ単体をルーターとして捉えるよりも、Rack準拠のHTTPルーターを開発するためのToolkitと捉える方が正しい。
Pendragon::Routerを継承したサブクラスにおいて、自分のニーズにあったルーティングアルゴリズムを組み込んで、Rack準拠のルーターが開発できる、というイメージである。

pendragon標準添付のルーターは、以下のように実装されている。

# Pendragon::Linear
require 'pendragon/router'

module Pendragon
  class Linear < Router
    register :linear

    on(:call) { |env| rotation(env) { |route| route.exec(env) } }
  end
end

# Pendragon::Realism
require 'pendragon/router'

module Pendragon
  class Realism < Router
    register :realism

    on :call do |env|
      identity(env) || rotation(env) { |route| route.exec(env) }
    end

    on :compile do |method, routes|
      patterns = routes.map.with_index do |route, index|
        route.index  = index
        route.regexp = /(?<_#{index}>#{route.pattern.to_regexp})/
      end
      omap[method] = Regexp.union(patterns)
    end

    private

    # @!visibility private
    def omap
      @omap ||= Hash.new { |hash, key| hash[key] = // }
    end

    # @!visibility private
    def match?(input, method)
      current_regexp = omap[method]
      return unless current_regexp.match(input)
      last_match = Regexp.last_match
      map[method].detect { |route| last_match["_#{route.index}"] }
    end

    # @!visibility private
    def identity(env, route = nil)
      with_transaction(env) do |input, method|
        route = match?(input, method)
        route.exec(env) if route
      end
    end

    # @!visibility private
    def with_transaction(env)
      input, method = extract(env)
      response = yield(input, method)
      response && !(cascade = cascade?(response)) ? response : nil
    end
  end
end

:callにはリクエストごとに実行される処理を、:compileには初回起動時に対象となるRoute群をコンパイルするなどの処理を設定する。
linearについてはそもそもコンパイルする必要がないため、:compileは設定していない。
:callの定義としては、Rackにおけるenvを受け取り、Rackレスポンスフォーマットに準拠したレスポンスを返却していれば何をしていても良いという制約を設けてある。

r2ree-rubyをpendragonに組み込む

前項のルールに則ってr2reeをpendragonに組み込む。
実装は単純で、以下のように実装できる。

require 'r2ree'

module Pendragon
  class Radix < Router
    register :radix

    on(:compile) { |m, rs| tree[m] = R2ree.new(rs.map(&:path)) }
    on(:call) do |env|
      input, method = extract(env)
      return unless current = tree[method]
      if (pos = current.find(input)) && pos >= 0
        map[method][pos].exec(env)
      end
    end

    def tree
      @tree ||= {}
    end
  end
end

初回起動時に、登録されているRoute群に対し、リクエストメソッドごとに基数木(R2ree)を作成する。
リクエスト時には、リクエストメソッドから対象となる基数木を取り出して、R2ree#findを実行し、Routeを一意に特定した上で、対象となるRouteに紐付いたアプリケーションを実行する、という流れである。

ちなみにこの実装は、pendragon-radixとしてgithub上で公開している。

ベンチマーク

この記事の最終目標であるpendragon-radixができあがったので、sinatraやgrapeなどと比較してベンチマークをとってみる。

シンプルなベンチマーク

まずはr2ree-rubyで行ったような、シンプルなベンチマークから検証する。
ベンチマークに使うスクリプトはr2ree-rubyで用いたものと同じ、BenchmarkSpecとbenchmark-ipsを用いた。

include BenchmarkSpec

describe '/0 .. /999' do
  self.benchmarker = -> (&block) { Benchmark.ips(&block) }

  startup { |x| x.config time: 5, warmup: 2 }
  teardown { |x| x.compare! }

  paths = 1000.times.to_a.map { |n| "/#{n}" }
  measure do
    paths.each do |path|
      env = Rack::MockRequest.env_for(path)
      router.call(env)
    end
  end

  report 'sinatra' do
    let(:router) do
      Class.new Sinatra::Base do
        paths.each { |path| get(path) { path } }
      end
    end
  end

  report 'grape' do
    let(:router) do
      grape = Class.new Grape::API do
        paths.each { |path| get(path) { path } }
      end
      grape.new
    end
  end

  report 'pendragon-radix' do
    let(:router) do
      Pendragon[:radix].new do
        paths.each { |path| get(path) { [200, {}, [path]] } }
      end
    end
  end
end

結果は以下の通りである。

Warming up --------------------------------------
             sinatra     1.000  i/100ms
               grape     1.000  i/100ms
     pendragon-radix     2.000  i/100ms
Calculating -------------------------------------
             sinatra      0.914  (± 0.0%) i/s -      5.000  in   6.411146s
               grape      1.231  (± 0.0%) i/s -      7.000  in   5.853178s
     pendragon-radix     23.721  (±16.9%) i/s -    116.000  in   5.066540s

Comparison:
     pendragon-radix:       23.7 i/s
               grape:        1.2 i/s - 19.27x  slower
             sinatra:        0.9 i/s - 25.95x  slower

シンプルなRouteを1000個、それぞれ持たせるケースでは、sinatraと比較して26倍、grapeと比較して20倍ほど高速に動作することがわかった。

実際のルーティングに近い状態でのベンチマーク

include BenchmarkSpec

paths = []

alpha = [(?a..?z), (?A..?Z), (?0..?9)].map(&:to_a).flatten
20.times do
  namespace = ?/ + alpha.shuffle.sample(5).join
  paths << namespace
  paths << "#{namespace}/:id"
  paths << "#{namespace}/:id/comments"
end

describe paths.join(', ') do

  self.benchmarker = -> (&block) { Benchmark.ips(&block) }

  startup { |x| x.config time: 5, warmup: 2 }
  teardown { |x| x.compare! }
  arguments = paths.map { |path| path.gsub(/(\:[^\/]+)/, "1234") }
  measure do
    arguments.each do |argument|
      env = Rack::MockRequest.env_for(argument)
      router.call(env)
    end
  end

  report 'sinatra' do
    let(:router) do
      Class.new Sinatra::Base do
        paths.each { |path| get(path) { path } }
      end
    end
  end

  report 'grape' do
    let(:router) do
      grape = Class.new Grape::API do
        paths.each { |path| get(path) { path } }
      end
      grape.new
    end
  end

  report 'pendragon-radix' do
    let(:router) do
      Pendragon[:radix].new do
        paths.each { |path| get(path) { [200, {}, [path]] } }
      end
    end
  end
end

結果は以下の通りである。

Warming up --------------------------------------
             sinatra     2.000  i/100ms
               grape     6.000  i/100ms
     pendragon-radix    31.000  i/100ms
Calculating -------------------------------------
             sinatra     45.175  (±17.7%) i/s -    212.000  in   5.001429s
               grape     67.748  (± 5.9%) i/s -    342.000  in   5.066237s
     pendragon-radix    394.446  (± 4.3%) i/s -      1.984k in   5.039347s

Comparison:
     pendragon-radix:      394.4 i/s
               grape:       67.7 i/s - 5.82x  slower
             sinatra:       45.2 i/s - 8.73x  slower

この結果から、sinatraよりも9倍、grapeよりも6倍高速に動作していることがわかる。
実際にはWebアプリケーションでどういったルーティングが行われるかによって、結果は変わってくるが、いずれにしても、既存の正規表現・線形探索をベースにした処理よりも大きく高速化できることは間違いないだろう。

また、pendragon-radixはまだ完全にチューニングしきれているわけではなく、Sinatra同様にパスの中に含まれる名前付きキャプチャをhashとして扱うための計算処理には、依然としてMustermannを使用している。
この部分をr2reeを用いた処理に置き換えることで、さらなる高速化が見込めるため、今後の課題としたい。

おわりに

一般的にWebアプリケーションにおけるルーティングは、内部的には正規表現を用いて処理が行なわれていることが多いものの、今回のケースのように適切にアルゴリズムを選択することで高速化を図ることができた。
おそらくこのpendragon-radixは、Rack準拠のルーティングアプリケーションとしては現時点で最速だと思われる。
また、実際にはWebアプリケーションのパフォーマンス向上を考える際に、ルーティングがボトルネックとなるケースは非常に少ないが、Webアプリケーションフレームワークを開発する際には、より高速な実装を求めるケースがままあるため、今回のような取り組みを実施した次第。

この記事がWebアプリケーションおよびそのフレームワーク開発者の役に立てば幸いである。