kubo39's blog

ただの雑記です。

D言語の八進数リテラルの特殊扱い

D言語はかつて八進数リテラルを定義していたが、現在は仕様上Invalidとなっており std.conv.octal を使うようにエラーメッセージが出現する。

(dmd-2.081.1)$ cat octal.d
void main()
{
    auto _ = 010;
}
(dmd-2.081.1)$ dmd octal.d
octal.d(3): Error: octal literals 010 are no longer supported, use std.conv.octal!10 instead

ところが 00 ~ 07 の八進数リテラルのみ特殊扱いしており、以下のコードは評価可能であり実行もされる。 (実はある時点で 0809 というそもそも不正なリテラルをうけつけるバグが混入してしまったのだが、これは修正しておいたので2.082.0以降では正しくエラーとなる)

void main()
{
    assert(01 == 1);
}

これは特殊扱いというより過去そのまま残ったバグなのであるが、phobosをはじめ2文字で表す八進数リテラルは広く使われているために今後修正は(おそらく)行われないだろう。

つまりD言語には隠れた仕様上不正だが許容されている構文が存在しているということである。

D言語の静的配列のちょっとかわった挙動

以下のコードの振る舞いはちょっと変わった感じをうけるかもしれない。

int[2] ARR = [5];

void main()
{
    // int[2] arr = [5]; // Error: mismatched array lengths, 2 and 1
    assert(ARR == [5, 0]);
}

この場合、D言語の静的配列はグローバルに宣言した場合は初期化(ArrayInitializer)として意味解析を行い、ローカルの場合は式(AssignExpression)の文脈で意味解析を行う。 これは構文上問題はないのだが意味論は定義されていないし、ぱっと見た感じ不自然な挙動に思える。 ここでもしエラーにする場合、単純にローカルと同じように扱ってしまえばいいのではと思うが、DのArrayInitializerで評価可能な構文に以下のようなものがある。

int[4] arr = [1:2]; // [0, 2, 0, 0]

これは現在(dmd-2.081.1)意味解析上で先のグローバルな配列宣言と区別することができないので、仮にエラーとする場合はおそらく構文解析に手を入れる必要があると思われる。

DMDにContributeした

D言語の数値まわりの字句解析のはなし - kubo39's blog これがほっといてもなおってなかったので、自分で報告して修正した。

github.com

DMDのビルドははやくて快適だけど、フルテスト回すとそこそこ時間がかかる。

追記

今きづいたけどエラーメッセージにSuffix入らんのでInteger LiteralじゃなくてIntegerにしたほうがよかった。。

あとDeprecationからErrorに昇格したときに0x._pのときにエラーメッセージが正しくならないような気がする。 まあこっちはその時考えればええんちゃう?という感じだけど。

採用面接で聞きたい55の質問

