kawasin73のブログ

技術記事とかいろんなことをかくブログです

Go 言語でタイムアウト付きのファイルロックを実現する

言語の壁をぶっ壊す。どうも、かわしんです。

プロセス間の待ち合わせの手法としてファイルロックがあります。このファイルロックをタイムアウトでキャンセルすることを可能にするために以下のライブラリを作ったのでその解説をしたいと思います。

github.com

対象

今回の対象は以下の環境とします

ファイルロックを実現するシステムコール

Linux では、fcntlflock というシステムコールでファイルロックができます。

この 2 つで獲得されるロックはカーネル内では別のものとして扱われますが、 FLOCK の 注意 にもある通り、一部のシステムでは flockfcntl が影響を与える可能性があるため、単一のプログラムの中ではどちらかのロックのみを使うようにした方が良さそうです。(プログラムの複雑性も軽減されます)

今回の話は、fcntlflock のどちらでも共通の話なので、fcntl を使ってデモを行います。

FCNTL

fcntl は、ファイルディスクリプタを操作するシステムコールです。

Man page of FCNTL

#include <unistd.h>
#include <fcntl.h>

int fcntl(int fd, int cmd, ... /* arg */ );

以下のコマンドを指定して、引数に flock 構造体を渡すとファイルロックができます。

ロックはファイルのバイト単位で範囲を指定してロックします。

基本はアドバイザリーロックで、頑張ると強制ロックも可能です。

これらは POSIX で標準化されています。

  • F_SETLK : ロックの獲得をノンブロッキングで行います。ロックの獲得に失敗した場合は EACCES または EAGAIN エラーが返ります。
  • F_SETLKW : ロックの獲得を行います。ロックの獲得に失敗した場合はロックの獲得ができるまで処理をブロックします。
  • F_GETLK : ロックの情報を取得します。

ロックの種類は F_RDLCKF_WRLCK があり flock 構造体で指定します。go でいう sync.RWMutex みたいな感じですね。F_UNLCK を指定するとロックを解除します。

FLOCK

次に flock は、名前の通りファイルをロックするシステムコールです。

Man page of FLOCK

flockBSD 系由来のシステムコールPOSIX には含まれませんが、シンプルなインターフェイスです。

ロックの範囲はファイル全体のみで、fcntl のように特定の範囲のみをロックすることはできません。

ロックはアドバイザリーロックになります。

#include <sys/file.h>

int flock(int fd, int operation);  

operation に以下のオペレーションを指定してファイルをロックします。

  • LOCK_SH : 共有ロック。fcntl でいう F_RDLCK みたいな
  • LOCK_EX : 排他ロック。fcntl でいう F_WRLCK みたいな
  • LOCK_UN : ロックの解除

また、operation論理和LOCK_NB を指定するとノンブロッキングでロックを獲得し、指定しない場合はロックを獲得できるまで処理をブロックします。

Go 言語におけるファイルロック

Go では syscall パッケージに syscall.FcntlFlock()syscall.Flock() が用意されています。

// fcntl のインターフェイス
func FcntlFlock(fd uintptr, cmd int, lk *Flock_t) error

// flock のインターフェイス
func Flock(fd int, how int) (err error)

これらはあくまでもシステムコールをラップしただけのものなのでタイムアウトの機能を追加する必要があります。

githubfile lockタイムアウト付きのファイルロックの Go の実装を調べていると以下の2つのライブラリを探すことができました。

github.com/gofrs/flock

GitHub - gofrs/flock: Thread-safe file locking library in Go (originally github.com/theckman/go-flock)

gofrs/flock には、TryLockContext というメソッドがあり context.Context を利用してタイムアウトやロックの中断を実現できます。

func (f *Flock) TryLockContext(ctx context.Context, retryDelay time.Duration) (bool, error)

しかし、その内部実装は syscall.Flock をノンブロッキングモードで呼び出し、成功するまで for 文で retryDelay で設定された間隔で呼び出し続けるものになっています。

これでは、カーネル内部のロックキュー に入らないため、 複数プロセス間のロックの順序が崩れてしまいます 。(参考 : linux - flock locking order? - Stack Overflow)

また、ロックの獲得まで 最大で retryDelay の分の遅延が発生する ことになります。

github.com/jviney/go-filelock

GitHub - jviney/go-filelock

jviney/go-filelock では、Obtain 関数にタイムアウトの時間を渡してタイムアウト付きのファイルロックができます。

func Obtain(path string, timeout time.Duration) (lock *Lock)

しかし、その内部実装は syscall.Flockブロッキングモードで実行する goroutine を立ち上げて、その終了とタイムアウトObtain 関数内で select 文で待つものでした。

タイムアウトするとさらに新しい goroutine を立ち上げ、その goroutine 内でロックが獲得できるまで待って即座にロックを開放するようにしています。

      // We hit the timeout without successfully getting the lock.
      // The goroutine blocked on syscall.Flock() is still running
      // and will eventually return at some point in the future.
      // If the lock is eventually obtained, it needs to be released.
      go func() {
        if err := <- flockChan; err == nil {
          releaseFlock(file)
        }
      }()

https://github.com/jviney/go-filelock/blob/ec38a70cdf163d7c9f50a224f4c422f8a1847d7a/filelock.go#L48-L56

ロックが獲得できなかった場合、 ロック開放用とロックを取得する 2 つの goroutine が残り続けます

また、ロックを獲得中のファイルディスクリプタを閉じるとロックが獲得するまでブロックします。 ファイルディスクリプタを解放することができない ためファイルディスクリプタも残り続けます。

これではリソース管理の面からガバガバです。

どうやってファイルロックを中断するか

上の 2 つのライブラリはファイルロックの直接的な中断ができなかったためにこのような課題が残っていました。

この点を解決するために、ここでどうやってブロックしているファイルロックを中断するかを考える必要があります。

答えは シグナル です。

ブロッキングするシステムコールはシグナルを受信することによってブロックが解除され EINTR エラーを返すようになっています。(タイムアウトという文脈では alarm を使うことが多そうです)

Timeouts for system calls are done with signals. Most blocking system calls return with EINTR when a signal happens, so you can use alarm to implement timeouts.

https://stackoverflow.com/questions/5255220/fcntl-flock-how-to-implement-a-timeout#answer-5255473

そのためシグナルを送信してロック獲得処理に EINTR を発生させることでファイルロックのタイムアウトや中断を実現できます。

シグナルによる割り込みを Go でも実現させる

シグナルを自分のプロセスに送れば解決するはずなのですが、Go では以下の 2 つの障壁があります。

  • SA_RESTART によって EINTR がそもそも発生しない
  • シグナルを pthread_kill 使って送信しないといけない

それぞれ順をおって解説します。

SA_RESTART によって EINTR がそもそも発生しない

SA_RESTARTsigaction に設定するフラグで、このフラグが設定されると、ブロッキングしているシステムコールがシグナルによって中断された場合でも EINTR を返さずにブロッキングを続行するようになります。

参考 : シグナルハンドラーによるシステムコールやライブラリ関数への割り込み

Go ではランタイムによって全てのシグナルに対して SA_RESTART が設定されています。これにより標準ライブラリは EINTR のエラーハンドリングをしなくてよくなります。(確かに標準ライブラリを読んでいると EINTR のハンドリングをしていないことに気づきます)

Also, the Go standard library expects that any signal handlers will use the SA_RESTART flag. Failing to do so may cause some library calls to return "interrupted system call" errors.

https://golang.org/pkg/os/signal/#hdr-Go_programs_that_use_cgo_or_SWIG

これは Go のランタイムの問題なのでどうしようもありません。Go 言語のレイヤーでは解決できません。

ここで、「 言語の壁をぶっ壊す 」CGO の出番です。Go 言語を壊していきます。

CGO によって直接 C 言語で sigaction を実行しシグナルハンドラを設定することで Go のランタイムが設定した SA_RESTART を上書きします。

この時点で Windows とかの可搬性は捨ててます。すみません。

void sighandler(int sig){
    // empty handler
}
static struct sigaction oact;

static int setup_signal(int sig) {
    struct sigaction act;
    // setup sigaction
    act.sa_handler = sighandler;
    act.sa_flags = 0;
    sigemptyset(&act.sa_mask);
    // set sigaction and cache old sigaction to oact
    if(sigaction(sig, &act, &oact) != 0){
        return errno;
    }
    return 0;
}

シグナルを pthread_kill 使って送信しないといけない

さて、SA_RESTART を上書きした上で自身のプロセスにシグナルを送るとブロッキングしているファイルロックを中断できる場合とできない場合が出てきます。

それは、事前に signal パッケージの signal.Ignore()signal.Notify() などを呼び出した時です。

これらのメソッドを呼び出した時に Go のランタイムは signal mask thread を立ち上げそのスレッドが全ての sigaction の登録を行います。(具体的には ensureSigM という関数)

go/signal_unix.go at 2c5363d9c1cf51457d6d2466a63e6576e80327f8 · golang/go · GitHub

これによって プロセススコープに送られたシグナル はランタイムの signal mask thread に送られてしまいます。その場合は別のスレッドでファイルロックをブロックしているためシグナルが届かず EINTR も発生しません。

この解決策は スレッドスコープでシグナルを送る ことです。

残念ながら Go 言語は OS のスレッド意識させないような作りになっており、スレッドに対して直接シグナルを送ることはできません。

そこで、「 言語の壁をぶっ壊す 」CGO の出番です。どんどん Go 言語を壊していきます。

C では、pthread_kill という関数があり特定のスレッドにシグナルを送ることができます。

static pthread_t tid;

static int setup_signal(int sig) {
    ...
    // set self thread id
    tid = pthread_self();
    ...
}

static int kill_thread(int sig) {
    // send signal to thread
    if (pthread_kill(tid, sig) == -1) {
        return errno;
    }
    return 0;
}

これでブロックしているファイルロックを中断させることができるようになりました。

github.com/kawasin73/gointr を作った

これまでの知見を元にブロッキングしている処理を中断させる処理をライブラリ化しました。

github.com

使い方としては

  1. 中断に使うシグナルを指定して gointr.Intruptter を作成する (gointr.New(syscall.SIGUSR1))
  2. ブロッキングする処理を行う goroutine を立ち上げて intr.Setup() を実行してから、ブロッキング処理を行う
  3. ブロッキング処理が終わったら intr.Close() する
  4. もし、中断する場合は intr.Signal() を呼び出す

となります。中断された場合は EINTRブロッキングするシステムコールから返ってきます。

注意点

注意点としては、以下のことが挙げられます。気をつけてください。

  • グローバル変数を内部で使っているため 複数のブロッキング処理の中断に対応していない
  • signal パッケージの関数を呼び出すと上書きした sigaction が上書きされ直されるので ブロッキング処理中は signal パッケージの関数を呼んではいけない
  • CGO を使っている

Example

package main

import (
    "fmt"
    "io"
    "log"
    "os"
    "os/signal"
    "syscall"
    "time"

    "github.com/kawasin73/gointr"
)

