憂鬱な午後のひととき

1月31日_

Haskellのquick sort(といわれるもの)の続き

昨日「遅延評価のおかげで」O(n log n)と書いたが違った. 遅延評価がなくてもO(n log n)のようだ(もちろん最悪時などを除く).

長さnのリストが長さaのリストに分かれているときを考える. 個数はn/a. aとaの連結操作では先頭からa-1回リストをたどる操作が行われる. したがって隣り合う二つのリストをくっつけあう操作を一度すると全体で(a-1)(n/a-1)=O(n).

この操作の後は長さ2aのリストがn/(2a)個になっている. 

- - - - - - - - - - - - - - - -
↓
--  --  --  --  --  --  --  --
↓
----    ----    ----    ----
↓
--------        --------
↓
----------------

こんな感じで最終的に長さnのリストが一つできて完了. その回数はlog nなのでトータルO(n log n). 単方向リストの連結ってもっとオーダーがありそうな気がしてたのだけど, この場合はうまくいくのだな.
# もちろん左から順に結合してるとO(n^2)になってしまうが.

ちなみにHaskellでいろんなソートのベンチマークは@kazu_yamamotoさんのHaskellの配列でクイックソートで紹介されている.

1月30日_

Haskellのquick sort(といわれるもの)

qs [] = []
qs (pt:xs) = qs (filter (<pt) xs) ++ [pt] ++ qs (filter (>=pt) xs)

というコードがリスト操作込みでO(n log n)で動くらしいと聞いたので本当かなと昼休み紙と鉛筆でシミュレートしてみた(今回はピボット選択に関しては気にしない). 遅延評価のおかげでそのオーダーで動きそうな気はしてきたのだけど確信が持てないとか言ってたら「実測せんかい, こらあ」という一声があったのでやってみた. 

import System.Environment
import System.Random
import System.Time
import Data.Time
import Data.List

qs [] = []
qs (pt:xs) = qs (filter (<pt) xs) ++ [pt] ++ qs (filter (>=pt) xs)

rand::(Int,Int) -> IO [Int]
rand range = do
 cur <- getCurrentTime
 let seed = 0 -- truncate $ utctDayTime cur * 1e6
 setStdGen $ mkStdGen seed
 g <- getStdGen
 return $ randomRs range g

main = do
 ss <- getArgs
 let n = if length ss > 0 then read (ss!!0)::Int else 100000
 x <- rand (0, 0x7fffffff)
 let xs = take n x
 print $ sum xs
 begin <- getCurrentTime
 let ys = qs xs
-- let ys = sort xs
 print $ sum ys
 end <- getCurrentTime
 print $ diffUTCTime end begin

ghc --make -O2 qs.hs

ソート時間にsumも入ってるけど, そちらはO(n)だし こうしておけばすべての値が確定するだろうということであまり細かいことは気にしない.

64bit Windows 7 + Haskell platform 2012.2.0.0(ghc 7.4.1)でベンチマーク.

integer sort benchmark[sec]
個数 1000000 2000000 4000000 8000000 16000000
qs 2.04 4.76 9.83 22.42 40?/out of memory
Data.sort 2.28 5.30 12.18 27.58 62.46
C++ list 0.312 0.749 1.841 4.243 9.734
C++ vector 0.063 0.156 0.343 0.718 1.497

確かにO(n log n)っぽい(もちろんこれだけでn log nとは言えないが酷いことにはなってないという程度で). 面白いのはqsの方が標準ライブラリのData.sortよりも速かったこと.

Data.Listを見るとData.Listのソートはmerge sortらしい. コメント欄を見ると 

Quicksort replaced by mergesort, 14/5/2002.

とあるので昔はquick sortだったのが10年前にmerge sortに変わったようだ. メモリ効率のよさが買われた模様. 確かにメモリ使用量を見るとData.Listの方が少ないしnが大きいとqsはout of memoryになった. 

ghc --make -O2 qs.hs -rtsopts
qs 8000000 +RTS -t --machine-readable
integer sort benchmark[sec]
n = 8M bytes allocated average bytes used max bytes used peak megabytes allocated
Data.sort 14725177140 54923469 207987780 594
qs 19318674416 193690576 456104816 1261
1月28日_

