2011年12月23日金曜日

Test.Framework & TemplateHaskell

LeftistHeapの実装をQuickCheckでテストするコードを有識者に見てもらったところ、QuickCheck単体で使うのではなく、TestFramework (とそのTemplateHaskell版) を使うのがいまどきのコードだと聞いたのでやってみた。

{-# LANGUAGE TemplateHaskell #-}
module TestLeftistHeap where

import Test.Framework.TH
import Test.Framework
import Test.HUnit
import Test.Framework.Providers.HUnit
import Test.Framework.Providers.QuickCheck2

import Data.List
import LeftistHeap

main = $(defaultMainGenerator)

prop_insert :: [Int] -> Bool
prop_insert ns = test' lh $ sort ns
  where
    lh :: LeftistHeap Int
    lh = foldl (\h n -> LeftistHeap.insert n h) empty ns
    
    test' :: (LeftistHeap Int) -> [Int] -> Bool
    test' _ []     = True
    test' h (m:ms) = findMin h == m && test' (deleteMin h) ms

TestFrameworkは、QuickCheckによるプロパティテストと、HUnitによるunit testとをひとつにまとめて並列に実行してくれる(ただし、テスト結果のdiffを取りやすいように、結果は決まった順序で出力する)フレームワークだそうです。と、Hackageのページを直訳してみる。

TemplateHaskellは、Haskell版プリプロセッサ(多分)。使わないコードを "{- ... -}" で囲んでコメントアウトしておいても、なんかパースされてコンパイルエラーになってしまった。一般的な使い方はよくわからないが、TestFrameworkと共に使うと、ほんの少しだけコード量が少なくなる。

2011年11月26日土曜日

KVM上のFedora 16 kernelをgdbでデバッグ

まえがき

こないだ衝動にかられてThinkpad X121e (Core i3モデル)を買ってしまった。IBM時代からのThinkpadファンだったのだが、iPhoneを買ったのを機に、にわかMacユーザーになっていたので、久しぶりにPCに復帰した形だ。キーボードがMacBook Proと同じタイプ(セパレート型というのだろうか)だが、MacBook Proよりもタイプ感が良い気がする。・・・というように、5万円(MacBook Proの1/3)の割にかなり満足度の高い買い物であった。Windows要らないので、そのぶん1000円でもいいから安くして欲しいとは思うが、まぁしょうがない。Windows 7さまは一度も起動されることなくFedora 16で上書きされた。さようなら。

さて新しいマシンで何をしようかと思っていたが、あれこれ記事を見ていると、KVMで動かしたLinux kernelをgdbでデバッグできるらしいので、それを試してみた。数年前にXenのインストールで挫折したので、仮想化関連で何か試してみたかったのだ。

ネットワークの知識不足もあってはまったところも多いので、まとめておきたい。なお、ホストはFedora 16 x86_64なので、環境が異なる人は多少の読み替えが必要だろう。


ネットワーク

KVM のドキュメントはたくさん見つかるが、多くはKVMを外からアクセス可能な、完全に独立したマシンとして作成することを前提としているようで、KVMに外からつなげるにはどうするか、ということを説明しているページが多いような気がする。

しかし、「KVMからインターネットにアクセスしたり、ホストマシンからKVMにアクセスしたりするが、その他のマシンからKVMにアクセスすることはない」という環境の場合、特別な設定は必要ない。「仮想ブリッジを作って外のネットワークと繋げて・・・」という説明もあるが、ブリッジをつくろうとすると、NetworkManagerが使えなくなって不便だし(NetworkManagerはブリッジをサポートしていない)、(ラップトップではデフォルトであろう)Wifiのカード・ドライバがブリッジに対応しているか調べなきゃいけないしで、大変なことこの上ないので、何もしないのがよかろう。

Fedora 16にはlibvirtがデフォルトで入っていて、ifconfigするとvirbr0という、見るからに仮想っぽいインターフェイスが見えるのだが、これを使ってホスト<->KVMの通信ができる。
$ /sbin/ifconfig virbr0              
virbr0    Link encap:Ethernet  HWaddr 52:54:00:F0:D1:F7  
inet addr:192.168.122.1  Bcast:192.168.122.255  Mask:255.255.255.0
UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
RX packets:5713 errors:0 dropped:0 overruns:0 frame:0
TX packets:5048 errors:0 dropped:0 overruns:0 carrier:0
collisions:0 txqueuelen:0 
RX bytes:1552502 (1.4 MiB)  TX bytes:344602 (336.5 KiB)
あと、NAT/IP masqueradeも設定されていて、iptables -t nat -Lで確認できる。
$ sudo /sbin/iptables -t nat -L POSTROUTING
Chain POSTROUTING (policy ACCEPT)
target     prot opt source               destination         
MASQUERADE  tcp  --  192.168.122.0/24    !192.168.122.0/24     masq ports: 1024-65535
MASQUERADE  udp  --  192.168.122.0/24    !192.168.122.0/24     masq ports: 1024-65535
MASQUERADE  all  --  192.168.122.0/24    !192.168.122.0/24    

まとめると、KVM用に192.168.122.0/24のネットワークが用意されていて、ホスト<ー>KVMはこのネットワークでつながることになる。また、ホストのiptablesにNAT/IP masqueradeの設定があるので、KVMからインターネットにアクセスすることもできる。(が、インターネット側からKVMにはアクセスできない)


Fedora 16 インストール

ネットワークは問題ないので、いよいよ仮想マシンを作ってOSをインストールする。virt-installというコマンドで、仮想マシンの設定と、OSインストールをスタートできる。(virt-managerを使うとGUIでインストールできるが試してない。)

ちなみに、virt-installとかvirt-managerとか(あとででてくる)virshとかは、libvirtが提供するコマンドで、KVMやXenやVirtualBoxなどの複数の仮想化環境を統一的に扱うためのツール群である(が、ここではKVMしか使わないので、恩恵はない。)

$ sudo virt-install \
-n fedora.kvm \ -- 仮想マシンの名前
-r 1024 \ -- メモリ (MB)
-f /var/kvm/images/fedora.kvm.img \ -- ディスクイメージの保存場所
-s 20 \ -- ディスクのサイズ
--vcpus=1 \ -- 割り当てるCPUの数
--os-type=linux \ -- OSタイプ。何に使われるのか不明。
--os-variant=fedora16 \ -- OSの細かい種別。何に使われるのか不明。
--network network=default \ -- 後述
--nographics \ -- テキストモードでインストールする
--location='http://ftp.jaist.ac.jp/pub/Linux/Fedora/releases/16/Fedora/x86_64/os/' \ -- インストールソースの指定。"man virt-install"にサンプルがある。
--extra-args='console=tty0 console=ttyS0,115200n8 serial' -- 再起動後にvirshから接続するために必要っぽいが、よくわからない。

"man virt-install"のNetworking Configurationを読むとわかるが、network=XXXのXXXに指定する名前は、virshコマンドで確認できる。virshは、おそらくVIRtual SHellの略でlibvirtの機能にアクセスするためのシェル。KVM作成後のVMの起動や終了もvirshから行う。以下のようにして、ネットワーク名を確認できる。(ホスト側に普通にFedora 16をインストールしていれば)"default"というネットワークが見えるはず。
$ sudo virsh
Welcome to virsh, the virtualization interactive terminal.

Type:  'help' for help with commands
'quit' to quit

virsh # net-list
Name                 State      Autostart
-----------------------------------------
default              active     yes       

で、上記のvirt-installコマンドを実行すると、Fedoraのサイトからいろいろダウンロードしたあと、インストールプロセスが始まる。
KVMとは本質的には関係ないが、Fedora 16はテキストインストール時には、デフォルトパーティション(LVMとか使うやつ)しか選べない(カスタマイズできない)。カスタマイズしたい場合は、途中でVNCを使ってGUIインストールに切り替えれば良い。その場合は、yumを使ってホスト側にtigervncというVNCクライアントをインストールしておくこと。

インストールが終わると、KVMが再起動して、ゲスト側のログインが表示される。

なお、KVM起動したあと、virshで"console fedora.kvm"と打つと、KVMのコンソールにつなぐことができる。(何らかの事情でSSHが使えなくなった時などは、コンソール接続必須)ちなみに、virshにはconnectというサブコマンドもあり、こちらはhypervisorに接続するためのコマンドなのだが、間違えて "connect fedora.kvm"と入力すると、virshの内部状態が壊れるようで、それ以降のすべてのコマンドがエラーになる。(quitして再度virshを起動すると直る)virsh 0.9.6のバグだと思うが気をつけていただきたい。


ゲストのIPの固定

ここまでの作業でKVM上のゲストOSは普通に使うことができる。が、ゲスト側のIPがDHCPなので、IPがいつか変わってしまうのではないかと思うと不安で夜も眠れないので、IPを固定することにする。

ホスト-KVM間の仮想ネットワークではDHCPが動いていて、192.168.122.2-254のIP(つまり全て)をDHCPで使っているので、まずこれを変更する。(変更しなくても問題ないのかもしれないが、気持ち悪いので) virshを起動し、"net-edit default"と入力すると、設定を変更できる。

<network>
  <name>default</name>
  <uuid>6c2b5811-9733-490f-b14a-e7d3c73c5d87</uuid>
  <forward mode='nat'/>
  <bridge name='virbr0' stp='on' delay='0' />
  <mac address='52:54:00:F0:D1:F7'/>
  <ip address='192.168.122.1' netmask='255.255.255.0'>
    <dhcp>
      <range start='192.168.122.2' end='192.168.122.254' />
    </dhcp>
  </ip>
</network>
と表示されるはずなので、254を適当に100などに変えておく。

あとは、ゲスト側の/etc/sysconfig/network-scripts/ifcfg-eth0を、こんな感じに書き換えれば良い。ここでは、192.168.122.240を割り当てることにする。

IPV6INIT="yes"
NM_CONTROLLED="no"
IPV6_AUTOCONF="yes"
HWADDR="52:54:00:7B:F4:D0"
BOOTPROTO="none"
DEVICE="eth0"
ONBOOT="yes"
IPADDR="192.168.122.240"
NETMASK="255.255.255.0"
GATEWAY="192.168.122.1"

gdbでデバッグするための設定

KVM(が使っているqemu)は、gdbserverの機能があり、起動時に-sオプションを指定することで、TCPポート 1234 でgdbからの接続を待つ。

ここに書いてあるとおりだが、virshで"edit fedora.kvm"と入力して、KVMを定義しているXMLを変更し、ルートエレメントのアトリビュートとして xmlns:qemu='http://libvirt.org/schemas/domain/qemu/1.0' を追加し、<domain>の最後の子要素に、
<qemu:commandline>
<qemu:arg value='-s'/>
</qemu:commandline>
を加える。

この変更をする前に、KVMを停止 (destroy) しておかないと反映されないようなので注意。


デバッグ
シンボル情報なしで、gdbからKVMに接続するとKVMが固まってしまう。バグっぽいが、シンボル情報があるに越したことはないので、vmlinux (vmlinuzではない)を(gdbが動くホスト側に)インストールする。Fedoraでは、kernel-debuginfoパッケージにvmlinuxが含まれているので、yumを使ってインストールする。

$ sudo yum \
--enablerepo=fedora-debuginfo \
--enablerepo=updates-debuginfo \
install kernel-debuginfo

ここでインストールしたkernel-debuginfoのバージョンと、ゲストのkernelのバージョンとが合ってないと、シンボルとアドレスがずれたりしてあとあと面倒になりそうなので注意すること。

これで準備完了。この記事と同じく、ext4_writepageで止めてみる。

まず、KVMを起動する。virshで"start fedora.kvm"。sshかvirshのconsoleコマンドでログインしておく。

ホスト側でgdbを起動し、vmlinuxからシンボル情報を読み込ませ、ブレイクポイントを指定し、デバッグターゲットを指定する。

$ gdb
GNU gdb (GDB) Fedora (7.3.50.20110722-10.fc16)
Copyright (C) 2011 Free Software Foundation, Inc.
(...)
(gdb) file /usr/lib/debug/lib/modules/3.1.2-1.fc16.x86_64/vmlinux 
Reading symbols from /usr/lib/debug/lib/modules/3.1.2-1.fc16.x86_64/vmlinux...done.
(gdb) b ext4_writepage
Breakpoint 1 at 0xffffffff8118c590: file fs/ext4/inode.c, line 1778.
(gdb) target remote localhost:1234
Remote debugging using localhost:1234
native_safe_halt () at /usr/src/debug/kernel-3.1.fc16/linux-3.1.x86_64/arch/x86/include/asm/irqflags.h:50
50      }
(gdb)