自分ひとりで考えたわけではない(というかほとんどそうではない)が、採用面接で質問したいことを一覧でまとめてみた。

  • リスク管理はしていますか, 破滅的なリスクを無視してしまうことを避けるためになにかしていますか?
  • どうやって成果の判断をするのですか?
  • プロジェクトの納期が私個人の力で達成できない場合は、どのような行動が望まれますか?
  • プロジェクトが失敗した場合、その責任はどの程度追うことになりますか?
  • 開発のライフサイクルモデルはなんですか?
  • アジャイル開発についてどのように考えていますか?
  • 計画はどのように立ててますか?
  • 計画どおりに進んでいるかどうかはどうやって観測しますか?
  • 見積もりはどのように立てますか?
  • 見積もりの不確実性にはどのような手法で対処していますか?
  • 各人の仕事はどのようにアサインしますか?
  • 各人の仕事が予定どおりに進んでいるかどうかはどうやって観測しますか?
  • 上からふってきたスケジュールがどう考えても実現できそうにないときはどのように対処しますか?
  • 何か問題をみつけたときにはどうやって報告しますか?
  • チケット管理システムはありますか?
  • 長期的な視点と短期的な視点での仕事(要求)はどのように可視化していますか?一覧できますか?
  • バグ管理システムは何かつかっていますか?検証する人たちとどのように情報を共有したり、やりとりしていますか?
  • バージョン管理システムはつかってますか?
  • CIはありますか?CIは速いですか?
  • サーバー管理者は別にいますか?カスタマイズは自分たちでできますか?オンプレミスですか?クラウドですか?
  • ソースコードレビューはどのようにしていますか?
  • 設計の正当性はどのように確認していますか?設計の表現(言語)には何を使いますか?
  • 仕様はどのように決めますか?
  • ユーザの声はどのように取得しますか?誰からどのような形で伝わってきますか?
  • エディターは何をつかっていますか?自由に選べますか?
  • 使っている言語はなんですか?その言語を採用している理由は何ですか?他の言語を選択しない理由はなんですか?
  • 開発環境のOSは何をつかっていますか?
  • キーボードは何をつかっていますか?自由に選べますか?
  • ディスプレイは自由に選べますか?
  • オープンソースのライブラリをつかっていますか?パッケージマネージャはつかえますか?
  • ちょっとした自動化はどのように行っていますか?
  • ビルドシステムは何をつかっていますか?どのようにメンテナンスしていますか?
  • わからないことがあったらどのように調べていますか?SOは見れますか?Qiitaは見れますか?
  • 本はどのように買っていますか?最近、買った本はなんですか?
  • 社内で勉強会をすることがありますか?勉強会のテーマはどのように決めますか?今までやって勉強会のテーマを教えてください
  • 自分で学んだことはどのように共有していますか?発表する場はありますか?
  • ふりかえりはしたことがありますか?自分たちのやり方を改善するために何かしていることがありますか?
  • グループチャットは使っていますか?メンバー同士のコミュニケーション手段としてどういうメディアが一番使われていますか?
  • ドキュメンテーションは何をつかっていますか?Markdownですか?プレーンテキストでないとバージョン管理しにくいと思いますが、どうやっていますか?
  • 単体テストはどのように書いてますか?何かテストフレームワークを使っていますか?
  • ペアプログラミングをしたことがありますか?
  • 開発について現状課題だと感じていることはなんですか?改善したいという気持ちはありますか?改善を妨げているものはなんですか?
  • 最近取り入れた新しい技術は何ですか?
  • リリース判定はどのように行いますか?自分たちのソフトウェアがリリースできる品質だというのはどうやって確認していますか?
  • 開発と品証とはどういうふうに協業していますか?
  • 品証はどのタイミングで加わりますか?
  • モデル検査や定理証明系は使っていますか?
  • 本棚を見せていただくことは可能でしょうか?
  • オフィスの中を見学させていただくことはできないでしょうか?
  • チームメンバーと30分程度雑談させていただけないでしょうか?
  • 以下を御読みいただき、御社のジョエル・テストの得点を教えていただけますでしょうか? http://japanese.joelonsoftware.com/Articles/TheJoelTest.html
  • 場合によっては自社開発したコードをオープンソースで公開することは許されますか?
  • 加入している健康保険組合を教えていただけないでしょうか?
  • 社員の就業規則を見せていただくことはできないでしょうか?
  • 定例で行われている打ち合わせはありますか?

こういった質問は直前になってそれっぽい回答を用意するなんてことでは対応できないだろうし、ほんとうに普段どのような仕事の進め方をしているのか把握するのに有用だと思える。 もっといろいろな視点からアップグレードしていきたいので、意見があれば是非教えて欲しい!

std.parallelismざっくり

D言語で並列処理を扱うためのライブラリとして、標準ライブラリにstd.parallelismがある。

これはstd.algorithmやstd.rangeを使うのとほとんど同じような感じで処理が書ける。

以下の処理はOSスレッドによって並列に実行される。 デフォルトのワーカースレッド(内部ではtaskPoolという言葉を使っている)のスレッド数はCPUコア数-1個である。

    // 標準ライブラリの例から持ってきたもの
    import std.algorithm.iteration : map;
    import std.math : approxEqual;
    import std.parallelism : taskPool;
    import std.range : iota;

    enum n = 1_000_000;
    enum delta = 1.0 / n;

    alias getTerm = (int i)
    {
        immutable x = ( i - 0.5 ) * delta;
        return delta / ( 1.0 + x * x ) ;
    };

    immutable pi = 4.0 * taskPool.reduce!"a + b"(n.iota.map!getTerm);

    assert(pi.approxEqual(3.1415926));

タスク

