2022-11-21

netctl環境でpkgfile-update.serviceがfailする問題を直す

pkgfile

pkgfileはファイルを所有しているパッケージを高速に検索できるプログラムである。そのパッケージをインストールしていなくても検索できるため、システムにないコマンドが入力されたら候補となるパッケージを提案するフックが作られている。

参考:

問題

このpkgfileはsystemdユニットファイルを持っており、システム起動時や一定間隔ごとにデータベースの更新処理を行う。データベースはインターネットからダウンロードしてくるため、ネットワーク設定が完了する前のタイミングではユニットがfailしてしまう。自分はネットワーク設定にnetctlを利用しているのだが、解決法が長いこと分からなかった。

解決法

pkgfile - ArchWikiではなくsystemd - ArchWikiのほうに解決法が書かれていた。

netctl環境でpkgfileを導入するには次のステップを踏まなければならない。

# pacman -Syu
# pacman -S pkgfile
# systemctl enable netctl-wait-online.service # <- これが必要
# systemctl enable pkgfile-update.timer

2022-05-04

競技プログラミングにRustで参加するときに、なるべく高速で入出力する

この記事の続きです。

elderica.hatenablog.jp

自分のコードが遅い

ここずっと、アルゴ式というサイトでいろいろな問題に挑戦しています。このサイトは競うためものではないので、正答例や解説を読んだり、他人のコードを読むのが簡単です。

自分はRustで解いていますが、自分のコードが他人の書いたC++より何倍も実行時間が長いのがずっと気になっていました。RustはC++と遜色ないパフォーマンスが出せる言語だったはずです。自分のコードと、正答例、他人のC++コードを比較してみましたが、問題を解く部分のアルゴリズムはほぼ同じに見えました。そうであれば何がコードを遅くしているのでしょうか？

問題のコード

algo-method.com

use std::collections::VecDeque;

fn main() {
    #[allow(unused)]
    let _x: usize = scan_line()[0];
    let _q: usize = scan_line()[0];

    let mut scheduled_completion_times: VecDeque<usize> = VecDeque::new();
    let mut completed_task_counter: usize = 0;
    for _ in 0.._q {
        let mut query = read_words().into_iter();
        let op_id = query.next().expect("query has operation id");
        let current_time: usize = query.next().unwrap().parse().unwrap();
        match op_id.as_str() {
            "0" => {
                scheduled_completion_times.push_back(current_time + _x);
            }
            "1" => {
                while let Some(&s) = scheduled_completion_times.front() {
                    if s <= current_time {
                        completed_task_counter += 1;
                        scheduled_completion_times.pop_front();
                    } else {
                        break;
                    }
                }
                println!("{}", completed_task_counter);
            }
            _ => unreachable!(),
        }
    }
}

fn read_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    String::from(line.trim())
}

#[allow(dead_code)]
fn read_words() -> Vec<String> {
    read_line().split_whitespace().map(String::from).collect()
}

#[allow(dead_code)]
fn scan_line<F>() -> Vec<F>
where
    F: std::str::FromStr,
{
    read_line()
        .split_whitespace()
        .flat_map(|s| s.parse::<F>())
        .collect()
}

プロファイリングしてみる

犯人探しに役立てるため、プロファイリングを行います。RustではCやC++と同じものが使えるようです。

nnethercote.github.io

qiita.com

cargo-flamegraphを利用してみることにします。まずはインストールします。

$ cargo install flamegraph

新しくパッケージを作り、問題のコードを配置します。ここで、大きめのテストケースをアルゴ式のサイトからダウンロードしておきます。

$ cargo new task889 && cd task889
$ cat > src/main.rs # コードをコピペ
$ cp ~/Downloads/<テストケースのファイル名> ./testcase.txt

計測します。

$ env CARGO_PROFILE_RELEASE_DEBUG=true cargo flamegraph --freq 10000 < testcase.txt > /dev/null

出てきたflamegraph.svg はこんな感じです。ブラウザで開くと、塗り分けられた四角形をクリックして拡大できます。縦軸がスタックで横軸が時間(正確にはサンプリングしたときに実行中だった関数の割合)です。

gist.github.com

std::io::stdio::_print関数とtask889::read_words関数が、main関数を実行中だった時間のほとんどを占めています。コードが遅い原因は入出力が怪しいことがわかりました。

事例を調べてみる

調べてみると、Rustは並行性を考慮してデフォルトではバッファリングを行なわないそうです。

keens.github.io

codom.hatenablog.com

