コグノスケ


link 未来から過去へ表示(*)  link 過去から未来へ表示

link もっと前
2022年11月11日 >>> 2022年10月29日
link もっと後

2022年11月11日

手動の最適化 対 コンパイラの最適化

ポッキーの日だそうですが、1(と0)といえば2進数、2進数といえばビット操作ですね(?)。以前 Bit Twiddling Hacks を最新のコンパイラ達に向けて試したときの悲しい結果をメモしておきたいと思います。

試したのはConditionally set or clear bits without branchingという項目で、fがtrueならwとmのビット論理和を、fがfalseならwからmのビットを消去した値を返す処理です。素朴な実装ではif文を使うでしょう。

1つ目の方式: Conditionally set or clear bits

int cond_set_or_clear1(bool f, int m, int w)
{
    if (f)
        return w | m;
    else
        return w & ~m;
}

さきほどのサイトでは最適化版として、条件分岐をなくす、データ依存性をなくす(スーパースカラプロセッサ用)、2つのバージョンを掲げています。まずは条件分岐をなくした版のコードを紹介します。

2つ目の方式: Conditionally set or clear bits (without branching)

int cond_set_or_clear2(bool f, int m, int w)
{
    return w ^ ((-f ^ w) & m);
}

分岐がなくなっています。なんでこれで同じ動作をするのか?は説明が必要でしょう。fがtrueなら -f = -1となり、-f ^ wはwのビット反転(notと同じ)と同じ結果 -1 ^ w = ~wになります。よって右側の括弧内 (-f ^ w) & m = ~w & mです。

あとは~w & mはw = 0, m = 1のビットだけ1になって残り、あとは全部0になります。w ^ (~w & m) はw | mと同じ結果ですが……そう言われてもわかりにくいので表にします。

w~wm~w & mw ^ (~w & m)
10101
10001
01111
01000

一方fがfalseの場合、0とみなされるので -f = 0となって、-f ^ w = 0 ^ w = wです。右側の括弧内 (-f ^ w) & m = w & mです。w ^ (w & m) は先ほどとは逆でw = 1, m = 1のビットだけ1になって残り、あとは全部0になります。

最後にwとこの結果をxorすることでwとmがともに1のビットだけ0になりますから、w ^ (w & m) はw & ~mと同じ結果です、が……これも表がわかりやすいでしょう。

wmw & mw ^ (w & m)
1110
1001
0100
0000

次にスーパースカラ版のコードを紹介します。

3つ目の方式: Conditionally set or clear bits (without branching, superscaler)

int cond_set_or_clear3(bool f, int m, int w)
{
    return (w & ~m) | (-f & m);
}

これは先ほどよりシンプルです。左側の括弧はfによらず常にw & ~mで一定で、右側の括弧の値だけが変化します。

まずfがtrueなら -f = -1となり、-f & m = mです。(w & ~m) | mですが、w & ~mはwからmの1となっているビット位置を0にする演算でした。そこにmをorすると消えたビットは再び1になります。すなわちw | mと同じ結果です。

wmw & ~m(w & ~m) | m
1101
1011
0101
0000

次にfがfalseなら -f = 0となり、-f & m = 0です。よって (w & ~m) | 0 = w & ~mになります。

なぜスーパースカラ向けか書いていませんが、w & ~mと -f & mに依存性がなくて同時に演算できるからだと思われます。じゃあ全部これでいいじゃないか?と思われるかもしれませんが、演算回数を見ると、

2つ目の方式と3つ目の方式の演算回数
2つ目の方式: w ^ ((-f ^ w) & m)

neg, xor, and, xorの4回の演算が必要

3つ目の方式: (w & ~m) | (-f & m)

not, and, neg, and, orの5回の演算が必要

このため同時に演算できないプロセッサの場合は2つ目の方式の方が良いと言えます。

全てを無にするコンパイラの最適化

ここまで長々と紹介しておいてこんなことを言うのは憚られますけど。この手のビット魔術は面白いのでつい手を出したくなりますが、最近のコンパイラに対しC言語レベルでの最適化はあまり意味がないです。

論より証拠でGCC 12.2.0の結果から見てみましょう。


GCC 12.2.0でのコンパイル結果

あれだけグダグダ語った3つ目の方式でしたが、なんと2つ目の方式と全く同じバイナリになりました

