ようへいの日々精進XP

よかろうもん

2018 年 11 月 30 日 (金)

ジョギング

  • 山王公園往復
  • 左足首周りの痛みが少し和らいだ
  • 超スローペース

日課

  • お休み
  • そろそろ, 再開する... まじで, まじで..., まじで..., まじで...まじで...まじで...

Lambda のランタイムとして Ruby が...

最高.

2018 年 11 月 29 日 (木)

ジョギング

  • 引き続き, 左足踵に痛みがあったのでお休み
  • ほんと, 休養だと思ってしっかりと直すことにする
  • この手の障害は走らないのが一番っぽい

日課

  • お休み
  • そろそろ, 再開する... まじで, まじで..., まじで..., まじで...まじで...

久しぶりに JAWS-UG 福岡もくもく会

青柳さんと二人. 二人という最小人数ではあったが, 色々と話が出来て良かった.

夕飯

美人居酒屋.

アルゴリズムとプログラミング 「第 8 章 配列の応用」の予習とまとめ

これは

放送大学教養学部の「アルゴリズムとプログラミング」という授業で使われる「アルゴリズムとプログラミング」という教材書籍を自分なりにまとめたものです.

序章

  • スタックとキューという基本的なデータ構造とその操作について学習する
  • 配列を利用したスタックとキューの実装例について学ぶ
  • コンウェイライフゲームについても考察する

1. スタック

スタックについて

  • スタック (stack) とは最も基本的なデータ構造の一つである
  • スタックには「積み重ねる」という意味がある

尚, スタックでは積み重なったデータの 1 つのデータしか読み取ることは出来ず, 一度に読み取ることが出来るデータは, 最後にスタックに積まれた (挿入された) データだけである.

スタックの構造

  • 最初に積まれたデータは, スタックの底 (bottom: ボトム)
  • 最後に積まれたデータは, スタックの頂上 (top: トップ)

このようなデータ構造は LIFO (Last In, First Out: 後出し先出し: ライフォ) と呼ばれ, 後入れ, 先出し の構造で保存される.

スタックの操作

以下のような基本操作がある.

  • プッシュ (push): データをスタックの頂上に積む操作
  • ポップ (pop): データをスタックの頂上から取り出す操作
  • ピーク (peek): スタック頂上のデータを削除せずに, データ値を見る (覗く) 場合に使われる, トップ (top) と呼ぶこともある
  • スワップ (swap): スタック頂上にあるデータと, その次にあるデータを入れ替える (交換) 操作
  • ダップ (dup): スタック頂上にあるデータを複製 (duplicate) し, 複製したデータを頂上にプッシュする

スタックの実装例

以下のコードは, 配列を使ってスタック構造を実装したもの. こちらより引用.

/* code: ex8-1.c   (v1.16.00) */
#include<stdio.h>
#include<stdlib.h>
 
#define MAX 128
#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2
 
/* ------------------------------------------- */
void stack_init (int *top)
{
  *top = 0;
}
 
/* ------------------------------------------- */
void display (int stack[], int top)
{
  int i;
  printf ("STACK(%d): ", top);
  for (i = 0; i < top; i++) {
    printf ("%d ", stack[i]);
  }
  printf ("\n");
}
 