ワーカースレッドが実行する処理の単位をタスクと呼ぶ。 スレッドはタスクキューの先頭から順にタスクを取っていき、タスクの実行が終わったら次のタスクをまたタスクキューから取り出していく。 タスクは少ない場合はスタックに,多い場合はヒープに連続した領域として確保する。(どうもallocaがバグで使えないという理由でmallocを使っているようだ) タスクは随時追加したり、専用の実行スレッドを新たに割り当てて実行させたりすることができる。

実は提供しているparallelやmap、reduceの内部では先頭のタスクはメインスレッドが実行するようになっており、さらに以降のタスクでワーカースレッドがタスクをとらなかった場合にそなえてメインスレッド側で肩代わり実行するようなメカニズムになっている。

「Is Parallel Programming Hard, And, If So, What Can You Do About It?」のSpinLockのPromelaのコードを書き直してみた

TLで「Is Parallel Programming Hard, And, If So, What Can You Do About It?」 https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html という本がおもしろそう、というのがまわってきた。

こういう本には珍しく形式検証を扱っている章があり、SpinLockのモデルをPromelaでコードを書いてSpinでモデル検査を行っていた。 ただそのコードがあまりいけてない書き方だったので、自分で書き直してみた。

以下のコードが書き直した内容。inline lockの中に全部いれてしまえるのならそれでいいし、active [N] proctypeで並列数を調整している。

bit mutex = 0;
int sum;

inline lock() {
  do
    :: 1 -> atomic {
      if
      :: mutex == 0
        sum++
        mutex = 1
        sum--
        break
      :: else
      fi
    }
  od
}

inline unlock() {
  mutex = 0
}

active [3] proctype locker() {
  do
    :: lock()
       unlock()
  od
}

spinはDebian系ならapt-get install spinで入れられる。

早速実行してみる。 全部で51状態、error: 0なので正しく出来ていそうだ。

$ spin -a lock.spin
$ gcc -o pan pan.c
$ ./pan

(Spin Version 6.4.6 -- 2 December 2016)
        + Partial Order Reduction

Full statespace search for:
        never claim             - (none specified)
        assertion violations    +
        acceptance   cycles     - (not selected)
        invalid end states      +

State-vector 36 byte, depth reached 43, errors: 0
       51 states, stored
       94 states, matched
      145 transitions (= stored+matched)
       17 atomic steps
hash conflicts:         0 (resolved)

Stats on memory usage (in Megabytes):
    0.003       equivalent memory usage for states (stored*(State-vector + overhead))
    0.290       actual memory usage for states
  128.000       memory used for hash table (-w24)
    0.534       memory used for DFS stack (-m10000)
  128.730       total actual memory usage


unreached in proctype locker
        lock.spin:29, state 21, "-end-"
        (1 of 21 states)

pan: elapsed time 0 seconds

すごい今更だけど、これってSpinLockとSpin model checkerがかけた高等なギャグなのでは…?

SpinlockのExponential Backoff実装について

SpinLockのExponential Backoffアルゴルズムの実装を少し調べた.

ParkingLot (WebKit,C++)

https://webkit.org/blog/6161/locking-in-webkit/ という素晴らしいブログ記事で spinning という節で触れている. どうやら JikesRVM というJVM実装に由来するようだ.

また本文中で Intelのpause命令に触れている箇所 があるが, どうも思うような性能が出なかったようだ. ParkingLotのSpinLockではマイクロベンチで性能のよかったsched_yieldを使った実装になっている.

Finally, it’s clear that the x86 pause instruction is not useful for our spinlocks. Intel shows that it is a speed-up, but we cannot confirm their claim.

parking_lot (Rust)

spinwait というところで実装されている.

  • カウンタ <= 10: Intelのpause命令 (nightlyかつx86の場合)
  • カウンタ <= 20: sched_yield (Unixの場合)
  • それ以上: falseを返す

Rustの実装ではIntelのpause命令を用いている.

corssbeam-channel (Rust)

crossbeam-channelでは parking_lot のspinwaitは使わず独自で実装している. といっても spin_loop_waitx86のpause命令を使っているし yield_nowsched_yield なのでカウンタの値による分岐が違っているくらい.

どうやら parking_lot でされている話が元で実装されているようだ. https://github.com/Amanieu/parking_lot/issues/43 本家の方は追随しないのだろうか.