GCCだけでは証拠として不安でしょうか?では次にclang 15.0.0の結果も見ましょう。


clang 15.0.0でのコンパイル結果

なんと3つ目の方式は「これ分岐じゃね?」と解釈されて分岐に戻されてしまいました。これが分岐に見えるclangはスゴイですね。私はこのコードを見ても分岐には見えません……。

1つ目の方式と2つ目の方式が違うバイナリになるところを見る限り、全くの無意味ではないです。しかし見やすさでは大幅に劣ります。基本は素朴なコードにしておき、遅くて困る場合のみビット魔術に手を出すべきでしょう。

編集者:すずき(2022/11/13 00:35)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2022年11月8日

皆既月食と惑星食

今日は皆既月食と惑星食(天王星)が同時に観測できる非常に珍しい日だそうです。天王星はさすがに撮影できないでしょうけど、月ならなんとか撮れるだろうと思い、三脚とカメラを持って撮影しました。

肉眼で見ると赤くボンヤリとした月に見えます。先日(2022年9月10日の日記参照)撮った、中秋の名月と比較するとかなり暗いです。

まずコンデジでは暗くて写りません。マニュアルで明るさの限界を狙って設定したものの、私の腕と知識では下記の写真が限界でした……。


コンデジ(CASIO EXILIM EX-ZR1300)で撮影

月の左下に天王星らしき点?が写っています。天王星は青いと聞きましたが、あまりに点が小さすぎて良くわかりません。もしかしたらレンズについたゴミかもしれないです。

奥さんの一眼レフでも撮りました。さすがの高解像度&性能ですが、残念ながらレンズのズーム倍率が足りず非常に小さくしか写りません。


一眼レフ(Canon EOS Kiss X10, Canon EF-S 18-55mmレンズ)で撮影

引き延ばしたところボンヤリした写真になってしまいました。世の写真家が撮影したきれいな写真がたくさんあるので、それを眺めることにします。

編集者:すずき(2022/11/09 18:57)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2022年11月6日

JTSA Limited練習記録2022

目次: 射的

スピードシューティングを始めてから半年ほど経過しました。いよいよ11月末は公式大会(リミティッド - 一般社団法人日本トイガン射撃協会JTSA)です。今までの練習会のタイムをまとめておこうかと思います。

基本的に練習は週1回のみです。たまに練習以外のシューティング系イベントにも行きますが、さほどタイム上達とは関係ないはず。たぶん。


JTSA Limited練習会の記録

トータルタイムが2種類ある理由は、途中でStage 5の追加が正式発表されたためです。そのため7月まではStage 1〜4の合計(赤い線、右軸)、8月からはStage 1〜5の合計(青い線、右軸)が記録となります。ですが8月以降もStage 1〜4の合計タイムを見たら、今までと比べて上達or停滞が分かりやすいかも?と思い、表示しています。

最初こそ順調に早くなっていますが、ここ2〜3か月は伸びが止まっています、記録は正直だな〜。タイムは80秒台前半、脱・初心者レベル(※)くらいです。もうオジサンだし、あんまり根詰めたり無理するとケガするだけなんで、気楽&気長にやります。

(※)大会の前の公式記録会だと、総合(Hands Up)で84/101位、カテゴリ内(LM)で21/28位でした。

編集者:すずき(2022/11/09 23:24)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2022年10月31日

Killできるpopenが欲しい

会社でpopenで作った子プロセスが残ってしまうが何とかならないか?という相談を受けて、面白そうだったので取り組んでみました。日記でも残しておきます。コード的には特に機密情報はありません。

popenて何ですか

マニュアルを読みましょう(Manpage of popen)。少しだけ解説するなら、子プロセスの入出力をパイプ経由で送ったり受け取ったりできるライブラリ関数です。

例えばyesコマンドをpopenで実行すると、出力パイプからはy y y y ... という文字列が読みだせます。

popenの困ったところ

非常に便利なpopenですが、子プロセスが終了するかどうかは子プロセス次第、言い換えれば子プロセスを強制的に終了させる方法がないことが欠点です。

例えば、先ほど挙げたyesコマンドは勝手に終了しないコマンドの代表例です。popen関数を呼んだ親プロセスが終了しても、子プロセスのyesコマンドは終了しないまま残ります。

改良popenを作る