/* ------------------------------------------- */
int push (int stack[], int *top, int data)
{
  if (*top >= MAX) {
    /* stack overflow */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}
 
/* ------------------------------------------- */
int pop (int stack[], int *top, int *data)
{
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}
 
/* ------------------------------------------- */
int main ()
{
  int stack[MAX];
  int top, data;
 
  stack_init (&top);
  data = 300;
  printf ("push: %d\n", data);
  push (stack, &top, data);
  data = 400;
  printf ("push: %d\n", data);
  push (stack, &top, data);
  data = 500;
  printf ("push: %d\n", data);
  push (stack, &top, data);
  display (stack, top);
  pop (stack, &top, &data);
  printf ("pop:  %d\n", data);
  pop (stack, &top, &data);
  printf ("pop:  %d\n", data);
  pop (stack, &top, &data);
  printf ("pop:  %d\n", data);
  return 0;
}

これをコンパイルして実行してみる.

root@0be431eebb77:/work# gcc ex8-1.c -g3 -o ex8-1
root@0be431eebb77:/work# ./ex8-1
push: 300
push: 400
push: 500
STACK(3): 300 400 500
pop:  500
pop:  400
pop:  300

2. キュー

キューについて

  • キュー (queue: 待ち行列), 「列に並んで待つこと」を意味する
  • スタックと類似した構造を持っている
  • 最初に挿入したデータが最初に取り出される構造

キューの構造

  • 最初のデータは, キューの先頭 (front)
  • 最後のデータは, キューの末尾 (rear)

このようなデータ構造は FIFO (First In, First Out: 先出し先出し: フィフォ) と呼ばれ, 先入れ, 先出し の構造で保存される.

キューの操作

以下のような基本操作がある.

  • エンキュー (enqueue): データをキューの末尾に入れる
  • デキュー (dequeue): キューの先頭からデータを取り出す
  • ピーク (peek: 覗く): キューの先頭データを削除せず, データ値を見る場合に使われる, front と呼ぶこともある

キューの実装例

以下のコードは, 配列を使ってキュー構造を実装したもの. こちらより引用.

/* code: ex8-2.c   (v1.16.00) */
#include<stdio.h>
#include<stdlib.h>
 
#define MAX 128
#define ENQUEUE_SUCCESS     1
#define ENQUEUE_FAILURE    -1
#define DEQUEUE_SUCCESS     2
#define DEQUEUE_FAILURE    -2
 
/* ------------------------------------------- */
void queue_init (int *front, int *rear)
{
  *front = -1;
  *rear = -1;
}
 
/* ------------------------------------------- */
int enqueue (int q[], int *rear, int data)
{
  if (*rear < MAX - 1) {
    *rear = *rear + 1;
    q[*rear] = data;
    return ENQUEUE_SUCCESS;
  }
  else {
    return ENQUEUE_FAILURE;
  }
}
 
/* ------------------------------------------- */
int dequeue (int q[], int *front, int rear, int *data)
{
  if (*front == rear) {
    return DEQUEUE_FAILURE;
  }
  *front = *front + 1;
  *data = q[*front];
  return DEQUEUE_SUCCESS;
}
 
/* ------------------------------------------- */
int main ()
{
  int queue[MAX];
  int front, rear, data;
  int stat;
 
  queue_init (&front, &rear);
  enqueue (queue, &rear, 100);
  enqueue (queue, &rear, 200);
  enqueue (queue, &rear, 300);
  enqueue (queue, &rear, 400);
  enqueue (queue, &rear, 500);
  while (rear - front) {
    stat = dequeue (queue, &front, rear, &data);
    if (stat == DEQUEUE_SUCCESS) {
      printf ("%d\n", data);
    }
    else {
      printf ("QUEUE is empty\n");
    }
  }
  return 0;
}

これをコンパイルして実行してみる.

root@0be431eebb77:/work# gcc ex8-2.c -g3 -o ex8-2
root@0be431eebb77:/work# ./ex8-2
100
200
300
400
500

エンキューとデキューの操作によっては, 先頭と末尾の位置関係から大きな配列が必要になってしまうことがある為, 配列の先頭と末尾が連続的に接続した循環構造として扱う, リングバッファ (ring buffer 又は, circular buffer: 環状バッファ) と呼ばれる構造が一般的に使われることが多い.

3. ライフゲーム

ライブゲームとは

ライフゲームの規則

  • 初期のセルの配置は第一世代と考えることが出来る
  • 第二世代目の配置は, セルの近傍にあるセルの状態と規則に基づき決定される
  • 規則は全てのセルに対して同時に実行される

以下, 標準的な規則.

  • 生存セルに隣接する生存セルが 2 個以下の場合, 次の世代で, セルは死滅 (die of loneliness) する (セル数: 0 〜 1)
  • 生存セルに隣接する生存セルが 3 個以上の場合, 次の世代ではセルは死滅 (die of overcrowding) する (セル数: 4 〜 8)
  • 生存セルに隣接する生存セルが 2 個, 又は, 3 個である場合, 次の世代でもセルは生存 (survive to next generation) する (セル数: 2 〜 3)
  • 死んだセルに隣接する生存セルが 3 個である場合, 次の世代でセルが誕生 (birth) する (セル数: 3)

セルの配置によって, 世代ごとにセルのパターンには様々な変化が起きる.

ライフゲームの実装例

こちらより引用.

/* code: ex8-3.c   (v1.16.00) */
#include <stdio.h>
#include <stdlib.h>
#define WIDTH  40
#define HEIGHT 20
 
/* ------------------------------------------- */
void cell_evolve (int array[HEIGHT][WIDTH])
{
  int array_new[HEIGHT][WIDTH];
  int x, y, n, x_width, y_height;
 
  for (y = 0; y < HEIGHT; y++) {
    for (x = 0; x < WIDTH; x++) {
      n = 0;
      for (y_height = y - 1; y_height <= y + 1; y_height++) {
    for (x_width = x - 1; x_width <= x + 1; x_width++) {
      if (array[(y_height + HEIGHT) % HEIGHT][(x_width + WIDTH) % WIDTH]) {
        n++;
      }
    }
      }
      if (array[y][x]) {
    n--;
      }
      array_new[y][x] = (n == 3 || (n == 2 && array[y][x]));
    }
  }
 
  for (y = 0; y < HEIGHT; y++) {
    for (x = 0; x < WIDTH; x++) {
      array[y][x] = array_new[y][x];
    }
  }
}
 
/* ------------------------------------------- */
void cell_first_generation (int array[HEIGHT][WIDTH])
{
  int x, y, r;
  for (x = 0; x < WIDTH; x++) {
    for (y = 0; y < HEIGHT; y++) {
      r = RAND_MAX / 8;
      if (rand () < r) {
    array[y][x] = 1;
      }
      else {
    array[y][x] = 0;
      }
    }
  }
}
 
/* ------------------------------------------- */
void cell_print (int array[HEIGHT][WIDTH], int generation)
{
  int x, y;
  printf ("[Generation: %05d]\n", generation);
  for (y = 0; y < HEIGHT; y++) {
    for (x = 0; x < WIDTH; x++) {
      if (array[y][x] == 1) {
    printf ("*");
      }
      else {
    printf (".");
      }
    }
    printf ("\n");
  }
  printf ("\n");
  fflush (stdout);
}
 
/* ------------------------------------------- */
int main ()
{
  int i;
  int array[HEIGHT][WIDTH];
  cell_first_generation (array);
  i = 0;
  while (i < 100) {
    cell_print (array, i);
    cell_evolve (array);
    i++;
  }
  return 0;
}

これをコンパイルして実行する.

root@0be431eebb77:/work# gcc ex8-3.c -g3 -o ex8-3


[Generation: 00000]
.*....**...........**.............*...*.
..............*..*......................
.......**........*..........*..*........
.................................*.....*
........................*..............*
.........*...*..*......**..*.....*......
...............................*..*.....
.*.........**....*.*...............*....
..*................*...........*...*...*
........*.*..*.......*..........**......
.............**............**........**.
..**....*.............*.....*....*....*.
.......**.............................*.
..................*........*.......**...
.........*.........*....................
.......*...*.......*..........*...*....*
..*....*............*..............*....
..*...............*.*..*................
..........*..........*.*................
..*...................................*.

...

[Generation: 00099]
............*..*..*.....................
...........**.**.*.*....................
...........**....*.*....................
..............*****.....................
.......*****..**.......**...............
......*.**.............**...............
......*..****.....................**....
.......**.*..*....................**....
.........*.**...........................
.........*.**...........................
..........*................**...........
...........................**...........
........................................
................**......................
................**......................
........................................
........................................
...................*....................
..................**....................
................**.*....................

ライフゲームをコンピュータプログラムといて実装するには, 格子状に分割されたセル空間で各セルの状態を保存する必要がある. セル空間の広さを限定すれば, 2 次元配列を利用すれば, 比較的容易に実装が可能である. 上記のコードでは, セルオートマトンはセルの状態は同時に更新される同期性の特徴がある為, 2 つの配列 (arrayarray_new) が必要である点に注意する.

演習問題

問 8.1

スタックの重要な操作を 2 つ答えなさい.

  • プッシュ (push): データをスタックの頂上に積む操作
  • ポップ (pop): データをスタックの頂上から取り出す操作

問 8.2

キューの重要な操作を 2 つ答えなさい.

  • エンキュー (enqueue): データをキューの末尾に入れる
  • デキュー (dequeue): キューの先頭からデータを取り出す

問 8.3

スタックに, 5 つのデータ 30, 20, 40, 50, 10 を順番にプッシュ (push) すると, スタック頂上のデータは 10 となる. このスタックから, ポップ (pop) を 3 回行うと, スタック頂上にあるデータは何か答えなさい.

これは, C で書けないので Ruby で解いてみたのが以下.

$ irb
irb(main):001:0> a = [30, 20, 40, 50, 10]
=> [30, 20, 40, 50, 10]
irb(main):002:0> a.pop
=> 10
irb(main):003:0> a.pop
=> 50
irb(main):004:0> a.pop
=> 40
irb(main):005:0> p a
[30, 20]
=> [30, 20]

スタックの頂上 (配列の最後尾) にあるデータは 20 になる. 尚, Ruby の pop メソッドは配列の末尾の要素を削除して, その要素を返す.

問 8.4

キューのデータ構造では, 最初に挿入したデータが, 最初に取り出される構造になる. 空のキューに 5 つのデータ 380, 370, 390, 350, 360 を順番にエンキューすると, キューの先頭データは 380, キューの末尾データは 360 となる. このキューからデキューを 3 回行うと, キューの先頭にあるデータは何か答えなさい.

とりあえず, これも Ruby で解いてみた.

irb(main):011:0> b = [380, 370, 390, 350, 360]
=> [380, 370, 390, 350, 360]
irb(main):012:0> b.shift
=> 380
irb(main):013:0> b.shift
=> 370
irb(main):014:0> b.shift
=> 390
irb(main):015:0> p b
[350, 360]
=> [350, 360]

配列 (キュー) の先頭は 350 となる. Ruby の shift メソッドは配列の先頭の要素を削除して, その要素を返す.

問 8.5

リングバッファによるキューの実装を考えなさい. リングバッファでは, 配列の添字をバッファの大きさで割って剰余を取る計算が使われる. これによって, 計算上, 直線バッファの両端がつながり円環状になる.

コードはこちらを参照. 実際に実行してみると, 以下のような結果となる.

root@0be431eebb77:/work# gcc q8-5.c -g3 -o q8-5
root@0be431eebb77:/work# ./q8-5
100
200
300
400
500

データのエンキュー時に, 変数 rear と配列の最大要素数のモジュロ演算を行い, その値を配列の添字にすることによって, リングバッファを実現している.

// 以下, コードより抜粋
...
/* ------------------------------------------- */
int rb_enqueue (int q[], int *front, int *rear, int data)
{
  int index_f, index_r, index_q;
  index_f = *front % MAX;
  index_r = (*rear + 1) % MAX;
  if (index_f != index_r) {
    index_q = (*rear)++ % MAX;
    q[index_q] = data;
    return ENQUEUE_SUCCESS;
  }
  else {
    return ENQUEUE_FAILURE;
  }
}
...

これにより, 配列の末尾が次の配列の先頭になるか, 配列の先頭の前が配列の末尾となるようだ.

問 8.6

エスケープシーケンスによる画面制御, または, OpenGL 等のグラフィックスライブラリを利用してコード 8.3 のライブゲームの出力を工夫しなさい.

コードはこちらを参照. 実際に実行してみると, 以下のような結果となる.

https://github.com/inokappa/algorithm_and_programming/blob/master/images/8-6.gif?raw=true

エスケープシーケンスによる画面制御を用いた例. おお〜.

以上

  • スタックやキューは配列を利用して表現することが出来る
  • スタックは後入れ先出し, キューは先入れ先出し
  • ライフゲーム, まだちゃんと理解出来ていないけど... 見てて面白いし, 2 次元配列の実装だけで表現出来ることに驚いた

AWS WAF の IPSet を管理するコマンドラインツール wafoo のそれから... 〜 gem 化してリリースしてみた 〜

これは

qiita.com

初老丸 Advent Calendar 2018 第 5 日目の記事になる予定です.

tl;dr

以前に以下のような記事を書きました.

inokara.hateblo.jp

AWS WAF の IPSet をコマンドラインで操作するツールを雑に作りはじめていて, その後, 放置気味だったのを改めて見直して gem 化してリリースしてみました.

wafoo | RubyGems.org | your community gem host

使い方自体は特に変わっておらず, export コマンドで指定した IPSets の IP アドレスリストを書き出して, 必要に応じて追加, 修正, 削除を行い apply コマンドで登録する流れです. 登録前に --dry-run で確認出来るので, 実際に運用する場合には --dry-run で確認してから apply という流れになると思います.

以前と変わったところ

IPSet 一覧表示

AWS SDK for Ruby のドキュメントを見ると, Aws::WAFAws::WAFRegional という 2 つのモジュールが提供されています. waf と waf regional の違いは, 前者が CloudFront に付与する WAF で, 後者が ELB に付与する WAF で別けられるようです. これらを一緒に一覧表示するようにしてみました.

$ bundle exec wafoo list
+-------------+--------------------------------------+----------+
| Type        | IPSets ID                            | Name     |
+-------------+--------------------------------------+----------+
| WAFRegional | xxxxxxxx-1234-5678-9000-xxxxxxxxxxxx | sample1  |
| WAFRegional | xxxxxxxx-1234-5678-9000-yyyyyyyyyyyy | sample2  |
| WAF         | xxxxxxxx-1234-5678-9000-zzzzzzzzzzzz | sample3  |
+-------------+--------------------------------------+----------+

とりあえず, こんな感じで.

オクテットではない CIDR boundary のサポート

AWS WAF より、2つの新機能のご紹介です。

dev.classmethod.jp

従来の AWS WAF の IPSet では, IP アドレスの指定は /8, /16, /24, /32 での CIDR 指定しか出来ませんでした. その為, これらのオクテット以外の IP アドレス (例えば, /29 とか) を登録した場合には, /32に分割して登録するような処理をいれていましたが, 非オクテット CIDR boundary のサポートに伴い, この処理が不要となりました.

現在では, コメントアウトしていますが, 以下のような処理を行っていました.

...
      # def split_cidr(ipset)
      #  addr = NetAddr::CIDR.create(ipset)
      # addr.enumerate
      # end
...
      # unless %w(8 16 24 32).include?(ipset.split('/').last)
      #   ips = split_cidr(ipset)
      #   ipsets_array = []
      #   ips.each do |ip|
      #     ipsets_array << {
      #                        action: 'INSERT',
      #                        ip_set_descriptor: {
      #                          type: 'IPV4',
      #                          value: ip + '/32'
      #                        }
      #                     }
      #   end
      #   return ipsets_array
      # end
...

汚いコードしか書けない自分にとっては, コードを減らせるというのはとても嬉しいです.

べた書きコードを少しずつ...

今後のメンテンスを考慮して, べた書きしていたコードを少しずつ機能毎に分割したり, テストを追加しています.

以上

wafoo の紹介でした. コマンド実行時のメッセージ出力や README の英語がアレな感じで恐縮ですが, 何卒, ご容赦ください.

よろしければ, ご利用いただきましてフィードバック等いただけると幸いです.

Ruby の YAML ライブラリで YAML をパースする vs オレオレ YAML パーサーで YAML をパースする 〜 この戦いは止むる (YAML) ことは出来ない 〜

これは

qiita.com

初老丸 Advent Calendar 2018 第 4 日目の記事になる予定です.

tl;dr

前々回, 以下のような記事を書きました.

inokara.hateblo.jp

hub という Github クライアントライブラリの長い歴史の中で, Ruby 標準の YAML ライブラリの変わりにオレオレ YAML パーサーが実装されていて, そのパーサーで解析出来ない YAML ファイルを書いてハマってしまったという話です.

github.com

コミットメッセージから察するに, コマンドラインツールにおいて, 設定ファイルの YAML ファイルを読み込む時間は 1 ミリ秒でも速くしたかった思いが伺えます.

では, どのくらい処理時間に差があるのか

調べてみました

というのが本記事です. 本記事では以下のような環境で検証を行います.

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.13.6
BuildVersion:   17G65

$ ruby --version
ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin17]