また、競技プログラミング向けに高速で入力が可能なクレートがありました。このクレートはMITライセンスかつモジュール一つで構成されています。このモジュールと標準出力のバッファリングを自分のコードに導入すると、C++と同等の実行時間になりました。

github.com

`fast_input` を読む

このクレートではStdinのロックを取って入力をEOFまで読み、全てをVec<u8>型でヒープに保持します。また、入力を切り出すときはヒープに割り当てを行うような操作をせず、単にスライスを返すだけという設計になっています。

ここで自分のコードとfast_inputを比べてみます。

fn read_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    String::from(line.trim())
}

#[allow(dead_code)]
fn read_words() -> Vec<String> {
    read_line().split_whitespace().map(String::from).collect()
}

単語ごと/行ごとにヒープに割り当てを行っている。
入出力で明示的にロックを取っておらず、バッファリングもしないため、ロックとアンロックが大量に発生する。

問題はここにあったのです。

入力コードの刷新

MITライセンスとはいえ、fast_input をそのまま使い続けるのはどうだろうかと感じ、こんな感じのコードを書きました。slurpする型なので安直にSlurperという名前です。もっと良い名前はあるでしょうか？

use std::cell::Cell;
use std::io::{stdin, Read};

struct Slurper {
    str: String,
    pos: Cell<usize>,
}

impl Slurper {
    fn stdin() -> Self {
        let mut s = String::with_capacity(65536);
        stdin()
            .lock()
            .read_to_string(&mut s)
            .expect("read until EOF");
        Self {
            str: s,
            pos: Cell::new(0),
        }
    }

    fn read_line(&self) -> &str {
        let start_pos = self.pos.get();
        let mut current_pos = start_pos;
        while current_pos < self.str.len() && &self.str[current_pos..current_pos + 1] != "\n" {
            current_pos += 1;
        }
        self.pos.set(current_pos + 1);
        self.str[start_pos..current_pos].trim_end()
    }

    #[allow(dead_code)]
    fn read_word(&self) -> &str {
        let start_pos = self.pos.get();
        let mut current_pos = start_pos;
        while current_pos < self.str.len()
            && &self.str[current_pos..current_pos + 1] != " "
            && &self.str[current_pos..current_pos + 1] != "\n"
        {
            current_pos += 1;
        }
        self.pos.set(current_pos + 1);
        self.str[start_pos..current_pos].trim_end()
    }

    #[allow(dead_code)]
    fn read_words(&self) -> Vec<&str> {
        self.read_line().split_ascii_whitespace().collect()
    }

    #[allow(dead_code)]
    fn scan_line<F>(&self) -> Vec<F>
    where
        F: std::str::FromStr,
    {
        self.read_line()
            .split_ascii_whitespace()
            .flat_map(str::parse::<F>)
            .collect()
    }
}

このコードを導入して試してみると、その結果はfast_inputを使ったものやC++コードとほぼ同等になりました! Vec<u8>ではなくStringで保持しているせいか、ごく僅かに遅いですが十分でしょう。 collectせずにイテレータを返してもいいかもしれません。

反省

実際には、かなりの試行錯誤とGoogle検索に頼り、構造的なアプローチが取れていませんでした。デバッグやプロファイリングの技術をもっと学ぶ必要がありそうです。

検索するなかで便利そうなツールを他にも見つけました。

Hotspot
perfのプロファイリングデータを読んで視覚的に表示するツールです。
KCachegrind
ValgrindのツールのCallgrindが出力したプロファイリングデータを読みこんで視覚的にコールグラフを見られるツールです。プロファイリングにも使えます。
gprof2dot
いろいろなプロファイリングツールが出力したプロファイリングデータから、コールグラフなどを出力できるツールです。

2022-05-04

コンパイラの開発を通してプログラムの書き方について学ぶ取り組み

低レイヤを知りたい人のためのCコンパイラ作成入門 https://www.sigbus.info/compilerbook
困ったら見るリファレンス実装: https://github.com/rui314/chibicc
自分で写経(？)しているコード https://github.com/sbwhitecap/9cc

記録を取ることもなく黙々とやっていたので、日記はステップ11から。