実はpopen関数は既存のライブラリ関数やシステムコールの組み合わせで実現できます。先にコードを載せましょうか。

killできるpopenのコード

/* SPDX-License-Identifier: Apache-2.0 */

#define _GNU_SOURCE

#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

void usage(int argc, char *argv[])
{
	printf("usage:\n"
		"  %s cmdline\n", argv[0]);
}

int main(int argc, char *argv[])
{
	const char *cmdline;
	pid_t pid, pgrp;
	int pipefd[2];
	FILE *fp;
	int r;

	if (argc <= 1) {
		usage(argc, argv);
		return -1;
	}
	
	cmdline = argv[1];
	
	printf("cmdline: %s\n", cmdline);

	// パイプを作成します。パイプに読み書きするファイルディスクリプタ(pipefd)2つが返されます。
	// pipefd[0] が読み出し用、pipefd[1] が書き込み用です。
	r = pipe2(pipefd, 0);
	if (r == -1) {
		perror("pipe2");
		return -1;
	}

	// ファイルディスクリプタをFILE * でラップします。
	// popenはFILE * を返すインタフェースなので、それに合わせるためです。
	fp = fdopen(pipefd[0], "r");
	if (fp == NULL) {
		perror("fdopen");
		return -1;
	}

	// 子プロセスを生成します。
	//    pidには子プロセスの場合は0、親プロセスの場合は子プロセスのプロセスIDが返されます。
	pid = fork();
	if (pid == -1) {
		perror("fork");
		return -1;
	} else if (pid == 0) {
		// child

		// 子プロセスを新たなプロセスグループに移します。
		// 理由はあとでkillを呼ぶときに親プロセスまで巻き添えにしないようにするためです。
		// setpgidを呼ばない場合
		//    プロセスグループA: 親、子、指定したコマンド
		//    kill(プロセスグループA): 親も子もコマンドも全て強制終了してしまう
		// setpgidを呼んだ場合
		//    プロセスグループA: 親
		//    プロセスグループB: 子、指定したコマンド
		//    kill(プロセスグループB): 子とコマンドのみ強制終了
		r = setpgid(0, getpid());
		if (r == -1) {
			perror("setpgrp");
			return -1;
		}

		// 子プロセスの標準出力を閉じ、パイプの書き込み用ファイルディスクリプタを代わりに使います。
		// つまり子プロセスの出力がパイプに書き込まれます。
		r = dup2(pipefd[1], 1);
		if (r == -1) {
			perror("dup(child)");
			return -1;
		}

		// シェルを利用して引数に指定されたコマンドを実行します。
		// シェルを利用する理由はpopenと同じ仕様(コマンド引数を1つの文字列で渡す)にしたいからです。
		// シェルを挟まない場合は、複数の文字列に分割して渡す必要があります。
		r = execl("/bin/sh", "sh", "-c", cmdline, (char *)NULL);
		if (r == -1) {
			perror("execl(child)");
			return -1;
		}

		// not reach here
		return -1;
	}

	// parent

	// パイプから読みだすと子プロセスが標準出力に出そうとした文字列が読める
	char buf[10];
	memset(buf, 0, sizeof(buf));
	fread(buf, 1, sizeof(buf) - 1, fp);

	printf("read from pipe: %s\n", buf);

	printf("sleep 5\n");
	sleep(5);

	// 子プロセスのプロセスグループを取得します。
	//    pidには子プロセスのプロセスIDが返されます。
	//    forkの部分も参照してください。
	printf("getpgid() pid:%d\n", (int)pid);
	pgrp = getpgid(pid);
	if (pgrp == -1) {
		perror("getpgid");
		return -1;
	}

	// 子プロセスのプロセスグループを強制終了します。
	printf("kill(SIGTERM) pgrp:%d\n", (int)pgrp);
	r = kill(-pgrp, SIGTERM);
	if (r == -1) {
		perror("killpg");
		return -1;
	}

	// 子プロセスが終了するまで待ちます。
	printf("wait child pid:%d\n", (int)pid);
	int wstat;
	r = waitpid(-pid, &wstat, 0);
	if (r == -1) {
		perror("waitpid");
		return -1;
	}
	if (r != pid) {
		fprintf(stderr, "kill %d but terminated pid %d, why?\n", (int)pid, (int)r);
	}

	printf("done!!\n");

	return 0;
}