まず, 以下のようなスクリプトをこさえて雑に YAML ファイルを生成してみます.

require 'erb'

contents =<<"EOS"
github.com:
<%- (0..100000).each do |id| -%>
  - user: foobar<%= format('%04d', id) %>
    oauth_token: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx<%= format('%04d', id) %>
<% end %>
EOS
erb = ERB.new(contents, nil, '-')
puts erb.result(binding).chomp

これを実行して YAML ファイルを生成します.

$ ruby generate-yaml.rb > sample.yml

以下のような無いようの YAML ファイルが生成されました.

github.com:
  - user: foobar0000
    oauth_token: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0000
  - user: foobar0001
    oauth_token: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0001
...
  - user: foobar99999
    oauth_token: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx99999
  - user: foobar100000
    oauth_token: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx100000

hub で利用する YAML ファイルのフォーマットそのままに 100000 ユーザー分のユーザー名 (user) とトークン (oauth_token) が生成されているはずです. (実際に 100000 ユーザー分を記載することは無いと思いますが...) これを sample.yml という名前で保存しておきます.

ruby-prof

調査には標準の profiler ライブラリではなく, ruby-prof という gem を利用しました.

github.com

profiler と ruby-prof の違いについては, ドキュメントや別の記事にお譲りしますが, ざっと使ってみた感じだと, プロファイルの実行速度や結果出力について profiler よりも優れているように思えます. ざっくりで恐縮ですが, ruby-prof の使い方は以下のように RubyProf.profile ブロック内に解析したいコードを差し込んで結果を RubyProf の各種プリンタクラスで表示します.

require 'yaml'
require 'ruby-prof'

result = RubyProf.profile do
  YAML.load_file('sample.yml')
end

printer = RubyProf::FlatPrinter.new(result)
printer.print(STDOUT, { :sort_method => :total_time })

上記の例だと, YAML.load_file('sample.yml') の解析結果が変数 result に格納され, RubyProf::FlatPrinter クラス (出力例はこちら) を使って結果を出力しています. 出力先として STDOUT に, total_time (対象のメソッドとそのメソッドから呼び出されたメソッドを含めた総処理時間) 順にソートされて出力します. 以下, 出力例です.

Measure Mode: wall_time
Thread ID: 70181951114860
Fiber ID: 70181959375120
Total: 0.119640
Sort by: total_time

 %self      total      self      wait     child     calls  name
  0.03      0.120     0.000     0.000     0.120        1   [global]#[no method]
  0.00      0.120     0.000     0.000     0.120        1   <Module::Psych>#load_file
  0.01      0.120     0.000     0.000     0.120        1   <Class::IO>#open
  0.01      0.119     0.000     0.000     0.119        1   <Module::Psych>#load
  0.00      0.066     0.000     0.000     0.066        1   <Module::Psych>#parse
...

尚, 出力は上記のテキスト出力だけではなく, HTML や graphviz で画像に書き出せる DOT 言語でも書き出すことが可能です. 詳細は README をご一読ください.