attachした瞬間に、ゲストはnative_safe_haltで止まるので、gdbのcontinueコマンドでゲストを走らせる。
あとは、ログインしておいたゲストOS側でなんかすれば、ext4_writepageで止まるはず。

(gdb) continue
Continuing.

Breakpoint 1, ext4_writepage (page=0xffffea0000c54880, wbc=0xffff880039499dd8) at fs/ext4/inode.c:1778
1778    {
(gdb) bt
#0  ext4_writepage (page=0xffffea0000c54880, wbc=0xffff880039499dd8) at fs/ext4/inode.c:1778
#1  0xffffffff810e61a2 in __writepage (page=, wbc=, data=0xffff880038d7e8f8) at mm/page-writeback.c:1222
#2  0xffffffff810e5fd4 in write_cache_pages (mapping=0xffff880038d7e8f8, wbc=0xffff880039499dd8, 
writepage=0xffffffff810e618d <__writepage>, data=0xffff880038d7e8f8) at mm/page-writeback.c:1160
#3  0xffffffff810e6144 in generic_writepages (mapping=0xffff880038d7e8f8, wbc=) at mm/page-writeback.c:1246
#4  0xffffffff811bace0 in journal_submit_inode_data_buffers (mapping=) at fs/jbd2/commit.c:186
#5  journal_submit_data_buffers (commit_transaction=0xffff880036c66400, journal=0xffff880036e3e000) at fs/jbd2/commit.c:217
#6  jbd2_journal_commit_transaction (journal=0xffff880036e3e000) at fs/jbd2/commit.c:456
#7  0xffffffff811bef97 in kjournald2 (arg=0xffff880036e3e000) at fs/jbd2/journal.c:162
#8  0xffffffff81072cdf in kthread (_create=0xffff8800385c3b00) at kernel/kthread.c:96
#9  0xffffffff814bfa74 in ?? () at arch/x86/kernel/entry_64.S:1152
#10 0x0000000000000000 in ?? ()

backtraceも見れた。


終わりに
Fedora 16上でのKVM+gdbによるkernelデバッグをやってみた。ウェブを見るとUbuntuでやってる人が多いようなので、Fedoraでやりたい人の参考になれば幸いだ。

2011年11月18日金曜日

LeftistHeap in Haskell

Leftist Heapとは、Purely Functional Data Structuresによると、
Heap-ordered binary tees that satisfy the leftist property: the rank of any left child is at least as large as the rank of its right sibling. The rank of a node is defined to be the length of its right spine (i.e., the rightmost path from the node in question to an empty node).
という性質をもつHeapです。

同書に載っているML, Haskellによる実装では、insertはmergeを使ってinsert x h = merge (T 1 x E E) hとなっていますが、これを「mergeを使わずに実装せよ」というのが、Exercise 3.2です。

挿入先のHeap(以降h)がEmptyな場合は簡単で、xのみを要素として持つHeapを返せばよい: insert x E = T 1 x E E

hがEmptyじゃない場合は、現在のminimum value (以下 m)と x との大小関係によって、更に場合分けします。Heap-ordered treeなので、あるノードの値は、子ノードの値よりも小さいか等しくないといけないからです。

xがmより小さいか等しい場合は、xをルートノードにすればよい: makeT x h E
もしくは、makeTを展開して: T 1 x h E

xがmより大きい場合は、hの子のどちらかにxを挿入します。つまり、insertを再帰的に呼び出します: makeT (hの値) (hの子供1) $ insert x (hの子供2)

まとめると、
insert x E    = T 1 x E E
insert x h@(T _ y a b)
  | x <= y    = makeT x h E
  | otherwise = makeT y a $ insert x b
となります。ちなみに、最後の行のaとbは入れ替えてもよい(はず)。

これが正しく動くことを確認したいので、この辺を参考にしてQuickCheckを使ってみました。
QuickCheckは、テスト関数(テストデータ -> Bool)を与えると、テストデータを生成して、期待通りの結果が出るか調べてくれるツールのようです。

今回は、
  1. 整数のリストを受け取る
  2. LeftistHeapに挿入する
  3. リストをsortする
  4. findMinとリストの先頭の値が等しいかをチェックし、等しくなければFalse、等しければ、deleteMinとcdrを再帰的にチェック
とすればテストになるので、テスト関数を
test :: [Int] -> Bool
test ns = test' lh $ sort ns
  where
    lh :: LeftistHeap Int
    lh = foldl (\h n -> LeftistHeap.insert n h) empty ns

    test' :: (LeftistHeap Int) -> [Int] -> Bool
    test' _ []          = True
    test' h (m:ms)      = findMin h == m && test' (deleteMin h) ms
と定義して、ghciで実行。
orange:~/work/pfds% ghci -Wall         
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :l TestLeftistHeap.hs 
[1 of 3] Compiling Heap             ( Heap.hs, interpreted )
[2 of 3] Compiling LeftistHeap      ( LeftistHeap.hs, interpreted )
[3 of 3] Compiling TestLeftistHeap  ( TestLeftistHeap.hs, interpreted )

TestLeftistHeap.hs:4:1:
    Warning: The import of `Test.QuickCheck' is redundant
               except perhaps to import instances from `Test.QuickCheck'
             To import instances alone, use: import Test.QuickCheck()
Ok, modules loaded: TestLeftistHeap, LeftistHeap, Heap.
*TestLeftistHeap> quickCheck test
Loading package extensible-exceptions-0.1.1.2 ... linking ... done.
Loading package old-locale-1.0.0.2 ... linking ... done.
Loading package time-1.2.0.3 ... linking ... done.
Loading package random-1.0.0.3 ... linking ... done.
Loading package array-0.3.0.2 ... linking ... done.
Loading package containers-0.4.0.0 ... linking ... done.
Loading package pretty-1.0.1.2 ... linking ... done.
Loading package template-haskell ... linking ... done.
Loading package QuickCheck-2.4.1.1 ... linking ... done.
+++ OK, passed 100 tests.

正しく動いてるっぽい。

[追記 2011-12-23] TestFrameworkを使った版

2011年10月20日木曜日

日本語エンコーディングの可視化

世の中の文字コードはUnicodeに統一される方向で動いているようで、ウェブアプリを作っていた頃に文字コードに悩まされた者としては、慶ばしい限りです。が、諸事情でレガシーコード("Shift_JIS"とか)を扱う必要があり、このサイトで勉強し直しました。以下がエンコーディングのまとめです。なお、「符号化文字集合」については省略します。


ISO-2022-JP
メールに使われているエンコーディング。それ以外ではみたことない。JISコードと呼ばれるらしいけど、個人的にはあんまり聞いたことないです。
ISO-2022-JPはISO-2022準拠のエンコーディングなので、複数のテーブルをエスケープシーケンスによって切り替えて使います。(ISO-2011-JPの説明は複雑なのでここでは省略します。このページをみてください。)簡単に言うと、特定の制御文字列を送ることで、「これからアルファベットを使います」「これから漢字を使います」と、状態を切り替えることで、たった7bitでアルファベット、数字、漢字をすべて表現することができるのです。

エスケープシーケンス
  • これから送る文字はASCIIです: 0x0F, "ESC ( B", or "ESC ( J"
  • これから送る文字は漢字です: "ESC $ @", or "ESC $ B"
  • これから送る文字は補助漢字です: "ESC $ ( D"
  • これから送る文字は半角カタカナです: 0x0E, or "ESC ( I"
なお、初期状態はASCIIです。なので、アルファベットと数字だけからなるメールにはエスケープシーケンスはいっさい含まれていません。(未確認ですがそのはず)

使用領域
7bitの領域をどのように使っているのか図示します。なお、制御文字が水色、ASCIIがオレンジ、漢字・補助漢字が緑、半角カタカナがグレーです。



ASCII使用時:
01234567
00010203040506070
10111213141516171
20212223242526272
30313233343536373
40414243444546474
50515253545556575
60616263646566676
70717273747576777
80818283848586878
90919293949596979
a0a1a2a3a4a5a6a7a
b0b1b2b3b4b5b6b7b
c0c1c2c3c4c5c6c7c
d0d1d2d3d4d5d6d7d
e0e1e2e3e4e5e6e7e
f0f1f2f3f4f5f6f7f

漢字・補助漢字使用時:
01234567
00010203040506070
10111213141516171
20212223242526272
30313233343536373
40414243444546474
50515253545556575
60616263646566676
70717273747576777
80818283848586878
90919293949596979
a0a1a2a3a4a5a6a7a
b0b1b2b3b4b5b6b7b
c0c1c2c3c4c5c6c7c
d0d1d2d3d4d5d6d7d
e0e1e2e3e4e5e6e7e
f0f1f2f3f4f5f6f7f

半角カタカナ使用時:
01234567
00010203040506070
10111213141516171
20212223242526272
30313233343536373
40414243444546474
50515253545556575
60616263646566676
70717273747576777
80818283848586878
90919293949596979
a0a1a2a3a4a5a6a7a
b0b1b2b3b4b5b6b7b
c0c1c2c3c4c5c6c7c
d0d1d2d3d4d5d6d7d
e0e1e2e3e4e5e6e7e
f0f1f2f3f4f5f6f7f


Shift_JIS / Windows-31J など
依然としてクライアントサイドでは最も使われているエンコーディング。符号化文字集合が微妙に異なる親戚がたくさんいる。Shift_JISと呼ばれているものの多くは正確にはWindows-31Jであろう。
エスケープシーケンスを使わずASCII、漢字、半角カタカナを表現可能なのが便利だが、あるバイトを見たときに、それがASCIIなのか漢字を表現する2バイト目なのかを判別できない(場合がある)ので、波紋を呼んだりもした。

使用領域
1バイト目:
0123456789abcdef
000102030405060708090a0b0c0d0e0f0
101112131415161718191a1b1c1d1e1f1
202122232425262728292a2b2c2d2e2f2
303132333435363738393a3b3c3d3e3f3
404142434445464748494a4b4c4d4e4f4
505152535455565758595a5b5c5d5e5f5
606162636465666768696a6b6c6d6e6f6
707172737475767778797a7b7c7d7e7f7
808182838485868788898a8b8c8d8e8f8
a09192939495969798999a9b9c9d9e9f9
a0a1a2a3a4a5a6a7a8a9aaabacadaeafa
b0b1b2b3b4b5b6b7b8b9babbbcbdbebfb
c0c1c2c3c4c5c6c7c8c9cacbcccdcecfc
d0d1d2d3d4d5d6d7d8d9dadbdcdddedfd
e0e1e2e3e4e5e6e7e8e9eaebecedeeefe
f0f1f2f3f4f5f6f7f8f9fafbfcfdfefff

2バイト目:
0123456789abcdef
000102030405060708090a0b0c0d0e0f0
101112131415161718191a1b1c1d1e1f1
202122232425262728292a2b2c2d2e2f2
303132333435363738393a3b3c3d3e3f3
404142434445464748494a4b4c4d4e4f4
505152535455565758595a5b5c5d5e5f5
606162636465666768696a6b6c6d6e6f6
707172737475767778797a7b7c7d7e7f7
808182838485868788898a8b8c8d8e8f8
909192939495969798999a9b9c9d9e9f9
a0a1a2a3a4a5a6a7a8a9aaabacadaeafa
b0b1b2b3b4b5b6b7b8b9babbbcbdbebfb
c0c1c2c3c4c5c6c7c8c9cacbcccdcecfc
d0d1d2d3d4d5d6d7d8d9dadbdcdddedfd
e0e1e2e3e4e5e6e7e8e9eaebecedeeefe
f0f1f2f3f4f5f6f7f8f9fafbfcfdfefff

1バイト目のオレンジ(ASCII)と、2バイト目の緑(漢字)が一部重なっているのがわかりますね。

EUC-JP
Unix系で使われていた・・・ような気がするけど、あんまり覚えてない。これもISO-2022準拠のエンコーディングですが、エスケープシーケンスは使わず、シングルシフトを使います。(しつこいですが、ISO-2022についてはこのページをみてください。)
簡単に言うと、1バイト目が0x8Eだったら次の1バイトを半角カタカナとして認識する、1バイト目が0x8Fだったら次の2バイトを補助漢字として認識する、というルールです。

使用領域
Shift_JISと違って、空白が目立ちます。空間を贅沢に使ってる分、「漢字の2バイト目がアルファベットと間違えられる」というような問題は起こりません。