Windows 8優待購入プログラムを利用しようかと思ったらうちのマシンの購入日は5月だった(対象は6月以降).

1月26日_

@ConstellationさんがARM版Xbyak作るとか言ってるし, 私もARMの勉強しようと同僚に勧められたNexus 7(16GB)を買った. 19800円. 最初Nexus 10を購入しようとして, あれ, 売ってないのかという程度にこの世界のことを何も知らない.

ARMって確か殆どの命令に条件分岐フラグがついてたんだっけ, へえSIMDもあるんだとか. ここはARM最適化勉強会とか開いてその筋の人に教えてもらおう計画.

自宅は未だに無線LANが無かったので, ついでにその場にあった無線LANルータを適当に選んで購入(WZR-HP-G302H). 4000円. 安くなったもんだなあ.

ルータのポートフォワード設定方法が今まで使ってたやつとかなり違って予想以上に苦労した. 一つ設定する毎にリセットがかかるのもうっとうしい. 四苦八苦してるところにLinuxサーバをrebootしたらkernel panic. げっ, とこんどはそちらの救済処置にかかる.

/dev/sda1をmountしようとして死亡してるのでどうしようもできず, 結局ubuntu 12.10を新規インストールしてデータ復旧した.

なんとか元の状態に戻せたので一安心. だが肝心のNexusはまだ触ってない….

1月25日_

@miura1729さんがいろいろ修正してくださってgithub.com/miura1729/mrubyがついにgcc 4.7.2で動作した. よかった, よかった.

『UXデザイン入門』(川西裕幸 潮田浩 栗山進)

ユーザエクスペリエンス(UX)とは何か, 何故UXデザインが必要か, これは何を解決するものであって何をしないものなのかなどが明確に説明されている.

UXデザインはプログラマやグラフィックデザイナーと独立して存在するもので, それらと同じレイヤに担当者をおくのが望ましいそうな.

ユーザの提案や要望をそのまま製品に反映させてはいけない. なぜならユーザはデザイナーでも開発者でもないのでそのまま受け入れると無秩序で一貫性の無いものになりがちだから. なるほどな. これはフリーソフトの開発でもありそうだ.

もちろん, ユーザの意見を聞くべきではないと主張しているのではなく, ユーザを調査して, 彼らの振る舞いや目的を理解し, それをデザインするのが大切と主張する.

会議室の種別の表示したいという要求の裏には, 実は簡単に会議室を変更したいという目的が隠れていたという話はおもしろかった.

1月24日_

うーん, 試行錯誤してるけどうまくいかない.

ci->entry()もasmの中に取り込みたいので少しずつまとめて 

  asm volatile("mov %%ecx, -0x4(%%esp)\n\t"
               "mov %%ebx, -0x8(%%esp)\n\t"
               "mov %0, %%ecx\n\t"
               "mov %1, %%eax\n\t"
               "mov %2, %%ebx\n\t"
               "mov %3, -0xc(%%esp)\n\t"
               "sub $0xc, %%esp\n\t"
#ifndef AAA
               "call *%1\n\t"
#endif
  : : "g"(regs), "r"(ci->entry), "g"(ppc), "r"(status) : "ebx");

#ifdef AAA
   ci->entry();
#endif
  asm volatile("add $0xc, %%esp\n\t"
               "mov %%eax, %0\n\t"
               "mov %%edx, %1\n\t"
               "mov -0x8(%%esp), %%ebx\n\t"
               "mov -0x4(%%esp), %%ecx\n\t"
  : "=o"(rc), "=g"(prev_entry));

のように書き換えてみるとgcc 4.6.3でAAAを定義してるときは動くのにAAAを定義しないときは動かない. asmの出力は該当個所はどちらも 

# 126 "src/jit.c" 1
    mov %ecx, -0x4(%esp)
    mov %ebx, -0x8(%esp)
    mov 40(%esp), %ecx
    mov %eax, %eax
    mov %edx, %ebx
    mov %ebp, -0xc(%esp)
    sub $0xc, %esp

    call *%eax

    add $0xc, %esp
    mov %eax, 60(%esp)
    mov %edx, 40(%esp)
    mov -0x8(%esp), %ebx
    mov -0x4(%esp), %ecx

