Big Sky

2013/04/30 タイトル修正

昨日、とある場所でこんな話で盛り上がった。

逆ポーランド計算機を作ろうと思ったんだけど、どうも結果が期待通りにならない。

ソースコードを見せて貰うと以下の様なコードだった。


#include<stdio.h>

#include<stdlib.h>



#define MAX_SIZE 100



int stack[MAX_SIZE];

int stack_pointer = 0;



void push(int data){

  stack[stack_pointer++] = data;

}



int pop(){

  return stack[--stack_pointer];

}



int pop1(int n){

  printf("pop %d\n", n);

  return stack[--stack_pointer];

}





int main(void){

  char s[MAX_SIZE];

  int a, b;



  while( scanf("%s", s) != EOF ){

    switch (s[0]) {

    case '+':

      push(pop() + pop());

      break;

    case '-':

      /*

       * "3 4 -"などを与えると

       * -1ではなく1となってしまう

       * push(-pop() + pop());

       *

       */

      a = pop();

      b = pop();

      push(b - a);



      break;

    case '*':

      push(pop() * pop());

      break;

    default:

      push(atoi(s));

      break;

    }

  }

  printf("%d\n", pop());



  return 0;

}

このコードはちゃんと動作する。足し算と掛け算は間違いなく動作するだろう。でもコメント部に書いてあるコードを有効にすると結果が変わる。


push(-pop() + pop());

もちろん皆さん知ってはいるだろうが、これはスタックから取り出す順に依存する。このコードを書いた人は「3 4 -」という入力を「3 - 4」として処理したいが為に、先に4を取り出して符号を逆転し、3を取り出して加算する事で-1を得るという動作を期待した。
引数の評価順が左から右である事を期待したんですね。


push(-4 + 3);

しかしこれをgccでコンパイルして実行すると結果は -1 ではなく 1 が得られるんです。
なんと gcc は上記のコードを


push(pop() - pop());

に戻してコンパイルしてるんです。試しに
pop1.c


#include <stdio.h>



int a[] = {3, 4}, p = sizeof(a) / sizeof(a[0]);



int

pop() {

  return a[--p];

}



int

main(int argc, char* argv[]) {

  printf("%d\n", -pop() + pop());

  return 0;

}

pop2.c


#include <stdio.h>



int a[] = {3, 4}, p = sizeof(a) / sizeof(a[0]);



int

pop() {

  return a[--p];

}



int

main(int argc, char* argv[]) {

  printf("%d\n", pop() - pop());

  return 0;

}

上記 pop1.c と pop2.c を「gcc -S」でアセンブリ出力して比較して見たら全く同じ出力内容になりました。


    .file   "pop1.c"

.globl a

    .data

    .align 4

    .type   a, @object

    .size   a, 8

a:

    .long   3

    .long   4

.globl p

    .align 4

    .type   p, @object

    .size   p, 4

p:

    .long   2

    .text

.globl pop

    .type   pop, @function

pop:

    pushl   %ebp

    movl    %esp, %ebp

    movl    p, %eax

    subl    $1, %eax

    movl    %eax, p

    movl    p, %eax

    movl    a(,%eax,4), %eax

    popl    %ebp

    ret

    .size   pop, .-pop

    .section    .rodata

.LC0:

    .string "%d\n"

    .text

.globl main

    .type   main, @function

main:

    pushl   %ebp

    movl    %esp, %ebp

    andl    $-16, %esp

    pushl   %ebx

    subl    $28, %esp

    call    pop

    movl    %eax, %ebx

    call    pop

    movl    %ebx, %edx

    subl    %eax, %edx

    movl    $.LC0, %eax

    movl    %edx, 4(%esp)

    movl    %eax, (%esp)

    call    printf

    movl    $0, %eax

    addl    $28, %esp

    popl    %ebx

    movl    %ebp, %esp

    popl    %ebp

    ret

    .size   main, .-main

    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-3)"

    .section    .note.GNU-stack,"",@progbits