// lock locks file using FCNTL.
func lock(file *os.File) error {
    // write lock whole file
    flock := syscall.Flock_t{
        Start:  0,
        Len:    0,
        Type:   syscall.F_WRLCK,
        Whence: io.SeekStart,
    }

    if err := syscall.FcntlFlock(file.Fd(), syscall.F_SETLKW, &flock); err != nil {
        // FCNTL returns EINTR if interrupted by signal on blocking mode
        if err == syscall.EINTR {
            return fmt.Errorf("file lock timeout for %q", file.Name())
        }
        return &os.PathError{Op: "fcntl", Path: file.Name(), Err: err}
    }
    return nil
}

func main() {
    signal.Ignore()

    file, err := os.Create("./.lock")
    if err != nil {
        log.Panic(err)
    }

    // init pthread
    intr := gointr.New(syscall.SIGUSR1)

    // init error channel
    chErr := make(chan error, 1)

    // setup timer
    timer := time.NewTimer(3 * time.Second)

    go func() {
        // setup the thread signal settings
        if terr := intr.Setup(); terr != nil {
            chErr <- terr
            return
        }
        defer func() {
            // reset signal settings
            if terr := intr.Close(); terr != nil {
                // if failed to reset sigaction, go runtime will be broken.
                // terr occurs on C memory error which does not happen.
                panic(terr)
            }
        }()
        // lock file blocking
        chErr <- lock(file)
    }()

    for {
        select {
        case err = <-chErr:
            timer.Stop()
            if err == nil {
                log.Println("lock success")
            } else {
                log.Println("lock fail err", err)
            }
            // break loop
            return

        case <-timer.C:
            log.Println("timeout")

            // send signal to the thread locking file and unblock the lock with EINTR
            err := intr.Signal()
            log.Println("signal")
            if err != nil {
                log.Panic("failed to kill thread", err)
            }
            // wait for lock result from chErr
        }
    }
}

最後に

以上です。ありがとうございました。

ぶっちゃけ、ここまで厳密にするなら Go を使わなくていいと思うし、多分自分が使うとしたら github.com/gofrs/flock を使う。

未踏 Demo Day に行ってきた

ビールは 1 日 4 缶まで。どうもかわしんです。

2018 年度の未踏プロジェクトの Demo Day という名の成果発表会が秋葉原で 2/16 と 2/17 の2日間に渡って行われ、中高の同級生が未踏プロジェクトに採択されて発表するというので聞いてきました。

MITOU2018 Demo Day/2018年度(第25回)未踏IT人材発掘・育成事業 成果報告会 開催のご案内:IPA 独立行政法人 情報処理推進機構

懇親会でビールを 3 杯飲んで、家に帰ってからも感動が冷めやまず今ビールを 1 缶飲みながらこの記事を書いてます。

全体的な印象

話を聴きながら思ったことは、さすが未踏ということだけあって技術的にさらにもう一歩深掘りしているものが多かったということです。

テーマを聞いて僕なりにだいたいこんなことをするんだろうなということが考えつくのですが、そこまでは当たり前のように開発した上で、さらにもうひと押しして新しい機能を技術的課題を突破して開発し、システムの利便性を上げて報告会に望んでいるという印象を受けました。

なので、毎回期待を上回るものが聞けてワクワクしながら発表を聞くことができました。

また、そのもうひと押しというのはだいたい機械学習遺伝的アルゴリズムなどで解決していることが多かったです。

僕は流行りに惑わされることが嫌だったので機械学習はやらないと、あえて決めてシステム開発に振ってエンジニアをやってきましたが、アプリケーションをもうひと押し使いやすくするためのツールとして機械学習を入れ込むことが必要になってきているのではないかと感じさせられました。

面白かった発表

特に印象に残ったのは以下の発表です。

AI 実況プレイ動画生成の発表は、プレゼンテーションのクオリティが常軌を逸していました。

プレゼンはエンターテイメントショーだということをマジマジと見せつけられました。

僕はスティーブ・ジョブスとかのプレゼンが好きでその演出とかに感動してしまうタイプなのですが、完全にエンターテイメントとしてストーリーを構成されている上に、そのプレゼンを死ぬほど練習したんだろうなということがうかがえるくらい完璧なプレゼンでした。

プレゼンのストーリーに必要のない過多な情報は全て切り捨て、質疑応答に回すという大胆な方法で、圧倒的わかりやすさとストーリーの没入感を演出していました。

このプレゼンは、もう一度観たいと思うほど感動した発表でした。

また、研究の内容もマリオカートの実況動画を作るためのステップを3つに分割して、それぞれのステップの課題を解決するための技術開発を行なっていてものすごいクオリティでした。 それぞれのステップが 1 つプロダクトになるレベルのことをやっていました。

面白かったです。

これはシンプルにプロダクトの完成度とそのプロダクトによる世界への影響度が半端ないと感じました。

数文字の文字のフォントを作ることによって最大 34 万字のフォントを自動生成するのは誰でもフォントを作ることができるため革新的です。 フォント生成をサーバーサイドではなくここのブラウザ上で行うことでサーバーコストを抑えることができるという有益な特徴を持っています。

また、デモやプロモーションの動画がとてもワクワクさせられました。

これが 2 日間で一番興奮した発表です。

発表の動画のビジュアルの完成度は圧倒的で、プレゼンの構成やスライドの作り方などもすごく考えられているんだろうなと伝わりました。

3D プリンターに印刷以上の機能を持たせるという既存の固定概念をぶっ壊して 3D プリンタを再発明するというテーマで、おそらく世界で誰もやっていないだろうことをやっており、新しい未来を作るんだという心意気が伝わってきました。

しかし研究の内容はテーマの鮮やかな感じとは打って変わって、解決したい大きな目標に達するまでに発生する課題を一つ一つ地道に潰しながら次のステップに進み、また課題を潰して次のステップに進み、という泥臭さがあり、発表の鮮やかさ、テーマの鮮やかさの中からもその泥臭さが伝わってきて、この1年という時間を妥協せずにこの研究に費やしてきたんだなと感動しました。

てか、1.5mm ~ 2.3mm という絶妙な数値なんだよ。その1つ1つのステップでレベルで試行錯誤してるのかよ。どんだけ時間がかかるんだ。

まさに努力の結晶という言葉がぴったりなプロダクトでドン引きしました。

人型ロボットを小学生から作り続けている高校生 2 人による発表でした。手作りのロボットのモーションを初心者でも簡単に作れるようにするアプリケーションでした。

これはもうひと押しどころか、もうふた押しくらいあるような深みのある研究でした。

ロボットのモーションを GUI で作れるようになるためのプラグインの開発を終えた後に、シミュレータのモデルと現実のモデルの重さや重心を合わせるために、ロボットを分解することなく各パーツの重さや長さを様々なポーズをさせた時の重心の位置の違いによって計測するというシステムを開発し(ひと押し目)、さらに GUI で作ったモーション(例えば二足歩行)が作成者の意図通りになるように遺伝的アルゴリズムを使ってシミュレーションして自動的に最適化させる(ふた押し目)というものでした。

ユーザーが求めているのはモーションを簡単に作ることだけではなく、自分が求めている動きによって機能が達成されることですが、とことんまでユーザーに求められるものを追求し、それに必要な技術的な課題を突破していく様は鮮やかですらありました。 僕は発表を聞いていて声が漏れました。


これらの他にも面白い発表ばかりでしたが、そろそろ眠いのでこのくらいにします。

また、発表の内容は後々 IPA の youtube で公開されるそうなので見てみてください。

発表でとったメモ

以下は、発表でとったメモです。両日とも遅刻していったので最初の発表のメモは薄いです。

また、メモの内容が薄い部分は僕がその発表に集中しすぎてメモを取ることを忘れてしまっているのでご容赦ください。


1 日目


タブ分類ブラウザ

氾濫するタブ一覧を自動で整理するモバイルブラウザ

モバイルブラウザのタブでメモを取る

キーワードだけでなく検索結果も含まれるから思い出しやすい

Search for Later メソッド

Leita

1週目のリテンションが悪い

ゲーム実況AI

マリオカートの実況をする

  • 見る
  • 感じる
  • 話す

見る

画面上の出来事を認識する

深層学習

  • 画像認識
    • CNN
  • 動作認識
    • LRCN
    • 1秒分の動作を認識
  • 物体検出
    • SSD
    • どこになるがあるかを検出

学習用のデータがない マリオカートコーパスの収集システムも作った

感じる

感情 ラッセルの感情モデル

喜怒哀楽の4つの感情を表す

ルールベース?

人間からデータをもらう プレイ中の心拍数

話す

どんなときにどんなリアクションをするのか。 既存の実況動画を分析する

毎回おなじリアクションになってしまう

自分なりのリアクションを生み出す

RNN を使う 多様なリアクションを取れる

リアクションを自動分類

展望

いろいろなゲームを実況する ゲームに関係ないことも話す

何をしようという意思は実況できるか?

顔の外見を変える顔拡張マスクの開発

お面

  • 正体を隠す
  • なりたい人やものに変化する

顔前面にディスプレイを設置 うまくいかなかった。思い、視界が悪い

お面を土台に

  • フォトクロミズムと赤外線ライト
    • 小型化が困難
    • 明るいところでは見えにくい

設計方針を決める

サーモクロミックと加熱回路層

銀ナノインクでプリントすることで回路をつくることを容易にした

ヒルベルト回路

文字形状を自動生成する Web フォント制作支援ソフトウェア

DeepGlyph

日本語フォントは、漢字が多いため制作コストが高い そのため日本語フォントは普及していない

普及させるために制作支援ソフトウェアを作った

ベクターデータとラスタデータをシームレスに行き来できる

生成の仕組み

深層学習を利用したスタイル変換

文字を画像として生成する

  • Content Reference
  • Style Reference

GAN でクロリティの高い書体を作り出す GAN を導入すると直線や曲線がなめらかになる

生成されたフォントの評価が難しい

Seed component 元になる文字

Glyph Wiki 34万字

WebDNN プレビュー Webブラウザ上で深層ニューラルネットワークの推論を行える

生成のコストを個々のマシンに負担させることができる

初心者でも作れる

https://deepglyph.app

配信もできるようにしたい

なんで10個なのか Seed component

C++ パッケージマネージャ

conan がある 使いづらい

poac

コミュニケーションロボットの会話制御ソフトウェア

なにを会話すればいいかわからない。 ロボットを十分に活用できていない

複数のロボット同士が会話する

同じ外見やアーキテクチャのロボット同士で会話する

GUI によるロボットプログラミング 1体の利用を想定した環境 できることは限られている

Roboript

  • Sota
  • Robohon
  • Pepper
  • Nao

ブロックベースの GUI プログラミング

話す順番を制御できる

Android アプリでプログラミング

ROS で通信 Android アプリが制御する ステップでブロックを当てはめる

ロボット場でロボットを制御するアプリを動かせる

保険で実証実験 子供を惹きつける

あらゆるアセットを管理するビジネスロジックを兼ね備えた汎用型分散台帳基盤の開発

リエータがシステム運営者を選ぶ

活動が、ビットコインにおけるマイニングの代替となる

Proof of Creator

フォロー・フォロワーの有向グラフで表現

