Path: ccsf.homeunix.org!ccsf.homeunix.org!news1.wakwak.com!nf1.xephion.ne.jp!onion.ish.org!news.daionet.gr.jp!news.yamada.gr.jp!newsfeed.media.kyoto-u.ac.jp!oix.u-ryukyu.ac.jp!u-ryukyu.ac.jp!ie.u-ryukyu.ac.jp!gama.is.tsukuba.ac.jp!nadesico.cc.tsukuba.ac.jp!gssm!kuno From: kuno@gssm.otsuka.tsukuba.ac.jp Newsgroups: fj.comp.lang.lisp Subject: Re: GCと計算量 (Re: GC Re:LISPを使うとき([Q] ログイン Date: Fri, 3 Sep 2004 02:25:18 GMT Organization: GSSM, Univ. Tsukuba, Tokyo, Japan Lines: 35 Message-ID: <040903112518.M0262707@sma.gssm.otsuka.tsukuba.ac.jp> References: <3990362news.pl@insigna.ie.u-ryukyu.ac.jp> <3990408news.pl@insigna.ie.u-ryukyu.ac.jp> <71pt5450tw.fsf@hinttika.msi.co.jp> <3990410news.pl@insigna.ie.u-ryukyu.ac.jp> <3990417news.pl@insigna.ie.u-ryukyu.ac.jp> <3990420news.pl@insigna.ie.u-ryukyu.ac.jp> NNTP-Posting-Host: sma.gssm.otsuka.tsukuba.ac.jp X-Newsreader: mnews [version 1.22PL7] 2003-09/29(Mon) Xref: ccsf.homeunix.org fj.comp.lang.lisp:81 久野です。 kono@ie.u-ryukyu.ac.jpさん: > GC がないとメモリが足りない例っていうのは、unbound っていう意味 > なわけなんだけど... 違うよ! 所要合計がヒープ量の倍で、でもワーキングセットは収まる とかそういう意味ですが。 > でもさぁ、メモリ使用量がunboundなアプリケーションって実は、 > インタプリタ的なものしかないんじゃないかなぁ。Conservative GC > とかでも対象は awk interpreter だったりしますよね。 それも大嘘だよ…でもとにかくunboundの話じゃないので。 > 生きているセルが定数の場合なんかそうですね。 それで結構ですよ。 > mark and sweep で ちょっと! markするのもsweepするのもヒープサイズに比例するじゃ ないですか。それはO(1)ではなくO(N)です。 それにGCはそういうもんで、私が河野さんに質問していたのは自前で alloc/freeするならO(1)で済むという方の具体例。セルの総量は平均定 数、でもランダムに割り付けと開放が行われる。で、どうやってヒープ サイズに関わらずに定数時間でalloc/freeするかというと。 うーん、その場合は… 久野 P.S. もしかしてセルは全部2のべきサイズでそのサイズ種類数だけリス トを作るってやつかな。無駄が最大50%だけどそれなら定数かも。 前田さんどうしますか。