2019-04-21

Rustの日付時刻処理(std::time, time, chrono)

標準ライブラリ

標準ライブラリには時刻を扱うための基礎となる型のみが定義されている。暦やタイムゾーンなどを扱うときは後述の chrono を使うのがよい。

std::time::Duration ... 時間。
std::time::Instant ... 体内時計の時刻。
std::time::SystemTime ... 時計の時刻。

Duration

時間はOSとは無関係なのでlibcoreに定義されている。 src/libcore/time.rs

pub struct Duration {
    secs: u64,
    nanos: u32, // Always 0 <= nanos < NANOS_PER_SEC
}

したがってこれは0秒以上2⁶⁴秒未満の範囲内の時間をナノ秒単位で正確に表現できる。

InstantとSystemTime

標準ライブラリには時刻を表す型が Instant と SystemTime の2つある(いわゆるmonotonic clockとrealtime clock)。この2つは時刻の補正があったときの挙動が異なる。たとえば、「5秒経過 + NTPや手動設定により時刻が3秒分手前に補正された」とき、

Instant は約5秒ぶん進む。
SystemTime は2秒ぶん進む。

つまり、 SystemTime はできるだけ正しい絶対時刻を表しているが、経過時間の計算が狂うことがある(最悪、逆転進行する可能性もある)。

一方、 Instant は経過時間をほぼ正確に表現するが、補正しなかった分が蓄積しているのでそもそも正しい絶対時刻を表していない。

Instant から意味のない値を取り出してしまわないように、 Instant から時刻表現を取り出す手段はそもそも用意されていない。2つの Instant を比較することではじめて意味が出てくる。

この Instant と SystemTime はOSごとに定義される型のラッパーになっている。

macos/iOS以外のunix系OSでは、Instant, SystemTimeともに struct timespec のラッパーである。その取得はclock_gettime(2)のCLOCK_MONOTONICとCLOCK_REALTIMEモードを単に呼ぶだけになっている。
- SystemTime の場合は、timespecはunix time (のはずだけどleap secondsの扱いに関する記述がOpen Group SpecificationにもLinux man pagesにもないので謎)
macos/iOSではInstantがu64のラッパーであるという違いがある。また、 Instant は mach_absolute_time、 SystemTime は gettimeofday で取得している。
- mach_absolute_timeに関する記述
- gettimeofdayなのでほぼ間違いなくunix timeを返すはず
WindowsではInstantはQueryPerformanceCounterの返すDurationで、SystemTimeはGetSystemTimeAsFileTimeの返すFILETIMEである。
- FILETIMEは時刻として使う場合は1601-01-01 00:00:00 UTCからの経過ナノ秒を100で割り、64bit整数として表したものを2つの32bit符号なし整数に分けてから符号つき整数にキャストして入れたものとして解釈されるので、Unix epochが謎のマジックナンバーになるし、色々面倒そう。
  - 1601年なのはグレゴリオ暦の導入が1582年なのと関係あるかも？それ以前の西暦は遡及ユリウス暦と遡及グレゴリオ暦の2種類の数え方が対立しているようなので難しそう。
  - しかもこのFILETIMEとかいう奴、(Rustの標準ライブラリでは使ってないけど)時間の表現にも使われるので設計ミス感が強い
wasmの現状の実装では Instant, SystemTime ともにunix epochからの経過時間としての Duration を使っており、shimの実装を見る感じでは単に Date.now() を呼んでいるだけでmonotonic clockとrealtime clockの区別はなさそう。
Windowsやwasmのmonotonic timerは信頼できないので、逆転しないような対策が入っている。
cloudabi, redox, sgxでの定義は割愛

例: 経過時間を調べる

playground

let instant1 = Instant::now();
std::thread::sleep(Duration::from_millis(200));
let instant2 = Instant::now();
eprintln!("elapsed: {:?}", instant2 - instant1);

ベンチマーク目的ならtestやcriterionなど専用のライブラリを使うのがいいだろう。

例: unix timeを調べる

playground

let now = SystemTime::now();
let unixtime = now.duration_since(UNIX_EPOCH).expect("back to the future");
eprintln!("unixtime = {}.{:09}", unixtime.as_secs(), unixtime.subsec_nanos())

`time`クレート

time はC言語風のシンプルな日付時刻処理を実装している。今となってはchronoがあるので積極的に利用することはあまりなさそう。

Durationがここでも定義されているが、こちらは負の値を取ることができる。標準ライブラリの Duration との変換も可能
- 歴史的にはこちらが先に定義され、 std::time::Duration があとから標準化されたようだ
TimespecとTmはunixでお馴染みのやつで、前者がepochからの経過時間表現で後者がカレンダー表現。この Timespec は std::time::SystemTime で事足りそう。

`chrono`クレート

chrono は日付時刻処理に関する事実上の標準ライブラリである。日付は遡及グレゴリオ暦(1582年より前もグレゴリオ暦の規則に従って日付を割り振る)で約-200000年から約200000年まで扱える。時刻はナノ秒までで閏秒も表現可能だが、閏秒の扱いは完全ではない (Utc::now は閏秒を返さないし、時刻の加減算では閏秒は無視される)

chrono の日付時刻型は以下の4つである。

DateTime<Utc>: UTCでの特定の日付時刻 (2019-04-20T12:59:20Z)。ある瞬間を一意的に特定できるので最も基本的な日付時刻型といえる。
DateTime<FixedOffset>: 日付時刻とオフセット (2019-04-20T21:59:20+0900)。
DateTime<Local>: 現在のタイムゾーン上での日付時刻。データ的には DateTime<FixedOffset> と同じ。
NaiveDateTime: タイムゾーン不定の日付時刻。
- さらにこれを日付部分と時刻部分に分けた NaiveDate と NaiveTime がある

「日付時刻+タイムゾーン(Asia/Tokyoなど)」を処理するにはtzdataが必要なので chrono-tz (後述) として分離されている。

また、上に挙げたものの他に Date<Utc> のような型もあるが、これは Utc.ymd(2019, 4, 21).and_hms(11, 22, 00) とやったときに出てくる中間状態的なもののようだ。日付とオフセットというのは中途半端なので、日付を外部とやりとりするときはどちらかというと NaiveDate を使うほうがよい。

例: 特定オフセットでの日付を表示

前述の通り、日付にはタイムゾーン情報のない NaiveDate を使うのがよいとされている。

playground

let datetime = Utc::now().with_timezone(&FixedOffset::east(9 * 3600));
eprintln!("{}", datetime);
// .naive_local() を取るとタイムゾーン情報を残せるが、多分あまり使わない
eprintln!("{}", datetime.naive_local().date());

例: 時刻指定+UTCへの変換+比較

playground

let threshold = FixedOffset::east(9 * 3600).ymd(2019, 5, 1).and_hms(0, 0, 0);
if Utc::now() < threshold.with_timezone(&Utc) {
    eprintln!("Heisei");
} else {
    eprintln!("Reiwa");
}

例: 遡及グレゴリオ暦であることを確かめる

紀元前8年から1581年まではユリウス暦(4年に一回の閏年のみで、100年/400年ルールはなし)が用いられていたが、chronoではこれを無視して遡及グレゴリオ暦を用いて計算する(現在の日付を基準に、1581年以前にもグレゴリオ暦の規則を適用して日付を割り振っていく)。したがってchronoには1500年2月29日は存在せず、これより前の日付はユリウス暦とずれていくことになる。

playground

let date1 = NaiveDate::from_ymd(1500, 3, 1);
let date2 = date1.pred();
assert_eq!(date2, NaiveDate::from_ymd(1500, 2, 28));

例: 天文暦である(0年が存在する)ことを確かめる

西暦1年の直前(紀元前1年)を西暦-1年とする方法もあるが、chronoでは紀元前1年を0年とおいている。これを天文暦などということもある。

playground

let date1 = NaiveDate::from_ymd(1, 1, 1);
let date2 = date1.pred();
assert_eq!(date2, NaiveDate::from_ymd(0, 12, 31));

例: 閏秒を表現する

chronoの閏秒はやや特殊で、秒を60にするのではなくミリ秒を1000にすることで表現する。前述のように完全なサポートがあるわけではないので注意。

playground

// 秒を60にするのではなく、ミリ秒を1000にすることで表現する
let datetime = FixedOffset::east(9 * 3600).ymd(2017, 1, 1).and_hms_milli(8, 59, 59, 1000);
dbg!(datetime);

例: 閏秒の計算を調べる

閏秒の大小関係は正しく判定されるが、時間計算では時刻の逆転が起きるようだ。