Proskenion

Merkle Patricia Tree

3D プリンタ

印刷以外もできるようにする

動くものを 3D ぷりんたで 破壊可能

3D プリンタの普及

印刷していないときのほうが長い これからは 3D プリンタが余る

直交ロボットだからプリント以外できるのは当たり前といえば当たり前

3D プリンタがその機能になる

エンドエフェクタ

エンドエフェクタ。ロボットの手みたいなもの 着脱可能なエンドエフェクタ

エンドエフェクタを 3D プリンタが印刷する

動くものを印刷する造形手法

中空にサポート材が必要

  • フィラメントのタレを利用

接地面と離れるくらいの厚みのタレをつくる

  • 剥がす・剥がさない

剥がれる場所 接地面を大きくする ガラスプレートに押し付ける

剥がれない場所 接地面を小さくするために、小さな柱をつける

  • 橋渡し

中空を作れる 柱を縁で繋いで橋渡しをする

  • 破壊可能なサポート材

3D プリンタでサポート材を破壊する

45 度だとサポート材のサポート材が必要ない

吹っ飛ばすために応力シミュレーションをする

  • 組み立て

ベベルギア 複雑な形状だと破壊できるサポート材でもできない

印刷後に組み立てる

デザインソフトウェア

パスを組み立てる

G-code を生成する

CAD 空間上と 3Dプランタうえの配置をする

エンドエフェクタの先端とエクストルーダの座標はことなるため

既存の3Dプリンタ

印刷いがいの動きを 3D プリンタに命令できるようにした

まとめ

  • 削ることができる
  • ディスプレイ表示
  • 既存のものを動かす

使わなくなったフィラメントを再利用 その場にあるものをふぃらめんとにする

宇宙開発でやくだつ


2 日目


認識 AI を迅速に賢くするフレームワークの構築

物体の画像認識

多視点画像収集 ロボットアームで多視点の画像を撮ることができる

自動アノテーション ものの周囲にAR マーカーを置くことで画像のものの輪郭を推測し、四角で囲む

15時間 -> 4分

学習データの準備

画像収集

ロボットアームのカメラ 回転ステージ

配置換えを自動化

画像を採用するかは特許技術になる

変形に対応できる さまざまな大きさに対応できる

ヒューマノイドロボット

人間型のロボット

ロボットの設計手法を情報発信してきた

知識がなくても動作をつくれる

歩かせるまでに9ヶ月かかった

40 分で素人ができるようになった

機体のモデルをつくる必要がある 重さなどが必要 分解しないで測る

Reficere 2分で1パーツ計測できる 重心センサーでわかる

誤差は 1.8%

Blender という 3DCG のソフトウェア ロボット用ではない

BlendMotion というアドオン

思った通りに動くようにシミュレーション環境で遺伝的アルゴリズムで試行錯誤する

倒れないように学習させる

ざっくりうごきをつくって、遺伝的アルゴリズムで最適化する 目的関数はどうするのか Blender の中で設定できる

分野限定型検索エンジンと分散型検索エンジン

kearch

自由な検索エンジンをつくる

作るのに莫大なリソースが必要

検索エンジンの不透明性

小リソースでだれでもデプロイ可能 アルゴリズムが公開 検閲ができない

分野を限定した検索エンジンを複数つなぎ合わせる

メタ検索エンジン、専門検索エンジン

専門検索エンジン

フォーカスクローリング 分野を限定する

メタ検索エンジン

Federated search

ユーザのクエリから専門検索エンジンを選ぶ

省リソース

専門分野のせってい

単語のリスト 起点となるURLのリスト

public と protected を選べる

Google とも接続できる

分野を学習する

分野外は辿らない

専門検索エンジンからメタ検索エンジンにサマリーをおくって、メタ検索エンジンのクエリの判断に役立てる

くろーるできているのか

起点となる URL 出てくるのは有用な情報になるのか?

ユーザのクエリを全てに流しているのか? 複数の場合はどのようにマージするのか 上位3つにクエリを投げる

一人称ライフログ映像から顔検出に基づいた社会活動量計の開発

ユーザ近傍におけるコンピューティング環境の開発

ローカル環境で使える物理基盤

便利な機能をパッケージ化

  • ネットワーク提供
  • 情報共有などのサービス提供

インターネットやネットワーク環境がなくてもサービスを提供できる

遠隔地との通信が不安定(遅延、トラフィックの集中)になる欠点がある

エッジコンピューティングが解決策

閉じた環境での共有ならクラウドサービスを使わなくてもいいのではないか

エッジコンピューティングの課題

  • ネットワーク構築
    • 設置する機材
  • システム運用
    • 故障、移動
  • コンピュータ制御機構
    • 柔軟に制御

一眼レフカメラのケースに入るくらい

tiparcel

ラズパイをアクセスポイントとして運用する 72Mbps

1万円のルーターは 800Mbps

72Mbps でも youtube 6台使えるくらい十分

電子ペーパーをモニタにした

Captive Portal は認証画面を自動で出す機能

認証画面ではなくサービス画面をだす

ストレージを気にした

ハードウェアを含めてパッケージ化されている ソフトウェアとして汎用化できないか その課題はなにか

ネットワークブートに依存している バイナリが arm に依存している

将来的にはシングルボードで動かしていく方針

NVDIMM 向けファイルシステムの開発

AEON

strace

システムコールの中身が違う

VMDIMM 不揮発性 RAM 速くて永続化する

速度を追求した設計 領域の使用効率をあげる

NOVA NVDIMM 専用ファイルシステム

スケーラビリティがある

使用効率をあげる

透過圧縮

設計

全体にカーネルアドレス空間マッピング

先頭からのオフセットで全体を管理

カーネルからユーザランドへコピー mmap で直接みれる?

Consistency Without Ordering ジャーナリングは使わずに、ポインタを相互に張る

対応したシステムコール

SSD との違い もっと早いだけ

DAX で直接読み書きする

設計がどのように変わるのか ブロック単位でなくてバイト単位でアクセスできるのが特徴

複数のプロセスが同時にアクセスできる

機械学習を用いたロボット制御のための汎用システムの開発

故障に強いロボット制御

  • 環境の変化
    • ゴミが落ちた床
  • 不測のトラブル
    • 故障
    • ケーブル破損

環境の変化は歩行で対応する

  • 真っ直ぐに進む
  • 妥当な動作

手法

  • 強化学習
    • 時間がかかる
    • 報酬設計が難しい
    • 予期した動きになるとは限らない
    • ロボットが壊れてしまう
  • シミュレーション上での学習
    • Sim to Real
    • 現実がちがう。床との摩擦、出力トルク
    • 強化学習とおなじデメリット
  • 既存歩行パターンの改善
    • 基本パターンから学習を開始
    • 馬など

具体的に

  • 基本歩行パターンから高評価なものを選定
  • 初期位置に関して学習
  • 動作パターンを学習
    • 壊れることによって無駄な動きがでてくるが省略することができる

初期位置が重要な理由

壊れた足を補うようにバランスを取る必要がある 脚の先端位置を微調整できるようになっている 初期位置を学習した

10~20分で学習できる

マーカーをつけて、カメラで撮影して正しく動いているかを判定する

プログラミングしたほうが早いのではないか? ちょっとしたズレを見抜いて最適なものをやってくれる

反復運動に特化しているかもしれない

ボルダリングコース作成支援アプリケーション

課題帳にコースが表示されている 身長によって向き不向きなコースがある

  • ホールド難易度の推定
  • コース作成支援
  • 身長情報の反映

折り紙

折り紙技術を利用する

Crane

複雑な折り紙アート

変形を構造で制御する

剛体折り紙

折り紙の本質

  • 平面から立体へ
  • 硬くなる
  • 動きの制御
    • 一箇所を動かすと全体が動く

折り紙技術は実用化されていない 作るのが難しいから

頂点の周りの角度の総和が 2π になるような制約条件がある

製造用データのソフトウェア CAM がない

厚みが障壁となる 厚み処理ソフトが存在しない

Rhinoceros + Grasshopper を使う

macOS で動かす C コンパイラを C で作った

LISENCE と LICENSE 、正しいスペルがどっちかわからない。どうも、かわしんです。正解は LICENSE です。

僕は、よく MIT ライセンスを使います。気が向いたら WTFPL( Do What The F*ck You Want To Public License )を使います。趣がありますよね。

さて、僕の実家は山口にあるのですが、年末の帰省のタイミングで C コンパイラを作りました。正確には去年の 12月 30 日の東京発博多行き新幹線のぞみ号に乗った時から、今年の 1 月 4 日の夜までです。新幹線は片道5時間くらい乗ってるので開発にうってつけです。本当は東京に戻ってきたらやめると決めてたんですが、キリが悪かったので1日延長して昨日までやってました。

去年の夏あたりに Rui Ueyama さんが作った 9cc が話題になり、僕もいつか作ってみたいなと思っていました。

年末にまとまった時間が取れて、流石にそろそろ C 言語を使えるようにならないといけないと思っていたので、C 言語を理解するために C 言語を C 言語で実装してみました。

出来上がったのはこれです。MIT ライセンスです。

github.com

結局セルフコンパイルまではたどり着きませんでしたが、テストコードをコンパイルするところまでできて、キリがよかったのでここで一旦やめることにしました。

実装の方針

11 月のはじめに Rui さんが コンパイラを作る教科書の最初の部分 を公開されました。

この教科書で初歩的なコンパイラが作るところまでサポートしてくれるのでこの教科書に沿って実装を進め、そのあとは 9cc の実装などを参考に進めることにしました。

また、その後の開発の順番はこの記事にオススメの開発の順番が書かれているのでそれを参考にマイルストーンとしました。

Cコンパイラ制作の夏期集中コースが思っていた以上にうまくいった話|Rui Ueyama|note

この記事では開発の順番として 配列 を実装してから ポインタ を実装することがオススメされていますが、配列はポインタのように扱われるので、まず ポインタを実装してから配列を実装する のがいいと思いました。僕は一回配列から実装したのですがうまく行かず、実装を捨ててポインタから実装し直してから配列を実装しました。

また、これは重要な点なのですが、この教科書は スタックベースのコンパイラ を作るのに対して 9ccレジスタベースのコンパイラ です。そのため構文解析や意味解析までは参考になりますが、アセンブリ言語への変換はあまり参考になりません。

そのため、スタックベースのコンパイラはセキュキャンのコースで一番早く実装が終わったという 艮 鮟鱇 さんの aqcc を参考にしました。ただ、コードベースが結構違うのでアセンブリへの変換のところあたりくらいしか読んでません。

今回は、macOS 上で動くスタックベースの C コンパイラ を作りました。

工夫した点(配列の扱い)

一番工夫したのは 配列の扱い です。以下の解説では、9cc のテストを C で書き直した時点のコミット と僕の kcc の比較として解説します。

C 言語では配列はポインタと同じように扱われます。値へのアクセスは、配列・ポインタ共に配列風のアクセス( a[1] )とポインタ風のアクセス( *(a+1) )ができます。

しかし、ポインタに配列を代入できますが、配列へは配列を代入することもポインタを代入することもできません。