2020/6/11
- 無引数の定義を実装した。
2020/5/28
- 忙しかったのと、ほかにやってみたいことがあったのでブランクが空いてしまった。
- 関数呼び出しの実装をした。
- strndup関数がimplicit declaration errorになって呼べないのでおかしいなと思って、manを見たりStackoverflowを見た。原因は、プログラム内で_POSIX_C_SOURCEを定義してないせいで関数原型宣言が公開されていなかったのだった。
2020/5/12
- for文を追加した。
- ブランク空けちゃったのはもったいない。
- リファレンス実装では補助的なファクトリ関数を用意して読みやすさと書きやすさを高めている。
  - new_unaryやread_expr_stmtなど。
  - リファレンンス実装ではlhsを使いまわしているのだから、自分は二項演算子用のファクトリ関数で書いているが、本来はunary用専用のノードを用意したほうがいいのだろうなと思った。
    - これはTODOとしたい。
2020/5/7
- if文とwhile文を追加した。
- リファレンス実装の中でシリアルナンバーを一時的な変数に保存しているのを見て、どうしてこう書いているのか不思議に思い、そうしないで直接シリアルナンバーを出力するよう書いてみたところ、このテストケースでGNUアセンブラからラベルが見つからないエラーが出た。
  - 理由は単純で、子のノードをコンパイル中にシリアルナンバーがインクリメントされてしまい、戻ってきたら対応が取れなくなってしまうからだった。
2020/5/5
- リファレンス実装に倣ってFunction構造体を足してみた。
- 9ccはchibiccを参考してCでやっているが、zinccでのやりかたも気になりCommon Lispで真似てみることにした。CLだとテストを整備するのが少々煩雑で、Cとシェルスクリプトの組みあわせのやりかたはとても単純で良いと思った。
2020/5/4
- if文を追加しようとしたがバグがあり、その解決の過程で、それまでに書いたコードにはその場しのぎのコードが目立つと感じて一旦取りやめた。
  - コード生成においてpop raxが入力プログラムの各式のコード生成終了後に挿入されてしまい、if文がraxの値に依存していたせいで、必要な値が潰されてしまう現象が起きていた。
- リファレンス実装を見ながらリファクタリングや、制約の撤廃を行なった。
  - main関数のコード生成の責任をコード生成部に移した。
  - ファイル名や関数名をより良いものにした。
  - 各モジュールが公開すべき関数やグローバル変数と非公開とすべき関数とグローバル変数を分けた。
  - オブジェクト生成を専用の関数で行なうように統一した。
  - スタックフレームのサイズを使った変数の個数から計算したり、受け入れ可能なプログラム行をメモリの許す限り無制限とした。
2020/4/28
- ステップ9からステップ11まで進んだ。
- 可変長の変数を定義できるようになった。
  - 本では、識別子に使用可能な文字を判定するのにctype.hのisalnum(3)関数の代わりにis_alnum関数を定義して使っていた。isalnum(3)はアンダースコアを認識せず、ロケールに左右されるためだろうか？
- returnキーワードを導入した。
  - 本ではreturnキーワードのために、トークン用の新たな列挙定数TK_RETURNを定義するように書いていたが、予約語を表すTK_RESERVEDで十分と考えた。演算子もキーワードも言語の予約語と考えたほうがすっきりするし、導入もしやすかった。
  - returnキーワードに対してコード生成するとき、return用のエピローグの中で誤ってmov rsp, rspと書いていて、SEGVを起こした。正しくはmov rsp, rbp。
- gdbのTUIを起動する方法を知った。
  - layout src ソースコードを表示する
  - layout asm 逆アセンブルコードを表示する
  - layout regs レジスタを表示する
  - stepiコマンド(si)で機械語を1命令実行できる

Tips/気をつけること

連結リストを構築するときは、ダミーのhead要素を作ってそこに新しい要素を繋げていって、最後にhead->nextを返すようにするとコードが簡単になります。このような方法ではhead要素に割り当てられたメモリはほとんど無駄になりますが、ローカル変数をアロケートするコストはほぼゼロなので、特に気にする必要はありません。

/* こういうこと？ */

#include <stdio.h>
#include <stdlib.h>

typedef struct Cell Cell;
struct Cell {
    struct Cell *next;
    char *word;
};

/* producer */
Cell *create_list(void) {
    Cell dummy = { .next = NULL, .word = NULL };
    Cell *current = &dummy;

    char *words[] = {"akizuki", "teruzuki", "suzutsuki", "hatsuzuki", NULL};

    for (char **place = words; *place != NULL; place++) {
        Cell *cell = calloc(1, sizeof(Cell));
        cell->word = *place;
        cell->next = NULL;
        current->next = cell;
        current = cell;
    }
    return dummy.next;
}

/* consumer */
int main(void) {
    Cell *current = create_list();

    for (; current != NULL; current = current->next) {
        printf("%s\n", current->word);
    }
    return 0;
}