playground

let datetime1 = Utc.ymd(2016, 12, 31).and_hms_milli(23, 59, 59, 1500);
let datetime2 = Utc.ymd(2017, 1, 1).and_hms_milli(0, 0, 0, 100);
assert!(datetime2 - datetime1 < chrono::Duration::seconds(0));
assert!(datetime2 > datetime1);

`chrono-tz` クレート

Asia/Tokyo や Europe/London などのタイムゾーンを扱うには chrono-tz クレートを使うことができる。UTC→ローカル時刻は一意に決まるのに対し、ローカル時刻→UTCは一意に決まらないことに注意が必要である。

例: タイムゾーンをパースする

playground ※chrono-tzがないのでplayground上では実行できない

let tz = "Asia/Tokyo".parse::<chrono_tz::Tz>().unwrap();
assert_eq!(tz, chrono_tz::Asia::Tokyo);

例: タイムゾーン指定で時刻を表示する

playground ※chrono-tzがないのでplayground上では実行できない

let tz = chrono_tz::Europe::London;
let datetime = Utc.ymd(2018, 10, 28).and_hms(0, 30, 0).with_timezone(&tz);
dbg!(datetime); // 2018-10-28T01:30:00BST
let datetime = Utc.ymd(2018, 10, 28).and_hms(1, 30, 0).with_timezone(&tz);
dbg!(datetime); // 2018-10-28T01:30:00GMT

例: タイムゾーン指定で時刻を組み立てる (一意に決まる場合)

Asia/Tokyo はかなり昔に遡らないと変動がないので、こういう風に処理してもあまり問題にならない。しかし後述のように夏時間などでオフセットに変更のあるタイムゾーンでは問題が起きる。

playground ※chrono-tzがないのでplayground上では実行できない

let tz = chrono_tz::Asia::Tokyo;
let datetime = tz.ymd(2019, 5, 1).and_hms(0, 0, 0);
dbg!(datetime); // 2019-05-01T00:00:00JST
dbg!(datetime.with_timezone(&Utc)); // 2019-04-30T15:00:00Z

例: タイムゾーン指定で時刻を組み立てる (一意に決まらない場合)

曖昧性を残したまま時刻の候補を取得するメソッドがあるが、バグっているようだ。

playground ※chrono-tzがないのでplayground上では実行できない

use chrono::prelude::*;

#[test]
#[should_panic(expected = "invalid time")]
fn test_double_time_fail() {
    let tz = chrono_tz::Europe::London;
    // この時刻はGMTとBSTの両方に存在する
    let datetime = tz.ymd(2018, 10, 28).and_hms(1, 30, 0);
    dbg!(datetime);
}

#[test]
#[should_panic(expected = "invalid time")]
fn test_skip_time_fail() {
    let tz = chrono_tz::Europe::London;
    // この時刻はGMTとBSTのどちらでも存在できない
    let datetime = tz.ymd(2019, 3, 31).and_hms(1, 30, 0);
    dbg!(datetime);
}

#[test]
fn test_double_time() {
    let tz = chrono_tz::Europe::London;
    // この時刻はGMTとBSTの両方に存在する
    // tz.ymd(2018, 10, 28).and_hms_opt(1, 30, 0) と書きたいけどこれだとNoneが返ってしまう
    let datetime = {
        let naive = NaiveDate::from_ymd(2018, 10, 28).and_hms(1, 30, 0);
        tz.offset_from_local_datetime(&naive)
            .map(|off| DateTime::<chrono_tz::Tz>::from_utc(naive - off.fix(), off))
    };
    assert_eq!(
        datetime,
        chrono::LocalResult::Ambiguous(
            Utc.ymd(2018, 10, 28).and_hms(0, 30, 0).with_timezone(&tz),
            Utc.ymd(2018, 10, 28).and_hms(1, 30, 0).with_timezone(&tz),
        ),
    );
}

#[test]
fn test_skip_time() {
    let tz = chrono_tz::Europe::London;
    // この時刻はGMTとBSTのどちらでも存在できない
    // tz.ymd(2019, 3, 31).and_hms_opt(1, 30, 0) と書きたいけどこれだと重複時もNoneが返ってしまう
    let datetime = {
        let naive = NaiveDate::from_ymd(2019, 3, 31).and_hms(1, 30, 0);
        tz.offset_from_local_datetime(&naive)
            .map(|off| DateTime::<chrono_tz::Tz>::from_utc(naive - off.fix(), off))
    };
    assert_eq!(datetime, chrono::LocalResult::None);
}

まとめ

抽象的な時間・時刻を扱うには std::time を使い、暦に基づく日付時刻処理をするには chrono クレートを使うのがよい。
歴史的には time クレートが使われていたので、これを見かけることもある。
std::time では時間計測のための Instant と絶対時刻の取得のための SystemTime が区別されている。
chrono ではタイムゾーン情報の有無やに応じて日付時刻型が何種類かに分かれている。基本的には DateTime<Utc> を使い、タイムゾーンを付与するときは DateTime<FixedOffset> を使う。タイムゾーン不定の日付時刻には NaiveDateTime を使う。
chrono を使う場合も、閏秒や1581年以前の暦の扱いには注意が必要である。

2018-11-18

有理数の付番

概要

有理数の付番の計算しやすい定義を与えた。

はじめに

有理数 ( $\mathbb{Q}$ ) は自然数 ( $\mathbb{N}$ ) と同じくらいの個数しかない(可算)というのはよく知られています。これは通常、以下のような理屈で納得されます。

$0, 1, -1, 2, -2, 3, -3, \ldots$ のように付番することで、 $\mathbb{Z}$ は $\mathbb{N}$ と同じくらいしかないことがわかる。
$(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), \ldots$ のように付番することで、 $\mathbb{N} \times \mathbb{N}$ は $\mathbb{N}$ と同じくらいしかないことがわかる。
$\mathbb{Q}$ は分子と分母の組で表せるので、 $\mathbb{N}$ と同じかそれより少ないとわかる。
一方、自然数はそのまま有理数なので、 $\mathbb{N}$ は $\mathbb{Q}$ と同じかそれより少ないとわかる。
したがって、 $\mathbb{N}$ と $\mathbb{Q}$ は同じくらいしかない (この推論をCantor-Bernstein-Schröderの定理という)

しかし以下のようにすると、具体的な付番を与えることができます:

了解1.1 $\mathbb{N}$ は0以上の整数全てからなる集合を指すこととする。自然数という言葉も同様の意味で用いる。また、 $\mathbb{N}^+$ を1以上の整数全てからなる集合とする。

定義1.2 $f\colon \mathbb{Q} \to \mathbb{N}$ を以下のように定義する。

$f(q) = 2f(1 / (q - 1)) + 2$ 　　　 ( $1 \lt q$ の場合)
$f(q) = 2f(1 / q - 1) + 1$ 　　　 ( $0 \lt q \le 1$ の場合)
$f(q) = 0$ 　　　　　　　　　　　　 ( $q = 0$ の場合)
$f(q) = 2f(1 / q + 1) + 2$ 　　　 ( $-1 \le q \lt 0$ の場合)
$f(q) = 2f(1 / (q + 1)) + 1$ 　　　 ( $q \lt -1$ の場合)

証明

では、これが実際に付番として機能することを証明していきます。証明とかよくわからない人は飛ばしてもOKです。

定理1.3 $f$ は矛盾なく定義される。

(証明) 方程式中の除算は以下のように正当化される。

1番目の方程式では $1 \lt q$ より $0 \lt q - 1$ となるため、除算可能。
2番目の方程式では $0 \lt q$ より除算可能。
4番目の方程式では $q \lt 0$ より除算可能。
5番目の方程式では $q \lt -1$ より $q + 1 \lt 0$ となるため、除算可能。

また $f$ の結果に対しては2をかける操作と1または2を足す操作しかしていないから、 $\mathbb{N}$ の範疇に収まる。

あとは、この方程式の解がちょうど1つあることを示せばよい。そのためには $f(q)$ の値が $q$ の何らかの順序にしたがって順番に決定されることを示せばよい。そのような指標としてここでは以下のようなものを考える。 $a \in \mathbb{Z}$ , $b \in \mathbb{N}^+$ , $\mathrm{gcd}(a, b) = 1$ に対し、 $|-|_f \colon \mathbb{Q} \to \mathbb{N}$ を

$\displaystyle |a/b|_f = |a| + |b|$

と定める。(有理数はこのような $a, b$ の組で一意に表せるので、ちゃんと定義される)

