「コンパイラ・スクリプトエンジン」相談室9

1 名前：デフォルトの名無しさん [2005/12/20(火) 21:43:02 ] プログラミング言語処理系の開発に興味のある人達のスレッドです。 字句解析・構文解析から，データフロー解析，ループ並列化，データ分散，SSA変換， CPS変換，レジスタ割付，命令スケジューリング，ソフトウェアパイプライン， SIMD命令生成，VLIW向けクラスタリング，スクラッチメモリ向け最適化，リンク時最適化， JIT，動的バイナリ変換等の各種最適化，それにVM，GC，低消費電力化などなど。 意味論に関する話題も歓迎です。 過去スレ 1 pc.2ch.net/tech/kako/981/981672957.html 2 pc2.2ch.net/test/read.cgi/tech/1021136715/ 3 pc5.2ch.net/test/read.cgi/tech/1070089173/ 4 pc5.2ch.net/test/read.cgi/tech/1100097050/ 5 pc8.2ch.net/test/read.cgi/tech/1106129164/ 6 pc8.2ch.net/test/read.cgi/tech/1115335709/ 7 pc8.2ch.net/test/read.cgi/tech/1129287390/ 8 pc8.2ch.net/test/read.cgi/tech/1131273918/ 関連リンクは多分 >>2-10 あたり 389 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 12:24:31 ] 継続でスタック保存するのが面倒ってんなら、駆動レコードを全部 ヒープに置くって手もあるが。それだとcall/ccは駆動レコード チェインの頭の掴んでおくだけだよ。 性能を気にしてるわけでもなさそうだし、駆動レコードごとに スタックなんて面倒なことをなぜするのかよくわからない。 390 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 13:54:36 ] Lisp使いはリストを見ると車とかCD-Rとかを使い出す 391 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 13:58:48 ] >>390 どうして車とCDRに発想が結びつくの？ 392 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 14:28:07 ] なにこの変なマジレス 393 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 14:39:34 ] Lisp使いはCD-Rのことを「ｸﾀﾞｰ」と読むんだな 394 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 17:54:48 ] 久多良木信者はLisp使いか否か? 395 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 18:21:20 ] >>391 しらないけどcarとcdrだからじゃない？ 396 名前：(ぱ) mailto:sage [2006/01/27(金) 20:21:31 ] >>383 >ただ、自分の目指しているのは型なし＆プロトタイプ指向ですので、やっぱりちょっと >ポイントが違うようですね。まあ、その違いを見るのも楽しいですが。 crowbarは思いっきり型なし&プロトタイプベースのつもりですが。 >いえ、関数の戻り値ですね。最初は関数の戻り値を次の継続に直接渡そうかと >考えていたのですが、そうすると今の自分のアイディアだと（継続のずっと先にある） >ブロックのローカル変数から実引数を取ってくるのが面倒にだったので、少し悩んでました。 継続をやりたいということ自体初耳なわけですが。 継続は詳しくないので以下見当外れならすみませんですが、 「Rubyみたいな解析木を実行するタイプ」で、解析木を再帰で辿っているとすれば、 「Cのスタックどうするの?」という疑問が出てきます。 「関数の戻り値を次の継続に直接渡そう」ということだから、CPS変換を前提にしている? だとすればそれはもう「Rubyみたいな解析木を実行するタイプ」とは言えないのでは。 >>389 関数内での、計算途中の値を積んでおくスタックのことなんじゃないでしょうか。 397 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 22:07:07 ] １＋１ねぇ、マジレスするけど、 ｙａｃｃ触りはじめてその日でできたよw 398 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 22:27:40 ] コンパイラ構成法の一番最初の項目が電卓だからな。 399 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 22:43:00 ] 1+1が一年以上できないとか言ってるなら、いったんScheme作ればいいのに。 コアな部分に限れば仮想マシンとコンパイラそれぞれ一日で書けるよ。 そしたら作りたい俺様言語で何をどうするかも少しは見えてくるんじゃね? 400 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 22:45:01 ] >>398 うちの大学は字句解析だったよ…。 401 名前：デフォルトの名無しさん mailto:sage [2006/01/27(金) 23:53:04 ] >>398 漏れが最初にやったのは逆ポーランド式の理解だった・・・懐かしいな 402 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 00:42:37 ] きっかけを大別すると、 ・yacc/lexまたはbison/flexで独学 ・大学や専学でコンパイラ/インタプリタの講義 って感じなのかな？ 403 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 00:43:46 ] 授業でちょっとやったけど、あまりに講義資料・内容がヘボかったから独学に切り替えたなぁ。 404 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 00:58:28 ] 情報処理の講師の説明よりも、数学の講師の説明の方が、実は分かりやすかったりするんだよな。ｗ 405 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 01:02:41 ] アルゴリズムの大半は、数学の勉強だからな 406 名前：366 mailto:sage [2006/01/28(土) 04:22:49 ] しまった……中途半端な情報で混乱させていますね。すみません >389 今作っている実装だと、駆動レコードチェイン＋駆動レコード内のスタックといった 感じにしています。>396の指摘通りですね……と言っても詳しく説明していないから わかんないよね。ごめん >396 >crowbarは思いっきり型なし&プロトタイプベースのつもりですが。 失礼しました。まだ読み込んでいないので…… >「Rubyみたいな解析木を実行するタイプ」で、解析木を再帰で辿っているとすれば、 >「Cのスタックどうするの?」という疑問が出てきます。 今のところ、Cの関数処理プロセスに頼らない（再帰を使わない）で、 ・解析木から継続の連鎖を作る ・継続を駆動する という駆動を外部からループで回そうとしています。 >399 そうなんだけど、作りたいのはSchemeじゃないし、Schemeからちょっと離れているし。 ……とはいっても、練習に作ってみるのもいい勉強かな…… >388 はあ。 407 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 04:27:43 ] 1年で1+1が作れない、最低限の理解力すら無い人間が406を書いたと思うと その恐ろしい知ったかぶりに愕然とする 408 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 04:45:28 ] しばらく放っとけないのか? 409 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 06:12:16 ] 俺は407の方の噛みつき具合いの方が愕然とする。 410 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 08:15:29 ] >>409 そう？　このスレの伝統だと思ってた。 411 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 10:56:44 ] 1+1 って、意外と難しいよ。特に数値オブジェクトを + メソッドで加算する場合……とか。 経験ない人が独学でやるには、１年はちょっとキツ過ぎじゃないか？　とか擁護してみる。 412 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 11:08:31 ] まあそういうのは人による部分が大きいよ。 CSのバックグラウンドあってOOにドップリつかった人がやり始めれば理解するのに１日かからないだろうし、逆にこれからプログラミングを始めますって人には１年じゃ無理だろうし。 極端に言えばね。 一口に何日で理解したとか何年かかっても理解できないとかから能力を量ってしまうのはナンセンスだとは思う。 413 名前：デフォルトの名無しさん [2006/01/28(土) 11:18:12 ] 10秒デデキマツタ! if(strcmp(str,"1+1")) printf("2\n"); 414 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 11:38:52 ] >>413 情報サンクスです。考え方のところとか色々と参考になります。 ただ、自分の目指しているのは型なし＆プロトタイプ指向ですので、やっぱりちょっと ポイントが違うようですね。まあ、その違いを見るのも楽しいですが。 415 名前：デフォルトの名無しさん mailto:389 [2006/01/28(土) 12:32:42 ] >>406 > 今のところ、Cの関数処理プロセスに頼らない（再帰を使わない）で、 > ・解析木から継続の連鎖を作る それをCPS変換というんじゃ… でも素直にCPS変換したらスタックなんて出てこないと思うんだけど (「計算途中の値」も全て継続への引数になる)。 それとも複数の引数を渡す際に、既に計算した引数の値を一時保存 しておくエリアってことかな。それを「スタック」と呼ぶのはどうかと 思うが (FILOである必要がないから)。 スタックは、普通の関数呼び出し→リターンに特化した一種の最適化 なんだよ。>>406 が何か特別な最適化のアイディアを試したいなら 別だが、原理を理解するために書いているなら、まず基本的な CPS変換→実行系を動かしてみることをお薦めする。判断に迷うところは とりあえず簡単に実装できるほうで書いてみる。書いてみないとわからない ことってたくさんあるからね。とにかく動かしてから、別のアイディアを 試してみればいい。 416 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 12:58:32 ] >411 そうだよね……自分の場合は駆動に引っ掛かっています。オブジェクトとメソッドを 等価に扱おうとして、『どうやって駆動すりゃいいの？』というところで散々悩んでいます。 あとは名前解決とか変数呼び出しとか…… >412 OOにはけっこうドップリ漬かっているんですけどね。 ここまで彷っているのは『当たり前と思っていた駆動とか関数呼び出しが、いざ やってみると全然当たり前じゃなかった』というのが大きいですかね。 >407, 413, 414 へえ？ 417 名前：デフォルトの名無しさん mailto:sage 366 [2006/01/28(土) 13:16:19 ] >415 >それをCPS変換というんじゃ… ……そうだった。 > でも素直にCPS変換したらスタックなんて出てこないと思うんだけど 最初は素直にCPS変換していたんですけど、レキシカルスコープやろうとしたときに （オレ言語のアイディアが邪魔して）うまくアクセスリンクが処理できなかったので、 スタック……というか単なるリストも併用する形を検討しています。 > まず基本的なCPS変換→実行系を動かしてみることをお薦めする やっぱりそっちの方が近道かな……もうちょっと悩んでみます。 418 名前：366 mailto:sage [2006/01/28(土) 13:38:37 ] >>415 情報サンクスです。CPS変換のところとか色々と参考になります。 ただ、自分の目指しているのはCの関数処理プロセスに頼らない（再帰を使わない）ですので、やっぱりちょっと ポイントが違うようですね。まあ、その違いを見るのも楽しいですが。 419 名前：デフォルトの名無しさん mailto:sage 366 [2006/01/28(土) 13:41:57 ] ありゃ、騙りも出て来たか……これだからIDの無い板は駄目だよな。 そろそろ名無しに戻るか。 >418 ふうん？ 420 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 13:42:19 ] >>419 ふうん？ 421 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 13:48:08 ] 彼は型無し＆プロトタイプ指向の言語に対して >ただ、自分の目指しているのは型なし＆プロトタイプ指向ですので、やっぱりちょっと >ポイントが違うようですね。まあ、その違いを見るのも楽しいですが。 とか言ったのが一番面白かった。最高にバカ丸出しで。 何か言われたら、はあ？とかへえ？とかふうん？とか、 何か言い返さないと気がすまないってのもポイント高し。 422 名前：デフォルトの名無しさん mailto:sage 366 [2006/01/28(土) 13:50:38 ] >>421 で？ 423 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 13:58:54 ] >>422 10ポイントアップ 424 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 17:51:31 ] プライドだけ高そうだね。技術は（ry 425 名前：デフォルトの名無しさん [2006/01/28(土) 17:55:29 ] ここの住人はプライド高いからナァ ただし、技術は（ry 426 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 18:08:16 ] お前の事か? 427 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 18:52:11 ] プライドが高くなるのは仕方が無いのでは？ ＰＧの四大欲求の一つである、言語の作成をやってるわけだし ＯＳと言語とファイルシステムとＡＩで良かったんだっけ？ 428 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 19:03:38 ] OS と言語と AI は分かるけど、ファイルシステムってのは何で? 4 番目に来るのは、Emacs とか Smalltalk みたいな「環境」じゃないかな。 429 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 23:43:42 ] OSと言語は分かるけど、AIってのは何で？ アフォ？ 430 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 23:48:46 ] ちょｗｗｗ「四大欲求」てｗｗｗ 431 名前：デフォルトの名無しさん mailto:sage [2006/01/28(土) 23:58:48 ] ファイルシステムってOSの一部じゃないの？ 432 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 00:06:41 ] DOS 433 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 00:50:20 ] どっちかってーと、OS・言語・マイクロコード(CPUの)・BIOS(とかEFI) とかの方が 434 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 01:50:22 ] それはただLow Levelな方をかき集めただけじゃん 435 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 01:55:09 ] ＯＳ、言語、データーベース、ゲームじゃね？ｗ 436 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 01:58:33 ] AIは、作れなさそうだから実際に作ろうとまでは思わないが、 願望を持つ奴は多いと思う。 ゲーム、言語、OS、AIだろう。 437 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 06:09:51 ] この人、数学者としてはいまいちなのかもしれないけど、 計算機科学の実情についてはよく分かってるね。 www.ritsumei.ac.jp/se/~takayama/MathEssays/essays.html >>428 どうでもいい話だけど、現代においてはOSこそ「環境」ではないのかな。 438 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 06:23:47 ] >>437 この人は自分が高いレベルにいすぎて、考え方の基準が高すぎるね。 確かに数学者を目指すレベルからすれば、計算機科学はおちこぼれが 流れる分野なのかもしれないが、一般の高校生から見れば やっぱり、数学が必要な学科だよ。 単位とるにも数学的なものの考え方が必要な科目ばかりだしね。 一般の高校生の99％は大学でどちらかと言えば数学嫌い になるだろうし。 一般の高校生のレベルと数学者のレベルを混同してるように見える。 439 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 06:30:44 ] そりゃ、京都大学理学部出身から、立命館大学情報工学科みりゃ レベル低くも見えるだろ。 それでもそこにいる学生は相対的に数学が得意で好きだった学生 なんだということが理解できないんだろうな。 440 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 09:23:25 ] 理学と工学は似て非なるものだしな。 441 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 15:33:57 ] 工学で一度数学の必要性を身に沁みるとまじめに勉強する気にもなるもんだが。 一度数学の講義を受けないとそもそも数学の必要性に気付けない罠。 442 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 15:41:09 ] >>436 ああなるほど、ようやく分かった 人工無能の事ではなく、ホントの人格の事だったのか 人間の場合は四つの判断力を持ってるからな。 直感と理性の再現だけならどうにかなるかもしれないが、 感情と欲求の再現となると、なかなか難しいだろな 443 名前：デフォルトの名無しさん [2006/01/29(日) 16:30:38 ] ＰＧの３第欲求 (1)ＯＳ (2)言語 (3)ハーレム この辺りが本当の所だろう。 444 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 16:34:41 ] で、エロゲで代用するわけか 445 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 19:55:35 ] プログラマをＰＧと略す奴にろくな奴がいない 446 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 20:06:05 ] >>443 OSも言語も興味ないやつはいくらでもいそうだけどな。 447 名前：デフォルトの名無しさん [2006/01/29(日) 20:15:58 ] （１）金 （２）酒 （３）ハーレム 448 名前：初心者 [2006/01/29(日) 21:13:56 ] 質問です。 Yaccとかで論理式の短絡評価を行う常套手段はどのようなものでしょうか？ 例えば、if(a==b||c==d) でa==bが確定するとc==dの評価はスキップ可能ですが、 Yaccとかだと、先にa==bとc==dが認識されてしまうと思うのです。 449 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 21:53:31 ] >>448 yaccが生成するのは構文解析器。 意味解析は通常は構文解析で構文木を作った後のステップであって、yaccはやってくれません。 [文字列]→字句解析→[トークン列]→構文解析→[構文木]→意味解析→[一時コード]→最適化→[ましなコード]→コード生成→[出力コード] というように道のりは長い。 yaccがやってくれるのは構文解析だけ（でも構文解析は最適化の次に面倒くさい部分なので大助かり）。 450 名前：デフォルトの名無しさん mailto:sage [2006/01/29(日) 23:39:37 ] >>447 それだ 451 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 00:42:32 ] まあ、たいていの入門書ではyaccの最初のサンプルは電卓で、 そのプログラムではアクションの中で計算もやっちゃってることが多いから >>448 のように思ってしまうのも無理はないのかも。 制御構造を持つちゃんとしたプログラミング言語を作ろうと思ったら、 yaccのアクションでは解析木を作るだけにしておいて、評価は後で行います。 452 名前：448(初心者) [2006/01/31(火) 02:22:55 ] >>449,451 そうでしたか。奥が深いですね。 一瞬、言語の仕組みが分かったような錯覚をしましたが、 本格的なものと電卓的なものとでは、ずいぶんとギャップがあるということが わかりました。 ありがとうございました。 453 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 02:33:12 ] C# コード出力するコンパイラコンパイラって、もしかして未だ無い？ 454 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 02:36:00 ] >>452 その錯覚はあながち間違いじゃないよ。 449で道のりは長いとか書いちゃったけど、実際には構文木まで作れれば終わったようなもんだし。 あとはその周辺の理論的な考察とか最適化の手法は好きなように学んだらいいだけ。 455 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 07:15:12 ] >>453 多分ある。というかC#でコンパイラ作るみたいな本がなかったっけか。 456 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 12:20:28 ] >>453 たしかANTLRが対応してたような気が 457 名前：448（初心者） [2006/01/31(火) 23:15:15 ] >>454 どうもです。すこしづつ勉強して行きたいと思います。 （老後の趣味です。ハハハ） ところで、Yaccってコンパイラコンパイラ等と呼ばれたりもしますが、 結構誇張された言い方とも受け取ったのですが、言語専門家の方は どのように感じますか？ （技術的な話でなくてすいません。） 458 名前：デフォルトの名無しさん mailto:sage [2006/01/31(火) 23:30:38 ] そんなことを聞いてどうする 459 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 01:12:13 ] コンパイラコンパイラは言い過ぎ パーサジェネレータの方がしっくり来る 460 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 02:09:03 ] なんで２ｃｈの回答者って偉そうなのばっかりなんですか？ 461 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 02:16:09 ] Copying でも Generational でも、オブジェクトを移動させる GC で、 移動不可なデータ（ロックとか）ってどう扱ってるのでしょうか。 何かおいしい資料（論文とか）ありましたら教えて下さい。 462 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 06:49:40 ] 移動不可なデータのみを別に扱っておけば良いのでは？ 例えば、移動不可データ専用の予備領域を取っておくとか 463 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 10:08:04 ] >>460 質問者にとっては初めての質問でも、答える方は３度目、４度目というのが当たり前。 日常では温厚な人間でも切れ気味になる。顔が見えりゃいいんだけどね。 おれは一度目にした質問にはレスしないことにしている。 464 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 11:48:51 ] members.at.infoseek.co.jp/zzyyb/gc/incremental-collector.html のインクリメンタルガベコレの説明ですが、 GCが処理しているカレントオブジェクトをプログラムが変更しちゃう場合が 言及されていないのですがまさにその場合が問題である気がします。 カレントオブジェクトが保持する別オブジェクトへの参照のうち、既に処理 した参照が書き換えられるとおかしくなると思うんですが。 465 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 20:10:10 ] >>462 どうもありがとう。後で思いついたんですが、世代別なら一番古い世代に置くというのも手ですね。 466 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 21:42:14 ] >>460 ﾋﾝﾄ：ﾙｻﾝﾁﾏﾝ 467 名前：デフォルトの名無しさん [2006/02/01(水) 22:19:13 ] >>463 ハツモノでもあんたのレスはいらんよw 468 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 23:38:35 ] >>461 俺もちゃんと読んでないけどひとまず貼っとく。 www.nminoru.jp/~nminoru/java/cms/concurrent_mark_sweep.html#45 469 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 00:59:19 ] つ www.shos.info/develop/oo/dscsnptn.html#chapter4 >464 GCが処理しているカレントオブジェクト 　灰色 カレントオブジェクトが保持する別オブジェクトへの参照のうち、既に処理した参照 　灰色 -> 黒 または 　灰色 -> 灰色 灰色 -> 灰色については言及されていないけど、どちらの種類のリンクともうまく処理されます。 470 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 01:46:04 ] 灰色→白は？ カレントオブジェクトに参照A,B,Cがあってこの順で処理するとして、 Aをキューに追加して灰色にした後、Bを処理しようとしているときに 別プログラムがAを白への参照に書き換えてしまったら？ 471 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 23:59:03 ] >470 ごめん、ちょっと勘違いしていたみたい。 ・カレントオブジェクトの処理（参照先の灰色化 & 参照元の黒化）はアトミックに処理する ・カレントオブジェクトが参照された場合、処理を中断してキューの最後に持ってくる ・カレントオブジェクトは黒と同様に処理する あたりはどう？ 472 名前：デフォルトの名無しさん mailto:sage [2006/02/03(金) 00:49:26 ] >>471 最後でしょうか。つまりこの条件においては黒→白取り付けと同様に考える (のでその後に書いてある各手法のようなバリアを張る)と。 前二者はオーバーヘッドが重すぎますよね。 このページ、過渡状態を無視せずにもうちょっと厳密に書いてくれていれば よかったんですけどねえ。 473 名前：デフォルトの名無しさん mailto:sage [2006/02/04(土) 01:50:29 ] まずカレントオブジェクトを黒にしてから参照先を灰色にすれば、カレントオブジェクトを 特別扱いしなくて済むかな？ 474 名前：デフォルトの名無しさん mailto:sage [2006/02/04(土) 02:13:51 ] ちょっと考えたら分かることだろ。 475 名前：デフォルトの名無しさん mailto:sage [2006/02/04(土) 02:48:08 ] >>473 処理中のカレントオブジェクトが 「それが参照している先は必ず灰色か黒」という黒の定義に反することになるのが 気持ち悪い。 476 名前：デフォルトの名無しさん mailto:sage [2006/02/04(土) 10:51:06 ] >>472 そのページはマルチスレッドは考えてないでしょ。 シングルスレッドなら普通 >>471 の 1 にするかと。 477 名前：デフォルトの名無しさん mailto:sage [2006/02/04(土) 13:02:40 ] >>475 アホかお前 478 名前：デフォルトの名無しさん mailto:sage 情報の無い発言には付き合いません [2006/02/04(土) 17:24:37 ] >475 黒の定義を変えるヨロシ 「GCから『それが参照している先は灰色か黒しか存在しない』と認識されるオブジェクト」 かな？ 479 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 00:59:07 ] スタックアロケーションには定数時間が必要なのに対し、 生きているオブジェクトの数だけに比例する時間がかかるGCは メモリを大きく取ることでいくらでも1セルあたりのGCコストを減らせますよね。 だからGCはスタックアロケーションよりも速いっていうのは間違ってますか? 480 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 01:39:53 ] 全体的にどういう計算、それ? 481 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 10:54:53 ] >>480 例えばコピーGCでメモリのサイズをM、GCで生き残ったオブジェクトのサイズをA とすると、GCにかかる時間は定数Cを使ってCAになります。 回収されたオブジェクトのサイズはM-Aなので、これで割るとCA/M-Aになります。 スタックのポップだと一般にサイズ当たりにかかる時間は定数です。 コピーGCではMを大きくすることで、いくらでもコストが減るので "Garbage Collection Can Be Faster Than Stack Allocation" Andrew W. Appel ということらしいです。 482 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 12:22:38 ] よくわかんないけど その理論だとスタックの最大サイズM（仮想メモリ使えば∞と思ってよい） に対して同じ式が出てくるんじゃないか？ スタックのポップのコストがサイズ当たりってことは、 ポップのコストはサイズに比例って意味だよね？ 483 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 12:44:12 ] >>482 スタックのポップは引き算すればいいだけなので、ほんとは比例しないんですが 使い終わる度にポップするのでサイズに比例するってことです。 スタックのポップのコストにスタックの最大サイズは関係ありません。 484 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 13:01:35 ] >479 それって、前提条件が １スタック＝１オブジェクト になっていない？ ただ単に「GCによるオーバーヘッド > まとめてメモリ回収する時間節約」つうてる だけのような気がする 485 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 13:28:06 ] >>484 すいませんがよく意味が分からないです... VMのスタックをポップせずに一杯になったときにGCを起動した方が 性能がいいんじゃないかって話です。 環境をヒープにコピーしたり末尾再帰を最適化したりしなくてすみます。 ただコンパクションしないと断片化するのでGCは結構重そうです。 >>482 のようにメモリが無限にあるのなら GC自体必要ないのでコストは0です。 で、現実問題としてどんなもんなのかなあと。Chickenで実装されているらしいのですが... 486 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 13:35:44 ] 元論文をつまみ読みして想像するに ・Mはメモリのサイズというよりは、今までアロケートしたセルのサイズ ・「スタックアロケーション」といっているのはヒープに確保したセルを明示的に開放する話。スタックは関係ない。 ・「スタック〜」では開放するセルの個数に比例したコストがかかるが、 　コピーGCでは生き残ったセルの個数に比例したコストがかかる。 ・コピーGCでは開放するセルあたりのコストはCA/M-A なので、 　開放するセルあたり１インストラクションより小さくなることすらある。 487 名前：デフォルトの名無しさん mailto:sage [2006/02/07(火) 13:57:28 ] >>486 > ・Mはメモリのサイズというよりは、今までアロケートしたセルのサイズ MはコピーGCで使われるメモリ領域です。つまり 2Mのメモリが必要です。 > ・「スタックアロケーション」といっているのはヒープに確保したセルを明示的に開放する話。スタックは関係ない。 どちらにしても explicit freeingはセルの個数(開放する回数)に比例したコストがかかります。 この論文でも特にヒープかスタックか特定していないような気がします 5章でもスタックとヒープを比較しているので、どちらかといえばスタックかなあと 間違ってたらすいません。 >・「スタック〜」では開放するセルの個数に比例したコストがかかるが、 >　コピーGCでは生き残ったセルの個数に比例したコストがかかる。 >・コピーGCでは開放するセルあたりのコストはCA/M-A なので、 >　開放するセルあたり１インストラクションより小さくなることすらある。 その通りです。 他の論文にも StackGCの性能がよいと書いてあったのですが Chicken くらいしか実装例を知らないのでどうなのかと思ったんです。 飯喰ってきます。 488 名前：484 mailto:sage [2006/02/07(火) 14:49:37 ] ごめん。 意図しているのは >486 の通りね。 GCによるオーバーヘッド => GCでの生き残ったセルの個数に比例したコスト まとめてメモリ回収する時間節約 => スタックでの開放するセルあたりのコスト - GCでの生き残ったセルの個数に比例したコスト といった感じかな？ 489 名前：デフォルトの名無しさん mailto:sage [2006/02/08(水) 14:42:58 ] >>481 >これで割るとCA/M-Aになります。 うんうん。なるほど・・・ ところで、その割った「値」っていうのは、 一体何を意味している数なのかな？

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef