憂鬱な午後のひととき

4月22日_

第18回数学カフェ

永田町の9a出口と溜池山王の9番出口を間違えてさまよった.

4月21日_

おかしなループに対する警告

gccは弱いらしい.

void loop()
{
    int i;
    for (;;) {
        if (i < 1) {
            i = 1;
        }
    }
}

clang-3.8やVC2015だとiが未初期化と警告を出すけどgcc-5は出さなかった.

int sum(int n, int k)
{
    int s = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; i++) {
            s++;
        }
    }
    return s;
}

もclangは警告を出す. VCはPVS-Studioだと出た. bad loop

ちなみにVCだとloop()のコードのあとにputs("a");とするとloopが無限ループしてるので「制御がわたらないコードです」という警告を出す.

4月20日_

Re: cmake

いくつかはまったところ.

project(mcl CXX ASM)

ASMを明示しないと*.sファイルをアセンブルしてくれなかった.

set(CMAKE_ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/lib)
set(CMAKE_LIBRARY_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/lib)

*.aと*.soの出力先はそれぞれ別に指定しないといけなかった.

${CMAKE_SYSTEM_PROCESSOR} STREQUAL "aarch64"

arm64の判定はこれでよい? あとで確認する.

VAIOを修理に出すことになったのでWindowsを初期化する. ゴールデンウィーク前に戻ってくるとうれしいな.

4月19日_

cmake

mclに入れてくれと要望があったので調べてみる. armやx86を区別するのは面倒そうだ. そういうところは簡単にできるものと思っていたが.

とりあえずライブラリと単体テスト用のバイナリを生成することはできた(CMakeLists.txt).

4月18日_

VAIOのSSD

電源を入れたらSSDがないと表示された. しばらく電源を入れたりたたいたりしてたら復活した. いよいよ修理に出さないと. しかし全然電話がつながらない. チャットのURLにアクセスしてもつながらない.

4月16日_

wafとgas

Pythonによるbuildシステムwafを使うことになってしばし勉強(なんで今wafなのと思わなくもないけど).

アセンブリファイル*.sを使おうとconfigure()でload("gas")したら怒られた. しばらく意味がわからなかったのだが, よくみたらgometalinterで入ったGo AST Scannerの実行ファイル名がgasだった.

そういう名前をぶつけてくるとはチャレンジングだな.
load("as")だとwafがエラーになる.

from waflib import TaskGen
TaskGen.declare_chain(
  rule = 'as ${SRC} -o ${TGT}',
  ext_in = '.s',
  ext_out = '.o'
)

とすると解決した.

4月15日_

Re: gometalinter

これはCの関数を呼び出す前に'// #nosec'というコメントを入れてとりあえず無視でよいと教えてもらった.

リハビリ

肩のマッサージをしてもらうと, 筋肉がゆるくなるせいか姿勢を変えた拍子にめちゃくちゃ痛くなる. しばらく我慢. まだ慢性的な寝不足は解決しそうにない.

4月14日_

gometalinter

gometalinterを教えてもらったので試してみる.

go get -u github.com/alecthomas/gometalinter
// GOPATH/binにパスを通す
gometalinter --install

gometalinter --deadline=16s --disable=gotype ./ターゲットフォルダ

で確認する. cgoの呼び出しで「Use of unsafe calls should be audited,LOW,HIGH (gas)」という警告が出た. endianの問題だろうか.

4月13日_

ebisu_optimized.cpp vol.2

本を読むというよりは本をネタにみながしゃべるというゆるい感じの会.

if-then-elseのはなしの補足. (昔の)Intel CPUの静的分岐予測は

  1. アドレスが大きくなる分岐は分岐しない
  2. アドレスが小さくなる分岐は分岐する

となっている. 条件A)によりif-then-elseのうちよく来る方をifの直後にしたほうがよい

   // if条件の否定
   jcc .else
   // thenの中身
   jmp .next
.else:
   // elseの中身
.next:
// 次のコード

こうすると初回実行時jccは飛ばないと予測してthenの中身に進むので条件分岐のコストを減らせる.

条件B)はループのことを想定している.

.loop:
  // ループの中身
  // 終了条件
  jcc .loop

この場合, 初回のjccはとりあえずloopに戻ると仮定して処理される.

ただCoreアーキテクチャはこれを使ってないとある(最初から動的予測?). likely, unlikely的な分岐ヒントをつけるプレフィクス2EH(分岐しない), 3EH(分岐する)も最近は使わないとある(Software Developer's Manual Vol 2の2.1.1 Instruction Prefixesの注釈). まあ今では「そんなこともあった」という程度なのだろうか.

likely, unlikelyをC++にというのも, だから今更なあという感がある.

(勉強会では出なかったけど)昔見た分岐のルールで個人的におもしろかったのはud2命令を使うもの.

udはundefined instructionの略で実行すると不正な命令の例外を出す. つまり実行してはいけない命令. これを

...
jmp rax
ud2

のように間接分岐命令の直後にud2を置く. するとCPUの命令デコーダはジャンプ以降は実行されないと判断してそのパスの命令デコードを止める(のでリソースがうく)らしい. 未定義命令をそんなふうに使う発想がすごい.

4月12日_

strstr revised

5年前のx86/x64最適化勉強会で調べたstrstrの速さを測り直してみた.

CPUはSkylake(i7-6700)でコンパイラはgcc 7.0.1. /usr/src/linux-headers-`uname -r`以下のファイルをcatでつなげたものに対してベンチマーク(適当に調べたので数値は書かない).

当時はまだライブラリのSSE4.2文字列処理の扱いが甘かったのか自分で書いたもの(mie_string.hpp)の方が速かったが今回はさすがにほぼ互角.

strcasestrはまだ私の方が数倍速い?(後でちゃんと測り直す)

gccのstrlenはSSE4.2を使わずにAVXのバイト比較とpmovmskbを組み合わせていてピーク速度はSSE4.2より速い.

string::findはSIMD化されないのでそれらの4~5倍遅い. 速度を気にするならCの関数を使いなさいというのは変わってない.

C++17で入る予定のboyer_moore(boostのを利用)などはstrstrに比べてずっと遅いので存在価値があるのかしら. 一番速いboyer_moore_horspoolはquick_searchとほぼ同じだった.

4月11日_

travis-ciでLinux kernelドライバのテスト

バックアップシステムWalBのテストできるかなと試してみる.

insmodとかはじかれるかもと思ったけどすんなりと通してくれた. ループバックデバイスを作ってその中にlvcreateなどもできた.

こんなのがクラウドでできるって凄いなあ.

4月5日_

実行時にCPUの種別によって関数を切り替える

gcc 4.8以降では__attribute__にtargetを指定して関数を定義できる. たとえばavx2があるマシンとそうでないマシンとで最適化されたコードを切り替えたい場合, 次のようにする.

#include <stdio.h>
template<class T>
T sumT(const T *p, size_t n)
{
    T sum = 0;
    for (size_t i = 0; i < n; i++) {
        sum += p[i];
    }
    return sum;
}

#pragma GCC push_options
#pragma GCC optimize("-ftree-vectorize")
__attribute__((target("default")))
int sum(const int *p, size_t n)
{
    puts("default");
    return sumT<int>(p, n);
}
#pragma GCC pop_options

#pragma GCC push_options
#pragma GCC optimize("-ftree-vectorize")
#pragma GCC optimize("-O3")
__attribute__((target("avx2")))
int sum(const int *p, size_t n)
{
    puts("avx2");
    return sumT<int>(p, n);
}
#pragma GCC pop_options

int main()
{
    int v[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    printf("%d\n", sum(v, 8));
}
// g++ -O2 t.cpp
// avx2なしマシン
./a.out
default
36
// avx2ありマシン
avx2
36

このようにtargetをdefaultとavx2とを指定するとプログラム起動時にavx2が使えることを検出すれば自動的にそちらの関数が呼ばれる.

sumはリンカレベルではsum.avx2というような名前になっている. 今のところclangでは使えないようだ.

4月4日_

inlineとstatic inline

staticとstatic inlineが分かりにくいとの声を聞いたのでまとめてみた(4/2から移動).

staticとinline
staticあり staticなし
inlineあり 複数実体 単一実体
inlineなし 複数実体 リンクエラー
// t.h
#include <stdio.h>
static inline int f1() { static int a; return ++a; }
static int f2() { static int a; return ++a; }
inline int f3() { static int a; return ++a; }
//int f4() { static int a; return ++a; } /* リンクエラー */
// t.cpp
#include "t.h"
void fff()
{
   f1();
   f2();
   f3();
   printf("&f1=%p &f2=%p &f3=%p\n", &f1, &f2, &f3);
}
// s.cpp
#include "t.h"
void fff();
int main()
{
   fff();
   printf("&f1=%p &f2=%p &f3=%p\n", &f1, &f2, &f3);
   printf("f1=%d f2=%d f3=%d\n", f1(), f2(), f3());
}

これを実行すると例えば

&f1=0x400526 &f2=0x400541 &f3=0x400590
f1=1 f2=1 f3=2
&f1=0x4005ab &f2=0x4005c6 &f3=0x400590

と表示される. f1, f2は異なる関数アドレスを持っている. 関数内のstatic変数も異なるのでs.cppとt.cppで2回呼び出しても値は1しか増えていない.

f3は同じ関数アドレスで実体が同じだから2回呼び出してstatic変数aの値も2増えている. static inlineとstaticの違いは殆どない. コンパイラの最適化により関数が小さければinlineがついてなくてもinline化されることもあるし, 関数が大きいとinlineがついていてもinline化されないことがある.

クラスのメソッドの関数定義は暗黙にinlineがついたのと同じ挙動をする. template関数の特殊化をヘッダに書く場合はinlineをつけないと多重定義になってしまう.

4月3日_

GLV

ペアリングで使う群G1のスカラー倍算で必要になるマルチスカラー倍の実装に手間取った.

最上位ビットを取り出すbsr(x)はx == 0のとき未定義だから別処理にしないといけない. lzcntを使ってもいいけどCPU判別が面倒なので別処理にした.

4月2日_

Goのtag

cgoの最初にタグ名とコマンドラインオプションをつけておくと条件コンパイルができる. bls.goではこうしてみた.

/*
#cgo CFLAGS:-I../../include -DBLS_MAX_OP_UNIT_SIZE=6
#cgo bn256 CFLAGS:-UBLS_MAX_OP_UNIT_SIZE -DBLS_MAX_OP_UNIT_SIZE=4
#cgo bn384 CFLAGS:-UBLS_MAX_OP_UNIT_SIZE -DBLS_MAX_OP_UNIT_SIZE=6
*/

デフォルト, あるいはgo -tags bn384とするとUNIT_SIZE = 6になり, go -tags bn256でSIZE = 4としてコンパイルできる.

一度-Uでマクロをundefしないと警告がうっとうしい.

構造体のサイズが変わるので異なるtagでビルドしたライブラリをリンクすると予測不能なエラーになる. こういうのは気を付けていても忘れたころにやってしまって痛い目に会う. 安全にするため予めbls.cppみたいにライブラリ初期化時にその値を渡してチェックする.

init()関数をinlineでヘッダに書いてしまうと意味がないので注意(昔やってしまった).

// hppでmaxUnitSizeにマクロの値を初期値で渡す.
void init(int curve = CurveFp254BNb, int maxUnitSize = BLS_MAX_OP_UNIT_SIZE);
// cppでcppがコンパイルされたときのマクロの値を同じかチェックする.
void init(int curve, int maxUnitSize)
{
    if (maxUnitSize != BLS_MAX_OP_UNIT_SIZE) {
        throw cybozu::Exception("bls:init:bad maxUnitSize") << maxUnitSize << BLS_MAX_OP_UNIT_SIZE;
    }
    ...
4月1日_

docker

今月はいろいろと普段触らないものを触ってみよう.

Dockerfileにインストールしたいものを書いてdocker buildでimageを作り, それを起動する. docker runに -vオプションでホストとゲストのディレクトリを接続できる.

もう少しいじって慣れたらメモをまとめよう.


御意見は光成滋生<herumi@nifty.com>までお願いします