デフォルト:
0123456789abcdef
000102030405060708090a0b0c0d0e0f0
101112131415161718191a1b1c1d1e1f1
202122232425262728292a2b2c2d2e2f2
303132333435363738393a3b3c3d3e3f3
404142434445464748494a4b4c4d4e4f4
505152535455565758595a5b5c5d5e5f5
606162636465666768696a6b6c6d6e6f6
707172737475767778797a7b7c7d7e7f7
808182838485868788898a8b8c8d8e8f8
909192939495969798999a9b9c9d9e9f9
a0a1a2a3a4a5a6a7a8a9aaabacadaeafa
b0b1b2b3b4b5b6b7b8b9babbbcbdbebfb
c0c1c2c3c4c5c6c7c8c9cacbcccdcecfc
d0d1d2d3d4d5d6d7d8d9dadbdcdddedfd
e0e1e2e3e4e5e6e7e8e9eaebecedeeefe
f0f1f2f3f4f5f6f7f8f9fafbfcfdfefff

1バイト目が0x8Eだったときの2バイト目:
0123456789abcdef
000102030405060708090a0b0c0d0e0f0
101112131415161718191a1b1c1d1e1f1
202122232425262728292a2b2c2d2e2f2
303132333435363738393a3b3c3d3e3f3
404142434445464748494a4b4c4d4e4f4
505152535455565758595a5b5c5d5e5f5
606162636465666768696a6b6c6d6e6f6
707172737475767778797a7b7c7d7e7f7
808182838485868788898a8b8c8d8e8f8
909192939495969798999a9b9c9d9e9f9
a0a1a2a3a4a5a6a7a8a9aaabacadaeafa
b0b1b2b3b4b5b6b7b8b9babbbcbdbebfb
c0c1c2c3c4c5c6c7c8c9cacbcccdcecfc
d0d1d2d3d4d5d6d7d8d9dadbdcdddedfd
e0e1e2e3e4e5e6e7e8e9eaebecedeeefe
f0f1f2f3f4f5f6f7f8f9fafbfcfdfefff


1バイト目が0x8Fだったときの2, 3バイト目:
0123456789abcdef
000102030405060708090a0b0c0d0e0f0
101112131415161718191a1b1c1d1e1f1
202122232425262728292a2b2c2d2e2f2
303132333435363738393a3b3c3d3e3f3
404142434445464748494a4b4c4d4e4f4
505152535455565758595a5b5c5d5e5f5
606162636465666768696a6b6c6d6e6f6
707172737475767778797a7b7c7d7e7f7
808182838485868788898a8b8c8d8e8f8
909192939495969798999a9b9c9d9e9f9
a0a1a2a3a4a5a6a7a8a9aaabacadaeafa
b0b1b2b3b4b5b6b7b8b9babbbcbdbebfb
c0c1c2c3c4c5c6c7c8c9cacbcccdcecfc
d0d1d2d3d4d5d6d7d8d9dadbdcdddedfd
e0e1e2e3e4e5e6e7e8e9eaebecedeeefe
f0f1f2f3f4f5f6f7f8f9fafbfcfdfefff


まとめ
意外にきれいな表になって嬉しい。Rubyを使ったのは半年ぶりだが、なんとなくそれっぽいコードを書けば動いてしまうのがRubyのすばらしいところだ。


余談: 元サイトの余談の引用
余談ですが、制御文字の中でDELだけ0x7Fなんていうところに飛ばされているのはなぜでしょうか? これは、データ入力媒体として紙テープを使っていたころの名残だといわれています。 紙テープでは、所定の位置に穴を空けてあるかどうかによって 2進数の1/0を区別します(SunOSのppt(6)を参照)。 1文字は7ビットですから、7つの位置の穴の有無で1文字を表します。 で、もし穴を空けるときにまちがってしまった場合、 穴をふさぐのは面倒ですので、そのまちがいを含む7ビット分全部の穴を空けて 「この字はまちがいだから削除ね」ということにしていました。 つまり、「削除」→「全ビット1」→「0x7F」というわけです。

Rubyソースコード
#!/usr/bin/ruby

ctrl = [0x00..0x1f, 0x7f..0x7f]
ascii = 0x0..0x0
#ascii = 0x20..0x7e
katakana = 0x0..0x0
#katakana = 0x21..0x5f
#katakana = 0xa1..0xdf
#katakana = 0xa1..0xdf
#kanji = []
#kanji = [0x21..0x7e]
#kanji = [0x81..0x9f, 0xe0..0xfc]
#kanji = [0x40..0x7e, 0x80..0xfc]
kanji = [0xa1..0xfe]

print <<EOS
<style type="text/css">
table.charcode {
  border-collapse: collapse;
  empty-cells: show;
}

table.charcode th,
table.charcode td {
  width: 2em;
  border: 1px solid gray;
  text-align: center;
}

td.ctrl {
  background-color: cyan;
}

td.ascii {
  background-color: orange;
}

td.katakana {
  background-color: lightgray;
}

td.kanji {
  background-color: lightgreen;
}
</style>
EOS

print %Q!<table class="charcode">\n!

print "<tr><th></th>"
for b in 0x0..0xf
  print "<th>#{sprintf("%x", b)}</th>"
end
print "</tr>"

for b0 in 0x0..0xf
  print "<tr><th>#{sprintf("%x", b0)}</th>"

  for b1 in 0x0..0xf
    b = b1 * 0x10 + b0
    
    if ctrl.any? { |r| r.include? b }
      print %Q!<td class="ctrl">#{sprintf("%02x", b)}</td>!
    elsif ascii.include? b
      print %Q!<td class="ascii">#{sprintf("%02x", b)}</td>!
    elsif katakana.include? b
      print %Q!<td class="katakana">#{sprintf("%02x", b)}</td>!
    elsif kanji.any? { |r| r.include? b }
      print %Q!<td class="kanji">#{sprintf("%02x", b)}</td>!
    else
      print %Q!<td>#{sprintf("%02x", b)}</td>!
    end
  end
  
  print "</tr>\n"
end

print "</table>\n"

2011年10月16日日曜日

末尾再帰を学ぶのは重要か? -> 重要


以前のエントリで、
と、ここまで書いてきてなんだけど、ある関数を末尾再帰にするというのは局所的な最適化なので、重要性は低いと思っている。初心者が知る必要はないし、ソフトウェアの開発初期に、部品となる関数一つ一つに対して、「これは末尾再帰にするべきか、末尾再帰になっているか」と考えるのは premature optimization というものだろう。
なのに、どうして多くの関数型言語の本もかなり序盤に末尾再帰の話を持ってくるのか疑問だ。そもそも関数型言語のような高レベル言語を使ってるのに、スタックを消費する・しない、とか考えたくない。と思うのは間違っているのだろうか? まぁ、パズルみたい (しかもたいてい簡単) なので、面白いけどね。 
と書きました。

この質問をHaskell歴の長いとある人に聞いてみたところ、「末尾再帰にしないと、スタックがのび過ぎて動かなくなることがよくある。なので初心者が末尾再帰を学ぶのは重要」とのことでした。

なるほど。速度の問題だけなら無視できるけど、動かなくなるのは困りますね。納得しました。


2011年10月6日木曜日

アイコン救急車

[Icon Ambulance の翻訳]


2008年1月6日の日曜日の朝、礼拝に参加しているときに携帯のバイブが震えた。目立たないようにそっと携帯をチェックすると、「発信者不明」だったので無視することにした。

礼拝のあと車に向かう途中で携帯のメールをチェックすると、Steve Jobsからメールが届いていた。「Vic、自宅に電話をくれ。緊急に君と話さなきゃいけないことがある。」

車に着く前にSteve Jobsに電話をかけた。私は Google で全てのモバイルアプリケーションの責任者であり、そのためSteveと定期的にやり取りをしていたが、これはその中でも思い出深い話だ。

「もしもし Steve。Vicです。」と言った。「今まで電話に出られなくてすみません。礼拝に出ていたし、発信者が不明だったので、電話に出なかったんです。」

Steveは笑ってこう言った。「Vic、神様からの電話じゃない限り、礼拝中に電話に出ちゃダメだよ。」

私は無理して笑った。Steveが平日に急いで電話してくることはよくあったが、日曜日に電話して、自宅に電話をくれなんて普通じゃない。何があったんだろうと気になっていた。

「Vic、緊急の問題があるんだ。すぐに何とかしなきゃいけない。私のチームの誰かに君をサポートするように指示したから、明日には直せると思うけど」とSteveは言う。

「GoogleのロゴをiPhoneで見ていたんだけど、アイコンが良くないんだ。Googleの2つ目のOの黄色のグラデーションがおかしい。とにかく間違ってるんだ。Gregに明日直させるけど、それでいいかい?」

もちろんそれで問題ない。その日曜の数分後、Steveから「アイコン救急車」というメールが送られてきた。私とGreg Christieにアイコンを直すよう指示していた。

11歳で Apple II と恋に落ちたものとしては、Apple製品について語りたいことは山ほどある。何十年にもわたって私の人生の一部になっている。15年間 Bill GatesのMicrosoftで働いていた時でさえ、SteveとAppleが作ってきたものとに大きな敬意を払っていた。

でも結局のところ、リーダーシップ、情熱、細部へのこだわりについて考えていると、1月の日曜日にSteve Jobsからかかってきた電話を思いだしてしまう。忘れられない教訓となった。CEOというものは、細部にこだわらなければいけない。黄色のグラデーションにまで。日曜日であっても。

私が知っている最高のリーダー Steve。あなたの健康を祈ってます。[訳注: 原文は、Steve JobsがCEOを辞任した翌日にポストされた。]

Vic

Steve Jobs


[The EconomistObituary: Steve Jobs の翻訳]

コンピュータ業界には、いや他の業界にさえも、Steve Jobsのようにプレゼンテーションができる人はいなかった。黒いステージに独りたち、「魅惑的」で「驚くほど素晴らしい」新製品を、どきどきしている観客に向けて魔法のように取り出すさまは、まさに天才エンターテイナーだった。コンピュータにできることなんて、数字を取り出して並べ替えるだけだ、とかつて彼は言った。でもそれをとても速く行えば、「魔法のような効果を生み出すんだ。」 その魔法を、美しくデザインされ、簡単に使える製品に詰め込むことに、彼は人生を捧げた。

彼は、1970年代において、普通の人にコンピュータを販売するというアイデアに可能性を見出した数少ない一人だった。黒い画面に緑の文字が表示され、フロッピーディスクがまだ柔らかかった時代に、コンピュータはすぐに誰もが使えるものになるなどと考えるのは非現実的だったが、Mr Jobsは次に何が起こるかを見ることができる、数少ないパイオニアだった。決定的だったのは、彼は、エンジニアとしてコンピュータを内側から見る才能だけではなく、ユーザーとして外側から見るという貴重な才覚も持っていたことだ。わがままな子供時代を過ごしたからだろう、と彼は語っていた。

Mr Jobsはシリコンバレーで育ち、コンピュータに取りつかれた。1960年代のティーンエイジャーは、あこがれだった Bill Hewlett に勧誘の電話をかけ、Hewlett-Packardでの夏休みのバイトを手に入れた。しかしその後、大学を中退し、インドに旅行に行き、仏教徒になり、幻覚剤を体験し、ようやく1976年のエイプリルフールに、カリフォルニアの両親のガレージでApple社を共同設立することになる。「私達の業界のほとんどの人は、幅広い体験をしたことがない」と彼は語っている。「だから、繋げられるような点を持っていないんだ。そしてとても直線的な解決策しか考えられない。」 Bill Gatesについて「若いころにLSDをやったり、ヒンズー教の僧院へ旅でもしてればもっと大きな男になっただろうにね」と言っていた。

例えば、大学を中退してカリグラフィーのクラスに出席したことで、Mr Jobs は、使い道のないタイポグラフィを愛するようになった。しかし、1984年にAppleが発売した、マウスで操作できる画期的なグラフィカルコンピュータ Macintosh にとって、様々なフォントをサポートしていることがその特徴を表していた。ウィンドウ、アイコン、そしてメニューを見たらわかるように、それは「一般人のためのコンピュータ」だった。Appleの最初の成功で富を成した Mr Jobsは新しいマシンを大量に売ろうと目論んだ。しかし、新マシンは望んだほどの成功は得られず、取締役会は Mr Jobsを追放することになった。