で同じなんだがその後ろの方が少しずつ違ってくる. 

     OK                     NG
1. movl    0(%ebp), %eax     movl    0(%ebp), %eax   ; 1
2. movl    (%eax), %eax      movl    (%edx), %edx    ; (*)
3. movl    %eax, 24(%esp)    movl    (%eax), %eax    ; 2
4. movl    28(%esp), %eax    movl    %eax, 24(%esp)  ; 3
5. movl    (%eax), %edx      movl    24(%esp), %eax  ; 6
6. movl    24(%esp), %eax    cmpl    $9, 28(%eax)    ; 7
7. cmpl    $9, 28(%eax)      movl    8(%eax), %ecx   ; 8
8. movl    8(%eax), %ecx

5行目が無くなって代わりに(*)になってるんだなあ. 二つ目のasm文の"=o"と"=g"の組み合わせもこれ以外では落ちるしinline assemblerわからん.

1月23日_

mrubyのJITがgcc 4.7で動かない.

@miura1729さんがmrubyの一部をJIT化(32bit)する作業をしてらして, ちょっと試してみた. gcc 4.6では動くのにgcc 4.7では動かない. 正確にいうと-O1なら動くけど-O2にすると落ちる. src/jit.cのasm文の隙間にあるci->entry()でこけているようだ.

まだ解決できてないのだけど試行錯誤してる様を書いてみる.

まず最適化でasmが消されてるかもしれないのでasm文に__volatile__をつけてみた. けど効果はなかった.

でasm("int $3");を直前に埋め込んでgdbで追いかける. これはgcc 4.6で正しく動作してるとき. 

=> 0x808631e <mrbjit_dispatch+334 at src/jit.c:156>:    mov    DWORD PTR [esp-0xc],eax
(gdb)
159           asm __volatile__("sub $0xc, %esp");
1: x/i $pc
=> 0x8086322 <mrbjit_dispatch+338 at src/jit.c:159>:    sub    esp,0xc
(gdb)
mrbjit_dispatch (mrb=0x4, status=0x0) at src/jit.c:161
161           ci->entry();
1: x/i $pc
=> 0x8086325 <mrbjit_dispatch+341 at src/jit.c:161>:    call   DWORD PTR [ebp+0xc]
(gdb)
0xf7be4000 in ?? ()
1: x/i $pc
=> 0xf7be4000:  push   ecx

ci->entry();がcall [ebp+0xc]になって正しくそこにジャンプしてる. in ?? ()になってるのはJIT生成コードだからシンボルが無いため. 次にgcc 4.7で動かしてみる. 