最適化オプションは付けていないので、デフォルトの動作としてこうなります。gcc のバージョンは 4.7.2 です。
この最適化をやめるオプションを軽く探してみましたが見つけられませんでした。
これ、実は clang や MSVC だとこの最適化は行われなくて左から評価が行われる為、どちらも結果は -1 となります。
これは僕の推測なのですが、gccはたぶん、-pop+pop について

左pop
符号逆転
右pop
加算

という処理ををコンパイル時に最適化して pop-pop にする事で

本来右pop
本来左pop
加算

という風に手数を減らしてるんじゃないかと思ってます。


int

main(int argc, char* argv[]) {

  int c = 1;

  printf("%d\n", -pop()*c + pop());

  return 0;

}

こうすれば評価順をちょっとだけ強制できるけど、これも最適化次第では消されてしまうかもしれないしなによりダサい。もちろん~~C言語において関数引数の評価順序は規定されていない~~し、本来こういう呼び出し方はしてはいけないのは皆さん知ってはいると思います。多くの人はこの問題には直面しないでしょう。

C/C++関数引数の評価順序 - yohhoyの日記

プログラミング言語C/C++では、関数実引数の評価順序は未規定(unspecified)となっている。
http://d.hatena.ne.jp/yohhoy/20120304/p1

しかしながら論理演算は左から右に評価される事を期待している為、この様な副作用のあるコードを書くと処理系によっては足をすくわれる事になるという、なんとも面白い事例でした。

気になったので他の言語ではどうなのか調べてみましたが
perl も


my @a = (3, 4);

print ((-pop @a) + (pop @a));

ruby も


a = [3, 4]

puts (-a.pop + a.pop)

python も


a = [3, 4]

print (-a.pop() + a.pop())

javascript も


log = typeof console != 'undefined' ? console.log : print;

var a = [1, 2];

log(-a.pop() + a.pop());

java も


import java.util.Stack;



public class poptest {

    public static void main(String[] args) {

        Stack<Integer> st = new Stack<Integer>();

        st.push(1);

        st.push(2);

        System.out.println(-st.pop() + st.pop());

    }

}

vim script も(誰も聞いてない)


let s:a = [3, 4]

function! s:pop()

  let r = s:a[-1]

  let s:a = s:a[:-2]

  return r

endfunction

echo (-s:pop() + s:pop())

-1 でした。
lisp だと


(setq x '(4 3))

(+ (- (pop x)) (pop x))

こう書けば -1 ですかね。

副作用のある処理を式として列挙記述するのはやめましょう。

vimに起動プロファイラが実装された。

Patch 7.2.269

Patch 7.2.269
Problem:    Many people struggle to find out why Vim startup is slow.
Solution:   Add the --startuptime command line flag.
Files:      runtime/doc/starting.txt, src/globals.h, src/feature.h,
            src/main.c, src/macros.h

http://groups.google.co.jp/group/vim_dev/browse_thread/thread/fcce6570fc7f025c/1ab37514f5656c7b


--startuptime={fname}                                   *--startuptime*

                During startup write timing messages to the file {fname}.

                This can be used to find out where time is spent while loading

                your .vimrc and plugins.

                When {fname} already exists new messages are appended.

                {only when compiled with this feature}

地味だけどこれは大きい修正だと思う。
これまで遅いvimscriptを見つけ出すには、時間を計測出来る様なスクリプト書いて内部で":source"させるとか、重そうなのを勘で選んでpluginから外してみるとかと言った人間臭いソリューションしかなかったんですが、これで楽に遅いvimscriptを見つけ出せる。
起動時に"--startuptime"オプションを付けるだけです。


# vim --startuptime=foo.log

こんな感じに出力するファイル名を指定すると、以下のファイル(foo.log)が生成される






times in msec

 clock   self+sourced   self:  sourced script

 clock   elapsed:              other lines



000.016  000.016: --- VIM STARTING ---

000.238  000.222: Allocated generic buffers

001.693  001.455: locale set

001.731  000.038: GUI prepared

001.742  000.011: clipboard setup

001.764  000.022: window checked

003.195  001.431: inits 1

003.214  000.019: parsing arguments

003.218  000.004: expanding arguments

003.263  000.045: shell init

010.436  007.173: xsmp init

011.004  000.568: Termcap init

011.102  000.098: inits 2

011.356  000.254: init highlight

012.165  000.537  000.537: sourcing /usr/share/vim/vim72/debian.vim

013.170  000.586  000.586: sourcing /usr/share/vim/vim72/syntax/syncolor.vim

013.469  001.031  000.445: sourcing /usr/share/vim/vim72/syntax/synload.vim

051.935  038.345  038.345: sourcing /usr/share/vim/vim72/filetype.vim

052.067  039.779  000.403: sourcing /usr/share/vim/vim72/syntax/syntax.vim

052.151  040.671  000.355: sourcing $VIM/vimrc

055.440  000.296  000.296: sourcing /usr/share/vim/vim72/syntax/nosyntax.vim

056.259  000.507  000.507: sourcing /usr/share/vim/vim72/syntax/syncolor.vim

056.522  000.920  000.413: sourcing /usr/share/vim/vim72/syntax/synload.vim

056.608  001.570  000.354: sourcing /usr/share/vim/vim72/syntax/syntax.vim

056.747  000.027  000.027: sourcing /usr/share/vim/vim72/filetype.vim

056.967  000.106  000.106: sourcing /usr/share/vim/vim72/ftplugin.vim

057.171  000.092  000.092: sourcing /usr/share/vim/vim72/indent.vim

058.050  005.805  004.010: sourcing $HOME/.vimrc

058.076  000.244: sourcing vimrc file(s)

059.677  001.041  001.041: sourcing /home/mattn/.vim/plugin/autodate.vim

062.523  002.768  002.768: sourcing /home/mattn/.vim/plugin/calendar.vim

086.597  024.004  024.004: sourcing /home/mattn/.vim/plugin/codepad.vim

087.964  001.247  001.247: sourcing /home/mattn/.vim/plugin/dicwin.vim

089.372  001.342  001.342: sourcing /home/mattn/.vim/plugin/fastladder.vim

090.757  001.281  001.281: sourcing /home/mattn/.vim/plugin/gist.vim

092.049  001.227  001.227: sourcing /home/mattn/.vim/plugin/googlereader.vim

094.195  002.080  002.080: sourcing /home/mattn/.vim/plugin/matchit.vim

094.577  000.309  000.309: sourcing /home/mattn/.vim/plugin/perldoc.vim

096.699  002.063  002.063: sourcing /home/mattn/.vim/plugin/quickrun.vim

097.149  000.366  000.366: sourcing /home/mattn/.vim/plugin/sudo.vim

099.234  002.013  002.013: sourcing /home/mattn/.vim/plugin/taglist.vim

100.264  000.964  000.964: sourcing /home/mattn/.vim/plugin/tetris.vim

100.895  000.568  000.568: sourcing /home/mattn/.vim/plugin/verifyenc.vim

101.915  000.275  000.275: sourcing /usr/share/vim/vim72/plugin/getscriptPlugin.vim

102.494  000.517  000.517: sourcing /usr/share/vim/vim72/plugin/gzip.vim

103.116  000.544  000.544: sourcing /usr/share/vim/vim72/plugin/matchparen.vim

104.978  001.798  001.798: sourcing /usr/share/vim/vim72/plugin/netrwPlugin.vim

105.210  000.157  000.157: sourcing /usr/share/vim/vim72/plugin/rrhelper.vim

105.340  000.077  000.077: sourcing /usr/share/vim/vim72/plugin/spellfile.vim

105.814  000.392  000.392: sourcing /usr/share/vim/vim72/plugin/tarPlugin.vim

106.039  000.152  000.152: sourcing /usr/share/vim/vim72/plugin/tohtml.vim

106.482  000.383  000.383: sourcing /usr/share/vim/vim72/plugin/vimballPlugin.vim

106.882  000.344  000.344: sourcing /usr/share/vim/vim72/plugin/zipPlugin.vim

109.159  001.825  001.825: sourcing /home/mattn/.vim/chalice/plugin/alice.vim

109.530  000.301  000.301: sourcing /home/mattn/.vim/chalice/plugin/cacheman.vim

110.813  000.897  000.897: sourcing /home/mattn/.vim/chalice/plugin/datutil.vim

111.379  000.392  000.392: sourcing /home/mattn/.vim/chalice/plugin/dolib.vim

126.889  017.296  016.007: sourcing /home/mattn/.vim/chalice/plugin/chalice.vim

128.028  000.909  000.909: sourcing /home/mattn/.vim/chalice/plugin/datutil.vim

128.470  000.374  000.374: sourcing /home/mattn/.vim/chalice/plugin/dolib.vim

128.487  003.794: loading plugins

130.381  001.894: inits 3

131.144  000.763: reading viminfo

137.261  006.117: setup clipboard

137.304  000.043: setting raw mode

137.336  000.032: start termcap

137.499  000.163: clearing screen

167.107  029.608: opening buffers

167.376  000.269: BufEnter autocommands

167.384  000.008: editing files in windows

167.438  000.054: VimEnter autocommands

167.443  000.005: before starting main loop

320.531  153.088: first screen update

320.544  000.013: --- VIM STARTED ---

これを見るとvimrcと、codepad.vimの読み込みが遅い事が一目瞭然である。

ちなみにcodepad.vimを外して起動すると






times in msec

 clock   self+sourced   self:  sourced script

 clock   elapsed:              other lines



000.016  000.016: --- VIM STARTING ---

000.251  000.235: Allocated generic buffers

001.749  001.498: locale set

001.786  000.037: GUI prepared

001.797  000.011: clipboard setup

001.819  000.022: window checked

003.267  001.448: inits 1

003.287  000.020: parsing arguments

003.291  000.004: expanding arguments

003.338  000.047: shell init

015.880  012.542: xsmp init

016.455  000.575: Termcap init

016.555  000.100: inits 2

016.807  000.252: init highlight

020.289  000.617  000.617: sourcing /usr/share/vim/vim72/debian.vim

021.349  000.627  000.627: sourcing /usr/share/vim/vim72/syntax/syncolor.vim

021.634  001.058  000.431: sourcing /usr/share/vim/vim72/syntax/synload.vim

059.675  037.918  037.918: sourcing /usr/share/vim/vim72/filetype.vim

059.815  039.391  000.415: sourcing /usr/share/vim/vim72/syntax/syntax.vim

059.898  042.967  002.959: sourcing $VIM/vimrc

063.216  000.304  000.304: sourcing /usr/share/vim/vim72/syntax/nosyntax.vim

064.068  000.536  000.536: sourcing /usr/share/vim/vim72/syntax/syncolor.vim

064.332  000.951  000.415: sourcing /usr/share/vim/vim72/syntax/synload.vim

064.418  001.613  000.358: sourcing /usr/share/vim/vim72/syntax/syntax.vim

064.557  000.028  000.028: sourcing /usr/share/vim/vim72/filetype.vim

064.775  000.107  000.107: sourcing /usr/share/vim/vim72/ftplugin.vim

065.189  000.301  000.301: sourcing /usr/share/vim/vim72/indent.vim

066.131  006.131  004.082: sourcing $HOME/.vimrc

066.161  000.256: sourcing vimrc file(s)

067.835  001.098  001.098: sourcing /home/mattn/.vim/plugin/autodate.vim

070.712  002.793  002.793: sourcing /home/mattn/.vim/plugin/calendar.vim

071.928  001.142  001.142: sourcing /home/mattn/.vim/plugin/dicwin.vim

073.385  001.389  001.389: sourcing /home/mattn/.vim/plugin/fastladder.vim

074.731  001.280  001.280: sourcing /home/mattn/.vim/plugin/gist.vim

076.102  001.298  001.298: sourcing /home/mattn/.vim/plugin/googlereader.vim

079.975  003.793  003.793: sourcing /home/mattn/.vim/plugin/matchit.vim

080.426  000.318  000.318: sourcing /home/mattn/.vim/plugin/perldoc.vim

082.556  002.071  002.071: sourcing /home/mattn/.vim/plugin/quickrun.vim

083.004  000.362  000.362: sourcing /home/mattn/.vim/plugin/sudo.vim

085.061  001.985  001.985: sourcing /home/mattn/.vim/plugin/taglist.vim

086.098  000.967  000.967: sourcing /home/mattn/.vim/plugin/tetris.vim

086.747  000.587  000.587: sourcing /home/mattn/.vim/plugin/verifyenc.vim

087.533  000.257  000.257: sourcing /usr/share/vim/vim72/plugin/getscriptPlugin.vim

088.056  000.467  000.467: sourcing /usr/share/vim/vim72/plugin/gzip.vim

088.678  000.543  000.543: sourcing /usr/share/vim/vim72/plugin/matchparen.vim

090.576  001.835  001.835: sourcing /usr/share/vim/vim72/plugin/netrwPlugin.vim

090.808  000.150  000.150: sourcing /usr/share/vim/vim72/plugin/rrhelper.vim

090.945  000.084  000.084: sourcing /usr/share/vim/vim72/plugin/spellfile.vim

091.401  000.402  000.402: sourcing /usr/share/vim/vim72/plugin/tarPlugin.vim

091.638  000.157  000.157: sourcing /usr/share/vim/vim72/plugin/tohtml.vim

092.072  000.376  000.376: sourcing /usr/share/vim/vim72/plugin/vimballPlugin.vim

092.498  000.365  000.365: sourcing /usr/share/vim/vim72/plugin/zipPlugin.vim

094.842  001.839  001.839: sourcing /home/mattn/.vim/chalice/plugin/alice.vim

095.189  000.272  000.272: sourcing /home/mattn/.vim/chalice/plugin/cacheman.vim

096.477  000.918  000.918: sourcing /home/mattn/.vim/chalice/plugin/datutil.vim

097.079  000.415  000.415: sourcing /home/mattn/.vim/chalice/plugin/dolib.vim

112.786  017.536  016.203: sourcing /home/mattn/.vim/chalice/plugin/chalice.vim

113.924  000.909  000.909: sourcing /home/mattn/.vim/chalice/plugin/datutil.vim

114.370  000.379  000.379: sourcing /home/mattn/.vim/chalice/plugin/dolib.vim

114.386  003.571: loading plugins

116.239  001.853: inits 3

117.053  000.814: reading viminfo

123.322  006.269: setup clipboard

123.367  000.045: setting raw mode

123.397  000.030: start termcap

123.437  000.040: clearing screen

124.526  001.089: opening buffers

124.899  000.373: BufEnter autocommands

124.907  000.008: editing files in windows

125.967  001.060: VimEnter autocommands

125.979  000.012: before starting main loop

287.072  161.093: first screen update

287.085  000.013: --- VIM STARTED ---

30msも減っている事が確認出来る。実はcodpad.vimは内部でpythonインタプリタを呼び出しており、これがvimの起動を遅くしている原因となっています。

vimrc内部でどの部分が遅いかについては、個々に見ていくしか無いのだけれど、ちょっと最近vimの起動が遅いのよねぇ...奥さん...って人には持って来いだと思う。

ちなみに入ったばかりなpatchなので、試すにはソースからビルドするしか方法はありませんが、プロファイル用にvimをビルドしてみる...ってのもありかもしれませんね。