このどう見ても破滅的な転換は、しかし、福音となる。「自分に起こった最高の出来事だ」と Mr Jobsは後に語っている。コンピュータグラフィックスに特化した新会社 Pixar と、新しいコンピュータメーカー NeXT とを共同設立した。輝かしい第二幕は、1996年に始まった。どうしようもなくなった Apple は NeXT を買収し、その技術を Apple の新製品のコアとして組み込むためにに Mr Jobs の再登場となった。あとは歴史のとおりだ。Apple は iMac, iPod, iPhone, iPadをリリースし、(一瞬だが) 世界で最も価値のある上場企業となった。「Appleを首にならなかったら、こんなことは起こり得なかったと確信を持って言える」と Mr Jobsは2005年に言った。8月に体調悪化のためボスの座を降りたときは、歴史上最高のCEOとしてもてはやされた。そうそう、彼の副業だった Pixar は、アニメ映画の大成功作を幾つも生み出した。

振り返ってみれば、Appleでの第一幕では、Mr Jobsは時代を先取りしすぎていたといえる。初期のコンピュータは技術屋のものだった。しかし、デザインと使いやすさを強調する姿勢は、のちに優位性を生み出す。コンピュータがファッションアイテムとなり、誰もが持ち歩き、なんでもできるようになった世界においては、上品でシンプルで、コンピュータ以外の世界を知っていることが強みとなった。2011年3月にiPad2を発表したときのスピーチの最後でMr Jobsは「技術だけではダメなんだ」と言った。「文学、教養、人文科学と技術とが出会うことで、心を震わせるような成果を生み出す。」 技術の会社のトップがこんなことを言うのは珍しいが、これこそ昔からのSteve Jobsだった。

複数の学問分野をまたがるようなアプローチは、細部への極端なこだわりに支えられていた。よいタンスを作っている大工は、たとえ誰も見ないとしても、背部にベニヤ板は使わない、というのが彼の主張で、自分の製品にも同じ姿勢で取り組んだ。「夜ぐっすりと眠るためには、美学と品質が貫かれてなくてはいけない。」 彼は、最初のMacintoshを作るときに、エンジニアの利便性よりもユーザーのニーズを重視し、内部の空冷ファンを無くすべきだ、そうすれば静かになる、と主張した。週末に、Googleのエンジニアを緊急に呼び出してこう言ったりもした。「iPhoneに表示されるGoogleロゴの文字の黄色が、少し違う。」 Appleの広告のテキストを自分で書いたり、書きなおしたりすることもよくあった。

ステージ上では禅のような神秘的な仮面をかぶっていたが、Mr Jobsは独裁的で激しい癇癪持ちのマネージャーだった。それでも彼のエゴは正当化された。まだ存在しない新市場を開拓する際は、マーケットリサーチャーやフォーカスグループ [訳注: 何人かの消費者に試作品を使ってもらい、意見を製品に反映させる手法] を廃し、自分の直感を信じた。「多くの場合、それが目の前に提示されるまで、自分が何が欲しいかなんてわからないものだ」というのが彼の意見だった。彼の判断は不気味なくらい正確で、人生全体を見れば、成功は失敗を大きく上回った。Appleを作って間もないころ、あるエンジニアは、Mr Jobsが「現実をねじ曲げる力」を放射していると言ったが、彼の物事を追求する姿勢はまさにそうだった。そして最後には、コンピュータの魔法を、音楽、電話、そしてメディアを再構築する製品へと導くことで、ついに現実を変えた。青年時代に「世界中に鳴り響くような鐘を叩きたい」と言っていた男は、それを成し遂げたのだ。



[原文の訂正に伴う訂正: 週末に呼び出されたのはAppleではなくGoogleのエンジニアでした。これは2008年の事で、AppleとGoogleがライバルではなく同盟を組んでいた時の話です。]

2011年9月24日土曜日

ステレオタイプとは真逆のギリシャの銀行

[The Economistの "Greek banks - Playing against type" の翻訳です。]

銀行は悪者だという見方は、ヨーロッパでもアメリカでも受け入れられている。これに関しては、これだけではないが、ギリシャは仲間外れだ。ギリシャの銀行の人と話すと、哀れみを覚えずにはいられない。

ギリシャの銀行は、2007-2008の金融危機の真っ最中もとても上手くやってきた。国の救済 (そんなものがあったら、の話だが) に頼ることなく、お金を逆方向に流していた。つまり、銀行が国債を買うことが、ギリシャ政府にとっての最も確実な収入源だった。ある銀行関係者によれば、国債の購入は今や強制されているようなもので、政府は「国債を購入しないなら、公営企業の預金を引き上げるぞ」と脅しているそうだ。

きっかけはどうあれ、国債のデフォルトリスクのせいで、銀行のバランスシートは炎上しやすくなっている。PSI (財政危機の対策のために民間企業の協力を求めること) のため、ギリシャが破綻しないための負担の一部は民間の債権者にも求められていて、すでに銀行は評価損を計上している。でも、更なるリストラのリスクは未だに高まっている。

財源は、関連する大きな問題だ。預金は金融システムの外へと流れ出ている。クレディ・スイスは、民間部門の預金額は 1 月から 7 月にかけて 10% 減少した、と見積もっている。人々は預金を引き出し、破綻のリスクに怯えている。ある銀行員は、人々が預金を引き出してタンス預金しないように説得している銀行の努力について、「私たちは預金者のサイコセラピストなんです」と語る。

ECB (ヨーロッパ中央銀行) は銀行を破綻させないはずだが、同時に、銀行が差し出した担保を定期的に再評価し、酸素供給 (銀行への資金供給) を絞っている。担保価値が下がりつづけ、貸出期間が短くなっている状況では、銀行はお金を中期の貸し出しにはまわしたくないだろう。しかし、それこそが経済が成長するために必要なのだが。

そのため、経済は停滞し、不良債権問題は増え続けている。おなじみの Blackrock Solutions から派遣されたチームは、銀行の貸出帳簿の検査に関して起訴された。今年中に銀行は更に資本が必要になるだろう。[訳注: よく分からない・・・]

銀行家たち自身は、(PSIによる一定の評価損以上の) ギリシャのデフォルトは望んでいない。そうなったら、彼らの資本は当然なくなってしまう。取締役会も、デフォルト危機の状態にあることが、ギリシャに更なる改革をすすめるための最良の方策だと言っている。憂慮すべきモラルハザードは、民間部門の債務が軽くなることではなく、ギリシャ政府が改革をやめてしまうことだ、とある銀行家はいう。

彼らの願いが叶ったとしても、銀行の未来は依然として窮屈なものだろう。2 つの銀行 (Eurobank と Alpha) は、資産の拡大とコストカットのために合併した。海外の資産は買い叩かれている。業務部門は、損失を補えるだけの引き当てを積むというつまらない目標を掲げている。同情を誘うには十分だ。

2011年9月11日日曜日

Haskellの中間形式を見て関数が末尾再帰かどうか調べる

きのう参加した Start Haskell ではパフォーマンスの話題、とくに末尾再帰の話が多かった。遅延評価が関わると (?)、ある関数が末尾再帰になっているかを判断することさえそれほど単純ではないようだ。コンパイル後のアセンブラを読むのはさすがにやりたくないので、もう少し手軽な方法はないかと思っていたら、GHCが生成する中間形式を見る、という方法があるそうだ。 昨日の演習問題だったsplitAtを例としてまとめてみる。

splitAtは、整数とリストを受け取って、リストを整数が示すインデックスで2つに分ける関数。splitAt 2 "abcd" -> ("ab", "cd") という感じ。Haskellのコードはこう。
sp1 :: Int -> [a] -> ([a], [a])
sp1 = sp1' ([],[])
  where
    sp1' (l1,l2) _ []    = (reverse l1, reverse l2)
    sp1' (l1,l2) m (l:ls)
      | m > 0        = sp1' (l:l1,l2) (m-1) ls
      | otherwise    = sp1' (l1,l:l2) (m-1) ls
これが末尾再帰になってなかったら死ねる、というコード。

このコードに対して、「reverse使うのは反則では?」という意見があった (出題は「リストを一回だけ走査する実装」だった)。まぁあと、ヘルパー関数を無くしたいとは思った。
sp2      :: Int -> [a] -> ([a], [a])
sp2 _ [] = ([], [])
sp2 n (x:xs)
    | n > 0     = (x:ys, zs)
    | otherwise = ([], x:xs)
  where
    (ys, zs) = sp2 (n-1) xs
この方が美しいとは思うが、再帰呼び出しのあとxをconsしているから、末尾再帰になってないと思った。が、「いや末尾再帰になっている」という声もあったので、調べてみた。ちなみに、ghcは "The Glorious Glasgow Haskell Compilation System, version 7.2.1"を使った。

% ghc -c -O2 -ddump-simpl [ソースファイル名]
とやると中間形式が標準出力に表示される。出力はかなり長いので、このエントリの最後にペーストした。