$f(q)$ の値が $|q|_f$ の小さいほうから順に定まるということを示したい。上記の方程式は $q$ に関する漏れや重複のない場合分けになっているので、各方程式をそれぞれ見ていけばよい。

1番目の方程式では $b \lt a$ として $f(a/b)$ を $f(b / (a - b))$ で表している。ここで $b$ と $a - b$ は互いに素のため、 $|b / (a - b)|_f = |b| + |a - b| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。
2番目の方程式では $0 \lt a \le b$ として $f(a/b)$ を $f( (b - a) / a)$ で表している。ここで $b - a$ と $a$ は互いに素のため、 $|(b - a) / a|_f = |b - a| + |a| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。
3番目の方程式はダイレクトに $f(a/b)$ を表しているので問題ない。
4番目の方程式では $-b \le a \lt 0$ として $f(a/b)$ を $f(-(b + a) / -a)$ で表している。ここで $-(b + a)$ と $-a$ は互いに素のため、 $|-(b + a) / -a|_f = |-(b + a)| + |-a| = |b + a| + |a| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。
5番目の方程式では $a \lt -b$ として $f(a/b)$ を $f(-b / -(a + b))$ で表している。ここで $-b$ と $-(a + b)$ は互いに素のため、 $|-b / -(a + b)|_f = |-b| + |-(a + b)| = |b| + |a + b| \lt |b| + |a| = |a / b|_f$ となる。したがって既に定まっている値を使って $f(a/b)$ を表している。

■

定理1.4 $f$ は全単射である。

まずは前者(全射)を示す。全射を示すためには、 $n \in \mathbb{N}$ とおいて、 $f(q) = n$ となる $q \in \mathbb{Q}$ の存在を示せばよい。これを $n$ に関する数学的帰納法 (累積帰納法) によって示す。

$n = 0$ のとき、 $q = 0$ とおけばよい。

$n > 0$ のときはさらに $n$ の偶奇で場合分けする。 $n$ が奇数のとき、 $m \in \mathbb{N}$ を用いて $n = 2m + 1$ と表記できる。 $m \lt n$ なので数学的帰納法の仮定より $f(r) = m$ となる $r \in \mathbb{Q}$ が存在する。

さらに $r$ の符号で場合分けする。 $r \ge 0$ のとき、 $q = 1 / (r + 1)$ とおく。すると $0 \lt q \le 1$ より $f(q) = 2f(1 / q - 1) + 1 = 2f(r) + 1 = 2m + 1 = n$ となる。 $r \lt 0$ のときは、 $q = 1 / r - 1$ とおく。すると $q \lt -1$ より $f(q) = 2f(1 / (q + 1)) + 1 = 2f(r) + 1 = 2m + 1 = n$ となる。

$n$ が(正の)偶数のとき、 $m \in \in \mathbb{N}$ を用いて $n = 2m + 2$ と表記できる。 $m \lt n$ なので数学的帰納法の仮定より $f(r) = m$ となる $r \in \mathbb{Q}$ が存在する。

こちらも $r$ の符号で場合分けする。 $r > 0$ のとき、 $q = 1 / r + 1$ とおく。すると $1 \lt q$ より $f(q) = 2f(1 / (q - 1)) + 2 = 2f(r) + 2 = 2m + 2 = n$ となる。 $r \le 0$ のときは、 $q = 1 / (r - 1)$ とおく。すると $-1 \le q \lt 0$ より $f(q) = 2f(1 / q + 1) + 2 = 2f(r) + 2 = 2m + 2 = n$ となる。

以上により $f$ は全射であることが示された。

続いて単射を示す。単射を示すためには、 $q, q' \in \mathbb{Q}$ とおいて $f(q) = f(q')$ なら $q = q'$ を示せばよい。これを $f(q)$ に関する数学的帰納法(累積帰納法)によって示す。

$f(q) = f(q') = 0$ のとき $q = q' = 0$ である。これは1番目、2番目、4番目、5番目の方程式が当てはまらないことからわかる。

$f(q) = f(q') > 0$ の場合、さらに偶奇で場合分けする。 $f(q) = f(q')$ が奇数のとき、1,3,4番目の方程式は当てはまらないので、 $q \lt -1$ または $0 \lt q \le 1$ である。 $q'$ についても同様に $q' \lt -1$ または $0 \lt q' \le 1$ である。ここで $q \lt -1$ なら $r = 1 / (q + 1)$ 、 $0 \lt q \le 1$ なら $r = 1 / q - 1$ と定義する。また同様に $r'$ も定義する。すると $f(q) = 2f(r) + 1$ , $f(q') = 2f(r') + 1$ となる。特に $f(r) = f(r') \lt f(q)$ なので、数学的帰納法の仮定より $r = r'$ がわかる。ここで、 $r = r' \ge 0$ なら $q = 1 / (r + 1) = 1 / (r' + 1) = q'$ となり、 $r = r' \lt 0$ なら $q = 1 / r - 1 = 1 / r' - 1 = q'$ となる。

同様に、 $f(q) = f(q')$ が(正の)偶数のとき、2,3,5番目の方程式は当てはまらないので、 $-1 \le q \lt 0$ または $1 \lt q$ である。 $q'$ についても同様に $-1 \le q' \lt 0$ または $1 \lt q'$ である。ここで $-1 \le q \lt 0$ なら $r = 1 / q + 1$ 、 $1 \lt q$ なら $r = 1 / (q - 1)$ と定義する。また同様に $r'$ も定義する。すると $f(q) = 2f(r) + 2$ , $f(q') = 2f(r') + 2$ となる。特に $f(r) = f(r') \lt f(q)$ なので、数学的帰納法の仮定より $r = r'$ がわかる。ここで、 $r = r' > 0$ なら $q = 1 / r + 1 = 1 / r' + 1 = q'$ となり、 $r = r' \le 0$ なら $q = 1 / (r - 1) = 1 / (r' - 1) = q'$ となる。

以上により $f$ が単射であることが示された。

■

原理

有理数に付番する場合、約分できる分数に番号を与えないようなトリックが必要です。これは通常、約分できる分数を見つけるたびにスキップするような方法で対処しますが、この定義ではユークリッドの互除法の手順をそのままエンコードすることで、はじめから互いに素なペアだけを発見するような仕組みになっています。

まずは正の整数2つのユークリッドの互除法をエンコードすることを考えます。たとえば33と57の互除法は以下のようになります。

57, 33
33, 24 (57を33で割った余り)
24, 9 (33を24で割った余り)
9, 6 (24を9で割った余り)
6, 3 (9を6で割った余り)
3, 0 (6を3で割った余り)

これを復元するには、各段階での商を覚えておけばいいです。つまりこの場合は (1, 1, 2, 1, 2) となります。これを逆順に再生することにより

1, 0 (初期状態)
2, 1 (1を2倍して0に足す)
3, 2 (2を1倍して1に足す)
8, 3 (3を2倍して2に足す)
11, 8 (8を1倍して3に足す)
19, 11 (11を1倍して8に足す)

と、約分された状態の互除法が復元できます。

ただこの方法をそのまま使うと、次のステップで整数の列を自然数にエンコードしなくてはならなくて面倒です。そこで互除法の亜種として、互減法を考えます。

57, 33
24, 33 (左を引く)
24, 9 (右を引く)
15, 9 (左を引く)
6, 9 (左を引く)
6, 3 (右を引く)
3, 3 (右を引く)

またちょっとした工夫として、0が出てきたら終わりではなく、左右が同じになったら終わりということにしておきます。

こうすると、左右のどちらから引いたかを覚えておけば復元できます (左、右、左、左、右、右)。

しかも嬉しいことに、この計算は分数としても簡単な計算に対応します。左を分子、右を分母とする場合、左から引く操作は1を引く操作に対応します。右から引く操作は逆数をとり、1を引いてまた逆数をとる操作に対応します。

いっぽう、 (左、右、左、左、右、右) のようなビット列を自然数に埋め込むときは、2進法を使うことができます。このとき、最上位ビットに番兵ビットとしての1を常に置くことによって、列の長さも自然にエンコードできます。つまり、

1 は2進法で 1 なので空のビット列
2 は2進法で 10 なので (0) というビット列
3 は2進法で 11 なので (1) というビット列
4 は2進法で 100 なので (0, 0) というビット列
5 は2進法で 101 なので (0, 1) というビット列
6 は2進法で 110 なので (1, 0) というビット列
7 は2進法で 111 なので (1, 1) というビット列
...

となります。初期値は1で、0を付加するときは2倍、1を付加するときは2倍して1を足せばいいことになります。

