SICP（計算機プログラムの構造と解釈）の講義ビデオがあった。G. J. Sussman 本人が講義してて楽しい。
このビデオでは、第4章の metacircular evaluator（超循環評価器）のあたりを解説している。
car, cdrだけでなくてcadarやcadadrまで発音しているのが微笑ましい（これは"horrible"ですねー、とか言いながら）
最初に流れるバッハの「主よ、人の望みの喜びよ」もかっこいい。音源のトーンに時代を感じるけどかえって新鮮。エッシャーの絵「描く手」も挿入されていて無限と自己言及を暗示してる。
netperf は TCP/UDP, Unix Domain Sockets などのスループットを計測できるソフトの一つ。ここで言う「スループット」は単位時間あたりのデータ転送量のこと。
これを使うためには、ネットワーク内で通信を行う両ホストにインストールしておく必要がある。インストール後は、まず一方のホストでサーバープログラム（netserver）を起動して、もう一方のホストでクライアントプログラム（netperf）を実行するという手順。デフォルト動作では、サーバーは12865番ポートをListenする模様（場合によっては通信できるよう開けておく必要がある）。
rpmforgeのレポジトリを使えば yum でインストールできる。
rpmforgeを参照するための設定は、「CentOS 6 - 初期設定 - yum用リポジトリ追加 ： Server World」に詳しく書いてある。
# yum --enablerepo=rpmforge install netperf
MacPortsでインストールできるらしいが、MacPortsをあまり使っていないので、ソースをコンパイルして入れた。
$ wget ftp://ftp.netperf.org/netperf/netperf-2.5.0.tar.bz2 $ tar xvjf netperf-2.5.0.tar.bz2 $ cd netperf-2.5.0 $ ./configure $ make $ make check $ sudo make install
こんな感じで結果が出力される。
$ netperf -H 192.168.1.20 MIGRATED TCP STREAM TEST from (null) (0.0.0.0) port 0 AF_INET to (null) (192.168.1.20) port 0 AF_INET Recv Send Send Socket Socket Message Elapsed Size Size Size Time Throughput bytes bytes bytes secs. 10^6bits/sec 262140 131070 131070 10.00 14149.31
ヒープソートで使う二分ヒープ（binary heap）。副作用を使わないリスト版を作ろうと思ったが、いいアイデアがない。
結局、よくある配列版のアルゴリズムで妥協した…
;;; すみませんがトップレベルの変数を使いますよ、と
(defvar *heap*)
=> *heap*
(defvar *n*)
=> *n*
;;; 初期化関数
(defun init-heap (N)
(setf *heap* (make-vector N -1) *n* 0)
N)
=> init-heap
;;; 追加する関数（最小値が根になるよう並べる）
(defun heap-push (x)
(let ((i *n*) (i-parent))
(incf *n*)
;; 親と比べながら上へ移動
(while (and (> i 0)
(< x (elt *heap* (setf i-parent (/ (- i 1) 2)))))
(aset *heap* i (elt *heap* i-parent))
(setf i i-parent))
(aset *heap* i x)))
=> heap-push
;;; 取り出す関数
(defun heap-pop ()
(if (zerop *n*)
nil
(let ((ret (elt *heap* 0))
(i 0)
(i-child nil)
(v-child nil)
(v-last (elt *heap* (1- *n*))))
;; 子と比べながら下へ移動
(while (and (setf i-child (select-child-idx i))
(< (setf v-child (elt *heap* i-child)) v-last))
(aset *heap* i v-child)
(setf i i-child))
(aset *heap* i v-last)
(decf *n*)
ret)))
=> heap-pop
;;; 補助関数（i番目の要素の子を求める。子が2つある場合は値が小さいほうを選ぶ）
(defun select-child-idx (i)
(let ((cleft (+ (* 2 i) 1))
(cright (+ (* 2 i) 2)))
(cond ((and (< cright *n*)
(< (elt *heap* cright) (elt *heap* cleft)))
cright)
((< cleft *n*) cleft)
(t nil))))
=> select-child-idx
やっぱりElispで配列を扱うのはめんどくさい。変数のsetf, asetが本当につらい…
続いて動作確認。
;;; 10要素のヒープを作る (init-heap 10) => 10 ;; 乱数10個作って push する (mapcar 'heap-push (loop for i from 1 to 10 collect (random 100))) => (29 80 21 8 70 96 19 93 62 86) ;; 10回ぶん pop してみる (loop for i from 1 to 10 collect (heap-pop)) => (8 19 21 29 62 70 80 86 93 96)
ちゃんと小さい順に pop されているのでOKだが、もっときれいに書きたい。
Wikipediaの二分ヒープのページを見てたら「スレッド木」というキーワードが載っていたので今度調べる。あるいは "Purely Functional Data Structures" とかか。
汎用的なのは、bcコマンドを使う方法。
# 16進 -> 10進 $ echo 'obase=10;ibase=16;FF'|bc 255 # 2進 -> 10進 $ echo 'obase=10;ibase=2;11111111'|bc 255 # 16進 -> 2進 $ echo 'obase=2;ibase=16;FF'|bc 11111111
10進と16進の変換なら、printfコマンドが使える。
# 16進 -> 10進 $ printf "%d\n" 0xFF 255 # 10進 -> 16進 $ printf "%X\n" 255 FF
最近、Perlにucfirstという関数があると知ったので、記録しておく。
ucfirst
$ perl -le 'print ucfirst("hello")'
Hello
ucfirst
$ php -r 'echo ucfirst("hello");'
Hello
upcase-initials(upcase-initials "hello") "Hello" (upcase-initials " hello") " Hello"
string-upcase(string-upcase "hello" :start 0 :end 1) "Hello"
「Mach-O」とは Mac OS X におけるオブジェクトファイルのフォーマットのこと（LinuxにおけるELFみたいなもの）。詳しいことは apple.com のドキュメント「Mac OS X ABI Mach-O File Format Reference」にとても分かりやすく書いてある。
LinuxのELFなら readelf や ldd などでオブジェクトファイルを解析できる。一方、Mach-O の場合はどうすればいいのだろうか。このあたり、実際に手を動かして調べたことを記録しておく。
Linuxの"readelf"みたいなコマンドで、Mach-Oの情報をフォーマットして出力してくれる。オプション-vで人間向けのシンボリックな表示になる。
$ otool -hv /bin/ls
/bin/ls:
Mach header
magic cputype cpusubtype caps filetype ncmds sizeofcmds flags
MH_MAGIC_64 X86_64 ALL LIB64 EXECUTE 13 1928 NOUNDEFS DYLDLINK TWOLEVEL
$ otool -tv /bin/ls /bin/ls: (__TEXT,__text) section 0000000100001478 pushq $0x00 000000010000147a movq %rsp,%rbp 000000010000147d andq $0xf0,%rsp （略）
$ otool -dv /bin/ls|head /bin/ls: (__DATA,__data) section 0000000100006540 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000000100006550 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0000000100006560 50 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 （略）
$ otool -Lv /bin/ls /bin/ls: /usr/lib/libncurses.5.4.dylib (compatibility version 5.4.0, current version 5.4.0) time stamp 2 Thu Jan 1 09:00:02 1970 /usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 123.0.0) time stamp 2 Thu Jan 1 09:00:02 1970
セグメントのサイズを表示してくれるコマンド。オプション無しなら __TEXT, __DATA, __OBJC, その他, 全体 を表示。オプション有り（-mなど）だと、すべてのセグメントについて表示。
$ size /bin/ls __TEXT __DATA __OBJC others dec hex 24576 4096 0 4294979584 4295008256 10000a000
$ size -m /bin/ls Segment __PAGEZERO: 4294967296 Segment __TEXT: 24576 Section __text: 14575 Section __symbol_stub1: 456 Section __stub_helper: 776 Section __cstring: 1199 Section __const: 56 Section __unwind_info: 188 Section __eh_frame: 2072 total 19322 Segment __DATA: 4096 Section __nl_symbol_ptr: 56 Section __la_symbol_ptr: 608 Section __program_vars: 40 Section __const: 600 Section __data: 76 Section __bss: 228 Section __common: 140 total 1748 Segment __LINKEDIT: 12288 total 4295008256
Linuxでおなじみのコマンドだが（GNU の binutils に入ってる）、Macにも同じ名前のコマンドがあった。U, sなどのシンボルの意味はLinuxとだいたい一緒かな。
$ nm /bin/ls
U __DefaultRuneLocale
U ___assert_rtn
U ___error
（略）
$ nm /usr/lib/libSystem.B.dylib 000000000014331a s stub helpers 000000000017a1e6 S $ld$hide$os10.4$__Unwind_Backtrace 000000000017a1d0 S $ld$hide$os10.4$__Unwind_DeleteException （略）
MacでCプログラムを書いていて、プロファイルを調べたくなった。Linuxであればgprofを使うので、とりあえず"which gprof"してみたらMac OSにも入っていた。
しかし、実際に使ってみると期待どおりに動かない。呼出回数は計測されるが時間が計測されないらしく、次の例のように 0.0 が並んでしまった。
$ gprof foo gmon.out （中略） % cumulative self self total time seconds seconds calls ms/call ms/call name 0.0 0.00 0.00 200001 0.00 0.00 _main [79] 0.0 0.00 0.00 200000 0.00 0.00 _f1 [80] 0.0 0.00 0.00 200000 0.00 0.00 _f2 [81] 0.0 0.00 0.00 100000 0.00 0.00 _f3 [82] 0.0 0.00 0.00 1 0.00 0.00 __start [83]
環境は以下のとおり。
$ uname -mrs Darwin 10.8.0 x86_64
調べたところ Mac OS で gprof の動作が不完全なのはFAQというか一般常識。代わりに"Shark"を使うのが定石らしい。
そのShark、「MacOSXではgprofが使えない→Sharkを使う - 西尾泰和のはてなダイアリー」で紹介されているように、確かにこれで間に合うのだが、GUIなのが面倒でツラい。1つのプロセスのプロファイルが欲しいのに、たくさんのプロセスを一度にプロファイリングしてその中から選ぶのも冗長な気がしてしまう。
man shark してみたら実はコマンドラインからも使えて、テキスト形式のレポートも簡単に生成できることがわかった。
以下はfooというプログラムのプロファイルをとってレポートする例。
$ shark -1 -G -i ./foo shark 4.7.3 (383) * Option+Esc to start/stop a trace session * Ctrl+c to stop sampling and quit (any pending samples are processed and saved) * Batch mode * Watching task exits * Profiling limited to foo (PID #33472) Sampling Config: Time Profile Timed Samples & Counters -Sampling begins immediately. -A sample is taken every 1ms. -Sampling ends automatically after 30s. Ready. Sampling... 0 #これはプログラムfooが出力した数字 Processing samples...( Ctrl-c will cancel processing; No session will be created. ) CHUDData - Analyzing samples... （略。WARNINGが出力される…）
sharkコマンドが終わると、カレントディレクトリにファイルが2個生成される。
一つは "session_001.mshark" で、shark的には session file と呼ばれるバイナリ。プロファイルの1セッション分の情報が記録されていると思われる。
もう一つは"session_001-report.txt" で、これがテキストのレポート。次のような内容になっている。長い。
$ cat session_001-report.txt
================================================================================
Session
================================================================================
Authored by: dminor11th on 2011-07-17 19:13:45 +0900 (started 2011-07-17 19:13:32 +0900)
Version: Shark 4.7.3-383 (Session v0.3.0)
Host: dminor11th-MacBookPro.local
Operating System: Mac OS X 10.6.8 (10K540)
Machine Class: MacBookPro5,5
Memory: 4096 MB
Processor: 2 x 2530/1064 MHz Intel Core 2 (Penryn) v7.0
Memory Controller: Unknown
IO Controller: UnknownCHUD.framework: v4.7.3
CHUDProf.kext: v366
CHUDUtils.kext: Unknown
================================================================================
Sampling Configuration
================================================================================
Timed Samples & Counters
-Sampling begins immediately.
-A sample is taken every 1ms.
-Sampling ends automatically after 30s.
================================================================================
Module: SharkProfileAnalysis
================================================================================
REPORT:
================================================================================
Active Process Summary
================================================================================
Process [PID] % Total
-----------------------------------------
foo [33472] 100.0%
-----------------------------------------
Total 100.0%
Process [PID] # Total
-----------------------------------------
foo [33472] 12107
-----------------------------------------
Total 12107
===============================================================================================
foo [33472]
% Total Symbol Library Address Length
-----------------------------------------------------------------------------------------------
58.4% strncmp /usr/lib/libSystem.B.dylib 0x7fff8833c280 0xe5
20.0% f2 /Users/dminor11th/temp/foo 0x100000863 0x14c
18.1% f3 /Users/dminor11th/temp/foo 0x100000a8d 0x81
2.4% dyld_stub_strncmp /Users/dminor11th/temp/foo 0x100000dae 0x6
0.1% __vfprintf /usr/lib/libSystem.B.dylib 0x7fff8834662c 0x5304
0.1% __bzero /usr/lib/libSystem.B.dylib 0x7fffffe00600 0x180
0.1% vsnprintf /usr/lib/libSystem.B.dylib 0x7fff8837b454 0x194
（略）
「あーあ、strncmpが58.4%か…」みたいな感じ。
以上、sharkについて。これでとりあえずは Mac OS でのプロファイラには困らないかなと。
シェルスクリプトには、command substitution や parameter expansion のほかにも process substitution、つまりプロセス置換という概念がある（Bash限定らしい）。
…を見て知った。
今ひとつな例だが、md5チェックサムの検証に使える。
$ diff -s <(md5 -q valgrind-3.6.1.tar.bz2) valgrind-3.6.1.md5 Files /dev/fd/63 and valgrind-3.6.1.md5 are identical
いまさらながら "sleep sort" というネタを知った。非同期処理を使ったすごい発想。
いちおうElispで書いてみた。run-at-timeなんて関数があるんですねー、と。
(defun sleep-sort (lat)
(if (null lat) nil
(lexical-let ((n (car lat)))
(run-at-time n nil (lambda () (print n))))
(sleep-sort (cdr lat))))
(sleep-sort '(3 2 1 0))