int a[10];
int *b;
b = a;  // OK
// a = b; // NG

a[0] = 1; a[9] = 10;
b[0];    // 1
b[9];    // 10
*a;      // 1
*(a+9); // 10

void tmp(int *x) {
    // do something
}
tmp(a); // OK

では違いは何かというと、変数が宣言された時の挙動とその変数が指し示すものです。

ポインタはその変数が宣言されるとアドレスを格納するのに必要なサイズのメモリ( 8 バイト )が確保されます。ポインタ変数が指し示す値はアドレス値です。

一方、配列はその変数が宣言されると配列の長さ分のメモリ( 型のサイズ * 配列の長さ )が確保されます。配列変数が指し示す値は配列の先頭要素です。

9cc では、配列風のアクセスとポインタ風のアクセスは共に同じように ND_DEREF として構文解析 されています。

// 配列アクセスの構文解析
while (consume('[')) {
  lhs = new_expr(ND_DEREF, new_binop('+', lhs, assign()));
  expect(']');
}

// ポインタアクセスの構文解析
if (consume('*'))
  return new_expr(ND_DEREF, mul());

そして意味解析の中ではこれら2つのアクセス手法は扱われていますが、ND_DEREF の対象は ポインタに対するアクセスに限定 され、それ以外はエラーになるように実装されています。

配列へのアクセスをポインタに対するアクセスとして読み替えるために、意味解析の中の maybe_decay() で、配列へのアクセスノードと ND_DEREF ノードの間に ND_ADDR ノードを差し込んでポインタアクセスに変換しています。

ただし、代入では配列の値に直接書き込む必要があるのでポインタに変換してはいけません。そのため、decay という対象ノードが代入として扱われているかを示すフラグを意味解析の全てに引き回して decayfalse の時は ND_ADDR ノードの差し込みを行わないように実装されています。

そのために再帰的に意味解析を行う walk() 関数のインターフェイスも変更されています。

// 配列のない時のインターフェイス
static void walk(Env *env, Node *node)

// 配列の解析が含まれた時のインターフェイス
static Node *walk(Env *env, Node *node, bool decay)

decay というフラグでコンテキストを引き回すのと、構築された AST を差し替えるのがなんとなく複雑だなと思ったのでなんとか工夫できないかを検討しました。

ポイントは、配列とポインタは同じように扱われる ということです。

9cc では、意味解析ステップAST の配列アクセスノードをポインタアクセスノードに差し替える ことで、配列とポインタを同じように扱っています。しかし、コンテキストを引き回したり AST を差し替えるため、ソースコードはやや複雑になっています。

僕の kcc では、AST からアセンブリの変換ステップ配列の値へのアクセス命令をアドレスの読み込み命令に切り替える ことで、配列とポインタを同じように扱っています。これにより、意味解析ステップでは以前と同じインターフェイスを保ち、アセンブリへの変換は ND_IDENTND_DEREF の処理を 配列へのアクセス時に切り替える条件分岐を入れる だけで済みます。

この方法では、配列へのアクセスが代入なのか値へ読み込みなのかのコンテキストを意識する必要がない ため実装が複雑になりません。

まだ、kcc は最適化などが最後まで実装できていないので本当にこの方針でいいのかはわかりませんが、とりあえず多次元配列の場合も含めてテストは通っているので大丈夫じゃないかと思っています。

macOSLinux の非互換性

教科書、9ccaqcc は全て Linux 上で動かすことを想定していると思います。確かに、Docker とか vagrant を使えばよかったんですが、やっぱりローカルで動かしたいなという軽い気持ちで macOSコンパイルするコンパイラを作ることにしました。

教科書には、macOSLinux の違いはラベルの書き方が先頭に _ をつけるようになるくらいのノリで書いてありましたが、教科書に載っている範囲を越えると割と非互換が多いのでハマります。(今教科書を確認したら、修正されて macOS は対象外になったようです。)

僕がハマった macOSLinux との違いをここで紹介しておきます。もし macOS で作る場合は参考にしてみてください。

Makefile

Makefile で複数ファイルから実行バイナリを生成する 9cc: $(OBJS) の部分が mac に標準で用意されている make コマンドでは動きません。

ターゲット名だけでコンパイルする時はターゲット名と同じ .c ファイルが必要だったみたいです。

代わりに直接 gcc を呼び出すようにして解決しました。

CC=gcc
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

kcc: $(OBJS)
    $(CC) -o $@ $(OBJS) $(LDFLAGS)

グローバル変数の扱い

アセンブラではグローバル変数は、.data セクションに確保してラベル経由でアクセスします。

Linux ではグローバル変数のアドレスは、lea 命令を使って取得します。

しかし、macOS では lea はエラーになります。

error: 32-bit absolute addressing is not supported in 64-bit mode
  lea rax, .L.str474

macOS では、グローバルなラベルへのアドレスはグローバルなラベルテーブル経由( GOTPCREL )で引いてくる必要があります。