そこそこ長いですね。

簡単な解説

コードを見ると目がチカチカする方向けにコメントだけ抜き出しました。動きが分かりやすいと思います。

  • pipe2: パイプを作成します。パイプに読み書きするファイルディスクリプタ(pipefd)2つが返されます。pipefd[0] が読み出し用、pipefd[1] が書き込み用です。
  • fdopen: ファイルディスクリプタをFILE * でラップします。popenはFILE * を返すインタフェースなので、それに合わせるためです。
  • fork: 子プロセスを生成します。

子プロセスはこんな動きです。

  • setpgid: 子プロセスを新たなプロセスグループに移します。理由はあとでkillを呼ぶときに親プロセスまで巻き添えにしないようにするためです。
  • dup2: 子プロセスの標準出力を閉じ、パイプの書き込み用ファイルディスクリプタを代わりに使います。つまり子プロセスの出力がパイプに書き込まれます。
  • execl: シェルを利用して引数に指定されたコマンドを実行します。シェルを利用する理由はpopenと同じ仕様(コマンド引数を1つの文字列で渡す)にしたいからです。シェルを挟まない場合は、複数の文字列に分割して渡す必要があります。

親プロセスはこんな動きです。

  • getpgid: 子プロセスのプロセスグループを取得します。
  • kill: 子プロセスのプロセスグループを強制終了します。
  • waitpid: 子プロセスが終了するまで待ちます。

プロセスの親子関係はこうなります。

プロセスの親子関係
|-a.out,536208 yes
|   `-sh,536209 -c yes
|       `-yes,536210

もしコマンドがさらに孫、ひ孫プロセスを生成しても、プロセスグループが一緒である限りkillが効くはずです。

残っている改善点

今回紹介した実装はpopenの完全な上位互換ではありません。理由としては入力側を扱えないこと、popenのようなAPIとして使えないこと、が挙げられますが、拡張は容易だと思います。

編集者:すずき(2023/08/10 01:48)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2022年10月29日

ヘッドフォン

今までお世話になった(なっている)ヘッドフォンたちをまとめておきます。

密閉タイプ。

SONY MDR-XD050
音は良いです、ややドンシャリかな?耳当てはフワフワで良いですが、すぐ表面が剥がれてしまうのはイケてないです。
SHURE SRH440-A
音はとても良いです。耳当ての合皮が汗を全く吸わず、夏はイマイチでした……。
SONY MDR-HW700
無線タイプです。音は良いのですが、無線とWi-Fiと干渉するのがあまり好きではないです。高かったのにあまり使ってなくてもったいない。

オープンタイプ。

Pioneer SE-M290
音はモワモワで遠くに居る感じであまり良くはないですが、付け心地はとても良くて疲れません。
audio-technica ATH-TAD500
音はややキンキンですが私は好きな音です。長時間使うと耳が痛いのが難点です。ヘッドバンド部分が壊れてしまったのでお別れ。
Superlux HD681B
金属っぽいキンキンした音です。耳当てがなんだかゴワゴワしていてイマイチです。
SENNHEISER HD599
癖を感じない良い音です。耳当ては良い感じですが、サイズが合っていないのか長時間使うと頭痛がします。
編集者:すずき(2022/11/12 15:31)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
2022年11月11日 >>> 2022年10月29日
link もっと後

管理用メニュー

link 記事を新規作成

<2022>
<<<11>>>
--12345
6789101112
13141516171819
20212223242526
27282930---

最近のコメント5件

  • link 21年3月13日
    すずきさん (03/05 15:13)
    「あー、このプログラムがまずいんですね。ご...」
  • link 21年3月13日
    emkさん (03/05 12:44)
    「キャストでvolatileを外してアクセ...」
  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」

最近の記事3件

  • link 24年3月25日
    すずき (03/26 03:20)
    「[Might and Magic Book One TASのその後] 目次: Might and Magicファミコン版以前(...」
  • link 21年10月4日
    すずき (03/26 03:14)
    「[Might and Magicファミコン版 - まとめリンク] 目次: Might and Magicファミコン版TASに挑...」
  • link 24年3月19日
    すずき (03/20 02:52)
    「[モジュラージャックの規格] 古くは電話線で、今だとEthernetで良く見かけるモジュラージャックというコネクタとレセプタク...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 03/26 03:20