sp1の再帰部分に対応するコードを見ると、
case GHC.Prim.># sc2_syd 0 of _ {
  GHC.Types.False ->
    SplitAt.sp1_$s$wsp1'
      @ a_am8
      sc_syb
      (GHC.Types.: @ a_am8 l_ajZ sc1_syc)
      (GHC.Prim.-# sc2_syd 1)
      ls_ak0;
  GHC.Types.True ->
    SplitAt.sp1_$s$wsp1'
      @ a_am8
      (GHC.Types.: @ a_am8 l_ajZ sc_syb)
      sc1_syc
      (GHC.Prim.-# sc2_syd 1)
      ls_ak0
となっているので、(これがチェックするべき中間言語であって、私が中間形式をただしく読めていて、ソースコードとの対応を間違っていなくて、GHCがこのあと更に最適化しなければ) 末尾再帰になっているといえるだろう。

一方、sp2の再帰部分に対応するコードは、
Case GHC.Prim.># sc_syz 0 of _ {
  GHC.Types.False -> (# GHC.Types.[] @ a_abq, wild_X9 #);
  GHC.Types.True ->
    let {
      ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
      [LclId, Str=DmdType]
      ds_swT =
        case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# sc_syz 1) xs_abt
        of _ { (# ww1_sxN, ww2_sxO #) ->
        (ww1_sxN, ww2_sxO)
        } } in
    (# GHC.Types.:
         @ a_abq x_abs (case ds_swT of _ { (ys_adK, zs_adL) -> ys_adK }),
       case ds_swT of _ { (ys_adK, zs_adL) -> zs_adL } #)
}
となっている。再帰呼び出しはletの中に入っていて、そのあとinの中で "GHC.Types.:" つまりconsを呼んでいる。なので、末尾再帰になっていないと考えられる。

ちなみに、-Oでも-O3でも結果は変わらなかった。

と、ここまで書いてきてなんだけど、ある関数を末尾再帰にするというのは局所的な最適化なので、重要性は低いと思っている。初心者が知る必要はないし、ソフトウェアの開発初期に、部品となる関数一つ一つに対して、「これは末尾再帰にするべきか、末尾再帰になっているか」と考えるのは premature optimization というものだろう。

なのに、どうして多くの関数型言語の本もかなり序盤に末尾再帰の話を持ってくるのか疑問だ。そもそも関数型言語のような高レベル言語を使ってるのに、スタックを消費する・しない、とか考えたくない。と思うのは間違っているのだろうか? まぁ、パズルみたい (しかもたいてい簡単) なので、面白いけどね。

dump-simplの全出力は以下のとおり。"@"とか"(#"とか"#)"とか謎のシンボルがある。トップレベルの関数と再帰用(Rec { ... } で定義されている)と2つの関数定義ができるみたい。

==================== Tidy Core ====================
Result size = 250

Rec {
SplitAt.sp1_$s$wsp1' [Occ=LoopBreaker]
  :: forall a_am8.
     [a_am8]
     -> [a_am8] -> GHC.Prim.Int# -> [a_am8] -> (# [a_am8], [a_am8] #)
[GblId, Arity=4, Caf=NoCafRefs, Str=DmdType LLLS]
SplitAt.sp1_$s$wsp1' =
  \ (@ a_am8)
    (sc_syb :: [a_am8])
    (sc1_syc :: [a_am8])
    (sc2_syd :: GHC.Prim.Int#)
    (sc3_sye :: [a_am8]) ->
    case sc3_sye of _ {
      [] ->
        (# GHC.List.reverse @ a_am8 sc_syb,
           GHC.List.reverse @ a_am8 sc1_syc #);
      : l_ajZ ls_ak0 ->
        case GHC.Prim.># sc2_syd 0 of _ {
          GHC.Types.False ->
            SplitAt.sp1_$s$wsp1'
              @ a_am8
              sc_syb
              (GHC.Types.: @ a_am8 l_ajZ sc1_syc)
              (GHC.Prim.-# sc2_syd 1)
              ls_ak0;
          GHC.Types.True ->
            SplitAt.sp1_$s$wsp1'
              @ a_am8
              (GHC.Types.: @ a_am8 l_ajZ sc_syb)
              sc1_syc
              (GHC.Prim.-# sc2_syd 1)
              ls_ak0
        }
    }
End Rec }

SplitAt.sp1
  :: forall a_abp. GHC.Types.Int -> [a_abp] -> ([a_abp], [a_abp])
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType,
 Unf=Unf{Src=, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [20 100] 283 360}]
SplitAt.sp1 =
  \ (@ a_am8) (w_sxu :: GHC.Types.Int) (w1_sxv :: [a_am8]) ->
    case w1_sxv of _ {
      [] ->
        (GHC.List.reverse1
           @ a_am8 (GHC.Types.[] @ a_am8) (GHC.Types.[] @ a_am8),
         GHC.List.reverse1
           @ a_am8 (GHC.Types.[] @ a_am8) (GHC.Types.[] @ a_am8));
      : l_ajZ ls_ak0 ->
        case w_sxu of _ { GHC.Types.I# x_awt ->
        case GHC.Prim.># x_awt 0 of _ {
          GHC.Types.False ->
            case SplitAt.sp1_$s$wsp1'
                   @ a_am8
                   (GHC.Types.[] @ a_am8)
                   (GHC.Types.: @ a_am8 l_ajZ (GHC.Types.[] @ a_am8))
                   (GHC.Prim.-# x_awt 1)
                   ls_ak0
            of _ { (# ww1_sxH, ww2_sxI #) ->
            (ww1_sxH, ww2_sxI)
            };
          GHC.Types.True ->
            case SplitAt.sp1_$s$wsp1'
                   @ a_am8
                   (GHC.Types.: @ a_am8 l_ajZ (GHC.Types.[] @ a_am8))
                   (GHC.Types.[] @ a_am8)
                   (GHC.Prim.-# x_awt 1)
                   ls_ak0
            of _ { (# ww1_sxH, ww2_sxI #) ->
            (ww1_sxH, ww2_sxI)
            }
        }
        }
    }

Rec {
SplitAt.sp2_$s$wsp2 [Occ=LoopBreaker]
  :: forall a_abq. GHC.Prim.Int# -> [a_abq] -> (# [a_abq], [a_abq] #)
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LS]
SplitAt.sp2_$s$wsp2 =
  \ (@ a_abq) (sc_syz :: GHC.Prim.Int#) (sc1_syA :: [a_abq]) ->
    case sc1_syA of wild_X9 {
      [] -> (# GHC.Types.[] @ a_abq, GHC.Types.[] @ a_abq #);
      : x_abs xs_abt ->
        case GHC.Prim.># sc_syz 0 of _ {
          GHC.Types.False -> (# GHC.Types.[] @ a_abq, wild_X9 #);
          GHC.Types.True ->
            let {
              ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
              [LclId, Str=DmdType]
              ds_swT =
                case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# sc_syz 1) xs_abt
                of _ { (# ww1_sxN, ww2_sxO #) ->
                (ww1_sxN, ww2_sxO)
                } } in
            (# GHC.Types.:
                 @ a_abq x_abs (case ds_swT of _ { (ys_adK, zs_adL) -> ys_adK }),
               case ds_swT of _ { (ys_adK, zs_adL) -> zs_adL } #)
        }
    }
end Rec }

SplitAt.sp2 [InlPrag=INLINE[0]]
  :: forall a_abq. GHC.Types.Int -> [a_abq] -> ([a_abq], [a_abq])
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType LSm,
 Unf=Unf{Src=InlineStable, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=False)
         Tmpl= \ (@ a_abq)
                 (w_sxA [Occ=Once!] :: GHC.Types.Int)
                 (w1_sxB [Occ=Once!] :: [a_abq]) ->
                 case w1_sxB of wild_X9 {
                   [] -> (GHC.Types.[] @ a_abq, GHC.Types.[] @ a_abq);
                   : x_abs [Occ=Once] xs_abt [Occ=Once] ->
                     case w_sxA of _ { GHC.Types.I# x1_awt ->
                     case GHC.Prim.># x1_awt 0 of _ {
                       GHC.Types.False -> (GHC.Types.[] @ a_abq, wild_X9);
                       GHC.Types.True ->
                         let {
                           ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
                           [LclId, Str=DmdType]
                           ds_swT =
                             case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# x1_awt 1) xs_abt
                             of _ { (# ww1_sxN [Occ=Once], ww2_sxO [Occ=Once] #) ->
                             (ww1_sxN, ww2_sxO)
                             } } in
                         (GHC.Types.:
                            @ a_abq
                            x_abs
                            (case ds_swT of _ { (ys_adK [Occ=Once], _) -> ys_adK }),
                          case ds_swT of _ { (_, zs_adL [Occ=Once]) -> zs_adL })
                     }
                     }
                 }}]
SplitAt.sp2 =
  \ (@ a_abq) (w_sxA :: GHC.Types.Int) (w1_sxB :: [a_abq]) ->
    case w1_sxB of wild_X9 {
      [] -> (GHC.Types.[] @ a_abq, GHC.Types.[] @ a_abq);
      : x_abs xs_abt ->
        case w_sxA of _ { GHC.Types.I# x1_awt ->
        case GHC.Prim.># x1_awt 0 of _ {
          GHC.Types.False -> (GHC.Types.[] @ a_abq, wild_X9);
          GHC.Types.True ->
            let {
              ds_swT [Dmd=Just D(SS)] :: ([a_abq], [a_abq])
              [LclId, Str=DmdType]
              ds_swT =
                case SplitAt.sp2_$s$wsp2 @ a_abq (GHC.Prim.-# x1_awt 1) xs_abt
                of _ { (# ww1_sxN, ww2_sxO #) ->
                (ww1_sxN, ww2_sxO)
                } } in
            (GHC.Types.:
               @ a_abq x_abs (case ds_swT of _ { (ys_adK, zs_adL) -> ys_adK }),
             case ds_swT of _ { (ys_adK, zs_adL) -> zs_adL })
        }
        }
    }

2011年6月3日金曜日

全てのCプログラマが未定義な振る舞いについて知っておくべきこと #3/3

[原文: What Every C Programmer Should Know About Undefined Behavior #3/3]

このシリーズのPart 1では、Cにおける未定義な振る舞いと、未定義な振る舞いによって"安全な"言語よりもCのパフォーマンスがよくなることがある事例を示した。Part 2では、未定義な振る舞いが引き起こす驚くようなバグと、多くのプログラマがCに対して持っている誤解を見てきた。この記事では、これらに対して警告を出すためにコンパイラが直面する困難と、いくつかの驚かされる問題を取り除きつつパフォーマンスの優位を保つために、LLVMとClangが提供する特長とツールについて説明したい。

未定義な振る舞いを使って最適化するときにどうして警告してくれないの?


「コンパイラが未定義な振る舞いを使って最適化するときに、どうしてコンパイラは警告を出さないのか? ユーザーコードのバグかもしれないのに。」とよく聞かれる。これが難しいのは次の理由による。1) 警告が多すぎて役に立たなくなってしまうと思われる。というのは、バグがない場合にもこの種の最適化は実行されるからだ。2) 人々が警告を欲しいと思う時だけ警告を出すのはとても手の込んだ作業になる。3) ある最適化を適用する機会が、どのような最適化の組み合わせによって生じたのかを (ユーザーに) 表現する良い方法がない。順番に見ていこう。

警告を役に立つようにするのは"本当に難しい"

例を見てみよう。型の不正なキャストのバグがtype based alias analysisによって見つかることが多いからといって、"zero_array" (シリーズのPart 1の例) を最適化するときに "オプティマイザはPとP[i]がaliasではないと仮定している"という警告を出すのは便利とは言えないだろう。

float *P;
 void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = 0.0f;
}

"false positive"問題の他にも、論理学的な問題として、意味のある警告を生成するのに十分な情報をオプティマイザが持っていない、というものがある。そもそも、オプティマイザは、Cとは全く異なるコードの抽象表現(LLVM IR)を扱っているし、二点目としては、コンパイラは多層化されていて、"Pからのロードをループの前に出す"ことを考えているオプティマイザは、TBAAがポインタのエイリアス問題を解決するための解析だということを知らない。そのとおり。これは"コンパイラ野郎がめそめそ泣き言を言っている"だけだ。でも本当に難しい問題なんだ。

みんなが本当に欲しい時だけ警告を生成するのは難しい

Clangは、未定義な振る舞いのうち、単純で明確なものに対しては数多くの警告を出すよう実装している。例えば、"x << 421"のような大きすぎるシフトなど。これは単純で明確だと思うかもしれない。しかし、これは実は難しいことで、というのはみんなはデッドコード中の未定義な振る舞いに対しては警告を出してほしくないからだ。(それと 冗長も参照)

このデッドコードというのはいくつかの形式を取る。マクロに定数が渡されたときに変な形で展開されたものとか。caseに到達しないことを証明するにはコントロールフロー解析が必要になるのに、あるcaseに到達できないことを警告すべきだと文句を言われたことさえある。Cのswtich文は適切に構成される必要はない事を考えれば、これは不可能だ。[訳注: 適切に構成されたswitch文ならコントロールフロー解析でデッドコードを判定できるが、そうじゃないswitch文もあるので一般にはできない、という意味だと思われるが、自信はない。]

これに対するClangの解決策としては、"実行時の振る舞い"に関する警告を扱う基盤を拡張し、同時にそのブロックが実行されないとわかったときには、警告が表示されないように取り除くことだ。でもこれはプログラマ同士の腕相撲みたいなもので、私たちが予想しなかったようなイディオムが出てくるし、こういうことをフロントエンドでやると、みんなが捉えて欲しいというケースを捉えられなくなったりする。
[訳注: ほとんど理解できていませんが、ある種の警告に対しては、静的解析時には警告せず、実際にそのブロックが実行されるときに警告を出す、ということでしょうか・・・? そしてその「ある種」の定義にはどうしても漏れが出てくるし、その「ある種」の警告の中でも場合によっては静的に出してほしいケースを捉えられなくなる、という感じか・・・?]

新しい最適化の機会を作りだした最適化の組み合わせを表現する

フロントエンドで適切な警告を生成するのが難しいんだとしたら、もしかしたら代わりにオプティマイザから警告を生成できるんじゃないだろうか! 役に立つメッセージをオプティマイザで生成するときの最大の問題は、データ追跡の一種だ。コンパイラのオプティマイザは、たくさんの最適化パスをふくんでいて、それぞれがコードを正規化したり、(願わくば) 速く動くように変更していく。もしインライン化モジュールがある関数をインライン化すると決定すると、これが他の最適化の機会、例えば"X*2/2"の最適化、を作り出す。

こういう最適化を例示するために、比較的単純で自己完結している例を出したが、多くのケースは、コンパイラが行うマクロ展開や、関数のインライン化、その他の抽象表現の削除によってこういう最適化が有効になる。現実には、人間はこういう馬鹿馬鹿しいコードを直接書いたりはしない。つまり、問題をユーザーコードに送り返すために、コンパイラがどのように中間コードを得たのかを、警告は再構築しなくてはならない。このようなことをいう能力が必要になるだろう。

警告: 3レベルの関数のインライン化 (リンク時最適化のためファイルを跨っている可能性がある) の後、いくつかの共通部分式が取り除かれ、これをループの前に移動して、13個のポインタがエイリアスになっていないことを証明した後、何か未定義な処理が見つかりました。コードにバグがある場合か、マクロやインライン化によって動的に到達不可能なコードが生成され、そればデッドコードだと証明できない場合のどちらかの可能性があります。

残念ながら、このような警告を生成するのに必要な内部のデータ追跡の仕組みがないし、もしあったとしても、コンパイラはこれをプログラマに伝えるのに十分なインターフェイスを持っていない。

究極的には、未定義な振る舞いは、"この操作は不正です - これは発生しないと仮定することができます"と言っていることになるので、オプティマイザにとって価値があるのだ。"*P"のような場合は、PがNULLではないとオプティマイザが演繹することを可能にしている。"*NULL"のような場合 (例えば、定数伝搬と関数のインライン化の後のコード) には、オプティマイザは、このコードが到達可能に成り得ないことを知ることができる。ここでの重要な教えは、停止性問題を解くことはできないので、コードが実際に死んでいるのか (Cの規格によれば死んでいなければならない)、それとも(長くなる可能性のある) 一連の最適化の末に発覚したバグなのかどうかを、コンパイラが知ることはできない。この2つを区別する一般的な良い方法がないので、生成されるほぼすべての警告はfalse positive (ノイズ) となるだろう。

未定義な振る舞いを扱うClangのやり方


未定義な振る舞いに関する残念な状態を考えると、ClangとLLVMが状況を改善するために何をしようとしているのか不思議に思うかもしれない。そのいくつかはすでに述べてきたが、Clang Static AnalyzerKlee project、そして-fcatch-undefined-behavior フラグは、これらのバグを見付け出すための便利なツールとなる。問題は、これらのツールはコンパイラほどに広く使われていないため、これらのツールを改良するよりは、コンパイラを直接改良したほうがずっと良いということだ。ただし、コンパイラは動的な情報を持っていないということと、コンパイル時間を大量に消費せずに出来ることに限られるという限界があることを覚えておいて欲しい。

世の中のコードの改善するためのClangの第一ステップは、他のコンパイラよりも多くの警告をデフォルトで生成することだ。開発者の中には、よく規律を守り、"-Wall -Wextra" (例えば) をつけてビルドする人たちもいるが、多くの人達は、こういうフラグを知らないか、手間を惜しんで指定しない。多くの警告をデフォルトで有効にすれば、より多くの場合により多くのバグを捉えることができる。

第二ステップは、よくある間違いを捉えるために、コード中で明らかな未定義な振る舞いの多くの種類 (NULLポインタのデリファレンス、大きすぎるシフト、など) に対して警告をだす事だ。前述のとおり、いくつかの注意点はあるが、現実にはこれらはうまく働く。

第三ステップは、LLVMのオプティマイザは、未定義な振る舞いに対して、全般的にあまり勝手なことをしないようにしていることだ。規格では、未定義な振る舞いのいかなる例も、プログラムに完全に勝手な効果を与えて良いことになっているが、これは特に便利なわけでも開発者に優しい振る舞いでもない。その代わりに、LLVMのオプティマイザは、いくつかの異なる方法で最適化している。(以下のリンクは、CではなくてLLVM IRのルールの説明だ。ごめん。)


  1. 未定義な振る舞いのうちのいくつかは、可能ならば、暗黙的にトラップする操作に黙って書き換えられる。例えば、Clangは次のC++関数を

    int *foo(long x) {
      return new int[x];
    }
    
    次のX86-64マシンコードにコンパイルする。

    __Z3fool:
            movl $4, %ecx
            movq %rdi, %rax
            mulq %rcx
            movq $-1, %rdi        # オーバーフローのときは -1 をセットする
            cmovnoq %rax, %rdi    # そうすると、'new' は std::bad_alloc を投げる。
            jmp __Znam
    
    GCCは次のコードを生成する。
    __Z3fool:
            salq $2, %rdi
            jmp __Znam             # オーバーフローの時にセキュリティバグとなる!
    
    この違いは、私たちは、バッファオーバーフローとセキュリティ上のバグに繋がる、潜在的に重大な整数オーバーフローのバグ防ぐために、数サイクルを費やすことを決断したという点にある。(operator newは一般的にとてもコストが高いので、このオーバーヘッドはほとんど目立たない。) GCC の人たちも少なくとも2005年からこの問題に気がついていたが、この記事を書いている時点ではまだ修正されていない。

  2. 未定義な値に対する操作は、未定義な振る舞いになるのではなく、未定義な値を生成するように考えられている。この違いは、未定義な値は、ハードディスクをフォーマットしないし、その他の好ましくない効果を生み出したりもしないことだ。便利な工夫としては、未定義な値の部分がどんな値をとったとしても、演算は同じbitを生成するようになっていることだ。例えば、オプティマイザは、"undef & 1"の上位ビットは0になることを仮定し、最下位ビットのみ未定義として扱う。つまり、((undef & 1) >> 1) はLLVMでは0と定義される。未定義にはならない。[訳注: 32bitで考えると (undef & 1) は 0000000000000000000000000000000? というように最下位ビットのみ未定義になるため、これを1ビット右シフトすると0になる。]

  3. 実行時に未定義な操作を実行する演算 (例えば、符号付き整数のオーバーフロー) は、論理的トラップ値を生成する。これはその後の全ての計算を汚染するが、全プログラムを破壊したりはしない。つまり、未定義な操作に依存している論理式は影響をうけるかもしれないが、プログラム全体を破壊することはないということだ。例えば、未初期化変数を操作しているコードをオプティマイザが削除するのはこういう理由だ。

  4. NULLポインタへのストアや、NULLポインタの呼び出しは __builtin_trap() コール変換される (そしてこれは x86における "ud2"のようにトラップ命令に変換される)。これらは最適化されたコード (関数のインライン化や定数伝搬などの変換の結果) でいつも起こっているが、以前は、これらを含むブロックを削除していた。というのは"明らかに到達不可能”だったからだ。

    (杓子定規な言語法学者という視点から言うと) この動作は厳密に正しいが、みんなはときどきNULLポインタをデリファレンスするし、本来呼ばれるべき関数の次の関数の頭でコードの実行が失敗すると、問題を理解するのがとても難しい、ということを我々は学んだ。[訳注: 以前は未定義な振る舞いを含む関数を削除することもあったので、そうすると、その関数のcallerは実際には、その次に配置されるべき関数を呼ぶことになり、(引数の数や型が当然異なるので) その関数の先頭付近で実行時エラーになっていた、という意味] パフォーマンスの観点では、これらを残すことは、下位のコードを押しつぶすことになる。[訳注: この文の意味がとれない] このため、Clangはこれらを実行時のトラップに変換する: もし実行時にどれか一つに到達したら、プログラムはすぐに停止し、デバッグできるようになる。この方法の欠点は、これらの操作や条件を残すことで、コードが少し膨らむということだ。

  5. プログラマが何をしたいかが明らかである (Pがfloatへのポインタであるときに"*(int*)P"を評価する、など) 場合は、オプティマイザが"正しいことをする”ように努力している。多くの場合これは役に立つが、これに頼りたくはないだろうし、あなたが”明らかだ”と思うことでも、コードが何度も変換された後では明らかでなくなる例もたくさんある。

  6. 以上のどれにも該当しない最適化、例えばPart 1における zero_array やset/callの例は、Part 1で説明したとおりに最適化され、ユーザーへの通知は何も無い。こうしている理由は、ユーザーに有用なことは何も通知できないし、これらの最適化によって現実の(バグのある)アプリケーションが壊れることはめったにないからだ。

私たちが取り組んでいる大きな改善点として、トラップの挿入が挙げられる。これによって、(デフォルトでは無効の) 警告フラグがコードに挿入され、オプティマイザがトラップ命令を生成するときに警告を発するようになるだろうと思っている。ある種のコードベースに対しては極めてノイズが多くなるだろうが、その他に対しては便利に使えるだろう。最初の課題として、オプティマイザが警告を生成できるようにするための、インフラストラクチャの開発が挙げられる。例えば、デバッグ情報の生成を有効にしない限り、オプティマイザはソースコードの行番号という有用な除法すら持っていないのだ。(でもこれは修正可能だ)

もうひとつのより重要な課題は、警告は"追跡”情報を一切持っていないので、「この操作は、ループアンロールを3回行って、関数呼び出しを4段階インライン化した結果です」というような説明ができないことだ。せいぜい、オリジナルの操作のファイル名、行番号、カラム数を指摘することしかできない。これは、非常に単純なケースでは役に立つだろうが、そうじゃなければ、大きな混乱を生むだけになると思われる。いずれにせよ、この機能が優先的に実装されてこなかったのは、a) ユーザーによいエクスペリエンスを提供できなさそうだから b) デフォルトでオンにすることはできないだろうだから c) 実装はとても手間がかかるからだ。

Cより安全な方言を使う (またはその他のオプション)


"究極のパフォーマンス"を求めているのでなければ、最後のオプションは、様々なコンパイラオプションを使ってCの方言を有効にし、未定義な振る舞いを取り除くことだ。例えば、-fwrapvフラグを使えば、符号付き整数のオーバーフローを取り除ける (ただし、全ての整数オーバーフローからくるセキュリティ脆弱性を取り除くわけではない)。-fno-strict-aliasingフラグはType Based Alias Analysisを無効にするので、この種の型のルールを気にする必要はなくなる。もし要望があれば、全ての局所変数をゼロに初期化するフラグや、シフト量が変数の場合のシフトの前に"and"を挿入するフラグなどを Clang に追加することは可能だ。残念ながら、ABIを壊したり、パフォーマンスを極限まで落としたりせずに、Cから未定義な振る舞いを完全に取り除く現実的な方法はない。他のオプションとしては、もうCでコードを書くのはやめて、移植不可能なCの方言でコードを書くということだ。 [訳注: 原文では "The other problem with this"となっているが、文脈上おかしいので、「他のオプション」と訳した。]

移植不可能なCの方言でコードを書くことが嫌なら、-ftrapvフラグと-fcatch-undefined-behaviorフラグ (そして以前に述べたその他のツール) が、この種のバグを追い詰めるための武器になるだろう。デバッグビルドでこれらを有効にすれば、関連するバグを早期に発見するのにとても役に立つだろう。もしセキュリティが重要なアプリケーションを作っているのなら、このフラグはプロダクションコードでも有効だろう。全てのバグを見つけることはできないが、バグの有益なサブセットは見つけるだろう。

究極的には、この問題の本質は、Cが"安全な”言語ではないこと、(Cは成功しているし人気もあるが) 多くの人達は、この言語がどのように動くか正しく理解していないことだ。1989年に標準化されるまでの10年間の進化の中で、Cは"PDPアセンブリの上の薄いレイヤである、低レイヤのシステムプログラミング言語"から"多くの人々の予測を裏切って素晴らしいパフォーマンスを提供しようとしている、低レイヤのシステムプログラミング言語"に変わった。これらのCの"ズル"は、ほとんどすべての場合に動作し、そして多くの場合よりよいパフォーマンスを (時には、極めてよいパフォーマンスを) だす一方で、Cのズルは時には人々を驚かせ、最悪のタイミングで襲ってくる。

Cは移植性のあるアセンブラなどではないし、時には驚くほど違う。この考察が、未定義な振る舞いの背後に潜むいくつかの問題を、少なくともコンパイラ実装者の観点から、うまく説明出来ていることを願う。

原著: Chris Lattner
翻訳: Ken Kawamoto

2011年5月30日月曜日

全てのCプログラマが未定義な振る舞いについて知っておくべきこと #2/3

[原文: What Every C Programmer Should Know About Undefined Behavior #2/3]

連載のpart 1では、未定義な振る舞いとは何か、未定義な振る舞いを利用して、「安全な」言語よりもハイパフォーマンスなアプリケーションを生成するためにCとC++コンパイラが未定義な振る舞いをどのように利用しているのかを議論した。この記事では、未定義な振る舞いが引き起こす全く驚くような結果を説明し、Cがどんなに"安全でない"かを話したい。part 3では、この驚くような結果をやわらげるために、親切なコンパイラは何が出来るのか (それが必須の機能でないとしても) について話したいと思う。

今回の記事は「Cプログラマにとって、未定義な振る舞いが怖くて恐ろしいことがあるのはなぜなのか」と呼びたい。:-)

コンパイラの最適化は驚くような結果を引き起こす



近年のコンパイラオプティマイザは多くの最適化処理を行う。それらは、特定の順番に、時には繰り返し適用され、そしてコンパイラが成長するにしたがって (つまり、新しいリリースが出ると) 変化する。また、異なるコンパイラは、根本的に異なるオプティマイザを持っていることがある。最適化は異なる段階で行われるので、ある最適化が発生させる効果は、それまでの最適化によるコードの変更によって異なることがある。

もっと具体的に説明するために、馬鹿馬鹿しい例を見てみよう(Linux Kernelで見つかったセキュリティーホールになり得るバグを簡略化したもの)
void contains_null_check(int *P) {
  int dead = *P;
  if (P == 0)
    return;
  *P = 4;
}

この例では、コードは"明確に"NULLポインタをチェックしている。もしコンパイラが、"冗長なNULLチェック削除" (Redundant Null Check Elimination: RNCE)よりも先に"デッドコード削除"(Dead Code Elimination: DCE)を行ったとすると、コードはこのように展開していくだろう。

void contains_null_check_after_DCE(int *P) {
  //int dead = *P;     // オプティマイザにより削除される
  if (P == 0)
    return;
  *P = 4;
}

そして次に

void contains_null_check_after_DCE_and_RNCE(int *P) {
  if (P == 0)   // NULLチェックは冗長ではないので、削除されない
    return;
  *P = 4;
}



しかし、もしオプティマイザの構成が異なっていて、"デッドコード削除"よりも先に"冗長なNULLチェック削除"を実行したとすると、このようになるだろう。

void contains_null_check_after_RNCE(int *P) {
  int dead = *P;
  if (false)  // P はすでにデリファレンスされているので、NULLのはずがない
    return;
  *P = 4;
}


そして次に冗長なコードが削除されると

void contains_null_check_after_RNCE_and_DCE(int *P) {
  //int dead = *P;
  //if (false)
  //  return;
  *P = 4;
}


となる。

多くの (分別のある!) プログラマは、この関数からNULLチェックが削除されるととても驚くようだ (そしてほとんどの場合、コンパイラのバグとして報告される)。しかし、C標準によると、"contains_null_check_after_DCE_and_RNCE" と "contains_null_check_after_RNCE_and_DCE" との両方とも完全に有効な最適化であり、様々なアプリケーションのパフォーマンスを向上させるために、二つの最適化があることが重要なのだ。

この例は、意図的に単純に人工的に作ったものだが、似たようなことは関数のインライン化に伴ってよく起こる。関数をインライン化すると、多くの場合、たくさんの最適化の機会が派生するからだ。つまり、オプティマイザが関数をインライン化することを決定すると、多くの局所的な最適化が始まり、コードの振る舞いを変えることになる。[訳注: 原文にある "This is both perfectly..." は前パラグラフと同じ内容であり、原文のミスだと思われるので、訳さない事にする。]


未定義な振る舞いとセキュリティとは仲良くできない


CとCから派生するプログラミング言語は、セキュリティが重要なアプリケーションを書くために幅広く使われている。カーネル、setuid デーモン、ウェブブラウザ、その他にもたくさんある。これらのコードは悪意のある入力にさらされているので、バグはセキュリティホールにつながる多くの問題につながる。Cの特長としてよく知られているものに、コードを読めば何が起こるのかを理解するのが比較的簡単だ、というものがある。[訳注: 前文とのつながりが明確ではないが、おそらく、「何が起こるのかわかりやすいので、セキュリティが重要なアプリケーションを書くのに向いている (と思われている)」という意味だと思われる。]

しかし、未定義な振る舞いによって、この特長はなくなってしまう。結局のところ、ほとんどのプログラマは、前述の"contains_null_check"がNULLチェックをすると思っていたのだろう。このコードはそれほど恐ろしいものではない (というのは、この関数にNULLが渡されると、ストア時にアプリケーションはおそらくクラッシュするであろうし、それはデバッグが比較的簡単だからだ) が、"極めて妥当"に見えて実際には完全に無効なCコードはたくさん存在する。この問題は、非常に多くのプロジェクト (Linux Kernel, OpenSSL, glibc, など) に関わっていて、CERTがGCCに対して脆弱性の注意を出したりもした。(とはいえ、個人的な見解としては、GCCだけではなく、広く使われている最適化を行うCコンパイラ全てがこの脆弱性を持っていると思っている。)

例を見てみよう。注意深く書かれたこのCコードを見てほしい。

void process_something(int size) {
  // 整数のオーバーフローをキャッチする
  if (size > size+1)
    abort();
  ...
  // エラーチェックは省略している
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

このコードは、malloc で確保する領域が、ファイルから読み込むデータ(nul終端バイトを追加する必要がある)を保存するのに十分大きいかをチェックしていて、整数のオーバーフローを回避している。しかし、これはまさに私たちが前に検討した例であり、コンパイラは最適化の一環として、整数オーバーフローのチェックを(正当に)削除することが許される。つまり、コンパイラがこの関数を次のように変換することは十分に可能だということだ。

void process_something(int *data, int size) {
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

64bitプラットフォームでビルドされた場合を考えると、"size"がINT_MAX (おそらくディスク上のファイルサイズ) のときに、これはセキュリティホールにつながるバグとなる。これがどんなに悲惨なことか検討してみよう。このコードを読んだ監査人は、オーバーフローが適切にチェックされていると当然考えるだろう。このコードをテストした誰かは、エラーが発生するケースでテストしない限り、問題を見つけることはないだろう。このセキュアなコードはうまく動いているが、そのうち誰かがうまくやって脆弱性を悪用することになる。要するに、これは驚くようなそして極めて恐ろしいバグなのだ。幸いなことに、この場合の修正は簡単だ。"size == INT_MAX" か似たような条件を使えば良い。

このように、整数のオーバーフローは多くの理由でセキュリティ上の問題となる。完全に定義された整数演算 (-fwrapv や、符号無し整数) を使っていたとしても、全く別の種類 の整数オーバーフローに関わるバグが生まれる可能性はある。幸いなことに、この種のバグはコードに現れるので、知識のあるセキュリティ監査人は大抵の場合問題を見つけるだろう。


最適化済みのコードをデバッグすることは何の役にも立たない


ある種の人々 (例えば、組込み系の低レイヤプログラマで、生成されたマシンコードを見るのが好きな人々) は、最適化を有効にしたままで全ての開発を行う。開発中のコードがバグを含むことはよくあるので、こういう人たちは、デバッグするのが難しい実行時の振る舞いにつながる、驚くような最適化を無駄に多く見ることになる。例えば、最初の記事の"zero_array"の例においてうっかり "i=0" を取り除いてしまうと、未初期化変数を使用していることになるので、コンパイラはループを完全に無視する (zero_arrayを"return;"にコンパイルする) ことが許される。

もうひとつ、(グローバル) 関数ポインタを使用した、最近起こった事例を見てみよう。簡略化したコードはこんな感じだ。

static void (*FP)() = 0;
static void impl() {
  printf("hello\n");
}
void set() {
  FP = impl;
}
void call() {
  FP();
}

Clangはこれを

void set() {}
void call() {
  printf("hello\n");
}
と最適化する。[訳注: 最適化されたため、call中にFPのNULLチェックが無く、implがインライン展開されている。]

NULLポインタを呼び出すのは未定義なため、call()の前にset()が呼ばれたと仮定することが許されるので、こういう最適化をして良い。この場合、開発者は"set"を呼ぶのを忘れたが、NULLポインタデリファレンスでクラッシュすることはなく[訳注: 最適化オプションをつけて開発していたため]、他の人がデバッグビルドを使ったときにコードが壊れた。

未定義な振る舞いを使用している"動いている"コードは、コンパイラが進化したり変わったりすると"壊れる"


私たちは、"動いているように見える”アプリケーションが、新しいLLVMを使ったり、GCCからLLVMに変更して時点で、動かなくなるという事例をたくさん見てきた。LLVM にたまたまバグが一つや二つあったということもあるのだが :-) 、アプリケーションの潜在的なバグが、コンパイラによってまさに表面化したから、というのがほとんだ。これはいろいろな方法で起こり得る。2つ例を挙げると、

1. "以前"は幸運なことにゼロ初期化されていた未初期化変数が、ゼロではないレジスタを共有することになった。これはレジスタ割り当ての変更によってよく起こる。

2. スタック上の配列のオーバーフローが、重要な変数を踏みつぶすようになったが、それは今までは使われていない領域だった。これは、コンパイラが、スタック上にモノを詰め込むやり方を変えたときや、生存期間の異なる変数がスタック領域をより積極的に共有するようになったときに起こる。

認識すべき重要で恐ろしいことは、将来の任意の時点において、未定義な振る舞いに関わるいかなる最適化でも、バグを含むコードの引き金を引き得るということだ。関数のインライン化、ループアンローリング、memory promotion [訳注: 何のことだかわかりません]、その他の最適化が改良され続けていて、上で見たように、これらの重要な目的は、派生的な最適化の機会を与えることである。

私はこの事態には深く失望している。必ずコンパイラが非難されるから、という理由もあるが、多くのCコードが地雷原であり、ただ爆発するのを待っているだけだからだ。そして状況はもっと悪い。というのは、、、。

大規模なコードベースが未定義な振る舞いを含んでいるかを決定する信頼できる方法はない


地雷原をもっともっとひどくする事実として、大規模なアプリケーションに未定義な振る舞いが存在するかどうかを判定する良い方法がないということがあり、したがって将来において状況を打破できる見込みがないことがある。いくつかのバグを見つけるのに使える便利なツールは存在するが、あなたのコードは将来も絶対壊れない、という自信を与えてくれるものはない。いくつかのオプションを、長所と短所とともに見てみよう。

1. Valgrindmemcheck toolは素晴らしいツールで、全ての未初期化変数やその他のメモリ関連バグを見つけてくれる。Valgrindは非常に遅いし、生成されたマシンコードに残っているバグしか発見出来ない (ので、オプティマイザが取り除くことは見つけられない) し、ソースコードの言語がCであることを知らない (ので、大きすぎるシフトや符号付き整数のオーバーフローバグは見つけられない) という意味で、限界がある。

2. Clangは実験的に-fcatch-undefined-behaviorモードを持っている。これは、実行時のチェックを挿入して、大きすぎるシフトや、単純な配列の範囲外アクセスエラーなどを見つけてくれる。これは、アプリケーションの実行速度を遅くするし、ランダムなポインタのデリファレンスは見つけられない (Valgrindは見つけられる) という天で限界があるが、その他の重要なバグを見つけることはできる。Clangはまた-ftrapvフラグ (-fwrapvフラグを間違えないように) を完全にサポートしているので、符号付き整数のオーバーフローを実行時にトラップする。(GCCにもこのフラグはあるが、私の経験から言うと、全く信頼できないしバグが多すぎる。) -fcatch-undefined-behaviorの簡単なデモは次のとおり。

$ cat t.c
int foo(int i) {
  int x[2];
  x[i] = 12;
  return x[i];
}

int main() {
  return foo(2);
}
$ clang t.c 
$ ./a.out 
$ clang t.c -fcatch-undefined-behavior 
$ ./a.out 
Illegal instruction

3. コンパイラの警告は、ある種のバグを見つけるのに役立つ。未初期化変数や単純な整数のオーバーフローのバグなど。これには2つの基本的な限界がある。1) コードが実行されるときの動的情報を持っていないし、2) コンパイル時間が長くならないように、非常に素早く解析しなくてはならない。

4. The Clang Static Analyzerは、バグ (未初期化変数の使用 [訳注: 原文では「未定義な振る舞いの使用」だが、それでは意味が通らないので、未初期化変数の使用に直した。] や、NULLポインタのデリファレンスなど) を見つけるために、もっと深く解析する。通常の警告のようにコンパイルタイムに制限されないので、高性能なコンパイラ警告メッセージだと思ってくれれば良い。静的アナライザの主要なデメリットとしては、1) コードが実行されるときの動的情報を持っていないし、2) 多くの開発者の通常のワークフローに組み込まれていない (ただし、Xcode 3.2 とそれ以降に組み込まれたことは素晴らしい) ことがある。

5. LLVM "Klee" Subprojectは、バグを見つけるために、シンボル解析を行ってコード断片の "全ての実行パスを試し"、テストケースを生成する。偉大な小さなプロジェクトではあるが、大きなアプリケーションに対して実行するのは現実的ではないという点で、大きな限界がある。

6. 私は試したことはないが、Chucky Ellison と Grigore RosuによるC-Semantics toolが、とても面白いツールで、ある種のバグ (sequence point violation [訳注: 日本語訳がわかりません] など) を発見できるようだ。まだ研究段階のプロトタイプだが、小さくて自己完結しているプログラムのバグを見つけるのには役立つかもしれない。詳しい情報を知りたい方には、John Regehrの記事を読むことを勧める。

結論としては、いくつかのバグを見つける道具は道具箱にたくさんあるのだが、アプリケーションに未定義な振る舞いが無いことを証明する良い方法はない、ということだ。実世界のアプリケーションにたくさんのバグがあり、重要なアプリケーションの多くにCが使われていることを考えると、これは極めて恐ろしい。最後の記事では、Clangに特に焦点をおきつつ、未定義な振る舞いを扱うためにCコンパイラが持っている様々なオプションを見ていきたい。

原著: Chris Lattner
翻訳: Ken Kawamoto

2011年5月29日日曜日

全てのCプログラマが未定義な振る舞いについて知っておくべきこと #1/3

[What Every C Programmer Should Know About Undefined Behavior #1/3 の翻訳です。]

LLVMでコンパイルしたコードは、最適化を有効にしているとたまにSIGTRAPシグナルを生成するのはなぜなのか、と聞かれることがある。いろいろ調べたあと、(X86での話だが) Clangは "ud2" インストラクションを生成していたことがわかった。"ud2" は__builtin_trap()が生成するインストラクションと同じものだ。[訳注: #UD例外を発生させる命令。ソフトウェアが#UD例外をハンドルできているかテストするために使われる。つまり、ソースコードが未定義な振る舞いを使っていたから、LLVMはud2インストラクションを生成したのであって、LLVMのバグではない、ということ] こういう問題は幾つかあって、すべて、Cの未定義な振る舞いとそれをLLVMがどう扱っているかとに関係している。


この記事 (3つの記事のうちの最初) では、トレードオフと問題の複雑さをより理解してもらうために、いくつかの問題を説明したい。それと、Cのダークサイドも少し話したい。経験のあるCプログラマ、特に低レイヤを扱っているプログラマは、Cを"高レベルなアセンブラ"だと考えるのが好きだが、Cは決して"高レベルなアセンブラ"などではなく、C++やObjective-Cは、その問題の多くを継承していることがわかるだろう。

未定義な振る舞いの紹介


LLVM IR [訳注: 中間言語実行系?] にもプログラミング言語Cにも"未定義な振る舞い”という概念がある。未定義な振る舞いとはいろいろな意味を含む幅広いトピックだ。John Regehrのブログの記事がもっともうまく説明していると思う。この素晴らしい記事を要約すると、パッと見た感じでは正しそうなCコードが実は未定義な振る舞いを含んでいて、これがバグの原因になっていることがよくある。さらに、Cの未定義な振る舞いがあると、実装 (コンパイラと実行系) は、ハードディスクをフォーマットしたり、全く予期できない挙動を示したり、もっと悪い事をしても良いことになっている。繰り返しになるが、Johnの記事を読むことを強く勧める。


CやCから派生した言語に未定義な振る舞いが存在するのは、Cの言語設計者がCをものすごく効率的な低レイヤプログラミング言語にしたかったからだ。対照的にJava(や他の「安全な」言語」)では、効率を犠牲にしてでも、安全で、実装によらずに同じ挙動を求めているので、未定義な振る舞いは避けられている。どちらも「追求すべき唯一の正しいゴール」ではないが、あなたがCプログラマなら、未定義な振る舞いが何であるのかを確実に理解すべきだ。


詳細に立ち入る前に、幅広いCアプリのパフォーマンスを引き出すためにコンパイラが何をやっているかを簡単に説明したい。というのも、魔法の弾丸などないからだ。ものすごく大雑把に説明すると、ハイパフォーマンスなアプリケーションを生成するために、コンパイラは次のことをする。a) レジスタアロケーションやスケジューリングなどの基本的なアルゴリズムを使って良い仕事をする。 b) 極めて大量の「トリック」(ピープホール最適化、ループ変換、など)を理解し、それが効きそうなら適用する。 c) 不要な抽象化をうまく取り除く (Cのマクロを使うことによる冗長性、関数のインライン化、C++のテンポラリオブジェクト)。 d) ソースコードを台無しにしない。以下の最適化は些細なものに見えるかもしれないが、たくさん実行されるループの中の、たった1サイクルでも削減出来れば、それによって、コーデックが10%速くなったり、消費電力が10%少なくなったりする。


Cの未定義な振る舞いのメリット。実例つきで。


未定義な振る舞いのダークサイドと、LLVMをCコンパイラとして使ったときのポリシーと振る舞いとを説明する前に、未定義な振る舞いのいくつかの実例を検討して、それらがJavaなどの安全な言語よりも良いパフォーマンスを実現するのが分かりやすいと思う。これらの実例は、未定義な振る舞いのクラスごとの"最適化を可能にする”とも言えるし、"未定義な振る舞い"を"定義された振る舞い"にするために必要な"オーバーヘッドを避ける"とも言える。コンパイラのオプティマイザは、このようなオーバーヘッドのいくつかは取り除けるのだが、全てのケースで一般的にオーバーヘッドを取り除くには、停止性問題やその他の"興味深い問題”を解決しなければならない。[訳注: 停止性問題は決定不能問題(解くことはできない)なので、つまり、コンパイラが一般的にオーバーヘッドを取り除くことはできない、と言っている。]


それと、Cの規格が未定義としている振る舞いのうちいくつかは、ClangでもGCCでも定義されていることを指摘しておきたい。これから説明するケースは、Cの規格で未定義とされていて、かつ、ClangとGCCの標準モードで未定義として扱われるものである。


未初期化変数の使用: これは、Cプログラムの問題の原因としてよく知られている。そのため、コンパイラの警告や動的アナライザといった、多くのツールでこの問題を発見できる。スコープに入ったときに変数を0で初期化する必要がない(Javaは0初期化する)ため、パフォーマンスの向上につながる。スカラー変数は、0初期化するとしてもオーバーヘッドは殆ど無いが、スタックに配置された配列やmallocで確保されたメモリを初期化しようとすると、ストレージに対してmemsetを呼ぶこともあり、それは非常にコストが高い。とくにストレージはたいてい完全に上書きされるので。[訳注: 「とくに」以降がよくわからない]


符号付き整数のオーバーフロー: 例えばint型に対する演算がオーバーフローすると、結果は未定義となる。例えば"INT_MAX+1"がINT_MINになることは保証されていない。この振る舞いにより、ある種のコードにとって重要な最適化を行うことが可能となる。例えば、INT_MAX + 1 が未定義であることを利用して、"X+1 > X" を "true" に最適化することができる。乗算がオーバーフローしない(オーバーフローした結果は未定義なので)ことを活かせば、"X*2/2" を "X" に最適化することができる。これらは些細な最適化に見えるかもしれないが、関数のインライン化やマクロ展開によってこのような最適化の機会がたくさん出てくる。より重要な最適化としては、"<=" を使ったループが考えられる。

for (i = 0; i <= N; ++i) { ... }

コンパイラは、iがオーバーフローすると結果が未定義になることを利用して、このループがちょうどN+1回ループすることを仮定できるし、それによって各種のループ最適化を使用できる。一方、もし変数がオーバーフローするとラップする[訳注: 最小値に戻る]と定義されていたとしたら、コンパイラはこれが無限ループになるかもしれない(NがINT_MAXだと無限ループする)ことを仮定しなければならない。intはループ変数によく使われているので、64-bitプラットフォームでは特に問題になる。[訳注: 64bitプラットフォームではNがINT_MAX以上になることが多いが、intは32bitなので、問題が表面化しやすい、という意味だと思われる。]

符合なし整数型のオーバーフローは、2の補数になる(wrapする)ことが保証されていて、これは常に活用できることを指摘しておく。符号つき整数のオーバーフローの振る舞いを定義するコストとしては、これらの最適化が全く使えなくなることがある。(たとえば、よくある症状としては64bitプラットフォームでのループ内で大量に符号拡張をしなくてはならなくなる。) ClangもGCCも "-fwrapv" フラッグをサポートしており、これをつけると、符号付き整数のオーバーフローを定義済みの挙動とするようにコンパイラに強制できる。(ただし、INT_MINを-1で割った場合のみ、依然として未定義となる)


大きすぎるシフト: uint32_t型の変数に対する32bit以上のシフトは未定義である。様々なCPUがこの種のシフトに対して異なる動作をすることから、この仕様が作られたと私は思っている。例えば X86 アーキテクチャでは 32bit 変数のシフト量は 5 bit に切り捨てられる (そのため32bitシフトするのは0bitシフトするのと同じである) が、PowerPC は 6bit に切り捨てる (なので32bitシフトすると0が生成される)。この未定義な振る舞いを取り除くためには、コンパイラが変数のシフトに対して、余分なオペレーション (例えば 'and') を発行しなくはならない。多くのCPUでは、これはコストを2倍にするだろう。[訳注: 例えば「シフト量は5bitに切り捨てられる」と定義すると、5bitに切り捨てるためにandインストラクションが必要になる。大抵のCPUではshiftもandも1サイクルで実行できるので、andを追加することはコストを2倍にすることになる。]



不正なポインタのデリファレンスと配列の範囲外アクセス: 不正なポインタ (NULLポインタや解放済みのメモリを参照するポインタ) のデリファレンスや配列の範囲外アクセスは、Cアプリケーションによく見られるバグなので、説明は不要だと思いたい。これを取り除くには、配列にアクセスするたびに範囲チェックが必要になるし、ABIを変更してポインタが範囲情報を持つようにしなくてはならない。この範囲情報は、ポインタ演算で使用/更新することになるだろう。これは、数値計算アプリケーションにとってもその他のアプリケーションにとっても極めてコストが高くつくし、既存のCライブラリとの互換性を壊してしまう。



NULLポインタのデリファレンス: 誤解されることが多いが、CにおけるNULLポインタのデリファレンスは未定義である。例外になるとは定義されていないし、アドレス0にmmapしたらそのページにアクセスできるとも定義されていない。これは、不正なポインタのデリファレンスを禁止するルールややNULLを番兵(sentinel)として使うこととは別の話だ。NULLポインタのデリファンレンスを未定義とすることで、様々な最適化が可能になる。対照的にJavaでは、コンパイラが、ポインタのデリファレンスをまたがるように、副作用のある操作を移動することを禁止している。ポインタがNULLではないことを証明できないからだ。これはスケジューリングやその他の最適化にとって大きな制約となる。Cを基盤とする言語においては、NULLのデリファレンスが未定義であることで、マクロ展開や関数のインライン化によって生じる多くの単純なスカラー最適化が可能になる。

LLVMから派生したコンパイラを使っているなら、"volatitle"なNULLポインタをデリファレンスすることで、プログラムを(もしそうしたいなら)クラッシュさせることができる。オプティマイザはvolatileなロード・ストアに普通は関与しないからだ。今のところ、NULLポインタを使ってのロードを有効なアクセスにしたり、ロードするときにポインタがNULLであるかもしれないことを明示するフラグは存在しない。


型に関するルール違反: int*をfloat*にキャストして、それをデリファレンスすること(intをfloatとしてアクセスすること)は未定義である。Cは、このような型変換をmemcpyを使って実現することを要求している。ポインタのキャストを使う方法は、正しい方法でなく、未定義な振る舞いとなる。このルールはとても微妙なので、ここでは詳細 (char*に対する例外、ベクタ型は特別な性質がある、共用体 (union) では事情が異なる、など) には触れない。この振る舞いは、メモリアクセス最適化で使われる "Type-Based Alias Analysis" (TBAA) という解析を可能にする。例えば、このルールのおかげで、Clangはこの関数

float *P;
 void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = 0.0f;
 }
を、"memset(P, 0, 40000)"に最適化できる。また、多くのメモリロードをループの前に移動させる、共通部分式を削除する、という最適化も可能になる。この種の未定義な振る舞いは、-fno-strict-aliasing フラグを指定することで無効にすることができ、この解析も無効になる。このフラグが渡されると、Clangは、このループを 10000個の 4byte ストアにコンパイルしなくてはならない (数倍遅くなる)。というのは、次の例のように、ストアによってPの値が変わる可能性を考慮しなくてはいけないからだ。

int main() {
   P = (float*)&P;  // このキャストによって zero_array の中で TBAA 違反となる
   zero_array();
 }
この種の型の乱用はあまり一般的ではないので、標準委員会は、"妥当な" 型のキャストによる予期しない結果と引き換えに、大幅なパフォーマンス向上を選んだ。Javaは、このような欠点なしに、型を利用した最適化を恩恵を受けていることを指摘したい。Javaではそもそも危険なポインタのキャストはできないからだ。

とにかく、Cにおける未定義な振る舞いによって、いくつかの最適化が可能になっていることを少しでも分かってもらえれば嬉しいと思う。もちろん、"foo(i, ++i)" のような sequence point violation [訳注: 日本語訳を知らないので原文のまま]、マルチスレッドプログラムにおける競合状態、"restrict" 違反、ゼロによる除算、など他にもいろいろある。


次の記事 では、パフォーマンスが唯一の目的でないとしたら、Cの未定義な振る舞いが極めて恐ろしいことを説明する。この連載の最後の記事では、LLVMとClangがどのように対処しているかについて話したい。


原著: Chris Lattner
翻訳: Ken Kawamoto