前章までに実装した機能では、関数の最後に必ず1つのret命令を出力していました。この章で説明した方法でreturn文を実装すると、return文ごとにさらに余分なret命令が出力されることになります。それらの命令はまとめることも可能ですが、ここでは簡単に実装するために、ret命令を複数出力してもかまわないということにしました。こういう細かいところは今の時点では気にしても仕方がないので、実装のシンプルさを優先することが大切です。難しいコードを書けるというのは役立つスキルですが、そもそもコードを難しくしすぎないというのは、時にはさらに役立つスキルなのです。
- 無駄が気になることは多い。つい、もっと賢い処理にしようとしてしまうこともあるが、その努力に見合わない結果になるどころか、複雑な書き方になりやすいってことだろうか？

Undefined Behavior(未定義の動作)

2022-05-04

Common Lispを学ぶためのリソース

まずはこの記事を読むことをおすすめします。

A Road to Common Lisp 翻訳 · GitHub

書籍

Practical Common Lisp(実践Common Lisp)

gigamonkeys.com

一番最初に読むのに向いている。内容は古びてはいるものの、リスト遊びに終始するよりはるかに良い。日本語版もある。

Programming Algorithms

vseloved.github.io

Common Lispで様々なアルゴリズムを実装する本。

Common Lisp Recipes

weitz.de

github.com

Vim/Neovimで編集するためのプラグイン

github.com

ソースコードを読むなら

Alexandria

alexandria.common-lisp.dev

数多くのユーティリティ関数やマクロを提供しており、これを利用するプロダクトも多い。

CL-UTILITIES

www.cliki.net ユーティリティ関数のつめあわせ。

GENERIC-COMPARABILITY

github.com

2022-05-04

OpenSMTPDを使ってOutlook.com経由でメールを送る

前提とする環境はArch Linuxで公式パッケージからopensmtpdをインストールする場合。

まずMicrosoftアカウントでアプリパスワードを発行する。パーミッションは640、所有ユーザはroot、所有グループはsmtpdとして/etc/smtpd/secretsを書く。

 hogefuga myaccount@outlook.jp:アプリパスワード

1列目のhogefugaはラベルなのでなんでもよい。あとで使う。 2列目は使っているメールアドレスとアプリパスワードをコロンで繋いだもの。

/etc/smtpd/smtpd.confは次のような内容にする。

table aliases file:/etc/smtpd/aliases
table secrets file:/etc/smtpd/secrets
 
listen on localhost
 
action "local" maildir alias <aliases>
action "relay" relay host smtp+tls://hogefuga@smtp.office365.com:587 auth <secrets>
 
match for local action "local"
match from local for any action "relay"

7行目のhogefugaはsecretsで定義したラベルにする。

これでsendmail(1)が使えるようになるので、sendjpmailなどで遊ぼう。

つぎのページを参考にした。

support.microsoft.com

2022-05-04

Vim/NeovimでLisp処理系と対話するためのプラグイン Vlime

導入

リポジトリはこちら github.com

公式マニュアル

公式チュートリアル

Susam Pal 氏によるチュートリアル

設定

デフォルトでは'\'(バックスラッシュ)キーをプレフィクスとするコマンドを使う。自分はカンマに設定している。

 let g:vlime_leader = ','
" sbclとcclはプラグイン内(vim/autoload/vlime/server.vim)で対応している
" 他の実装はドキュメントを見て少々特別な設定をする必要がある
let g:vlime_cl_impl = 'ccl'

Vlimeのリポジトリに含まれるstart-vlime.lispを手動でLisp処理系にロードしてから使うプラグインである。そのためシェルのエイリアスを設定しておくとよい。

よく使うコマンド

太字は特によく使う。

,rr Lisp実装を起動してSLIMEサーバを開始し、接続する。オムニ補完はSLIMEサーバと繋がっているときに有効。
,cc 手動で起動したSLIMEサーバに接続する。
- リモートのLisp処理系に繋いでリモートデバッグできる(!)。
REPLへ送信(,s)
- \i インタラクションモードの開始と終了。
  - ノーマルモードでEnterキーを叩くだけで送信してくれる。
- \st バッファ内のトップレベルにある式で、カーソルの下にあるものを送信する。
- \se 今カーソルが合っている式を送信する。
- \sa 今カーソルが合っているアトムを送信する。
  - 変数を参照するときに使う。