これは、グローバル領域のメモリは再配置されることがありアドレスの絶対値を持つことができないかららしいです。(macos - Why does this movq instruction work on linux and not osx? - Stack Overflow

また、Apple の公式ドキュメントにも GOTPCREL のサンプルコードが載っていましたが AT&T 記法であったため、それを Intel 記法にするのにも苦労しました。その苦労の結果がこれです。

  mov rax, [label@GOTPCREL + rip]

これで、グローバル領域のラベルのアドレスを rax に読み込むことができます。

stderr

テストコードの中fprintf() でエラー出力するために extern int *stderr; が宣言されています。

Linux では、stderr は、_IO_FILE のポインタ変数です。

# Ubuntu 18.04 + gcc 環境
$ cat /usr/include/stdio.h | grep stderr
extern struct _IO_FILE *stderr;     /* Standard error output stream.  */
#define stderr stderr

しかし、macOS では stderr はマクロです。そのため僕は printf() 関数をエラー出力に追加ました。

今考えると stderr の代わりに __stderrp でよかったのかもしれないですが。

# macOS 10.14.2
$ cat /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/stdio.h | grep stderr
extern FILE *__stderrp;
#define stderr  __stderrp

スタックサイズ

これは macOSLinux の違いではなく両方とも対応する必要があると思いますが、スタックのサイズは 16 の倍数にアライメントされている必要があります。これに結構ハマりました。

printf を呼び出すテストでローカル変数を定義するとなぜか make: *** [test] Segmentation fault: 11 のエラーが発生し、llvmデバッグ実行すると stack_not_16_byte_aligned_error エラーが発生していたのでわかりました。

$ lldb ./tmp-test
(lldb) target create "./tmp-test"
Current executable set to './tmp-test' (x86_64).
(lldb) run
Process 69817 launched: './tmp-test' (x86_64)
Process 69817 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
    frame #0: 0x00007fff59c5cc56 libdyld.dylib`stack_not_16_byte_aligned_error
libdyld.dylib`stack_not_16_byte_aligned_error:

デバッガを使えば一発でわかるエラーですが、デバッガを使う心理的障壁が高くてなかなか原因がわかりませんでした。

今後

やったことと未対応のことは以下の issue にまとめました。

Issues · Issue #1 · kawasin73/kcc · GitHub

あとは、大まかに以下のような項目が残っています。

ここまでやった感想としては、楽しかったのですが新しい型や演算子の対応は「やるだけ」という感じでめんどくさくなってきました。

テストを kcc でコンパイルできるところまでできたのでもういいかなという感じです。

時間があったら struct は実装しておきたいところです。

最後に、9ccCコンパイラの教科書 を無料で公開してくださった Rui Ueyama さんには深く感謝する次第です。ありがとうございました。

作る人と使う人

この記事は、PSI(東京大学工学部システム創成学科知能社会システムコース) Advent Calendar 2018 の 25 日目です。

はじめに

この記事は、僕がどんなエンジニアになりたいと思っているのかをつらつらと書くポエムです。

この考えを誰かに押し付けるつもりもありませんし、この考えが完全に正しいと主張している訳でもありません。「こういう考え方もあるんだな」程度に思っていただければ嬉しいです。

ここでのエンジニアは主に Web 系とかのソフトウェアエンジニアとかを想定しています。

作る人と使う人

エンジニアはプロダクトを作ります。そしてユーザーがそのプロダクトを使います。プロダクトには、作る人(エンジニア)と使う人(ユーザー)がいます。

同じようにエンジニアの世界にも作る人と使う人がいます。様々なフレームワークやライブラリを作る人と使う人です。

ライブラリを 作るエンジニア にはライブラリのインターフェイスやライブラリ自体のパフォーマンス、フレームワークの使い方などを洗練させるために高い技術力や経験が必要とされます。

そして、現代の web 系のアプリやサービスは OSS として世の中(github など)に転がっているライブラリやフレームワークを使い、組み合わせて作ることができます。

ライブラリを 使うエンジニア はライブラリやフレームワークの使い方をドキュメントなどで理解して、ライブラリ同士をつなぎ合わせるコードを書くだけでアプリやサービスが出来上がります。

そう、アプリケーションを作るのはとても簡単になってきています。それはエンジニアがより楽をしようとする生き物で、開発を楽にするライブラリやフレームワークをどんどん開発しているからです。

それによってアプリケーションを作るエンジニアには技術力はだんだんと必要とされなくなってきています。例えば、RailsWebサービスを作る上では TCP ソケットがどのように扱われているかや、Ruby ではどのようにメモリが管理されているかを気にしなくても動くアプリケーションが作れます。大学でコンピュータサイエンスを学ばなくても誰でもエンジニアになることができるようになってきました。

その一方でライブラリを 使うエンジニア にはライブラリをうまく使ってユーザーにとっての価値を創出する、ビジネス力や UX などのデザイン力が重要になってきていると思います。

これはとても素晴らしいことだと思います。誰でも自分の作りたい物を簡単に作れるようになるのは人類の生産性や創造性を向上させます。これからロボットや AI が発展していき人間が事務作業から解放された時に、自由になった時間を使って行う創造的活動を支える土台となります。

決して、作るエンジニア使うエンジニア より偉いと言っている訳ではありません。それぞれの役割が異なるだけです。作るエンジニアはエンジニアを相手にして高い生産性をもたらします。使うエンジニア は一般的なユーザーを相手にして新しいビジネス価値を生み出します。

そして、作る人と使う人は 0:100 で完全に別れている訳ではありません。使うエンジニアは、自分に必要な機能を持ったライブラリがない場合は自分でそのライブラリを作ればいいですし、作るエンジニア は、使うエンジニアがどのようにそのライブラリを使うかを知る必要があります。両方の役割を持ったエンジニアが多いのではないでしょうか。

使うだけのエンジニアでいいのか

しかし、使うだけで作ることができないエンジニアでは作ることのできるアプリケーションが限られてきます。

一般的なアプリケーションを作る上では世の中に転がっている OSS を組み合わせるだけでアプリを作ることはできるので、困ることは少ないと思います。

ただし、作りたいアプリケーションの要求を満たすライブラリがなかった時に、ライブラリを作ることができないエンジニアはそのアプリケーションを作ることを断念することになります。

技術が要因で作れたかもしれないアプリを作れなくなってしまうことはとても悔しいことです。

2 年前は僕は 使うだけのエンジニア でした。Rails サービス・iOS アプリ・Android アプリの開発、Docker を使った開発環境の構築、Terraform での AWS クラウド環境の構築など、一人前とは言いませんがフルスタックエンジニアとして自信を持っていました。

しかし、それらは全て既存のライブラリやフレームワークを使って何かを作るエンジニアで、作りたいアプリに必要なライブラリがない場合にはそのアプリは作れませんでした。

自分のその状況に危機感を抱いて、DMM にミドルウェアを作るインターンにいきました。DMM にきて早 1 年と半年が過ぎ全然成果が出せていなくて苦しんでいますが、インターンではデータベースを作ったり、分散システムの設計をさせてもらっています。

作るエンジニアになるために

使うだけのエンジニア から 作ることもできるエンジニア になるために、何かライブラリを作りたくなりますがどんなライブラリを作ればいいのでしょうか?作っても使われるとは限らないですし。

それは 自分が必要なアプリを作ってそのアプリに必要なライブラリを作る ということだと思います。

自分に必要なアプリとそれに必要なライブラリを作ることでモチベーションを保ち続けることができます。また、自分がそのライブラリのユーザーになるので使いやすいインターフェイスを自分で実験しながら試行錯誤することができます。

自分のアプリに必要なライブラリがすでにある場合はそのライブラリを無条件で採用するのではなく、その 中身をよく読んでみてパフォーマンスや使いやすさなどに課題がないかどうかを検証してみる のがいいと思います。もし、何かの課題があれば自分でより良いライブラリを作ることができます。既存のライブラリのソースコードを参考に作ることができるので障壁も低いです。

世の中にあるものだけで作るのではなく、世の中に足りないものがあったら作って利用する という姿勢が作るエンジニアになるためにはいいと思います。

僕の場合は、彼女が薬を飲むのを忘れないように Go 言語でリマインダー LINE bot の「管理上手のうさちゃん」を作りました。(詳しくは以下の記事で紹介しています)

qiita.com

この LINE bot を作る上で Go 言語のスケジューラが必要になり、既存の github スター数の多い Go のスケジューラライブラリ 3 つのソースコードを読みました。

その結果、それぞれのライブラリにパフォーマンス上の課題があることに気づき、それを解決する新しいスケジューラライブラリ /kawasin73/htask を作りました。(詳しくは以下の記事で紹介しています)

qiita.com

また、管理上手のうさちゃんを動的 IP 割り当てをされる自宅サーバーで運用するために、wanpoll という DNS の自動登録エージェントを作成しました。

qiita.com

このような感じで、必要だけど世の中にないから諦めるのではなく作ってみるという姿勢がいいと思います。

自分の目指すエンジニア像

この1年半ずっとミドルウェアなど、アプリケーションから離れた物を作ったり設計したりしてきました。この経験を通じて思ったのは、やっぱりユーザーが近いプロダクトを作るのが楽しいということです。

ハードウェアやコンパイラ、言語そのものの開発などの低レイヤーというよりは、それを具体的に誰かが使って価値を感じてもらえるアプリケーションに近いレイヤーのエンジニアが僕は楽しいと思えるようになりました。

アプリケーションを作る上で必要なライブラリやミドルウェアがない場合は、自分でそれを作ることが選択できるエンジニアになりたいです。

既存のライブラリに縛られることなく、自分の手でパフォーマンスと UX を追求していける、世の中にあるものだけで作るのではなく、世の中に足りないものがあったら作って利用する、そんなエンジニアが僕の理想像です。

参考

Webpackerを過去の遺物(1.2)から現代(3.5.5)にバージョンアップする

この記事は、Ruby on Rails その2 Advent Calendar 2018 の 22 日目です。

1 年半前の遺物

約 1 年半前に作った Rails プロジェクトがありました。

受託で 2017 年 4 月に僕 1 人で開発をはじめ、その年の 6 月に僕 1 人で開発を終えたプロジェクトです。

当時は、Rails5.1.0.rc1 から 5.1.0 にアップデートされてリリースされ、webpacker は 1.1 から 1.2 にアップデートされたあたりの時期でした。

その 6 月に開発を終えて heroku にデプロイされたそのアプリはその後大きな改修もなく 放置され 粛々と運用されていました。

その後新しい機能の追加を行う予定がなかったため放置していたプロジェクトですが、突然そのアプリをベースにして新しいビジネスを始めることになりました。

そして、1 年半前の遺物の開発が再び動き出したのです。

1 年半前の遺物を再開発する

2018 年 12 月現在、Rails5.1.0 から 5.2.2 に進化し、webpacker に至っては 1.2 から 3.5.5 まで進化していました。

ライブラリの古いバージョンを使い続けることは、ライブラリの脆弱性のリスクのみならず、最新の開発手法を利用できないために開発効率が上がらず開発スピードの低下にも繋がります。

特にフレームワークである Rails や webpacker では開発効率の低下の影響が大きいです。

時代に取り残されたプロジェクトを最新のバージョンに追随させる作業を 2 日間やっていましたが、その中で一番の大敵だった webpacker1.2 から 3.5.5 へのアップデートの詳細をここで紹介したいと思います。

webpacker とは

webpacker は、Rails で webpack を使ったフロントエンド環境の構築をサポートしてくれるライブラリです。

webpacker は Rails 向けの webpack の設定ファイルの自動生成や、webpack でビルドされた js ファイルや css ファイルと Rails の View テンプレートをバインディングしてくれるヘルパーの提供などをするライブラリです。

webpack をはじめとしたモダンな Web フロントエンド開発環境を簡単に Rails の中で使えるようになる便利なライブラリです。

ただ、webpack の設定を隠蔽しているため細かい調整をしようとすると逆にややこしくなったり、最新の webpack を使えないというデメリットもあり、Web フロントエンジニアのリソースが豊富な場合は素の webpack を使うというプロジェクトもあるようです。

いかんせん僕は 1 人で開発しているので webpack と Rails の橋渡しの部分の設定を任せるために webpacker を使っています。

また、heroku では webpacker を検出して自動で npm モジュールのインストールや webpack のコンパイルとアセットファイルの設定を行ってくれます。そのデプロイの容易さも heroku + Rails 環境で webpacker を使うメリットです。

webpacker 1.23.5.5 の違い

まず、webpacker をアップデートする上で設定ファイルなどのファイル構成がどう変わったのかを知る必要があります。

Rails のバージョンの差異は、RailsDiff という Web サイトで容易に確認することができますが、webpacker ではそのようなサイトは発見できなかったので自分で差異を調べることにしました。

Ruby 2.4.5 + Rails 5.1.0 + webpacker 1.2Ruby 2.4.5 + Rails 5.1.0 + webpacker 3.5.5 のそれぞれで rails new をしてプロジェクトを作成してそのファイル構成の差分を取ることにしました。

プロジェクトの作成には、docker で rails の開発環境を作成する自前の rails_docker_template を利用しました。( Rails プロジェクトを Docker で開発したい場合は参考にしてみてください。)

それによって2つのバージョンの rails new を試してみました。内容は以下のリポジトリにアップロードしてあります。

github.com

以下のスクリプトでプロジェクトを作成しました。

$ script/init

// webpacker のバージョンを指定してインストール

$ bin/rails webpacker:install
$ bin/rails webpacker:install:react

git diff の結果は以下の通りです。

Diff between 1.2 and 3.5.5 · Issue #1 · kawasin73/webpacker_diff · GitHub

$ git diff ruby-2.4.5-rails-5.1.0-webpacker-1.2 ruby-2.4.5-rails-5.1.0-webpacker-3.5.5 --name-only
.babelrc
.gitignore
.postcssrc.yml
Gemfile
Gemfile.lock
bin/webpack
bin/webpack-dev-server
config/environments/development.rb
config/environments/production.rb
config/secrets.yml
config/webpack/configuration.js
config/webpack/development.js
config/webpack/development.server.js
config/webpack/development.server.yml
config/webpack/environment.js
config/webpack/loaders/assets.js
config/webpack/loaders/babel.js
config/webpack/loaders/coffee.js
config/webpack/loaders/erb.js
config/webpack/loaders/react.js
config/webpack/loaders/sass.js
config/webpack/paths.yml
config/webpack/production.js
config/webpack/shared.js
config/webpack/test.js
config/webpacker.yml
package.json
yarn.lock

ただ git diff をしても CLI ではその差異がわかりにくかったので、SourceTree という GUI の git クライアントアプリでその差分を見てみました。

f:id:kawasin73:20181222230438p:plain

なるほど。

これで設定ファイルのどれが不要になってどれが追加され、どれが中身が変更されたのかがわかりました。

公式のアップデートコマンド

webpacker の README ( https://github.com/rails/webpacker#upgrading )でバージョンアップするためのコマンドが紹介されています。

bundle update webpacker
rails webpacker:binstubs
yarn upgrade @rails/webpacker --latest
yarn add webpack-dev-server@^2.11.1

# Or to install a latest release (including pre-releases)
yarn add @rails/webpacker@next

これを、webpacker 1.2 のプロジェクトに対して実行し 3.5.5 までアップデートしてみました。その差分は以下のコミットです。

Upgrade webpacker to 3.5.5 · kawasin73/webpacker_diff@c41fc94 · GitHub

これによると以下のことがわかります。

  • bin/webpackbin/webpack-dev-server というスクリプトの中身が変更されており rails webpacker:binstubs を実行することによって上書き変更される
  • @rails/webpacker という謎の npm パッケージが使われるようになっている。
  • webpack-dev-server2.11.1 でバージョン固定されている。
  • 設定ファイルの追加や削除、修正はされない

謎の npm パッケージ @rails/webpacker

ここで、@rails/webpacker という謎の npm パッケージがインストールされていることが発覚しました。その中身は以下の開発支援用のパッケージの集合です。

@rails/webpacker - npm

Dependencies (25)

  • babel-core
  • babel-loader
  • babel-plugin-syntax-dynamic-import
  • babel-plugin-transform-class-properties
  • babel-plugin-transform-object-rest-spread
  • babel-polyfill
  • babel-preset-envcase-sensitive-paths-webpack-plugin
  • compression-webpack-plugin
  • css-loader
  • extract-text-webpack-plugin
  • file-loader
  • glob
  • js-yaml
  • node-sass
  • optimize-css-assets-webpack-plugin
  • path-complete-extname
  • postcss-cssnext
  • postcss-import
  • postcss-loader
  • sass-loader
  • style-loader
  • uglifyjs-webpack-plugin
  • webpack
  • webpack-manifest-plugin

Dev Dependencies (6)

  • eslint
  • eslint-config-airbnb
  • eslint-plugin-import
  • eslint-plugin-jsx-a11y
  • eslint-plugin-reactjest

このパッケージのほとんどは webpacker 1.2 では package.json に直接記載されてインストールされていたものです。それを @rails/webpacker にまとめたものであると理解しました。

しかし、開発支援用のパッケージのうちビルドに必要なパッケージがが Dev Dependencies ではなく Dependencies としてインストールされているのはちょっと気持ち悪いです。

この理由は以下の issue で議論されている通り production 環境で js ファイルのビルドをできるようにするために Dependencies に配置されているようです。

Webpack executable not found on production · Issue #117 · rails/webpacker · GitHub

ここを独自にわざわざ Dev Dependencies に変更して本来の Dependencies のあり方を求めるより、Rails way にのっとってパッケージ管理を webpacker の内部に隠蔽して開発をスムースに進めることのメリットが大きいと判断して @rails/webpacker パッケージをそのまま使うことにしました。

アップデートの方針

アップデートは以下のように行うことにしました。設定ファイルの更新は自動ではやってくれないので自分で1ファイルずつ編集していきます。

webpacker のアップデート

Gemfile の webpacker3.5.5 にあげてアップデートします。

$ bundle update --conservative webpacker

アップデートコマンドで上書きするファイル

$ bin/rails webpacker:binstubs

このコマンドを実行することで以下のファイルが更新されます。

  • bin/webpack
  • bin/webpack-dev-server

追加するファイル

以下のファイルを追加します。ファイルの内容は webpacker 3.5.5 でビルドしたもの からコピーします。

  • config/webpack/environment.js
  • config/webpacker.yml

削除するファイル

以下のファイルを削除します。

  • config/webpack/configuration.js
  • config/webpack/development.server.js
  • config/webpack/development.server.yml
  • config/webpack/loaders/assets.js
  • config/webpack/loaders/babel.js
  • config/webpack/loaders/coffee.js
  • config/webpack/loaders/erb.js
  • config/webpack/loaders/react.js
  • config/webpack/loaders/sass.js
  • config/webpack/paths.yml
  • config/webpack/shared.js

修正するファイル

以下のファイルを 1.23.5.5 の差分をみて修正していきます。差分は Diff between 1.2 and 3.5.5 · Issue #1 · kawasin73/webpacker_diff · GitHub にまとめてありますが、SourceTree などの GUI アプリで差分を見た方がわかりやすいと思います。

  • .babelrc
  • .gitignore
  • .postcssrc.yml
  • config/webpack/development.js
  • config/webpack/production.js
  • config/webpack/test.js
  • config/environments/development.rb
  • config/environments/production.rb

package.json

1.23.5.5 の差分をみて package.json から @rails/webpacker パッケージにまとめられるパッケージを削除します。( Diff between 1.2 and 3.5.5 · Issue #1 · kawasin73/webpacker_diff · GitHub

そのあと、以下のコマンドで @rails/webpacker をインストールし、webpack-dev-server@^2.11.1 をインストールします。

$ bin/yarn add @rails/webpacker
$ bin/yarn add webpack-dev-server@^2.11.1

以上で webpacker のアップデートは完成です。

最後に

ここまで慎重に調査するのに疲れましたが、なんとか webpacker を 1.2 から 3.5.5 にアップデートできました。

これは、プロジェクトを作った時に webpacker の設定を独自に変更せずにそのまま使っていたのも功を奏していると思います。

おそらく、webpacker の 1.2 なんていう過去の遺物を使っているプロジェクトは少ないんじゃないかと思いますが、アップデートする時は参考にして見てください。

現場からは以上です。

Mac で起動可能な Windows 10 の USB イメージを作る

この記事は、PSI(東京大学工学部システム創成学科知能社会システムコース) Advent Calendar 2018 の 22 日目です。

はじめに

東大の応用プロジェクトという授業で、LabVIEW というソフトウェアを使ってセンサーアプリケーションを作ることになりました。

しかし、大学から支給される Windows PCが遅い。信じられないくらい遅い。

LabVIEW を立ち上げるのに10分とかかかります。平気で。

それが許せなくて自分のパソコンで LabVIEW をやりたくなりました。ところが、macOS しか持っていない僕はインストールできない。(LabVIEW 自体は macOS にもインストールできるみたいですが、ライセンス関係がめんどくさそう)

さらに、他の授業でも Window でしか動かないソフトウェアを使うことがあり(ここで支給される PC も遅い)、自分も Windows が使える環境があると便利なのでインストールを試行錯誤しました。

というか、東大はまともな PC を用意してくれ。

Boot Camp

MacWindows をインストールする一般的な方法として BootCamp があります。Mac を買った時からデフォルトでインストールされているアプリで、Windows をインストールしてデュアルブートを可能にしてくれます。

Boot Camp を使って Mac に Windows をインストールする - Apple サポート

しかし、重大な欠点があります。それは、マシンのディスクのパーティションを切ってそこにインストールする ことです。わざわざ Windows のためにマシンのリソースを汚染されたくない。

USB にブートイメージをインストールして Mac を汚染せずにポータブルな Windows USB を作りたいというのがこの記事の趣旨です。

Windows To Go

Windows を USB にインストールする手法として Windows Enterprise で提供されているらしい 「Windows To Go」 というソフトウェアがあるらしいです。しかし、Windows Enterprise 持ってないので使えない。

さらに調べると、AOMEI Partition Assistant とかいう怪しげなソフトウェアで Windows To Go という機能が搭載されていて USB に Windows をインストールできるらしい。便利!しかも、Standard 版は無料!

Windows 10 To Go USBを作成してポータブル作業環境を取得します

早速インストールしてみたら、Windows To Go は有料版でないといけないらしい。5000円くらいするけど早速買ってやってみました。

が、Mac で起動しても途中で落ちて macOS にフォールバックしてしまい、役には立ちませんでした。クソが

90 日間返金可能ということなので返金してもらいました。(英語の対応だったけど如何に役に立たなかったかを説明したらちゃんと返金してくれた。)

自分でゴリゴリやる

色々思考錯誤したり、記事を探したりする中でこの記事に出会いました。

ohaohaoha.cocolog-nifty.com

ここで紹介されている方法を参考にやったらうまくいきました。マジでありがとうございます。

ちなみに、この記事で紹介されていたのは Windows マシンでインストールする方法ですが、今回は Mac しか持っていない人向けにアレンジしています。

諸事情あって 2 回 Windows をインストールしたのですが、1回目はこの記事の通り Windows マシンでインストールして、2 回目は Mac だけでインストールしたので、正しく動くことは確認しています。

必要なもの

Mac

まず、何らかの Mac が必要です。

僕の Macbook Pro のスペックはこんな感じです。

f:id:kawasin73:20181217222428p:plain

USB メモリ

次に USB が 2 本必要です。 1 本はインストーラ用、もう 1 本が Windows ポータブル USB になる本番用です。

インストーラ用には、以下の 64 GB の USBを

本番用には、同じ USB の 128 GB のやつを買いました。

2本ともまぁまぁ高いですが、書き込み性能が 100MB / s 以上出るので OS として使うために必要な経費ということで泣く泣く買いました。 Windowsインストーラは 4 GB くらいあるのですが、高速な書き込み性能を持っているのでインストールも比較的早く終わりました。

ぶっちゃけ、インストーラ用の USB は本番用の USB が完成したら必要ないので、30GB くらいの安いものでもいいと思います。(コピーが遅いかもしれないけど)

あと、2本の USB は容量が違ったほうが見分けがついて便利です。

Windows ライセンス

そして Windows の ISO ファイルとライセンス が必要です。

Windows のライセンスは調べてみると 1 万円は超えるみたいです。高い。

ただ、東京大学Microsoft 製品を無償で学生に提供していて、Windows のライセンスもあったのでそれを利用してライセンスを取得しました。

UTokyo Microsoft Windows 10 for students | 東京大学

ISO ファイルは、東大のライセンスを購入したページにしたがってダウンロードしました。

それ以外の場合は、以下のリンクからダウンロードできるようです。

Windows 10 のディスク イメージ (ISO ファイル) のダウンロード

今回は、Microsoft Windows 10 Education をインストールしましたが、他のエディションでも基本的にインストール方法は変わらないと思います。

根気

ディスクコピーには時間がかかりますし、オペミスでディスクを失う可能性もあるので細心の注意が必要です。

根気強くやっていきましょう。

免責

ディスクを触るコマンドがあるので自己責任でお願いします。

インストール手順

大まかな手順は以下の通りです。

  1. macOSインストーラ用 USB をフォーマット
  2. インストーラ用 USB にインストーラモードの Windows をコピー
  3. インストーラ用 USB から Windows を起動
  4. 本番用 USB を diskpartwindows のコマンド)を使ってフォーマット
  5. 本番用 USB に Windows 10 をインストール
  6. macOS に切り替えて、Boot Camp Windows サポートライブラリ をダウンロードし、インストーラ用 USB にコピー
  7. 本番用 USB で Windows 10 を起動
  8. Windows 10 に Mac 用の様々なドライバーを Boot Camp Windows サポートライブラリ を使ってインストール
  9. Windows 10 のライセンス認証

かなり長いですが、頑張って行きましょう。

1. macOSインストーラ用 USB をフォーマット

macOSインストーラ用 USB を差した状態で、ディスクユーティリティ アプリを開きます。

USB を選択した状態で上にある 消去 ボタンをクリックし、以下の項目を入力して 消去 ボタンを押して USB をフォーマットします。

  • 名前:Windows(これは別の適当なものでもいいです)
  • フォーマット:exFAT(インストールするファイルサイズが大きいのでこれが必要です)
  • 方式:マスター・ブート・レコードGUID パーティションマップ でも大丈夫だと思いますが、今回はこっちで)

f:id:kawasin73:20181217231520p:plain

注意としてこれによって USB ディスクの中身は全て失われます。また、間違って別のディスクを消去することがないように 気をつけてください。

2. インストーラ用 USB にインストーラモードの Windows をコピー

Finder で Windows の ISO ファイルをダブルクリックして開きます。

ISO ファイルの中身が表示されるので、中身を全てコピーして、フォーマットした インストール用 USB の一番上のルートディレクトリにペーストします。この操作は Finder アプリ上で行います。(dd を使ってやってもうまくいきませんでした。)

かなり内容が大きい上に多いので時間がかかります。僕の環境では、10 分くらいかかりました。その間に洗濯物でも干しておきましょう。

3. インストーラ用 USB から Windows を起動

ここで一旦 Mac をシャットダウンします。

そして、インストーラ用 USB だけを差した状態で alt キー(または option キー)を押しながら起動します。音がするまで alt キーを押していると起動ディスクを選択する画面が表示されます。

オレンジ色の EFI Boot を矢印キーで選択して Enter キーを押してインストーラWindows を起動します。

f:id:kawasin73:20181217233132j:plain

Windows が起動するはずです。初期化が終わると以下のような画面が表示されるので 次へ ボタンを選択します。

f:id:kawasin73:20181217233519j:plain

ちなみ画面サイズがバグってるので文字がとても小さいです。この文字が小さい地獄はステップ 8 で Macデバイスドライバをインストールするまで続きます。

「今すぐインストール」のページが表示されたら、今すぐインストールせずに左下の コンピューターを修復する をクリックします。

f:id:kawasin73:20181217233941j:plain

トラブルシューティング を選択し、

f:id:kawasin73:20181217234458j:plain

コマンドプロンプト を起動します。このコマンドプロンプトは管理者権限で起動されます。

f:id:kawasin73:20181217234558j:plain

4. 本番用 USB を diskpart を使ってフォーマット

ここで、本番用 USBMac に差し込みます。

diskpart とは、Windows のディスクをフォーマットするコマンドです。(多分)

起動したコマンドプロンプトdiskpart と入力して Enter を押すと diskpart の画面に切り替わります。

diskpart

diskpart の画面では、先頭に DISKPART> が表示されます。これ以降のこの節のコマンドは、diskpart の中でのコマンド実行です。

list disk コマンドでディスクの一覧を表示し、本番用 USB のディスク番号を確認します。USB のディスクサイズが違っているとわかりやすいです。

select disk <number> でディスクを選択します。僕の環境では、3 番でした。

list disk をもう一度実行し、選択したディスクの左側に白い * が表示されて正しく選択できていることを確認します。

もし、異なるディスクを選択していた場合 Mac のディスクが吹っ飛ぶ可能性があるので十分注意してください

list disk
select disk 3
list disk

clean で選択されたディスクを初期化します。

create partition primary size=350ブート用パーティション領域350 MB)を作った後、create partition primary で残りの領域のパーティションを作成します。

create partition するときに、エラー(DiskPart は最新の状態でないオブジェクトを参照しています・・・・)が発生することがあります。その時は、diskpart で rescan を実行して、最初の list disk からやり直して下さい。

それでもうまくいかない場合は、exit で diskpart を終了して、再度 diskpart を実行するところからやり直してください。(それでもうまくいかない場合は知らん

clean
create partition primary size=350
create partition primary

list partitionパーティションを確認し、パーティションが 2 つ作成されていることを確認します。

select partition350 MB のブートパーティションを選択し、format fs=fat32 quick でフォーマットし、active でアクティベートし、assign letter=b で、B ドライブとして設定します。

次に、select partition 2 でメインパーティションを選択し、format fs=ntfs quick でフォーマットし、assign letter=o で、O ドライブとして設定します。

list partition
select partition 1
format fs=fat32 quick
active
assign letter=b

select partition 2
format fs=ntfs quick
assign letter=o

雰囲気としてはこんな感じです。(画質が悪くてすみません)

f:id:kawasin73:20181218000435j:plain

これで、本番用 USB のフォーマットは完成です。exit で diskpart を抜けます。

exit

5. 本番用 USB に Windows 10 をインストール

そのまま、コマンドプロンプトWindows 10 をインストールしていきます。

Windows のイメージファイルは、install.wim か、install.esd というファイルです。どちらでも同じようにインストールすることができるらしいです。

僕の環境では install.wim だったので、それがない場合は install.esd と読み替えてください。

まず、install.wim を探します。install.wim はステップ 2 でコピーした ISO ファイルの sources ディレクトリの下にあります。まず、コピーした USB のディスクドライブを探します。

wmic logicaldisk get caption で利用可能なディスクドライブの一覧が表示されます。

wmic logicaldisk get caption

Caption
B:
C:
D:
O:
X:

BO は、さっき作ったドライブで、X は現在いるドライブです。僕の環境では、C ドライブに install.wim がありました。dir C:¥sources¥ でファイルの一覧が表示されるので install.wim を目グレップで探しましょう。

違う場合は、別のドライブにあるはずです。

dir C:¥sources¥

Windows のイメージを本番用 USB にインストールします。(Dism /Apply-Image /ImageFile:C:¥sources¥install.wim /Index=1 /ApplyDir:o:¥)コマンドの C ドライブは、発見したドライブ名に差し替えてください。

Index の番号が不安になりますが、これは複合 Windows イメージの何番目のイメージを使うかということを表すらしいので 1 で大丈夫だと思います。(参考:Windowsイメージ操作まとめ - Qiita

これも時間がかかります。僕の環境では 15 分くらいかかりました。この間に最後のステップに備えてシャワーでも浴びておきましょう。

Dism /Apply-Image /ImageFile:C:¥sources¥install.wim /Index=1 /ApplyDir:o:¥

最後にブートパーティション領域を初期化します。

o:\Windows\System32\bcdboot o:\Windows /l ja-JP /s b: /f ALL

/ll は、小文字の L です。見分けがつかなくて一回 Itypo しました。ややこしい。

以上で Windows のインストールは完了です!お疲れ様でした!

コマンドプロンプトexit で抜けて、シャットダウンしましょう。

exit

6. macOS に切り替えて、Boot Camp から Windows サポートライブラリ をダウンロードし、インストーラ用 USB にコピー

あ、完成したと思いました?残念。まだあります。

このまま Windows を起動することはできますが、Mac のハードウェアのデバイスドライバがないので wifi に繋げません。外部ネットワークにアクセスできないので、ライセンス認証もできないですし、デバイスドライバーをダウンロードすることすらできません。残念でした。

ここで、起動するのは Windows ではなく macOS です。(macOS が起動しない場合は、alt キーを押したまま電源を入れ Macintosh HD を選択して起動してください)

Windows のための MacデバイスドライバBoot CampWindows サポートライブラリ として提供しているのでそれを利用します。

Boot Camp で Windows を実行しているときに Mac の一部の機能が働かない場合 - Apple サポート

Boot Camp アプリを起動して、メニューバーにある アクション をクリックし、Windowsサポートソフトウェアをダウンロード をクリックします。

f:id:kawasin73:20181218010521p:plain

場所を指定してダウンロードします。全部で 2.8 GB くらいあるので気をつけてください。

ダウンロードが終わったら、インストーラ用 USB にダウンロードした WindowsSupport ディレクトリをコピーします。コピー先はどこでも大丈夫なので一番上がいいんじゃないでしょうか。

インストーラ用 USBの Windows イメージはもう使わないので、コピーする前にインストーラ用 USB を消去してフォーマットし直しても大丈夫です。

コピーが終わったら macOS をシャットダウンしてください。

7. 本番用 USB で Windows 10 を起動

インストーラ用 USB を抜いて、本番用 USB を差してください。いよいよ Windows を起動します。

alt キーを押しながら Mac の電源を入れてインストーラの時と同じようにオレンジ色の EFI Boot を選択して Windows 10 を起動します。

Windows の初期化画面が出てくるので、みなさんのお好みの設定で初期化を進めてください。

ただ、ネットワークの設定はデバイスを認識しないため、スキップしてください。

初期化が終わると Windows 10 が起動します。

8. Windows 10 に Mac 用の様々なドライバーを Boot CampWindows サポートライブラリ を使ってインストール

Windows 10 が起動したら、インストーラ用 USB を差してください。

エクスプローラで(Mac の Finder みたいなアプリ)インストーラ用 USB の中身を開いてステップ 6 でコピーした WindowsSupport を探します。

WindowsSupport¥BootCamp¥Setup をダブルクリックして実行すると Macデバイスドライバがインストールされます。

インストール中に画面サイズがいい感じになって感動すると思います。

インストールが終わると再起動するのでなされるがままに再起動しましょう。

9. Windows 10 のライセンス認証

最後に Windows 10 のライセンス認証をします。

スタートメニュー (左下のウィンドウズアイコン)をクリックし、設定(左側の歯車マーク)をクリックします。

更新とセキュリティ を開き、ナビゲーションバーから ライセンス認証 を表示します。

ライセンス認証をするために プロダクトキーを変更する をクリックして、ライセンスキーを入力します。

これで、晴れてポータブルな Windows 10 の USB ドライブが完成しました。お疲れ様でした。

使い方

これからは好きな時に Windows を使えます。

Mac に USB を差した状態で alt キーを押しながら電源を入れると OS を選べます。

alt キーを押さないで起動した場合は前回起動した OS が起動します。

USB が刺さっていない時は macOS が起動します。

簡単ですね。

何で2回もインストールしたか

これは後日談なのですが、冒頭で諸事情により2回 Windows をインストールしたと書きました。

諸事情あって 2 回 Windows をインストールしたのですが、1回目はこの記事の通り Windows マシンでインストールして、2 回目は Mac だけでインストールしたので、正しく動くことは確認しています。

これは、1回目は 64 GB のUSB メモリに Windows 10 をインストールして授業に挑んだわけですが、LabVIEW がインストールするのに全部で 45GB を必要とするということが発覚し挫折したからです。

てか、45 GB ですよ!!!!奥さん!!!信じられますか????

64GB のうち Windows をインストールした後に空き容量が 20 GB くらいしか残っていなかったので、泣く泣く 128 GB の USB を買ってインストールし直しました。

以上恨みつらみでした。

最後に

かなり長くなりましたが、お疲れ様でした。ぜひポータブルな Windows USB ドライブライフを試してみてください。

Go でビットベクトルライブラリを作った話

この記事は、DMM.com Advent Calendar 2018 の 15 日目の記事です。

Go 言語でエンディアン(ビッグエンディアン、リトルエンディアン)を指定できるビットベクトルライブラリを作ったのでその紹介をします。

このライブラリは、mmap でファイルがマッピングされたメモリを直接扱うことを想定し、ビットベクトルの中身がマシンのエンディアンに関わらず指定したエンディアンになるように操作を行います。

そのため、ファイルに保存したビットベクトルのバイト列を異なるエンディアンのマシンで扱うことができるようになります。

また、不必要なコピーとエンディアンの変換処理が発生しないように設計されています。そのために内部で unsafe パッケージを使って []byte から []uint64 へのキャストを行なって、バイト列を直接扱えるように工夫しています。

github.com

ビットベクトルとは

ビットベクトルとは、 ある非負の整数と true, false の 2 値をマッピングする 簡潔データ構造 の一種で、空間的にも計算量的にも効率良く動作します。


ある非負の整数とブーリアン型とのマッピングデータ構造の一例として例えば []bool が考えられます。

Go 言語においてブーリアン型は 1 バイトのメモリを必要とし、[]boolN 個の bool 値を保存するのに N バイトを消費 します。(厳密にはスライス構造体もメモリを消費しますが、ここでは無視します。)

fmt.Println(unsafe.Sizeof(true)) // 1

boolVec := make([]bool, N)

// N bytes for N items
// [ true | false | false | true | true | false | false | false | .... ]

i 番目の値を引いてくる計算は、スライスのインデックスを渡すことで一発で引いてくることができます。

boolVec[i] // true or false

0 ~ N の値の中で true がセットされていない最小の数値を見つける計算( Find First Zero )は、最悪で N 回のループを処理します。

for i := 0; i < N; i++ {
    if !boolVec[i] {
        // i is false!
    }
}

一方、ビットベクトルは true, false の値を 1 ビットの 1, 0 として表し、N 個の値を保存するのに N / 8 バイトを消費 します。つまり、メモリ空間の消費量は 1/8 に圧縮 されます。

// N / 8 bytes for N items
[ 10011000 ... ]

また、ビットベクトルは 64 ビットの符号なし整数の配列 []uint64 で表されます。

bitVec := make([]uint64, (N + 63)/64)
[ 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 |
  00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 |
  ....]

i 番目の値は、[]uint64i / 64 番目の 64 ビットのうち下から i % 64 ビット目のビットが 01 かどうかを調べることでわかります。

実際には割り算の計算は重いため、ビットの操作によって軽く計算します。

  • i / 64i6 ビット右シフトさせたもの(i >> 6
  • i % 64i の下位 6 ビット(i & 63
  • i % 64 ビット目のビットマスク:1 << (i & 63)
bitVec[i >> 6] & (1 << (i & 63)) != 0 // true or false

0 ~ N の値の中で true がセットされていない最小の数値を見つける計算( Find First Zero )は 64 ビットごとに検索し、N / 64 回のループ処理で検索することができます。つまり、計算量は 1 / 64 に圧縮 されます。

これは、CPU が一度に 64 ビットずつ計算を行うためです(64 ビット CPU アーキテクチャの場合。32 ビット CPU アーキテクチャの場合は 32 ビットずつです)。

このように、ビットベクトルを使うと true, false の値を空間的にも計算量的にも効率よく保存できます。

ビッグエンディアン、リトルエンディアンとは

ここまででビットベクトルの説明をしたわけですが、ファイルにビットベクトルを書き出す時にはエンディアンを意識する必要があります。

エンディアン( Endianness )とはバイトの並び順のことで、ビッグエンディアン( Big Endian )とリトルエンディアン( Little Endian )の2種類があります。(ミドルエンディアンなど他のエンディアンもあるらしいですがごく少数派らしいです)また、バイトオーダーとも呼ばれます。

ビッグエンディアンは上位のバイトから並べていく方式で、リトルエンディアンは下位のバイトから並べていく方式です。

例えば Go 言語の uint64 の場合 64 ビットの整数であるためこれは 8 バイトで表されます。

16進数で 0x0123456789abcdef と表される数値は、ビッグエンディアンでは 0x01 | 0x23 | 0x45 | 0x67 | 0x89 | 0xab | 0xcd | 0xef と、リトルエンディアンでは 0xef | 0xcd | 0xab | 0x89 | 0x67 | 0x45 | 0x23 | 0x01 と表されます。

エンディアン - Wikipedia

エンディアンは CPU のアーキテクチャによって変わります。よく使われている amd64 のCPU(IntelAMD などの CPU)では、リトルエンディアンです。

また、CPU によってはビッグエンディアンとリトルエンディアンを指定できる CPU もあるみたいです。

同一プロセスのメモリ上の値は全て同じエンディアンで扱われているため、通常のメモリ上の値を操作するプログラミングをする場合はエンディアンを気にする必要はありません。

しかし、マシンをまたいでバイナリデータをやり取りする場合はこのエンディアンに注意しないと、マシンによって全く異なる値に認識されてしまうことになります。(TCP/IP などのネットワークプロトコル操作やバイナリエンコードされたファイルを異なるマシンで扱うときなど)

Go言語でのビットベクトルライブラリ

ここまでで、ビットベクトルとエンディアンの説明をしました。ここからが本題です。

Go 言語にはすでにビットベクトルのライブラリとして、github.com/willf/bitset があります。

github.com

Go のバージョン 1.7 から対応しているとても良いライブラリなのですが、外部のメモリを直接扱えず willf/bitset 内で管理している []uint64 にコピーする必要があるという欠点があります。

willf/bitset はバイト列ストリームへエンディアンを指定した書き出しと読み込みをする WriteTo()ReadFrom() インターフェイスを提供しており、これによりファイルへの書き出しと読み込みが可能になります。

しかし、ファイルへの書き出しでは変更された部分だけではなく全てを書き出すため、必要のないコピーが発生します。また、初期値のロードでは必ずカーネルランドからユーザーランドへのメモリコピーが発生します。

willf/bitset は内部のメモリ []uint64 をマシンのエンディアンで処理します。そして、書き出しと読み込み時に内部で binary.Write()binary.Read() を使い指定されたエンディアンに変換します。エンディアンの変換ではマシンのエンディアンに関わらず 8 バイトごとに変換処理をするため、頻繁にファイルと同期をとる場合はこの 変換のコストコピーのコスト が大きくかかってきます。

ビットベクトルライブラリを作る

ファイルへの書き出しと読み込みの メモリコピーのオーバヘッド と、エンディアンの変換処理のオーバーヘッド を極力抑えるために github.com/kawasin73/bitset というビットベクトルのライブラリを作成しました。

github.com

このライブラリは外部から提供されたバイト列 []byte を直接扱います。

mmap はファイルがマッピングされたカーネル側のメモリをユーザーランドから直接操作することができる機能です。

kawasin73/bigset では mmap によってファイルがマッピングされたメモリも直接扱うことができるため、初期値のロードのメモリコピーが発生せず、ファイルへの書き戻しのメモリコピーも必要なくなります。

また、ビットベクトルの操作ではマシンのエンディアンによって処理を切り替えることによって、エンディアンの変換処理のオーバーヘッドをなくすことができます。

このライブラリを作る上では、https://github.com/willf/bitset を参考にして実装し、以下の点を工夫しました。

  • []byte から []uint64 へのゼロコピー変換
  • それぞれのマシンエンディアンに最適化されたビットベクトル操作

[]byte から []uint64 へのゼロコピー変換

通常 []byte から []uint64 への変換は、8 バイトずつ binary.BigEndian.Uint64() または、binary.LittleEndian.Uint64() によって変換してコピーを行います。しかし、それでは mmap されたメモリを操作することはできず、またメモリコピーのコストがかかります。

そこで、以下のようにして unsafe パッケージを使い []byte から []uint64 へコピーすることなく変換しています。

buf := make([]byte, 8 * n)
header := *(*reflect.SliceHeader)(unsafe.Pointer(&buf))
header.Len /= 8
header.Cap /= 8

vec := *(*[]uint64)(unsafe.Pointer(&header))

この手法では従来のバイト列が 8 の倍数でなかった場合、末尾のあまりの部分は無視されます。

利用者にとって想定外の領域の切り詰めが起こらないように、このライブラリでは8 の倍数でない長さのバイト列の場合は初期化時に bitset.ErrInvalidLength エラーを返すようにしています。

変換された []uint64 だけを bitset.BitSetvec として保持して元の []byte の参照を消した時、バイト列が GC されて vec の内容が別の処理に書き換えられるバグがあったため、元の []bytebitset.BitSetorig として保持して GC されないように工夫しています。

マシンエンディアンに最適化されたビットベクトル操作

このライブラリではマシンのエンディアンhostEndian)を検出し、利用者が指定したエンディアンuserEndian)と hostEndian を比較して処理を切り分けています。

hostEndianuserEndian の組み合わせは、(hostEndian, userEndian) = (LittleEndian, LittleEndian), (BigEndian, LittleEndian), (LittleEndian, BigEndian), (BigEndian, BigEndian) の全部で 4 通り あります。

しかし、リトルエンディアン と ビッグエンディアン は逆に並んでいるだけであるので、hostEndianuserEndian同じ違う かの 2 通りだけを考えればよい ということになります。

初期バージョンでは、以下の 64 ビットを 8ビットずつ反転させるスワップ関数を利用して実装しました。

func swapUint64(n uint64) uint64 {
    return ((n & 0x00000000000000FF) << 56) |
        ((n & 0x000000000000FF00) << 40) |
        ((n & 0x0000000000FF0000) << 24) |
        ((n & 0x00000000FF000000) << 8) |
        ((n & 0x000000FF00000000) >> 8) |
        ((n & 0x0000FF0000000000) >> 24) |
        ((n & 0x00FF000000000000) >> 40) |
        ((n & 0xFF00000000000000) >> 56)
}

hostEndianuserEndian が異なる時に、以下の手順で操作を行うとユーザーが指定したエンディアンでメモリ操作ができます。

  1. メモリから反転させて一時メモリに読み出し
  2. マシンのエンディアンで処理を行い
  3. 反転させてメモリに書きもどす

初期バージョンの実装とテストが終わった後に、それぞれのエンディアンが異なる時の操作を最適化された処理に書き換えています。

テスト

このライブラリはビッグエンディアンとリトルエンディアンに対応してものであると謳っている以上、それぞれのエンディアンのマシンでテストをする必要があります。

travis の上でビッグエンディアンをエミュレートしてテストする手法は以下の記事にまとめています。

kawasin73.hatenablog.com

利用方法

だいたいこんな感じで使います。(README.md からコピーしてきました。)

func main() {
    // in memory usage
    buf := make([]byte, 2*8)
    b, _ := bitset.New(buf, binary.LittleEndian)
    for _, v := range []uint{0, 1, 3, 6, 10, 64, 127, 128} {
        b.Set(v) // when v == 128 returns false because overflow
    }
    fmt.Println(buf) // [75 4 0 0 0 0 0 0 1 0 0 0 0 0 0 128]

    b.Unset(127)
    fmt.Println(b.Get(127)) // false

    for v, ok := b.FindFirstOne(0); ok; v, ok = b.FindFirstOne(v + 1) {
        fmt.Println(v) // 0 1 3 6 10 64
    }

    // File + mmap usage
    const pageSize = 4 * 1024
    f, _ := os.OpenFile("example.bit", os.O_RDWR|os.O_CREATE, 0666)
    f.Truncate(pageSize)
    buf, _ = syscall.Mmap(int(f.Fd()), 0, pageSize,
        syscall.PROT_READ|syscall.PROT_WRITE,
        syscall.MAP_SHARED)
    defer func() {
        f.Sync()
        syscall.Munmap(buf)
        f.Close()
    }()

    b, _ = bitset.New(buf, binary.BigEndian)
    for v, ok := b.FindFirstOne(0); ok; v, ok = b.FindFirstOne(v + 1) {
        fmt.Println(v) // 0 1 3 6 10 64  if executed twice
    }
    for _, v := range []uint{0, 1, 3, 6, 10, 64, 127, 128} {
        b.Set(v) // when v == 128 returns false because overflow
    }
    fmt.Println(buf) // [0 0 0 0 0 0 4 75 128 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 ....
}

今対応している操作はこのくらいなので、今後操作の種類を追加していけるといいなと思っています。

  • func (b *BitSet) Count() uint
  • func (b *BitSet) FindFirstOne(i uint) (uint, bool)
  • func (b *BitSet) FindFirstZero(i uint) (uint, bool)
  • func (b *BitSet) FindLastOne() (uint, bool)
  • func (b *BitSet) Get(i uint) bool
  • func (b *BitSet) Set(i uint) bool
  • func (b *BitSet) Unset(i uint) bool

制約

https://github.com/willf/bitset では、大きな違いとして、メモリサイズの自動拡張機能があります。ビットベクトルの範囲を超えた整数に Set があった場合は []uint64 のサイズを自動で拡張してくれる機能です。

このライブラリでは、mmap したメモリも想定しているので自動でメモリを拡張することができません。(拡張すると違うメモリ空間にビットベクトルが移動し、mmap したメモリへの変更がされなくなる)

このライブラリ自体は、mmap したメモリ以外のヒープメモリも受け付けるものなので、サイズを自動で拡張する機能があれば便利だなと考えています。

最後に

長かったですが以上です。

ビットベクトルを使いたい時にぜひ使ってみてください。