標準の YAML ライブラリを ruby-prof で解析してみる

コード

以下のようなコードで検証してみます.

require 'yaml'
require 'ruby-prof'

RubyProf::measure_mode = RubyProf::PROCESS_TIME
result = RubyProf.profile do
  YAML.load_file('sample.yml')
end

printer = RubyProf::FlatPrinter.new(result)
printer.print(STDOUT, { :sort_method => :self_time })

以下のように実行します.

$ bundle exec ruby parser1.rb > result1.txt

実行結果

以下のような結果となりました.

$ head -15 result1.txt
Measure Mode: process_time_time
Thread ID: 70238351920700
Fiber ID: 70238356042040
Total: 57.293642
Sort by: self_time

 %self      total      self      wait     child     calls  name
  7.07      5.715     4.050     0.000     1.665   400005   Psych::ScalarScanner#tokenize
  6.79      3.892     3.892     0.000     0.000   400005   Psych::Nodes::Scalar#initialize
  6.75      3.867     3.867     0.000     0.000   600014   Psych::TreeBuilder#event_location
  6.45     14.876     3.694     0.000    11.181   400005   Psych::TreeBuilder#scalar
  5.66     11.522     3.241     0.000     8.281   400005   Psych::Visitors::ToRuby#deserialize
  4.81     27.601     2.757     0.000    24.844        1   Psych::Parser#parse
  4.48      6.035     2.566     0.000     3.470   400005   Psych::TreeBuilder#set_location
  4.06      2.326     2.326     0.000     0.000   500009   Psych::TreeBuilder#set_start_location