この場合実際には正の整数にエンコードしていることになるので、非負整数として書くときにはうまく1ずつずらす必要があります。つまり、

初期値は0
0を付加するときは2倍して1を足す
1を付加するときは2倍して2を足す

というルールになります。

これを使って、正の有理数を自然数にエンコードする関数は以下のように書けます。

$f(q) = 2f(q - 1) + 1$ 　　　 ( $1 \lt q$ の場合)
$f(q) = 0$ 　　　　　　　　　　　　 ( $q = 1$ の場合)
$f(q) = 2f(1 / (1 / q - 1)) + 2$ 　　　 ( $0 \lt q \lt 1$ の場合)

これを改良していきます。まず、単に見た目の問題ですが、1番目の方程式と3番目の方程式がアンバランスなので工夫します。1ステップごとに分母と分子を入れ替えるルールにすると、逆数を取る処理を公平に負担することができます。

$f(q) = 2f(1 / (q - 1)) + 1$ 　　　 ( $1 \lt q$ の場合)
$f(q) = 0$ 　　　　　　　　　　　　 ( $q = 1$ の場合)
$f(q) = 2f(1 / q - 1) + 2$ 　　　 ( $0 \lt q \lt 1$ の場合)

次に、ゼロと負の有理数に対応する必要があります。負の数は負の数のなかでループすることにして、符号のために1ビット追加することでうまく対処できます。

$f(q) = 2f(1 / (q - 1)) + 1$ 　　　 ( $1 \lt q$ の場合)
$f(q) = 1$ 　　　　　　　　　　　　 ( $q = 1$ の場合)
$f(q) = 2f(1 / q - 1) + 2$ 　　　 ( $0 \lt q \lt 1$ の場合)
$f(q) = 0$ 　　　　　　　　　　　　 ( $q = 0$ の場合)
$f(q) = 2f(1 / q + 1) + 2$ 　　　 ( $-1 \lt q \lt 0$ の場合)
$f(q) = 2$ 　　　　　　　　　　　　 ( $q = -1$ の場合)
$f(q) = 2f(1 / (q + 1)) + 1$ 　　　 ( $q \lt -1$ の場合)

さらに場合分けを減らすために、 $q = 1$ の場合と $q = -1$ をいい感じに統合します。このとき、 $f(0) = 0$ かつ $f(1) = 1$ となるようにビットの値も調整しておきます。 (何となくそのほうが綺麗なので)

$f(q) = 2f(1 / (q - 1)) + 2$ 　　　 ( $1 \lt q$ の場合)
$f(q) = 2f(1 / q - 1) + 1$ 　　　 ( $0 \lt q \le 1$ の場合)
$f(q) = 0$ 　　　　　　　　　　　　 ( $q = 0$ の場合)
$f(q) = 2f(1 / q + 1) + 2$ 　　　 ( $-1 \le q \lt 0$ の場合)
$f(q) = 2f(1 / (q + 1)) + 1$ 　　　 ( $q \lt -1$ の場合)

これで冒頭の定義になりました。

まとめ

有理数の付番を、比較的簡単な方程式で与えることができました。これはユークリッドの互除法をうまくエンコードすることによって作られています。

ところで $\mathbb{Q}$ といえば、最近Qiitaというサービスで記事を書いてみました。ぶっちゃけはてなブログより使いやすくて、技術記事を書くには快適でよいですね。気まぐれに使いわけてみようと思っています。

2018-09-29

RustのREPL "evcxr" を使ってみた

概要

evcxrはRustのパーサーとコンパイラを外部から呼び出すことでREPLを実現している。セミブラックボックス的なアプローチにも関わらずなかなかの完成度で、今後が期待できる。

evcxr

evcxrは最近公開されたRustのREPL (GitHub, redditのpos)である。また、Jupyterのカーネルもあるため、Jupyter Notebook上でRustを書くこともできる。

Evaluation Context for Rust とのことで、 ev + cx + r と思えば覚えられる。

インストール方法

コマンドラインは以下で入る。

cargo install evcxr_repl

Jupyter版については公式サイトを参照するとよい。

基本的な動作を試してみる。

$ evcxr
Welcome to evcxr. For help, type :help
>> :help
:vars             List bound variables and their types
:opt              Toggle optimization
:explain          Print explanation of last error
:clear            Clear all state, keeping compilation cache
:dep              Add dependency. e.g. :dep regex = "1.0"

Mostly for development / debugging purposes:
:last_compile_dir Print the directory in which we last compiled
:timing           Toggle printing of how long evaluations take
:last_error_json  Print the last compilation error as JSON (for debugging)
:internal_debug   Toggle various internal debugging code
>>

: がメタコマンド。今のところ終了コマンドはないが、Ctrl+CやCtrl+Dで終了できる。

>> let s = String::from("Hello, ");
>> s
"Hello, "
>> s.push_str("world!");
   ^ cannot borrow mutably
cannot borrow immutable local variable `s` as mutable

エラーに色がついて、年季のわりに凝っている。

>> let mut s = s;
>> s.push_str("world!");

シャドーイングも普通にできる。

1行ずつコンパイルしているため体感がかなり遅い。

>> s
"Hello, world!"
>> s
"Hello, world!"

式はborrowして表示しているっぽい。

>> drop(s);
>> s
   ^ not found in this scope
cannot find value `s` in this scope

dropするとなくなる。

>> let s = String::from("ABC");
>> if false { drop(s) };
>> s
   ^ not found in this scope
cannot find value `s` in this scope

実際にはdropされていなくても、同じコンパイルエラーの条件に落ちるときは、なくなった扱いになる。

>> let s = String::from("foo");
>> let z = &s;
            ^ borrowed value does not live long enough