- \l 今のファイルをロードする。
- \b 関数の入口にブレークポイントを設定する。
コンパイル(,o)
- \ot バッファ内のトップレベルにある式で、カーソルの下にあるものをコンパイルする。
- \oe 今カーソルが合っている式をコンパイルする。
- \o ビジュアルモードで選択中の領域をコンパイルする。
- \of 今のファイルをコンパイルする。
- \a カーソルの下の式を逆アセンブルする。
定義の削除
- \uf 関数を削除する。
- \us シンボルを削除する。
- \ui 対話的に削除する。
マクロ展開
- \mm MACROEXPANDしてプレビューバッファに出す。
- \m1 MACROEXPAND-1してプレビューバッファに出す。
- \ma 全ての入れ子のマクロを展開する。
REPLバッファ
- CTRL-C REPLスレッドを止める
- \I カーソル下の評価結果をインスペクタで見る。
- \y 無名バッファに評価結果をヤンクする。
- \C REPLバッファをクリアする。
- CTRL-n 表示されている次のオブジェクトに移動？
- CTRL-p 表示されている前のオブジェクトに移動？
デバッガバッファ
- d カーソルの下のフレームについて、ローカル変数やソースファイル位置などの詳細を表示する。
- S カーソル下のフレームに関係するコードへジャンプする。
- T カーソル下のフレームに関係するコードへ新しいタブでジャンプする。
- a ABORTする。
- c CONTINUEする。
- e カーソルの下のフレーム内で式を評価する。
  - 誤りを修正できる？
- E カーソルの下のフレーム内で式を評価してREPLへ送信する。
- C コンディションオブジェクトをインスペクタで見る。
- r カーソル下のフレームを再起動する。
- s カーソル下のフレームでステップ実行を始める。
- x ステップオーバー。
- o ステップアウト。
- D 逆アセンブル。
インスペクタ
- 型やオブジェクトのスロットなどを表示してくれるようだ
- \IT トップレベルにある中でカーソルの下にあるものをインスペクタで見る
- \II カーソルの下の式またはアトムを評価してインスペクタで見る
- \IE カーソルの下の式を評価してインスペクタで見る
- \IA カーソルの下のアトムを評価してインスペクタで見る
- \I ビジュアルモードで選択中の領域を評価してインスペクタで見る
- インスペクタバッファ
  - Space フィールドやボタンを押す
  - CTRL-n 次のフィールドやボタンへ
  - CTRL-p 前のフィールドやボタンへ
  - s カーソルの下のフィールドの値をREPLに送信する。
  - S インスペクタで見ている値をREPLに送信する。
  - p インスペクタで一つ前に見ていたオブジェクトに移動する。
  - P インスペクタで一つ次に見るオブジェクトに移動する。
  - R インスペクタバッファを更新する。
- インプットバッファではiで書いてEscで抜けてEnterキーで確定
パッケージ
- \p 現在のバッファで使うパッケージを指定する
クロスリファレンス

2022-02-23

Rustで1行に数字が並ぶテキストを読む方法

はじめに

AtCoderなどの競技プログラミングのプラットフォームでは、標準入力として空白と改行で区切られたテキストが与えられることが多い。

例

N
A_1 A_2 ... A_N

Rustでは入出力の記述が煩雑になりやすいとされているため、有志によってproconioというクレートが開発されている。

docs.rs

もっと単純に事を済ませることができないかと考えたので、ここにコードを記録しておく。

コード

fn read_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line
}

fn scan_line<F>() -> Vec<F>
where
    F: std::str::FromStr,
{
    read_line()
        .trim()
        .split_whitespace()
        .flat_map(|s| s.parse::<F>())
        .collect()
}

データが空白区切りで、それぞれのデータが FromStr が実装されている型としてパースできればよいということにしてみた。

上の例のフォーマットで入力が与えられるとき、以下のようにすれば読み取ることができる。

if let [n] = scan_line()[..] {
    let a_n = scan_line()[..n].to_vec();
    solve(n, a_n);
}

pkgfile

問題

解決法

自分のコードが遅い

問題のコード

プロファイリングしてみる

事例を調べてみる

fast_input を読む

入力コードの刷新

反省

Tips/気をつけること

まずはこの記事を読むことをおすすめします。

書籍

Practical Common Lisp(実践Common Lisp)

Programming Algorithms

Common Lisp Recipes

Vim/Neovimで編集するためのプラグイン

ソースコードを読むなら

Alexandria

CL-UTILITIES

GENERIC-COMPARABILITY

導入

設定

よく使うコマンド

はじめに

コード

`fast_input` を読む