... 以下略

処理時間は Total: を確認すると良さそうです. 約 57 秒掛かっていることが分かります. また, Psych::ScalarScanner#tokenize というメソッドが 400005 回コールされて, 4 秒程処理に要していることが分かります. 1 回のコールあたり 9 マイクロ秒の時間で処理されていることになります. この数字だけ見ると遅いという印象は特に感じません.

ただ, YAML が解析されるまでに非常に多くのメソッドが呼ばれていることが結果から読み取れます. これを ruby-prof を利用することで可視化することが可能です. 検証コードを以下のように修正して Graphviz で読み取れる DOT 言語で結果をプリントするようにします.

require 'yaml'
require 'ruby-prof'

RubyProf::measure_mode = RubyProf::PROCESS_TIME
result = RubyProf.profile do
  YAML.load_file('sample.yml')
end

printer = RubyProf::DotPrinter.new(result)
printer.print(STDOUT, { :sort_method => :self_time })

以下のように実行して, Graphviz で画像に変換してみます. (事前に Graphviz をインストールしておきます.)

$ bundle exec ruby parser1.rb > result1.dot
$ dot -Tpng result1.dot -o result1.png
$ open result1.png

以下のように多くのメソッドが呼ばれていることが解ります. すごい.

f:id:inokara:20181128152125p:plain