`s` does not live long enough
Values assigned to variables in Evcxr cannot contain references (unless they're static)
>> { let z = &s; }
()

行をまたいで参照を渡すことはできないが、スコープを切ってやればできる。

>> use std::io::{self, Read, Write, BufRead};
>> use std::fs::File;
>> use std::io::BufReader;
>> let f = File::open("/proc/cpuinfo").unwrap();
>> let mut f = BufReader::new(f);
>> let mut line = String::new();
>> f.read_line(&mut line).unwrap();
>> line
"processor\t: 0\n"

インポートは行をまたいで有効。

シリアライズできない値も持ち越せる。

>> extern crate rand;

extern crate を宣言すると、いい感じに依存関係を追加してくれる。依存関係のコンパイルをするので、時間はかかる。

ここで、手元に evcxr-test というlibrary crateを作ってみる。内容はこんな感じ。

pub fn fib(n: u32) -> u32 {
    (0..n).fold((0, 1), |(a, b), _| (b, a + b)).0
}

これは以下のようにして追加できた。evcxrのtemporary directory上にある Cargo.toml に依存を追加するような仕組みになっているっぽい。

>> :dep evcxr-test = { path = "/home/qnighy/workdir/evcxr-test" }
>> evcxr_test::fib(40)
102334155

ただ、 path はevcxrのtmpdirからの相対パスのため、現状ではほぼ絶対パスしか使えないようだ。

さっき作ったライブラリを書き換えてみる。

pub fn fib(n: u32) -> u32 {
    (0..n).fold((0, 1), |(a, b), _| (b, a + b)).0
}

pub fn foo(n: u32) -> u32 {
    n
}

:dep でリロードしてみる。

>> :dep evcxr-test = { path = "/home/qnighy/workdir/evcxr-test" }
>> evcxr_test::foo(40)
40

リロードできた。

>> struct Foo(u32);
Items currently need to be explicitly made pub along with all fields of structs.
>> pub struct Foo(u32);
Items currently need to be explicitly made pub along with all fields of structs.
>> pub struct Foo(pub u32);
>> let x = Foo(42);
>> let y: Foo = x;

アイテム定義は持ち越されるが、プライベートな定義が含まれてはいけない。(フィールドも含めて)

>> pub struct Foo(pub u32);
>> let z: Foo = y;
                ^ expected struct `user_code_29::Foo`, found struct `user_code_26::Foo`
mismatched types

同じ名前をもう一度定義したときは、別のものとして扱われる。シャドーイングしたかのような動作になる。

仕組み

HOW_IT_WORKSという文書があった。Rustで外部REPLを作ろうと思ったらこうなるだろう、という妥当な設計になっている。

シリアライズできない値も持ち越したい。また、パニックやunsafeによるsegfaultなどもある程度ハンドリングしたい。
- REPLコードを実行するための子プロセスをひとつ立ち上げて、そこに順次ライブラリをロードしていく形になる。
- 親プロセスは新しい行が来たら syn でパースして、必要なスタブをくっつけてからコンパイルする。
- コンパイルされた行 (単独のライブラリになっている) を子プロセスにロードさせて、実行させる。式だったら結果を Debug で表示する。
各行を、あたかも前の行の続きであるかのように実行させるには、インポートとグローバル定義、ローカル定義を引き継ぐ必要がある。
- インポートは単に、過去に実行した extern crate と use を全部覚えておいて、毎回リプレイすればよい。
- グローバル定義は、過去に定義したものを覚えておいて、前に実行したときの定義を引き継ぐような use を生成する。
  - 行をまたぐと別のモジュールになってしまうため、privateな定義は直感的に振る舞わない。今はそういう定義を丸ごと禁止している。
- ローカル定義の型定義は、変数名と型名を String の対として (親プロセスが) 持っておく。
- ローカル定義の実体は、 HashMap<String, Box<dyn Any + 'static>> という評価文脈として (子プロセスが) 持っておく(おそらくこれが名前の由来)。
  - そのため、参照は持ち越せない。
- 実際に生成されるコードは、文脈を受け取って文脈を返す関数になる。
  - 文脈を受け取る部分は、親プロセス側が知っている型定義に基づいてdowncastする let が挿入される。
  - 文脈を返す部分は、その行の let に基づいて、構文的に返しうる変数を全て挿入するような処理が生成される。これはコンパイルエラーになる可能性があるが、とりあえずコンパイルしてから判断する。
  - その変数が 'static でないためにエラーになった場合は、その旨をユーザーに報告して以上。
  - その変数がmove outされている可能性があるという趣旨のエラーだった場合は、その変数の挿入処理を削除して再試行する。

rustcにはコンパイル結果をJSONで返す仕組みがあるため、コンパイルエラーに基づく処理は意外と堅牢に動作するらしい。

感想

思ったよりよく出来ている。REPLの用途の一つはライブラリ制作時のちょっとした確認用だが、そのための機能は少々足りていないと感じた。具体的にはtmpdirを使うと、起動するたびに依存ライブラリの再コンパイルが必要なのと、手元のライブラリの参照が面倒なのがネックになる。まさにその問題がTODOに書かれているので今後に期待。

redditの作者コメントによると2ヶ月ちょいでここまでできたとのことなので、今後の発展でかなり良くなる可能性はありそう。

2018-09-17

Rustコンパイラをクラウドでビルドする備忘録(改良版)

概要

前回の改良版。 Rustコンパイラをいじっているとビルドの遅さのせいで作業に支障をきたすため、クラウドでビルドするようにしてみる。

EC2を立ち上げる

Ubuntu 16.04 (HVM) の c5.4xlarge を使うことにする(結局、手元とあわせたくなったので18.04に上げた)。使うインスタンスの強さは財布と相談して決めることにする。ディスクは結構必要なので上げておく。

何度も再起動して使いたいのでEIPを割り当てておく。(デフォルトのグローバルIPは再起動のたびに変わるっぽい)

高くて強いインスタンスを使っていくので、使わないときは落とし忘れないように気をつける(停止時はEBSやEIPだけ課金される)。このあたりも必要なら自動でシャットダウンする仕組みを考えるといいかもしれない。

IAMユーザーを作る

当該インスタンスを立ち上げられるだけの専用のユーザーを作る。以下のようなインラインポリシーを作る。 (i- ではじまる部分に当該インスタンスのインスタンスIDを入れる)

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Effect": "Allow",
            "Action": "ec2:StartInstances",
            "Resource": "arn:aws:ec2:*:*:instance/i-0123456789abcdef0"
        }
    ]
}

このユーザーのコンソールへのログインを不許可にしてクレデンシャルを発行する。手元のマシンで以下を実行してクレデンシャルを入れる。 (~/.aws/credentials を直接編集してもOK)

$ aws configure --profile rust-builder

セットアップ

手元から rust-builder という名前でSSHできるようにする。依存関係として以下を入れておく。

$ sudo apt update && sudo apt upgrade && sudo apt install build-essential python-minimal cmake curl git

自動シャットダウン

以下のファイルを /home/qnighy/shutdown-timer.sh として置き、実行権限をつける。 (ユーザー名は適宜置き換えて) (ログイン状態のチェックのために w の出力を雑にgrepしているので、そこの置き換えを忘れないように)

#!/usr/bin/env bash
set -ue

count=0
sleep=600
max_count=6

while true; do
  sleep "$sleep"
  date >&2
  if w | grep -q qnighy; then
    echo "logged in; reset" >&2
    count=0
  else
    count="$((count + 1))"
    echo "not logged in; count=$count" >&2
    if [[ $count -ge $max_count ]]; then
      echo "shutting down..." >&2
      shutdown -h now
    fi
  fi
done

また以下のsystemd設定ファイルを /etc/systemd/system/shutdown-timer.service に置く。

[Unit]
Description = shutdown timer

[Service]
ExecStart = /home/qnighy/shutdown-timer.sh
Restart = always
Type = simple

[Install]
WantedBy = multi-user.target

以下で有効化

sudo systemctl enable shutdown-timer
sudo systemctl start shutdown-timer

これにより、10分に1回の頻度でログイン状態をチェックし、60分間非ログインだったらシャットダウンするようになる。

スクリプトの配置

Rustコンパイラを手元にcloneして、 x.py があるのと同じ位置に以下の y.sh を置いてexec permissionをつける。

#!/usr/bin/env bash
set -ue

# Remote side:
# sudo apt update && sudo apt upgrade && sudo apt install build-essential python-minimal cmake curl git gdb

ec2_profile=rust-builder
ec2_region=ap-northeast-1
ec2_instance=i-0123456789abcdef0

builder_host=rust-builder
local_host="$(hostname)"
dirpath="$(realpath --relative-to "$HOME" "$(pwd)")"

while ! aws --profile "$ec2_profile" --region "$ec2_region" ec2 start-instances --instance-ids "$ec2_instance" | grep -q running; do
  echo "waiting for EC2 wakeup..." >&2
  sleep 1
done

git submodule update --init --recursive
rsync -avz --delete --exclude '.git' --exclude '/build' "$HOME/$dirpath/" "$builder_host:$local_host/$dirpath"
ssh -t "$builder_host" "cd $local_host/$dirpath; $@"

やっていることは以下。

まずEC2インスタンスを立ち上げる、replyに "start" が含まれるようになるまで待つ。
rsyncで送って向こうでビルドを叩く。
gitを全部転送したくないので .git は省く。ただしsubmoduleが必要なのでsubmodule updateを自動で叩く。 (x.pyは.gitがあるときはsubmodule updateを自動でやってくれる)
build も当然省く。手元のbuildと衝突しうるし、 --delete に巻き込まれないようにする意図もある。ただしbuildというディレクトリがソースツリーの中にあるので、 /build と指定する必要がある。
tmuxを立ち上げたりはしない。ビルドが短くなることが期待されているので途中で切れてもよい。むしろ自動アタッチとか考えるのが面倒。

ビルド

./remote.sh ./x.py test --stage 1 のように通常のビルドコマンドに ./remote.sh をつけるとリモートでのビルドになる。

設定

クラウドとは関係ないが、コンパイラを開発するときは config.toml を絶対にいじったほうがよい。