=> 0x80862bd <mrbjit_dispatch+317 at src/jit.c:156>:    mov    eax,DWORD PTR [esp+0x54]
(gdb)
0x080862c1      156           asm __volatile__("mov %0, -0xc(%%esp)"
1: x/i $pc
=> 0x80862c1 <mrbjit_dispatch+321 at src/jit.c:156>:    mov    DWORD PTR [esp-0xc],eax
(gdb)
159           asm __volatile__("sub $0xc, %esp");
1: x/i $pc
=> 0x80862c5 <mrbjit_dispatch+325 at src/jit.c:159>:    sub    esp,0xc
(gdb)
mrbjit_dispatch (mrb=0x4, status=0x0) at src/jit.c:161
161           ci->entry();
1: x/i $pc
=> 0x80862c8 <mrbjit_dispatch+328 at src/jit.c:161>:    call   DWORD PTR [ebx+0xc]
(gdb)
0xf7d5e22f in ?? () from /lib/i386-linux-gnu/libc.so.6
1: x/i $pc
=> 0xf7d5e22f:  mov    ebp,DWORD PTR [esp+0x38]

ebx経由でジャンプしてわけのわからんところに飛んでしまった. 正しいコードはgcc 4.6のときと同じく$ebp+0xcのところにある. p/xコマンドでアドレスをとって, その領域をdisasして確認できる. 

(gdb) p/x *(int*)($ebp+0xc)
$6 = 0xf7be4000
(gdb) disas 0xf7be4000,+32
Dump of assembler code from 0xf7be4000 to 0xf7be4020:
   0xf7be4000:  push   ecx
   0xf7be4001:  push   ebx
   0xf7be4002:  mov    eax,DWORD PTR [esp+0xc]
   0xf7be4006:  push   eax
   0xf7be4007:  mov    eax,DWORD PTR [eax+0x8]
   0xf7be400a:  mov    DWORD PTR [eax],0x81a0f70
   0xf7be4010:  push   0x80d32b8
   0xf7be4015:  call   0x8086af0 <mrbjit_exec_enter at src/jit.c:366>
   0xf7be401a:  add    esp,0x8
   0xf7be401d:  pop    ebx
   0xf7be401e:  pop    ecx
   0xf7be401f:  cmp    eax,eax
End of assembler dump.

ebxの値がおかしいのはなぜだろうとjit.cをよく見るとその直前でebxに値を設定している. 

  asm __volatile__("mov %ebx, -0x8(%esp)");
  asm __volatile__("mov %0, %%ebx" :: "a"(ppc));

この直前でebxの値を見ると正しい場所を指していた. 

(gdb) p/x *(int*)($ebx+0xc)
$2 = 0xf7be4000

つまりasm文の中でebxを書き換えたのをコンパイラが知らずに正しい値が入っているものと思ったコードが生成されているわけだ. というわけでci->entry()のところをcall [ebx+0xc]からcall [ebp+0xc]にしたら動くだろうと思ったのに駄目だった. まあ決め打ちはいかんかと思って 

  asm __volatile__("mov %0, %%eax" : : "a"(ci->entry));
  asm __volatile__("mov %0, %%ebx" : : "r"(ppc));
  asm __volatile__("sub $0xc, %esp");
  asm __volatile__("call *%eax");

こんな風にebxを壊す前にeaxに代入してcallしたらdebugで見ると正しく飛んでる. 

0x080862c5      142           asm __volatile__("mov %0, %%eax" : : "a"(ci->entry));
1: x/i $pc
=> 0x80862c5 <mrbjit_dispatch+325 at src/jit.c:142>:    mov    eax,eax
(gdb)
143           asm __volatile__("mov %0, %%ebx" : : "r"(ppc));
1: x/i $pc
=> 0x80862c7 <mrbjit_dispatch+327 at src/jit.c:143>:    mov    ebx,ebp
(gdb)
144           asm __volatile__("sub $0xc, %esp");
1: x/i $pc
=> 0x80862c9 <mrbjit_dispatch+329 at src/jit.c:144>:    sub    esp,0xc
(gdb)
mrbjit_dispatch (mrb=0x4, status=0x0) at src/jit.c:145
145           asm __volatile__("call *%eax");
1: x/i $pc
=> 0x80862cc <mrbjit_dispatch+332 at src/jit.c:145>:    call   eax
(gdb) si
0xf7be4000 in ?? ()
1: x/i $pc
=> 0xf7be4000:  push   ecx

けれども実行すると別のところで落ちてしまった. なぜだろう. 出口の部分でも何かしないといけないのか, ebxが正しい値を指してること前提のコードになってるのか. いずれにせよここの呼び出し規約が普通と違う感じなのでまじめにコード読まないとわからない.

てかgcc 4.6でもeaxにジャンプ先アドレス入れてcallすると駄目というのが不可解.

個人的にはこういうややこしいところはgasのinline assemblerだと思った通りに コードを生成させるのが大変なのでXbyakでやってしまいそう.

1月17日_

先日のプロシンで場外乱入(?)してきた@sinya8282さんがTensors:Geometry and Applicationsを読めと言う. たまには数学ちっくな本でも読んでみるかと2章の頭を見始める.

いきなりそれw = 0のとき成り立たないでしょうという記述がでてきてちょっとめげる. それともどっかの仮定に含まれているのかな.

1月14日_

ものすごい大雪. 明日に備えて長靴を買いに行こうかと思ったけど店までいくのを断念. 泥縄すら失敗.

1月13日_

寝不足の疲れで体調悪い. 眠たいのだがうとうとしてても頭が休んでない.

1月12日_

若い人たち(笑)に合わせて4時過ぎまで数学の議論につきあってたら眠くて頭が痛い.

1月11日_

第54回プログラム・シンポジウム参加

箱根登山鉄道の電車のスイッチバックやのんびりとした速度(20km/hぐらい)が新鮮で窓の外ずっと眺めてたり.

今回は去年参加したラボユースの鈴木さんが山内賞受賞したのと、今年のラボユースの内田さんが参加するため付き添いのような感じで.

鈴木さんのivに実験的にmie/string.hppを組み込んでみて, 多少長めの文字列でindexOfのマイクロベンチマークでv8より速くなってやったねとか.

二人とも発表は落ち着いてでていてたいしたもんだなあと感心.

1月10日_

自己書き換え

#include <stdio.h>
#include <xbyak/xbyak.h>

struct Code : public Xbyak::CodeGenerator {
    void set(int x)
    {
        mov(eax, x);
        ret();
    }
};

int main()
{
    Code c;
    int (*f)() = (int (*)())c.getCode();
    c.set(0);
    printf("f=%d\n", f());
    c.reset();
    puts("reset");
    c.set(1);
    int ret = f();
    printf("f=%d\n", ret);
    if (ret == 0) {
        puts("maybe on valgrind");
    }
}

みたいなコード書いたらvalgrind上で実行してるか判別できるのかなと思ったらそもそも動かなかった. マニュアルを見ると--smc-check=allをつけたらうまくいく(smc=self-modified-code)っぽいんだが駄目だった. まあ, ひどいコードなのでいいけど.

ちなみにIntelのマニュアルを見ると特に何もコードをフラッシュさせなくても動くと書いてあるように見える(もちろんペナルティは食うが).

実際, 上記コードはWin/Linux + i3上で動いた(Xbyakはdevelop版). win32にはFlushInstructionCacheという関数もあるけど昔は何もしなかったようだ.

1月9日_

ubuntu 12.04から12.10へのupgrade.

最初do-release-upgradeを実行したら環境変数を取得してるPythonスクリプトの中でこけた. locale.getdefaultlocale()が空を返すのが悪いらしい. ようわからんが 

sudo sh -c "export LC_ALL='ja_JP.UTF-8'; do-release-upgrade"

としたらLC_ALL周りで警告が出つつも動いた. あとはvmware-toolの入れ直しでOKと思ったらhgfsのドライバのbuildでエラー. ただVMwareも古かったので新しいのにしてやり直したら無事完了.

1月7日_

会社は4日からだったけどその日は有給を取ったので今日が初出社. 今年は人さまの役に立ってると思える仕事をしたいな.

まずは自分のコードを棚に上げてちまちまと人さまのコードをレビュー. うーん, 後ろ向きだ.

1月6日_

XbyakをJavaScriptのJIT部分に使ってくれてる@Constellationさんの依頼により, 内部でstd::mapを使っている部分を可能ならstd::unordered_mapを使うように修正.

mini-SQLインタプリタのJITで使ってるというtorshieさんからはCodeGeneratorのコンストラクタのコストが無視できないという要件が. 1k個の関数を作ったり破棄したりするらしい.

そんなたいしたことしてないので重たくないと思うんだけど, みんなヘビーな使い方だな. ぼちぼちXbyak自体の最適化もしないといかんのか.

1月4日_

しぶんぎ座流星群を見るため夜中ぶらっと散歩. 残念ながら雲がかかって見えなかった.

1月1日_

年末, 年始帰省したときいろいろしようと思ってたのにノートPCのACアダプタを忘れて何もできなかった. ネットワークも無しで約5日. まあ無くてもどってことない. てなわけでいろいろ本を読んでいた.

『ルーズヴェルト・ゲーム』(池井戸潤)

野球チームがお荷物になってる中堅企業の再建. それを妨害する大会社. 銀行も出てくるがその要素は凄く薄い. 著者のいつものパターン. おもしろいんだけどあまりに型通りでどうかなと.

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