オレオレ YAML パーサーを ruby-prof で解析してみる

コード

以下のようなコードで検証してみます.

require 'yaml'
require 'ruby-prof'

def yaml_load(string)
  hash = {}
  host = nil
  string.split("\n").each do |line|
    case line
    when /^---\s*$/, /^\s*(?:#|$)/
      # ignore
    when /^(.+):\s*$/
      host = hash[$1] = []
    when /(^[- ]) (.+?): (.+)/
      key, value = $2, $3
      host << {} if $1 == '-' or $2 =~ /^\s*-\s*/
      key.gsub!(/^\s*-\s*|^\s*/, '')
      # require 'byebug'; byebug
      host.last[key] = value.gsub(/^'|'$/, '')
    else
      raise "unsupported YAML line: #{line}"
    end
  end
  hash
end

RubyProf::measure_mode = RubyProf::PROCESS_TIME
result = RubyProf.profile do
  File.open("sample.yml", "r") do |f|
    yaml_load(f.read)
  end
end

printer = RubyProf::FlatPrinter.new(result)
printer.print(STDOUT, {})

以下のように実行します.

$ bundle exec ruby parser2.rb > result2.txt

実行結果

以下のような結果となりました.

$ cat result2.txt
Measure Mode: process_time_time
Thread ID: 70351828807260
Fiber ID: 70351829107000
Total: 7.317221
Sort by: self_time

 %self      total      self      wait     child     calls  name
 49.76      7.242     3.641     0.000     3.601        1   Array#each
 27.34      2.001     2.001     0.000     0.000   800011   Regexp#===
 12.90      0.944     0.944     0.000     0.000   200002   String#gsub!
  5.46      0.400     0.400     0.000     0.000   200002   String#gsub
  3.50      0.256     0.256     0.000     0.000   200002   Array#last
  0.91      0.067     0.067     0.000     0.000        1   String#split
  0.12      0.009     0.009     0.000     0.000        1   IO#read
  0.00      0.000     0.000     0.000     0.000        1   File#initialize
  0.00      7.317     0.000     0.000     7.317        1   [global]#[no method]
  0.00      7.317     0.000     0.000     7.317        1   <Class::IO>#open
  0.00      7.308     0.000     0.000     7.308        1   Object#yaml_load
  0.00      0.000     0.000     0.000     0.000        1   IO#close
  0.00      0.000     0.000     0.000     0.000        1   IO#closed?

* indicates recursively called methods

トータルの処理時間は 7.3 秒. Regex クラス=== メソッドが 800011 回コールされていることが分かります. === メソッドは左辺と右辺の String を正規表現マッチするメソッドなので, オレオレ YAML パーサーでは愚直に文字列比較を行って YAML を解析していると思われます. 処理時間は YAML ライブラリの 8 倍程度速く処理出来ていますので, hub の作者が嘆いていた理由は分かりました.

一応, YAML ライブラリと同様に, 呼ばれているメソッドを可視化したところ, 以下の通りとなりました.

f:id:inokara:20181128152402p:plain

YAML ライブラリと比較すると実にシンプルであることが分かりました.

以上

YAML ライブラリと hub で実装されていたオレオレ YAML パーサーの処理時間の比較を通して, ruby-prof を用いて, どのような処理が行われているかを把握し, 可視化することが出来ました.

速度を比較した結果は YAML ライブラリの方がオレオレ YAML パーサーよりも処理時間が長くなりましたが, これを一概に遅いと言えないと思いますし, 多くのメソッドが呼ばれるにはそれなりの意味があると考えています.

今回はこれ以上は踏み込んで調査は行いませんが, 機会があれば YAML ライブラリのソースコードをちゃんと読んで理解を深めたいと思います.

有難うございました.

2018 年 11 月 28 日 (水)

ジョギング

  • 引き続き, 左足踵に痛みがあったのでお休み
  • 湿布を張っていたらカブれて辛い...
  • 休養だと思ってしっかりと直すことにする

日課

  • お休み
  • そろそろ, 再開する... まじで, まじで..., まじで..., まじで...

Alternative Architecture DOJO Offline #1

久しぶりにもくもく会でもなく, 自分が話すわけではない勉強会に参加した. Microservice の文脈で語られる k8s の話が 7 割くらい. k8s は勉強しておかなければと改めて思った. 今日の収穫の一つ.

全てのセッションにおいて, ツイートするのも忘れて聞き入ってしまったし勉強になった.

2018 年 11 月 27 日 (火)

ジョギング

  • 左足踵に痛みがあったのでお休み
  • 休養だと思ってしっかりと直すことにする

日課

  • お休み
  • そろそろ, 再開する... まじで, まじで..., まじで...

白菜ミルフィーユ鍋

実家から多くの野菜を送ってもらった. その中で大きな白菜があったので豚バラと白菜のミルフィーユ鍋を作った. 出しは利尻昆布からとった出汁を使ったので更に美味しかった.

re:Invent 2018

クラスメソッドさんのブログが速報性が高くて良い. 幾つか気になった記事を.

dev.classmethod.jp

dev.classmethod.jp

dev.classmethod.jp

2018 年 11 月 26 日 (月)

ジョギング

  • 山王公園往復 (だいたい 30 分くらい)
  • 引き続き, 左踵に痛み, 右足甲に痛み, 色々と痛みがあったのでゆっくりと走る

日課

  • お休み
  • そろそろ, 再開する... まじで, まじで..., まじで...

ランチ

引っ越して以来, ずっと気になっていたお鮨屋さんに. うっかり 1.5 人前をオーダーしたり, 赤出汁飲み放題につられて 2 杯も赤出汁を飲んでお腹いっぱいになった. お鮨の味はさておき, 大将と奥さんが気さくに話しかけてくださったのが嬉しかった.

ティファール

昨日, ヨドバシで購入したティファールを早速使ってみた.

驚きしかなかった.

2018 年 11 月 25 日 (日)

ジョギング

  • 山王公園
  • 左踵に痛み, 右足甲に痛み, 色々と痛みがあったのでゆっくりと走る

日課

  • お休み
  • そろそろ, 再開する... まじで, まじで...

博多にちょっと

2018 年 11 月 24 日 (土)

ジョギング

  • 産山村の民宿からやまなみハイウェイを少し登ったり, 阿蘇の外輪山を少し走ったりして 40 分
  • 朝 6 時半スタートだったけど, 手足が冷たすぎて走りづらかったが, 朝日がのぼり始めると少しずつ温まって, とても気分が良かった

日本一のマラソン練習コース

日本一のマラソン練習コースに来た。次回は走ろう。

近くまできたので, 日本一のマラソン練習コースに立ち寄った.

次回来た時には走ろうと思った次第.