compiler-docs = true。ほとんどの関数はdoc-comment (///) を持たないが、シグネチャが一覧できるだけでもありがたい。
debug-assertions = true。これがないとログがほとんど出ない。また、これを有効にすると一部の追加のチェックが行われる。
debuginfo = true, debuginfo-lines = true。これがないとICE(コンパイラ内部エラー)の時のバックトレースがちょっと貧弱で困る。
incremental = true。効果は計測してないけど効率がちょっと上がりそう

2018-09-16

ISUCON8にRustで参加するためにしたこと

背景

ISUCONとは、与えられたWebサービスをいい感じにスピードアップするコンテストである。
いい感じに最適化すさえすれば言語は問われない。ということは、最初に提供される参照実装の書かれた言語を使うのが得策である。
複数の言語で参照実装が提供されることはあるが、Rust版が提供される可能性は高くない。

まず、ISUCONではないコンテストをする覚悟を持つ

http://isucon.net/archives/52012898.html

競技の成り立ちにも由来しますが、ISUCONは参加して学ぶことではなく「勝つこと」が前提となっているイベントです。

とある。↑に書いたように参照実装でない言語を好んで使うということは割とこれに反しているし、ISUCONで本来得られる経験の一部を「IShokU CONtest」の経験に変換することになる。(オペレーション担当が必死にログを見ている傍らでひたすらコードを右から左に移植する)

「そうは言っても、私はこの言語が好きなんだから仕方ない」と思うしかない。

いずれにせよ、本来の勝利条件を捨てているので勝利条件を設定する必要はある。ハッキリと宣言したわけではないが、今回は「Rustを一部でも使って点数に貢献する」といったところが暗黙の勝利条件になっていた気がする。ここは凡そ達成されたと思う。

チームメンバー集め

社内にRustに興味があるエンジニアがいたので、その人達に組んでもらった。とはいっても、Rustでアプリケーションを書けるレベルまで練習する余裕はなかったので、一人で書くことになってしまった。

フレームワークの選定

フレームワークをくまなく漁ったわけではないが、昨今のRustではActix-Webを使うのが正解っぽい雰囲気がある。

5月にあった社内ISUCONでもRustで参加し、このときはGothamを使ったが、これはあまり良くなかった。Gotham自身の設計はよくできているが、ミドルウェアのインターフェースがあっても肝心の実装がないみたいな状況が多く、Actix-Webに比べると心許ない。

逆にActix-WebはRustでサーバーを書くにあたっての最低限(クッキーセッションミドルウェア、redisセッションミドルウェア、グレースフルシャットダウン、JSON APIのためのアダプタなど)が揃っていてよく出来ているが、個人的には以下のような不安点もある。

Actix-Webはtokioベースの非同期処理を採用しているが、実はその上にもう1枚Actixというレイヤが挟まっている。Actixはアクターフレームワークで、正直このレイヤがどんな仕事をしているのかはあまり詳しくない。Actix-WebはActixのレイヤをそこまで露出していないが、たまに困ることがある。
- 例えば、Actix-Web用のライブラリだと思ったらActix用のライブラリだったときにがっかりする(Actix-Webしか使わない人は脳内でActix-WebをActixと省略しがちなので)。
- また、Actixはexecutor(futureを回すお仕事をする人)を独自に実装しており、tokioのデフォルトであるtokio-threadpoolを使っていない。これはいくつか問題がある。
  - たとえば最近のRust非同期界隈ではFutureがSend (有り体にいえばスレッドセーフ) であることが割と前提になりつつある。しかし、Actixはまだそうではないらしく、Actix-Web関連のデータ型にはSendでないものが結構あり、tokioとの相互運用で困ることがある。
  - tokio-threadpoolに特有の処理 (tokio_threadpool::blocking など) が使えない。
歴史的な事情からか、ハンドラのインターフェースの決定版がなく、APIごとに少しずつ異なっている。たとえば Responder トレイトの他に AsyncResponder トレイトもあるが、 Responder トレイトでも非同期処理を書けるし、現在の標準的なハンドラ挿入インターフェースである route メソッドでは Responder が想定されている。

テンプレートエンジンの選定

5月の社内ISUCONではHandlebarsを使ったが、これは失敗で、コンパイルに時間がかかるのにHandlebarsまわりのミスは実行時までわからないことが多かった。(そもそもこいつはJavaScript用のテンプレートエンジンの移植なのでさもありなん)

今回はAskamaというテンプレートエンジンを採用した。これはJinja2風の記法で、Rustコードにコンパイルしてから使用する。テンプレートパラメーターも、「テンプレートごとに別々の構造体にマップしてから渡す」というRustイディオマティックな方法でできるので圧倒的に型に守られる。また、Actix-Web連携機能もあり、有効にしておくとテンプレート構造体がそのまま Responder になってくれるので、とても便利だった。

ちょっと運が悪かった点としては、今回対象となっているHTMLがVuejs用のやつで、Jinja2記法と衝突して面倒だった。

DB・コネクションプール

まず、不本意なことにISUCONではPostgreSQLではなくMySQL(またはMariaDB)ばかり使われるそうなので(日本のWebサービスの傾向がそうらしい？)、基本的にMySQLを想定して準備する。

MySQL用のDBライブラリとしては最もポピュラーな mysql を使い、コネクションプールにも最もポピュラーな r2d2 を用いることにした。

この組み合わせなら、さらに著名なORMの diesel を載せることもできるが、ISUCONではORMを使わずクエリを直接書く傾向にある (参照実装もそうだし、改善する上でもクエリをいじる方が便利) ということで、使わないことにした。

この部分の選定では、ORMを使うか否かのほかに難しい選択がひとつある。それは、非同期に対応させるかどうかである。特にコネクションプールの r2d2 とORMの diesel には非同期の代替品がない。それらの作者が非同期に対応しない理由はissueから伺い知ることができ、以下のように推測される。

Rustの非同期まわりの基礎部分のインターフェースが確立していない。
- たとえば、 Future のインターフェースは0.1から0.2までで大きく変わった。単にAPIが変わっただけではなく、コンテキストを陽に持ち回すようになったので、全体的な設計変更が必要になる可能性がある。
- その上、async/awaitの対応のため、(0.2をほとんど見捨てる形で0.3が導入され) 0.2から0.3まででさらに変化した。Pinという特殊な参照型が導入された上に、 Future が標準ライブラリに移管された。
- futures は汎用非同期ライブラリだが、その上の非同期I/Oライブラリである tokio にも大きな変化があった。元々のランタイムであった tokio-core が廃止され、新しいランタイムライブラリである tokio に移行されるようになった。特に大きな変更として、シングルスレッドからマルチスレッドへの移行がある。 tokio-core は1:Nの非同期モデルなのに対して、 tokio はN:Mの非同期モデルである。そのため tokio への移行では関連するデータ型をスレッドセーフなものにアップグレードする必要がある。
現状で実装しようにも、現状の非同期エコシステムではコネクション系のAPIを適切に設計する準備ができていない。
- 特に、現状の非同期エコシステムは参照との相性が悪い。しかし、コネクションで conn: &mut Conn を受け渡すようなパターンを回避しようとすると、Conn を受け取って (Result, Conn) を返すといったパターンになりがちで、これは皮肉にもRustイディオマティックではないし利便性も低い。
  - async/awaitの導入により非同期における参照の問題はかなり解決される見込みなので、あと少しの辛抱かもしれない。

そもそも、RDBに貼るコネクションが同時10000接続とかそういうことはしない。 (postgresとかだと1コネクション1プロセスらしいので、それをやるとサーバー側が大変なことになりそう) たとえば10接続くらいだったら、同じ数のOSスレッドを用意してやればイベントループをブロックせずに捌けることになる。

さて、そういうとき (OSスレッドを使うことで、非同期処理の一部で同期的な処理をする) には以下の2つの選択肢がある。

futures-cpupool 。専用のCPUプール(OSスレッドのプール)を持っておき、そこに同期処理をオフロードする。今回はこちらを使った。
tokio_threadpool::blocking。tokioのランタイムが所有するスレッドプールのスレッドをロックする。別スレッドに移動せず、その場で同期処理を行うことができる。イベントループはロックされていないスレッドに移管されるので、非同期処理が間違ってブロックされることはない。
- Actix-Webが tokio-threadpool を使っていないため、こちらは使えなかった

ちなみにDBクライアントレベルでは非同期に対応しているものもある。たとえば mysql ライブラリの作者は mysql-async というライブラリも作っていて、同じ作者だけあってインターフェースも似通っている。(5月の社内ISUCONのときはこれを使った)

(もう1点、非同期とかとは関係なく困った点として、手元のMacBookに入れたmysql8のサーバーと相性が悪く接続するとpanicになるという問題があった。結局mysql5系列を入れたら治った)

redis

redisなどのオンメモリキャッシュストレージもISUCONでは頻出とのことでredisのことも考えた。基本的な方針は↑と同じだけど、オンメモリキャッシュの目的上、もっと非同期で繋いでバシバシ捌けるほうがいいのかなと思って、迷っているうちに当日が来てしまった。結果、redisが本質じゃないっぽい問題で、redisを使う機会自体が来なかったので結果オーライ。

ちなみに状況としては、事実上の標準である redis が最近非同期接続をサポートしたので、その部分の選定では困らなさそう。ただ、非同期接続のほうは r2d2 とかには対応していないのでやはり悩ましい。自分でプーリングする？同期的に使う？それともプーリングをしないで戦う？

非同期対応のクライアントとしては他に redis-async というのもあり、5月の社内ISUCONではこっちを使っていた。

セッションミドルウェア

ここが肝で、今回はRack::Session::Cookie互換のクッキーセッションミドルウェアを自作した。別にわざわざRubyのMarshalをデコードしてやる義理はないので、JSONフォーマットの互換を書いた。

なぜ互換である必要があるか？それは、Rubyで書かれた参照実装から少しずつRustに移植していくためである。「一気に移植して、移植しきれなかったらドボン」みたいな怖い真似をわざわざする必要はないので、このようにした。こんな互換ミドルウェアは需要が少ない(真面目に作るとN²種類必要になる……)ので、諦めて自作するのがよい。

ISUCONではRuby実装があってSinatraで書かれているのが相場のようなので、そういう想定で互換ミドルウェアを書いた。↑にあるようにJSONフォーマットにする必要があるが、これはRuby側を1,2行修正すればすむ。

「一部だけ移植なんて甘え」という声はあるかもしれない。ちなみに「ちょっとずつ移植するなら、セッション共有の必要があるじゃん」というのは5月の社内ISUCONの当日に気付いた話で、その時はかろうじて全部移植した。(その時は2人チームで相方のagatanはRustが書ける)

過去問を解く

過去問を解くといい感じにノウハウが溜まるし、何よりもいい感じのプロジェクトテンプレートができてよい。上記のセッションミドルウェアも当然、過去問を解きながら作った。

愛と気合で移植する

どうせ、サーバーサイドのための便利関数もミドルウェアもデザパタも出揃ってないので、冗長でもとにかく書くしか勝利への道はない。

移植しながら最適化するか、移植してから最適化するかは悩ましい。今回はRustでアプリを書けるメンバーが自分しかいなかったので、「Rubyで最適化してから移植する」とか「Rubyで最適化して、それとは別にRustに移植して、Ruby側の最適化を参考にRust側も最適化する」とかになってしまったので、そこは反省が必要だった。

それはそれとしてRustで最適化した部分で点数が上がったりしたのでちょっと嬉しかった。しかし、点数がガチャであることが後に発覚してちょっと悲しかったりした。 /api/events の内容を一通り移植してN+1を潰すのはできたので、あとはapiのつなぎ込みという感じだったが、まあそのつなぎ込みが結局大変という……

その他の話

今回のISUCONではRustの参照実装が出るかもという話があったが、「どちらかというと出ないでしょう」という仮定のもと、チーム全員書けるRubyから移植することを始めから確定させていた。結果、やっぱり参照実装は出なかった。

まとめ

ISUCONは頻出パターンがあるので、それにあわせてフレームワークやミドルウェアの選定をする
選定ミスると結構つらいが、使ってみないとわからない点もあるので過去問を走るとよい
セッション共有は可能なので、変な言語でやる人にはオススメ
その言語でアプリを書ける人間が2人はいたほうが良い

2018-09-09

Rustコンパイラをクラウドでビルドする備忘録

概要

Rustコンパイラをいじっているとビルドの遅さのせいで作業に支障をきたすため、クラウドでビルドするようにしてみる。

EC2を立ち上げる

Ubuntu 16.04 (HVM) の c5.4xlarge を使うことにする。使うインスタンスの強さは財布と相談して決めることにする。

セットアップ

手元から rust-builder という名前でSSHできるようにする。依存関係として以下を入れておく。

$ sudo apt update && sudo apt upgrade && sudo apt install build-essential python-minimal cmake curl git

スクリプトの配置

Rustコンパイラを手元にcloneして、 x.py があるのと同じ位置に以下の y.sh を置いてexec permissionをつける。

#!/usr/bin/env bash
set -ue

# Remote side:
# sudo apt update && sudo apt upgrade && sudo apt install build-essential python-minimal cmake curl git

builder_host=rust-builder
local_host="$(hostname)"
dirpath="$(realpath --relative-to "$HOME" "$(pwd)")"

git submodule update --init --recursive
rsync -avz --delete --exclude '.git' --exclude '/build' "$HOME/$dirpath/" "$builder_host:$local_host/$dirpath"
ssh -t "$builder_host" "cd $local_host/$dirpath; ./x.py $@"

やっていることは以下。

rsyncで送って向こうでビルドを叩く。
gitを全部転送したくないので .git は省く。ただしsubmoduleが必要なのでsubmodule updateを自動で叩く。 (x.pyは.gitがあるときはsubmodule updateを自動でやってくれる)
build も当然省く。手元のbuildと衝突しうるし、 --delete に巻き込まれないようにする意図もある。ただしbuildというディレクトリがソースツリーの中にあるので、 /build と指定する必要がある。
tmuxを立ち上げたりはしない。ビルドが短くなることが期待されているので途中で切れてもよい。むしろ自動アタッチとか考えるのが面倒。

ビルド

./x.py のかわりに ./y.sh をつけてビルドする。(例: ./y.sh test --stage 1)

設定

クラウドとは関係ないが、コンパイラを開発するときは config.toml を絶対にいじったほうがよい。

compiler-docs = true。ほとんどの関数はdoc-comment (///) を持たないが、シグネチャが一覧できるだけでもありがたい。
debug-assertions = true。これがないとログがほとんど出ない。また、これを有効にすると一部の追加のチェックが行われる。
debuginfo = true, debuginfo-lines = true。これがないとICE(コンパイラ内部エラー)の時のバックトレースがちょっと貧弱で困る。
incremental = true。効果は計測してないけど効率がちょっと上がりそう

2018-06-17

Rustのstaticいろいろ

概要: Rustのstaticの亜種をいろいろ挙げる。

ここでは以下のように分類します。

変数
- ローカル束縛 (引数、 let, match, for, if let, while let)
- 静的変数/定数
  - コンパイル時定数 (const)
    - アイテム位置の定数
    - トレイトの定数
    - 実装の定数
  - 静的変数 (static)
    - 非スコープ借用される静的変数
      - 組み込み static
      - lazy_static!
      - futures-0.2 task_local!
    - スコープ借用される静的変数
      - thread_local!
      - scoped_thread_local!
      - futures-0.1 task_local!

const と static の違い
スコープ借用と非スコープ借用
組み込み static
lazy_static!
thread_local!
scoped_thread_local!
futures-0.1 task_local!
futures-0.2 task_local!

`const` と `static` の違い

const はコンパイル時に決まる値そのものを定義します。この値はコンパイル時定数が必要な他の場所で使えます。
static は(コンパイル時に決まる値が入っている)場所を定義します。値がコンパイル時に決まるのは初期化の都合上にすぎず、それ以上の意味はありません。

たとえば、次のようなコードを考えます。

use std::sync::atomic::{self, AtomicUsize};

const X: AtomicUsize = AtomicUsize::new(0);
static Y: AtomicUsize = AtomicUsize::new(0);

fn main() {
    // どちらもX, Yを5回インクリメントして表示している
    for _ in 0..5 {
        // 0が5回表示される
        println!("X = {}", X.fetch_add(1, atomic::Ordering::SeqCst));
    }
    for _ in 0..5 {
        // ちゃんとインクリメントされる
        println!("Y = {}", Y.fetch_add(1, atomic::Ordering::SeqCst));
    }
}

これを実行すると以下のように出力されます。

X = 0
X = 0
X = 0
X = 0
X = 0
Y = 0
Y = 1
Y = 2
Y = 3
Y = 4

fetch_add は &self をとるので、実際には &X と &Y が計算されています。この & の動作は以下のように規定されています。

X が左辺値なら、そのアドレスをとる。
X が右辺値なら、匿名のローカル変数に X を代入して、そのアドレスをとる。
ただし、 X が右辺値の場合であっても、以下の条件が満たされる場合は、一時変数ではなく匿名の静的領域に X を代入して、そのアドレスをとる。 (RFC1414 rvalue static promotion)
- &mut ではなく & 参照をとろうとしている。
- X はコンパイル時に決定される。
- X は内部可変性をもたない。
- X の計算中に内部可変性をもつ関数が使われていない。

ここで X は内部可変性をもつ定数右辺値ですから、2番目の規則が適用されて、一時変数の値が使われます。その結果毎回新しい AtomicUsize が生成されるため、毎回0が出力されます。

このように、状態を管理する場所を作りたい場合は、 static を使います。そのため static が必要なときは内部可変性をともなうことがほとんどです。

一方、コンパイル時に決まる値そのものを定義したい場合は const が適しています。たとえば以下のような場合です。

const X: usize = 0;
// constは他のconst/staticの初期化に利用できる
static Y: usize = X;

fn main() {
    // constは長さのようなコンパイル時定数に使える
    let a = [0; X];
}

以前は、static ではなく const にしてしまうと借用が常に一時的になってしまって煩わしいという問題がありましたが、rvalue static promotionによりこの問題は改善しています。そのため、「値を定義するときは const」「場所を定義するときは static」という原則に近い運用であまり困らないと思います。

スコープ借用と非スコープ借用

Rustの組み込み static 以外にも、 static に準ずる機能を提供するマクロはいくつかあります。これらは使われ方で「スコープ借用」型と「非スコープ借用」型に分類できます。(※本稿独自の分類)

スコープ借用では、借用ごとにクロージャのコールバックが必要になります。コールバックの終了時に借用の終了が強制されます。

X.with(|x| {
  ...
})

いっぽう、非スコープ借用では &X や X.get(..) のような方法で借用をとることができます。

組み込み `static`

言語に組み込みの static です。

use std::sync::atomic::{self, AtomicUsize};

static COUNTER: AtomicUsize = AtomicUsize::new(0);

fn main() {
    // インクリメント
    COUNTER.fetch_add(1, atomic::Ordering::SeqCst);
}

ポイント

スコープ: プロセス全体で共有される。
要請: T: Sync + 'static
初期化: コンパイル時定数式でしか初期化できない。 (より高度な初期化には lazy_static! を使う)
借用: &X で借用できる。
drop: dropされない。

組み込み `static` の亜種

組み込みの static は原則として単独で使いますが、以下のような亜種があります。

static mut: &mut X での借用が可能になるが、unsafe。排他性を自分で確認する必要がある。 static から借用したものを無理矢理 &mut X として使うとUBになるので static mut にする必要がある。たいていの場合は static + 内部可変性で事足りる。
#[thread_local] static: スレッドローカルになる。不安定機能なので #![feature(thread_local)] が必要。以下の問題点がある。
- thread_local! と違って動かないプラットフォームがある。
- dropされない。
extern { static }: FFIで使われる。

`lazy_static!`

初回使用時に初期化される静的変数のためのマクロです。

Mutex::new() 等がコンパイル時定数でないために必要になることが多いです。これは Mutex::new() が内部で Box::new() を必要としているなどの事情があります。軽量同期ライブラリの parking_lot を使って解決する手もあります。

#[macro_use]
extern crate lazy_static;

use std::sync::Mutex;

lazy_static! {
    // 文法上の特徴: "static" ではなく "static ref" を使う
    static ref COUNTER: Mutex<i64> = Mutex::new(0);
}

fn main() {
    // インクリメント
    *COUNTER.lock().unwrap() += 1;
}

ポイント

スコープ: プロセス全体で共有される。
要請: T: Sync + 'static
初期化: 初回使用時に初期化するので、コンパイル時定数の必要はない。明示的な初期化も可能。
借用: &X で借用できる。(Derefが実装されている)
drop: dropされない。

`thread_local!`

thread_local! は標準ライブラリマクロで、スレッドローカル変数を作ります。

use std::cell::RefCell;

thread_local! {
    static COUNTER: RefCell<i32> = RefCell::new(0);
}

fn main() {
    COUNTER.with(|counter| {
        // インクリメント
        *counter.borrow_mut() += 1;
    })
}

ポイント

スコープ: スレッドごと
要請: T: 'static
初期化: スレッドごとの初回使用時に初期化するので、コンパイル時定数の必要はない。
借用: with でスコープを作って借用する必要がある。
drop: 通常はスレッド終了時にdropされるが、保証されているわけではない。

なお、 thread_localクレイトはスレッドごとの静的変数ではなく、スレッドごと×オブジェクトごとの静的領域を提供します。

`scoped_thread_local!`

scoped_thread_local! は scoped-tlsクレイトが提供するマクロで、参照をそのまま保管できる特殊なストレージを提供します。何らかのコンテキストを暗黙的に引き回す必要がある場合に便利です。 (基本的には明示的に引き回したほうがいいと思いますが)

#[macro_use]
extern crate scoped_tls;

scoped_thread_local!(
    static CONTEXT: i32
);

fn main() {
    let context = 42;
    CONTEXT.set(&context, || {
        CONTEXT.with(|context| {
            println!("context = {}", context);
        })
    })
}

ポイント

スコープ: スレッドごと
要請: T: 'static (設計上は T: ?Sized になりそうだけどそれは対応していない様子) ただし、実際には T ではなく &T を保管する。
初期化: set が呼び出されている間だけ値が入っていて、それ以外の期間に with を呼ぶとパニックになる。
借用: with でスコープを作って借用する必要がある。
drop: 参照渡しなのでdropは関係ない。

futures-0.1 `task_local!`

futuresの task_local! はタスク(軽量スレッド) ごとに異なる記憶領域を擬似的に提供しますが、このインターフェースはfutures-0.1とfutures-0.2で異なります。futures-0.1のそれはスコープ借用で、 thread_local! と似た使い心地です。

#[macro_use]
extern crate futures;
extern crate tokio;

use tokio::prelude::*;

use std::cell::RefCell;

task_local!(
    static COUNTER: RefCell<i32> = RefCell::new(0)
);

fn main() {
    tokio::run(future::lazy(|| {
        COUNTER.with(|counter| {
            // インクリメント
            *counter.borrow_mut() += 1;
        });
        Ok(())
    }));
}

スコープ: タスクごと
要請: T: Send + 'static (宣言時は Send は要求されない)
初期化: タスクごとの初回使用時に初期化するので、コンパイル時定数の必要はない。
借用: with でスコープを作って借用する必要がある。
drop: タスク終了時にdropされる。

futures-0.2 `task_local!`

futuresの task_local! はタスク(軽量スレッド) ごとに異なる記憶領域を擬似的に提供しますが、このインターフェースはfutures-0.1とfutures-0.2で異なります。futures-0.2のそれは非スコープ借用で、面白い構成になっています。contextを引き回しているおかげで、&mut な借用ができるというのも面白い点といえます。

#[macro_use]
extern crate futures;

use futures::prelude::*;

use futures::executor::ThreadPool;

task_local!(
    static COUNTER: i32 = 0
);

fn main() {
    ThreadPool::new()
        .unwrap()
        .run(futures::future::lazy(|context| {
            // インクリメント
            *COUNTER.get_mut(context) += 1;
            Ok(()) as Result<(), futures::never::Never>
        }))
        .unwrap();
}

スコープ: タスクごと
要請: T: Send + 'static (宣言時は Send は要求されない)
初期化: タスクごとの初回使用時に初期化するので、コンパイル時定数の必要はない。
借用: contextのライフタイムだけ借用できるが、同時に1つのtask-local dataしか借用できない。
drop: タスク終了時にdropされる。

なお事実上のfutures-0.3にあたるRFC2408の現時点でのドラフトでは、contextからLocalMapを削除することが提案されています。したがってfutures-0.3のtask-local storageはfutures-0.1方式に戻るのではないかと思います。

まとめ

const は値、 static は場所を定義する。
static っぽいことをするマクロは色々あり、使い分けると幸せになれる。

標準ライブラリ

Duration

InstantとSystemTime

例: 経過時間を調べる

例: unix timeを調べる

例: 特定オフセットでの日付を表示

例: 時刻指定+UTCへの変換+比較

例: 遡及グレゴリオ暦であることを確かめる

例: 天文暦である(0年が存在する)ことを確かめる

例: 閏秒を表現する

例: 閏秒の計算を調べる

例: タイムゾーンをパースする

例: タイムゾーン指定で時刻を表示する

例: タイムゾーン指定で時刻を組み立てる (一意に決まる場合)

例: タイムゾーン指定で時刻を組み立てる (一意に決まらない場合)

まとめ

概要

はじめに

証明

原理

まとめ

概要

evcxr

インストール方法

基本的な動作を試してみる。

仕組み

感想

概要

EC2を立ち上げる

IAMユーザーを作る

セットアップ

自動シャットダウン

スクリプトの配置

ビルド

設定

背景

まず、ISUCONではないコンテストをする覚悟を持つ

チームメンバー集め

フレームワークの選定

テンプレートエンジンの選定

DB・コネクションプール

redis

セッションミドルウェア

過去問を解く

愛と気合で移植する

その他の話

まとめ

概要

EC2を立ち上げる

セットアップ

スクリプトの配置

ビルド

設定

const と static の違い

スコープ借用と非スコープ借用

組み込み static

組み込み static の亜種

lazy_static!

thread_local!

scoped_thread_local!

futures-0.1 task_local!

futures-0.2 task_local!

まとめ

`const` と `static` の違い

組み込み `static`

組み込み `static` の亜種

`lazy_static!`

`thread_local!`

`scoped_thread_local!`

futures-0.1 `task_local!`

futures-0.2 `task_local!`