struct timeval
KOBAYASHI Kaori
現在時刻をマイクロ秒まで表示するサンプルプログラムを以下のように
作成しました．
-------
#include <stdio.h>
#include <time.h>
int
main()
{
struct timeval tv;
struct tm *tmptr;
gettimeofday(&tv, NULL);
tmptr = localtime(&tv.tv_sec);
printf("%04d/%02d/%02d %02d:%02d:%02d:%06d\n",
tmptr->tm_year + 1900, tmptr->tm_mon + 1,
tmptr->tm_mday, tmptr->tm_hour,
tmptr->tm_min, tmptr->tm_sec,
tv.tv_usec);
return 0;
}
-------
solaris 8 x86 の gcc 2.95.3 ではコンパイルできて，考えた通りの動
作をするのですが，red hat linux の gcc 3.2.2 では
now_in_usec.c: 関数 `main' 内:
now_in_usec.c:10: `tv' の領域サイズがわかりません
というエラーメッセージが出て，コンパイルできませんでした．
#include <time.h> を #include <sys/time.h>
に置き換えると
now_in_usec.c: 関数 `main' 内:
now_in_usec.c:14: 警告: 代入により、キャストなしで整数からポインタを作りました
now_in_usec.c:17: 不完全型のポインタへの間接参照
......
というエラーメッセージが出て，コンパイルできませんでした．
良くわからなくなって，
#include <time.h>
#include <sys/time.h>
と２行とも書くと，コンパイルは正常に終了し，期待の動作をしました．
でも，２つとも include されているプログラム例をあまりみないので，
この解決方法で正しいのか，今一つ納得できません．
google で sys/time.h と time.h の違いに関してサーチしてみました
が，良くわかりません．gcc のバージョンによる違いなのか，OS によ
る違いなのか，原因がわからないので，情報へのポインタがあれば教え
てください．
ku...@gssm.otsuka.tsukuba.ac.jp
> #include <time.h>
> #include <sys/time.h>
> と２行とも書くと，コンパイルは正常に終了し，期待の動作をしました．
> でも，２つとも include されているプログラム例をあまりみないので，
> この解決方法で正しいのか，今一つ納得できません．
Solaris 9でですが、「man gettimeofday」するとsys/time.hを入れ
ろと書いてありますし、「man localtime」するとtime.hを入れろと書
いてありますんで、両方入れるので正しいんじゃないですか。前者は
システムコール関係、後者は変換等のライブラリ関係、ですよね。
FreeBSD 5.2.1でも同様でした。 久野
Takashi SHIRAI
In article <0408231930...@sma.gssm.otsuka.tsukuba.ac.jp>,
<ku...@gssm.otsuka.tsukuba.ac.jp> wrote:
>久野です。
久野先生には釈迦に説法かも知れませんが。
> Solaris 9でですが、「man gettimeofday」するとsys/time.hを入れ
>ろと書いてありますし、「man localtime」するとtime.hを入れろと書
>いてありますんで、両方入れるので正しいんじゃないですか。前者は
>システムコール関係、後者は変換等のライブラリ関係、ですよね。
問題はそう簡単ではないんです。<sys/time.h> の中で <time.h>
を include している実装では、二つとも include することにより
<time.h> が二重に include されます。
更にそういう実装では、<time.h> が二重 include に堪える仕様
になっていないことが多く、結果として二重定義等の error が発
生して compile に失敗してしまうんです。
なので portability を考えるならば、環境に応じて <sys/time.h>
単品 include か両方とも include かを切替えられるようにしてお
く必要があります。
例えば GNU autoconf ではこの判定を行なうマクロが用意されて
いて「AC_HEADER_TIME」によって「TIME_WITH_SYS_TIME」という識
別子が適宜定義されますね。
経験則としては、両方必要なのは SystemV に多いですね。POSIX
以降の SVR4 や BSD 系では <sys/time.h> だけで十分な実装が多
いようです。
どういう訳か SystemV 系はこの手の header の依存関係に弱い
ですねー。HP-UX なんかに至っては、man page の sample をその
まま compile しても warning の山だし。
>> #include <time.h>
>> #include <sys/time.h>
>> と２行とも書くと，コンパイルは正常に終了し，期待の動作をしました．
>> でも，２つとも include されているプログラム例をあまりみないので，
>> この解決方法で正しいのか，今一つ納得できません．
TIME_WITH_SYS_TIME で検索すると、両方とも include する実装
は全然珍しくないことが判ると思います。勿論、この識別子を使っ
ているということは、「両方」以外に「片方」の実装も用意されて
いる筈ですが。
ざっと探してみたところ、有名どころでは Samba とか bash と
か diff とか、そんな辺りが使ってるみたいです。探せば他にも見
つかると思いますよ。
--
しらい たかし
ku...@gssm.otsuka.tsukuba.ac.jp
> 問題はそう簡単ではないんです。<sys/time.h> の中で <time.h>
> を include している実装では、二つとも include することにより
> <time.h> が二重に include されます。
> 更にそういう実装では、<time.h> が二重 include に堪える仕様
> になっていないことが多く、結果として二重定義等の error が発
> 生して compile に失敗してしまうんです。
そ、そうなの。二重include対策はお約束と思ってた。 久野
Shinji KONO
In article <0408232143...@sma.gssm.otsuka.tsukuba.ac.jp>, ku...@gssm.otsuka.tsukuba.ac.jp writes
> そ、そうなの。二重include対策はお約束と思ってた。 久野
僕は「#ifndef _HOGE_H_」は、やるなって教えることが多い。
でも、
class_a.h
#include <class_b.h>
struct class_a { struct class_b *b; }
class_b.h
#include <class_a.h>
struct class_b { struct class_a *a; }
みたいなことをやる学生がいるんで、結構、困るんですよね。
(これを通すためには、#ifndef だけではだめで少し工夫がいるんだけど)
それでも C を使わなきゃいけないのって、なんか不幸。じゃ、
C++ の方が良いかっていうと、どうしても、C++ の(一見便利で
実は邪悪な...) 機能を使う人がでて来ちゃって。
> > 更にそういう実装では、<time.h> が二重 include に堪える仕様
> > になっていないことが多く、結果として二重定義等の error が発
> > 生して compile に失敗してしまうんです。
そのあたりは、最初に教えるときは言わない方が良いと思う。
言いたくなるのはわかるんだけど。僕も最初はそうだったし。
---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科
吉見 隆
Shinji KONOさんの<3990299...@insigna.ie.u-ryukyu.ac.jp>から
>河野真治 @ 琉球大学情報工学です。
>
>In article <0408232143...@sma.gssm.otsuka.tsukuba.ac.jp>,
>ku...@gssm.otsuka.tsukuba.ac.jp writes
>> そ、そうなの。二重include対策はお約束と思ってた。 久野
>
>僕は「#ifndef _HOGE_H_」は、やるなって教えることが多い。
やるなという心は何ですか？
学生が自分で使うプログラム用のヘッダを書くときの話でしょうか？
ifndef による対策がどういう副作用を持っているのか知りませんので教えて
ください。
システムのヘッダーでも別のヘッダーをincludeしているのは珍しくないんで
すが、もし二重include対策をしていなければユーザーはincludeする前にすべ
てのヘッダーのincludeファイルを遡ってチェックしなければならなくなりま
す。
例えば，man で独立した関数 func_a() と func_b()の記述に
func_a() #include <h_a.h>
func_b() #include <h_b.h>
というヘッダを使うとかかれていた場合，h_a.h が絶対 h_b.h をinclude し
ていないとか、その逆とかの判定をソースを書くユーザーに義務付けるのは酷
ではないでしょうか。
#プリプロセッサーが自動チェックしてくれればいいんですが。
--
吉見 mailto:tak-y...@NOSWENrio.odn.ne.jp
Remove NOSWEN
Shinji KONO
In article <cge534$7ac$1...@caraway.media.kyoto-u.ac.jp>, 吉見 隆<tak-y...@NOSWENrio.odn.ne.jp> writes
> >僕は「#ifndef _HOGE_H_」は、やるなって教えることが多い。
> やるなという心は何ですか？
> 学生が自分で使うプログラム用のヘッダを書くときの話でしょうか？
自分でプログラムを書く時に、不必要に複雑な依存関係を入れるな、
っていうことなんだけど。まず、そういうものなしに動く構造で書
けるかどうかを試すべきだと思う。
相互依存は、再帰includeでも解決できないから、そのあたりで
はまる学生もいるし。(多くはないが)
> システムのヘッダーでも別のヘッダーをincludeしているのは珍しくないんで
> すが、もし二重include対策をしていなければユーザーはincludeする前にすべ
> てのヘッダーのincludeファイルを遡ってチェックしなければならなくなりま
> す。
本来、二重includeチェックって必要ないはずですよね。ちゃんと、木構造
になっていれば良いはず。
hoge_func() を使う => hoge.h を include
ってなっていて、それだけであるべきだと思う。
hoge_func_a() を使う => hoge.h を include
hoge_func_b() を使う => hoge.h を include
で、hoge.h を二回includeしても動くべきだっていう話もあるし、
僕もそうであるべきだと思うけど、それでも、二重includeチェックなし
で動くべきだと思います。
Linux kernel 2.6 は、そのあたり、もうあきらめていて、
すべてのファイルがinclude するのは、config.h だけ
で、config.hには、すべてのinclude file がflatに入っている
っていう構造になっている...
> #プリプロセッサーが自動チェックしてくれればいいんですが。
それでもいいんだけど...
*.h を手で書かせるな
って気もかなりするんだよな。
ku...@gssm.otsuka.tsukuba.ac.jp
ko...@ie.u-ryukyu.ac.jpさん:
> *.h を手で書かせるな
>
> って気もかなりするんだよな。
そこでJavaですよ(笑) 久野
Takao Ono
<0408241221...@sma.gssm.otsuka.tsukuba.ac.jp>の記事において
ku...@gssm.otsuka.tsukuba.ac.jpさんは書きました。
kuno> > *.h を手で書かせるな
kuno> > って気もかなりするんだよな。
kuno> そこでJavaですよ(笑) 久野
*.c に目印付けておいて, sed なりなんなりで *.h を生成するという方
針もあるかと.
# zsh がそんな感じ.
--
名古屋大学大学院 情報科学研究科 計算機数理科学専攻
小野 孝男 (ta...@hirata.nuee.nagoya-u.ac.jp)
Shinji KONO
In article <0408241221...@sma.gssm.otsuka.tsukuba.ac.jp>, ku...@gssm.otsuka.tsukuba.ac.jp writes
Java は、そのあたりは、悪くないんだけど、メモリ管理がなぁ...
Finalize / Delete を、こっちで管理させてくれれば、もっと使う
んだけど。あれじゃぁ、
作りまくって GC しまくりプログラムやれ
って言っているようなものだものね。資源管理のできないプログラム
言語は実用にならないです。
まぁ、スクリプト言語として使うならそれでもいいのかも知れないけど。
それなら、Perl でいいし。
KOBAYASHI Kaori
ku...@gssm.otsuka.tsukuba.ac.jp writes
in <0408231930...@sma.gssm.otsuka.tsukuba.ac.jp>:
でも，Solaris 8 x86 では time.h を入れただけで warning もなく
期待の動作をしました．両方入れるのが正解なのかもしれませんが，
そうすると「time.h のみで動く」のが理解できなくなります．
ku...@gssm.otsuka.tsukuba.ac.jp
> Java は、そのあたりは、悪くないんだけど、メモリ管理がなぁ...
> Finalize / Delete を、こっちで管理させてくれれば、もっと使う
> んだけど。あれじゃぁ、
言語屋としては「普通は」
> 作りまくって GC しまくりプログラムやれ
こっちが正しいと考えてます。 久野
> って言っているようなものだものね。資源管理のできないプログラム
> 言語は実用にならないです。
P.S. それは河野さんが資源管理をコーディングしたいからでしょ。そ
ういう用途だとあの実行系のままではつらいね。
ku...@gssm.otsuka.tsukuba.ac.jp
> でも，Solaris 8 x86 では time.h を入れただけで warning もなく
> 期待の動作をしました．両方入れるのが正解なのかもしれませんが，
> そうすると「time.h のみで動く」のが理解できなくなります．
time.hの中でsys/time.hをincludeしている場合は当然そうなります
よね。
そういうのは普通にあるんじゃないの。 久野
Yasushi Shinjo
In article <3990299...@insigna.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> class_a.h
> #include <class_b.h>
> struct class_a { struct class_b *b; }
> class_b.h
> #include <class_a.h>
> struct class_b { struct class_a *a; }
> みたいなことをやる学生がいるんで、結構、困るんですよね。
> (これを通すためには、#ifndef だけではだめで少し工夫がいるんだけど)
struct class_a の中で struct class_b を使うとしても、ポイン
タだったら、struct class_b の定義は不要です。
% cat struct-mutual.c
struct class_a { struct class_b *b; };
main()
{
struct class_a a1;
printf("%d\n", sizeof(a1) );
}
% gcc struct-mutual.c -o struct-mutual
% ./struct-mutual
4
%
ポインタではなくて、構造体本体の参照なら、必要になります。
データ構造で構造体の相互参照が出てくるのは、表現したい対象が
そうなっているなら、そうするんじゃないですか。自然だし。
工夫というと、
struct class_a;
のように書かないといけない局面があった気がしたんだけど、すぐ
に思い出せません。
＼＼ 新城 靖 （しんじょう やすし） ＼＼
＼＼ 筑波大学 電子・情報 ＼＼
MAEDA Atusi
> 言語屋としては「普通は」
>
> > 作りまくって GC しまくりプログラムやれ
>
> こっちが正しいと考えてます。 久野
「使い捨ててどんどんGC」の方が速いと思いますね、たいていは。
> ko...@ie.u-ryukyu.ac.jpさん:
> > Java は、そのあたりは、悪くないんだけど、メモリ管理がなぁ...
> > Finalize / Delete を、こっちで管理させてくれれば、もっと使う
> > んだけど。あれじゃぁ、
finalizeは、確かに、あんまり使わない方がよろしいかと思います。
蛇足というかおまけというか癌というかlast resortというか…
あんなのに頼らず、自分で陽に「使えない/閉じた/切れた」状態に変更するの
が良いかと。
前田敦司
Shinji KONO
In article <m3u0usy...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda...@ialab.is.tsukuba.ac.jp> writes
> 「使い捨ててどんどんGC」の方が速いと思いますね、たいていは。
参照カウント方式では、単純なリストアクセスでも倍の手間なので、
全部、配列でプログラムするとかでない限りCより倍遅いです。な
ので、Java だと配列でプログラムしているのが普通でしょ? リン
クリスト抜きでプログラムするのって、かなり辛い。
で、参照カウント方式でないと、incremental GCは、ほぼ不可能で
す。ってわけなので、リアルタイム・プログラムでは、Java 使い
ようがないです。で、いまや、リアルタイムでないプログラムなん
て存在するのかなぁ。
資源管理が出来ない言語って、僕は役にたたないと思う。
> あんなのに頼らず、自分で陽に「使えない/閉じた/切れた」状態に変更するの
> が良いかと。
それをやるってことは、実は、自分でリンクリストを管理するわけ
なんだけど、そいつをいじるたびに参照カウントがいじられるわけ
で... まぁ、それだけが遅い原因ではないんだろうけど...
最近、割りとローレベルなプログラムをJavaでやって、どうしても、
C と同等な速度を出せなくて... とかいう話をソフトウェア科学会
ので話すことになっていたりしますが...
mihi~star
うちは、gcc (GCC) 3.3.3 (Debian 20040401)を使っていますが、
同じ結果になります。
>>>>> KOBAYASHI Kaori <ka...@pu-toyama.ac.jp> さんの wrote:
>>>>> in <ueu0uu1...@pu-toyama.ac.jp> より
>
> solaris 8 x86 の gcc 2.95.3 ではコンパイルできて，考えた通りの動
> 作をするのですが，red hat linux の gcc 3.2.2 では
> now_in_usec.c:10: `tv' の領域サイズがわかりません
> というエラーメッセージが出て，コンパイルできませんでした．
これは、struct timevalが、<time.h>をincludeしただけでは定義
されていない状態になっているということでしょう。
struct timevalは、<bits/time.h>で定義されています。
<time.h>は<bits/time.h>をincludeするようになっています。
しかし、struct timevalを定義する部分は__need_timevalがdefine
されていないと読まれません。<time.h>には__need_timeがdefine
されていないので、<bits/time.h>のstruct timevalを定義する部分が
飛ばされることになります。
> #include <time.h> を #include <sys/time.h>
> に置き換えると
> now_in_usec.c:14: 警告: 代入により、キャストなしで整数からポインタを作りました
これは、localtime()の返り値の型が、<time.h>で定義されている
ためですね。定義がない状態なので、返り値の型が整数ということに
なっているのだと思います。
> now_in_usec.c:17: 不完全型のポインタへの間接参照
これも同様に、struct tmが定義されていないのが原因でしょう。
とはいえ、<sys/time.h>からは<time.h>が読まれています。
<time.h>においては、localtime()とstruct tmが定義されています。
ちょっと見ただけでは、何が原因かわかりませんでしたが、上に書いた
のと同じような理由で、この部分が飛ばされているのでしょう。
> google で sys/time.h と time.h の違いに関してサーチしてみました
> が，良くわかりません．gcc のバージョンによる違いなのか，OS によ
> る違いなのか，原因がわからないので，情報へのポインタがあれば教え
> てください．
コンパイラが使っているヘッダ・ファイルの違いが、異なった結果を
生み出しているのだと思います。
ヘッダ・ファイルは、/usr/include/time.hとか、/usr/include/
sys/time.hなんかにあります。
あと、gccは、-Eというオプションを付けて起動するとプリプロセスが
終った状態のファイルを見せてくれます。
これを見てみると、何が足りないからそうなるのかがわかるでしょう。
それでは。
--
＿∧∧＿/∧＿＿ mihi~star <mi...@childstar.club.ne.jp>
／~(=^-')(-'*)／|＼ あと少し探せば きっと見つかりますよっ♪
|￣∪∪￣￣￣|／ ￣
Shinji KONO
In article <YAS.04Au...@kirk.is.tsukuba.ac.jp>, y...@is.tsukuba.ac.jp (Yasushi Shinjo) writes
> struct class_a の中で struct class_b を使うとしても、ポイン
> タだったら、struct class_b の定義は不要です。
ま、そうなんだけど。
> データ構造で構造体の相互参照が出てくるのは、表現したい対象が
> そうなっているなら、そうするんじゃないですか。自然だし。
自然だったら、#include も自然になって欲しいですよね～
#ifndef HOGE_H が自然だってなら、自然なわけだけどさ。
#import は、そのあたりの面倒を見てくれるはずだけど。
相互参照は、
A ⇔ B
なんだけど、実は、
A → C ← B
ってことが多いんだと思う。で、C は、そういうことを期待している
言語なんでしょう。
いや、そうじゃなくて、#ifndef を使えってこと?
ku...@gssm.otsuka.tsukuba.ac.jp
ko...@ie.u-ryukyu.ac.jpさん:
> で、参照カウント方式でないと、incremental GCは、ほぼ不可能です。
河野さん…言語屋でないとはいえ、それはあんまりでしょ。 久野
Yasushi Shinjo
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> 河野真治 @ 琉球大学情報工学です。
> > データ構造で構造体の相互参照が出てくるのは、表現したい対象が
> > そうなっているなら、そうするんじゃないですか。自然だし。
> 自然だったら、#include も自然になって欲しいですよね～
> #ifndef HOGE_H が自然だってなら、自然なわけだけどさ。
はい。
(defun insert-prototype-h ()
(interactive)
(insert "
/*
dir/name.h
$Header$
Created on: ")
(insert-date)
(insert "
*/
#ifndef _DIR_NAME_H_
#define _DIR_NAME_H_
#endif _DIR_NAME_H_
/* --------------------- dir/name.h --------------------- */
" ))
> #import は、そのあたりの面倒を見てくれるはずだけど。
Ｃ言語なんですか？
> 相互参照は、
> A ⇔ B
> なんだけど、実は、
> A → C ← B
> ってことが多いんだと思う。で、C は、そういうことを期待している
> 言語なんでしょう。
そうでしょうね。もっと言うと、「a.c がコンパイルできれば、Ｏ
Ｋ」なので、モジュールの依存関係はどうでもよくて、
・呼ぶ関数の型宣言が入っている .h を includeする。
・ポインタではない struct xxx が出ている .h を includeする。
ということなのでしょう。それで、 a.h, b.h には、でも、struct
本体は、書かないで隠したくなるんだけどなあ。a.c, b.c の方に
定義して。
Shinji KONO
In article <cgf89o$1r...@utogw.gssm.otsuka.tsukuba.ac.jp>, ku...@gssm.otsuka.tsukuba.ac.jp writes
> ko...@ie.u-ryukyu.ac.jpさん:
> > で、参照カウント方式でないと、incremental GCは、ほぼ不可能です。
> 河野さん…言語屋でないとはいえ、それはあんまりでしょ。 久野
え、そう? どんなの考えているんですか?
Reference counting しない incremental GC って言えば、あれが
あるけど、実際に実装したのはないんじゃないかなぁ。
今年のPOPLには、Reference count の計算量みたいな話が出ていて、
「やっぱり、だめだぁ」みたいな話だったし。僕も、Reference
count はダメだと思っていた方なので「やっぱりね」って感じ
でした。
まぁ、家で散らかす程度だったら mark & sweep とかでもいいし、
帳簿で管理するような物だったら Reference count もいいけど、
工場でJust in time やるようなもので、ゴミとそうでないものを
区別せずに扱うってのは無理なんだよね。
ku...@gssm.otsuka.tsukuba.ac.jp
Garbage Collectionという本があります。素人なんだったらこれを読
みなよ。よくまとまってますよ。
河野さん:
> え、そう? どんなの考えているんですか?
私が考えてるんじゃなくて常識なの。
sequentialのだったらマークスイープをallocationのつど一定量ずつ
やるというのが定番ですね。あと世代コピー方式で新世代の容量を調整
してコピー時間を限定というのはもっと古くからある(でも旧世代まで
GCした場合がなあ)。
並列屋の河野さんだったら当然、マルチCPUで並列GCがあるでしょ?
> 今年のPOPLには、Reference count の計算量みたいな話が出ていて、
> 「やっぱり、だめだぁ」みたいな話だったし。僕も、Reference
> count はダメだと思っていた方なので「やっぱりね」って感じ
> でした。
あのペーパーも面白かったですね。ああいう話も上述の本にけっこう
載ってました。
まあreference countはあんまりね。 久野
KOBAYASHI Kaori
＃ 何度もすみません．
たしかに，man gettimeofday すると，#include <sys/time.h> しろ，
man localtime すると #include <time.h> しろとありました．
どちらかでも欠けていれば，うまくいかないだろうことは納得しています．
solaris 8 x86 & gcc 2.95.3 で，２つのヘッダとも include しても
問題なく動作しました．
ku...@gssm.otsuka.tsukuba.ac.jp writes
in <0408241354...@sma.gssm.otsuka.tsukuba.ac.jp>:
time.h の中で直接 include されている
#include <sys/feature_tests.h>
#include <sys/types.h>
#include <iso/time_iso.h>
#include <sys/time_impl.h>
これらの４つには sys/time.h は直接含まれてはいませんでした．
一応，孫までたどりましたが，やっぱり陽にはありません．
＃ 逆に，陽に書くと「二重定義」の問題が発生して困る？
time.h の先頭に
#ifndef _TIME_H
#define _TIME_H
というのがあったので，_TIME_H が定義済で，_SYS_TIME_H が未定義な
らば sys/time.h を呼ぶようになっているのでしょうか．
MAEDA Atusi
> > > で、参照カウント方式でないと、incremental GCは、ほぼ不可能です。
> > 河野さん…言語屋でないとはいえ、それはあんまりでしょ。 久野
>
> え、そう? どんなの考えているんですか?
>
> Reference counting しない incremental GC って言えば、あれが
> あるけど、実際に実装したのはないんじゃないかなぁ。
> 今年のPOPLには、Reference count の計算量みたいな話が出ていて、
> 「やっぱり、だめだぁ」みたいな話だったし。僕も、Reference
> count はダメだと思っていた方なので「やっぱりね」って感じ
> でした。
"The space cost of lazy reference counting" ですか。
たしかに最近 reference counting に関する話題が少しありましたけど、ポイ
ンタ追跡型のrealtime GCだってありますよ。
たとえば、
David F. Bacon and Perry Cheng and V. T. Rajan: A real-time garbage
collector with low overhead and consistent utilization, Proc. POPL
2003, pp.285-298
Perry Cheng and Guy E. Blelloch: A parallel, real-time garbage collector,
Proc. PLDI 2001, pp.125-136
Taiichi Yuasa, Return Barrier: Incremental Stack Scanning for Snapshot
Real-time Garbage Collection, International Lisp Conference 2002, Oct. 2002
とか。
> まぁ、家で散らかす程度だったら mark & sweep とかでもいいし、
> 帳簿で管理するような物だったら Reference count もいいけど、
> 工場でJust in time やるようなもので、ゴミとそうでないものを
> 区別せずに扱うってのは無理なんだよね。
まあ、たしかにreal-time GCが完全に実用になってるかと言えばそこまで行っ
てないですね。だから Real-time specification for Java ではGCに頼らず
Regionを持ってきたんですよね。GC研究者としては大変くやしいですね。
> で、いまや、リアルタイムでないプログラムなん
> て存在するのかなぁ。
これは大げさでしょ。
少なくともWindowsやUnixで動いてるプログラムにリアルタイムなものなんて
ほぼ皆無なわけだし、Javaで書かれているプログラムもそうでしょ。
コード量の割合にすれば組み込み/リアルタイムのプログラムの方がはるかに
多いかもしれませんけどね。
前田敦司
MAEDA Atusi
> 資源管理が出来ない言語って、僕は役にたたないと思う。
メモリ管理を自動化しただけで、すべての資源が管理できなくなっちゃうんで
すか? 今までだってレジスタ割り付けとかスタックとかは自動でやってました
が。
> > あんなのに頼らず、自分で陽に「使えない/閉じた/切れた」状態に変更するの
> > が良いかと。
>
> それをやるってことは、実は、自分でリンクリストを管理するわけ
> なんだけど、そいつをいじるたびに参照カウントがいじられるわけ
> で... まぁ、それだけが遅い原因ではないんだろうけど...
メモリ管理と他の資源の「破壊/閉じる/切断」は必ずしも同じタイミングじゃ
ない…ってのはmalloc/free論争の時に出てきましたよね。
たとえばウィンドウを閉じるとか、ページキャッシュをフラッシュしてDBファ
イルを閉じるとか、普通はfinalizerでやったりしませんよね。
> 最近、割りとローレベルなプログラムをJavaでやって、どうしても、
> C と同等な速度を出せなくて... とかいう話をソフトウェア科学会
> ので話すことになっていたりしますが...
標準Cで書けることですか?
標準Cで書けない(標準Javaでもできない)ような部分、たとえばGCとかスター
トアップルーチンとかスレッドライブラリとかを書く時、Jikesなんかは、が
んがん言語を拡張しちゃってますね。「このインターフェースを使っておくと
JITコンパイラが特別扱いしてインライン展開する」とかね。 処理系の中でし
か使わないので別にかまわない。まあCだろうとJavaだろうと、そうするしか
ないんだけど。
前田敦司
Shinji KONO
In article <cgfh3a$22...@utogw.gssm.otsuka.tsukuba.ac.jp>,ku...@gssm.otsuka.tsukuba.ac.jp writes
> 私が考えてるんじゃなくて常識なの。
「ほとんどない」は言いすぎだったか。
> sequentialのだったらマークスイープをallocationのつど一定量ずつ
> やるというのが定番ですね。あと世代コピー方式で新世代の容量を調整
> してコピー時間を限定というのはもっと古くからある(でも旧世代まで
> GCした場合がなあ)。
まぁ、いろんな努力はあるんだけど、実装が複雑なのが多いですよね。
In article <m3llg4xy...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda...@ialab.is.tsukuba.ac.jp> writes
> まあ、たしかにreal-time GCが完全に実用になってるかと言えばそこまで行っ
> てないですね。だから Real-time specification for Java ではGCに頼らず
> Regionを持ってきたんですよね。GC研究者としては大変くやしいですね。
Region と Reference count を両立させるのも難しいんだろうなぁ。
> たしかに最近 reference counting に関する話題が少しありましたけど、ポイ
> ンタ追跡型のrealtime GCだってありますよ。
なんか定番の実装みたいのがあるといいんだけど...
> > で、いまや、リアルタイムでないプログラムなん
> > て存在するのかなぁ。
>
> これは大げさでしょ。
>
> 少なくともWindowsやUnixで動いてるプログラムにリアルタイムなものなんて
> ほぼ皆無なわけだし、Javaで書かれているプログラムもそうでしょ。
そんな風に考えるのか。じゃぁ、前田さんは、Word とか Browser
はリアルタイム・プログラムだとは考えてないんですね。そういう
立場ってことなのかな。
僕は、grid computing とかでもリアルタイム・プログラムだと思う。
「あ、ちょっと、待ってね」と言えなくなるようなことは、今は許
されないぐらいの意味で、「いまや、リアルタイムでないプログラ
ムなんて存在するのかなぁ。」って感じ。
Shinji KONO
In article <m3hdqsxx...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda...@ialab.is.tsukuba.ac.jp> writes
>メモリ管理を自動化しただけで、すべての資源が管理できなくなっちゃうんで
>すか? 今までだってレジスタ割り付けとかスタックとかは自動でやってました
>が。
出来なくなるとは言わないけど、難しいですね。レジスタ割り当て
でも、volatie とか欲しくなるじゃない。スタックでも、alloca
とか欲しくなるでしょ?
OS の役割は資源管理なんだけど、言語の機能も、資源管理とみな
すことも出来ると思う。そうでないとすると、言語は入出力だけを
制御するってことになるけど、普通は、時間とか領域とか問題にす
るよね。問題にならない場合の方が少ないと思う。そういう場合が
ないとは言わないけど。
> メモリ管理と他の資源の「破壊/閉じる/切断」は必ずしも同じタイミングじゃ
> ない…ってのはmalloc/free論争の時に出てきましたよね。
....
> たとえばウィンドウを閉じるとか、ページキャッシュをフラッシュしてDBファ
> イルを閉じるとか、普通はfinalizerでやったりしませんよね。
(懐かし～) だから、そのタイミングを判断できない場合は、GC
すべきだってことね。それは、その通りだな。
いや、明示的にウィンドウは閉じてGCにやらせるべきではないって
ことか。その時に、ウィンドウのOS/Window System の資源が解放
されれば良くて、メモリはGCで解放されれば良いってことかぁ。
それはどうかなぁ。
> 標準Cで書けない(標準Javaでもできない)ような部分、たとえばGCとかスター
> トアップルーチンとかスレッドライブラリとかを書く時、Jikesなんかは、が
> んがん言語を拡張しちゃってますね。「このインターフェースを使っておくと
> JITコンパイラが特別扱いしてインライン展開する」とかね。 処理系の中でし
> か使わないので別にかまわない。まあCだろうとJavaだろうと、そうするしか
> ないんだけど。
まぁ、そうしても、もちろんいいんだけど「とりあえず、Java で
頑張る」っていう段階があるはずだと思う。(んだけど、あきらめ
つつあります...)
いや、もう少し頑張れば「リアルタイムだと今のJavaでは、Cの半
分の速度」ってのを乗り越えられるかも知れないんだけど、いまん
ところはだめってな所ですね。
ku...@gssm.otsuka.tsukuba.ac.jp
> > time.hの中でsys/time.hをincludeしている場合は当然そうなります
> > よね。
> >
> > そういうのは普通にあるんじゃないの。 久野
>
> time.h の中で直接 include されている
推測が外れてすみません。追跡して調べるの、大変ですよね。
> というのがあったので，_TIME_H が定義済で，_SYS_TIME_H が未定義な
> らば sys/time.h を呼ぶようになっているのでしょうか．
なるほど、そうかも。 久野
ku...@gssm.otsuka.tsukuba.ac.jp
> そんな風に考えるのか。じゃぁ、前田さんは、Word とか Browser
> はリアルタイム・プログラムだとは考えてないんですね。そういう
> 立場ってことなのかな。
ユーザを待たせて怒らせて済むものはリアルタイムじゃないでしょ。
> 僕は、grid computing とかでもリアルタイム・プログラムだと思う。
ユーザが端末の前で待ってないなら全然リアルタイムじゃないでしょ。
ハードリアルタイム→応答時間の制約厳守で守れないとfail
ソフトリアルタイム→できるかぎりフルスピードで動く(ゲームとか)
これくらいが普通の定義と思う。
河野さんが普通じゃないのは普通なんだけど :-) 久野
> 「あ、ちょっと、待ってね」と言えなくなるようなことは、今は許
> されないぐらいの意味で、「いまや、リアルタイムでないプログラ
> ムなんて存在するのかなぁ。」って感じ。
P.S. 真夜中に動くバックアップジョブは河野さんワールドではリアル
タイムなんですね? :-P
MAEDA Atusi
> > sequentialのだったらマークスイープをallocationのつど一定量ずつ
> > やるというのが定番ですね。あと世代コピー方式で新世代の容量を調整
> > してコピー時間を限定というのはもっと古くからある(でも旧世代まで
> > GCした場合がなあ)。
>
> まぁ、いろんな努力はあるんだけど、実装が複雑なのが多いですよね。
reference countingだって最近の(lazyとかdeferredとか)は結構複雑ですよ。
素朴な実装だと遅すぎますから。(ポインタ変数を1回代入しただけで、メモリ
上のカウンタをアトミックにインクリメント/デクリメントしなきゃならない。)
> Region と Reference count を両立させるのも難しいんだろうなぁ。
Regionは、GCとは別に型システムと組み合わせて使う研究がもともとあったん
だけど、Real-time Javaのやつは中途半端ですね。
HeapのオブジェクトからRegionを指すことはできなくって、しかもそれは実行
時に検査するしかない。
> > > で、いまや、リアルタイムでないプログラムなん
> > > て存在するのかなぁ。
> >
> > これは大げさでしょ。
> >
> > 少なくともWindowsやUnixで動いてるプログラムにリアルタイムなものなんて
> > ほぼ皆無なわけだし、Javaで書かれているプログラムもそうでしょ。
>
> そんな風に考えるのか。じゃぁ、前田さんは、Word とか Browser
> はリアルタイム・プログラムだとは考えてないんですね。そういう
> 立場ってことなのかな。
少なくとも教科書的な定義からすれば全くリアルタイムではないですねえ。
デッドラインが無いから。
で、リアルタイム性がないのはmalloc/free, new/deleteだって(というかsbrk
だってmmapだって)同じですが、今のWordやブラウザは河野さんの定義だとリ
アルタイム・プログラムなんですか?
Wordやブラウザ程度のリアルタイム性で良いなら、GC使っても何も困らない
でしょう? (実際、ふつーのJavaで書いたワープロやブラウザもあるし。)
> 僕は、grid computing とかでもリアルタイム・プログラムだと思う。
>
> 「あ、ちょっと、待ってね」と言えなくなるようなことは、今は許
> されないぐらいの意味で、「いまや、リアルタイムでないプログラ
> ムなんて存在するのかなぁ。」って感じ。
ふーむ。grid computingでGC使ってもやっぱり問題ないように思いますが。
前田敦司
MAEDA Atusi
> いや、明示的にウィンドウは閉じてGCにやらせるべきではないって
> ことか。その時に、ウィンドウのOS/Window System の資源が解放
> されれば良くて、メモリはGCで解放されれば良いってことかぁ。
> それはどうかなぁ。
でも、実際にそうしてません? 参照が残っていてもWindowCloseイベントが来
たらウィンドウは閉じるし、通信が終ったらソケットは閉じるでしょ。
プログラムの外の資源への参照を、メモリ管理だけに任せるのはあんまり良く
ないと思いますねえ。他に手がなければ仕方がないですけど。あるいは保険と
して使うとかね。
# だからlast resort。
> > 標準Cで書けない(標準Javaでもできない)ような部分、たとえばGCとかスター
> > トアップルーチンとかスレッドライブラリとかを書く時、Jikesなんかは、が
> > んがん言語を拡張しちゃってますね。「このインターフェースを使っておくと
> > JITコンパイラが特別扱いしてインライン展開する」とかね。 処理系の中でし
> > か使わないので別にかまわない。まあCだろうとJavaだろうと、そうするしか
> > ないんだけど。
>
> まぁ、そうしても、もちろんいいんだけど「とりあえず、Java で
> 頑張る」っていう段階があるはずだと思う。(んだけど、あきらめ
> つつあります...)
>
> いや、もう少し頑張れば「リアルタイムだと今のJavaでは、Cの半
> 分の速度」ってのを乗り越えられるかも知れないんだけど、いまん
> ところはだめってな所ですね。
具体的な話が分からないと何ともいえないですが、メモリ管理の話だとすると、
メモリ管理やGCの研究者のコンセンサスとしては、
・GCがある言語で、自分でメモリ管理(再利用とか)しようとすると大概かえっ
て遅くなる。
ということになっています。
(cf.)
http://java.sun.com/docs/hotspot/gc1.4.2/faq.html のQ.31
http://www-106.ibm.com/developerworks/library/j-jtp01274.html#3.0
http://citeseer.nj.nec.com/zorn92measured.html
前田敦司
Shinji KONO
In article <m3eklwv...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda...@ialab.is.tsukuba.ac.jp> writes
> 具体的な話が分からないと何ともいえないですが、メモリ管理の話だとすると、
> メモリ管理やGCの研究者のコンセンサスとしては、
> ・GCがある言語で、自分でメモリ管理(再利用とか)しようとすると大概かえっ
> て遅くなる。
> ということになっています。
ぐ。それは、僕の経験とも一致するな。やっぱり、Java はあきら
めろってことか。
いや、でも、それでも、new と copy を減らすのは、もちろん、効果
があるんですけどね。なんか、使い方があるんだろうなぁ。
class hoge supporting gc
{
}
とかできないの?
> (cf.)
> http://java.sun.com/docs/hotspot/gc1.4.2/faq.html のQ.31
> http://www-106.ibm.com/developerworks/library/j-jtp01274.html#3.0
> http://citeseer.nj.nec.com/zorn92measured.html
---
MAEDA Atusi
> ということなのでしょう。それで、 a.h, b.h には、でも、struct
> 本体は、書かないで隠したくなるんだけどなあ。a.c, b.c の方に
> 定義して。
賛成。
学生に教え込むんなら、もう、全部 抽象データ型にさせちゃって、実装は隠
すことにしちゃうと、話が簡単になりませんかね。
#define AbsType(type) typedef struct type##_impl *type
しておいて、
#ifndef FOO_H
#define FOO_H
AbsType(foo);
AbsType(bar);
foo make_foo(void);
void foo_bar_method(foo, bar);
...
#endif
とか。んで、struct foo_impl の定義は foo.c にしか出てこない。
struct bar_impl の定義は bar.c にしか出てこない。
こうすれば、相互依存しててもあんまり気にする必要ないですよね。
(でも、全部 抽象データ型への参照で扱うと、GCが欲しくなる。
上のやりかただとgetter/setterもインラインに書けないし。
で、けっきょくJavaへ...)
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> Linux kernel 2.6 は、そのあたり、もうあきらめていて、
>
> すべてのファイルがinclude するのは、config.h だけ
>
> で、config.hには、すべてのinclude file がflatに入っている
> っていう構造になっている...
1行変更しても、全部コンパイルし直しなんですよねえ。
> > #プリプロセッサーが自動チェックしてくれればいいんですが。
>
> それでもいいんだけど...
>
> *.h を手で書かせるな
>
> って気もかなりするんだよな。
Modula-2やAdaみたいな緊縛マゾ言語にしてガチガチにチェックするでもなし、
Javaみたいに依存関係を自動で見てくれるでもなし、中途半端ですよねえ。
前田敦司
Shinji KONO
In article <m37jrnx...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda...@ialab.is.tsukuba.ac.jp> writes
> (でも、全部 抽象データ型への参照で扱うと、GCが欲しくなる。
> 上のやりかただとgetter/setterもインラインに書けないし。
> で、けっきょくJavaへ...)
いや、まぁ、256Kbyte メモリのGBAで、それが通用するなら、
そうしているんだけど...
32MB の PS2とかでも「mallocすると怒られる。まして、C++ おや。」
って世界みたいですね。「キャッシュに収まるように書き、メイン
メモリは、ハードディスクのように使う」んだそうです。そこで、
Java を使おうって僕が馬鹿なのはわかってはいるんだが...
> > ということなのでしょう。それで、 a.h, b.h には、でも、struct
> > 本体は、書かないで隠したくなるんだけどなあ。a.c, b.c の方に
> > 定義して。
> 学生に教え込むんなら、もう、全部 抽象データ型にさせちゃって、実装は隠
> すことにしちゃうと、話が簡単になりませんかね。
うむぅ。それだと、構造体へのアクセスは、全部、アクセス関数を
使うってことになりますね。inline にすれば良いんだろうけど、
そうすると、やっぱり *.h に書くことになるし...
> Modula-2やAdaみたいな緊縛マゾ言語にしてガチガチにチェックするでもなし、
> Javaみたいに依存関係を自動で見てくれるでもなし、中途半端ですよねえ。
ってわけで、自分で作りたくなるってわけだけど。
Hideki Kato
＃しかし何で lang.c なの？
In article <3990321...@insigna.ie.u-ryukyu.ac.jp>, Shinji KONO wrote:
>河野真治 @ 琉球大学情報工学です。
>
>In article <m3hdqsxx...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi
><maeda...@ialab.is.tsukuba.ac.jp> writes
>>メモリ管理を自動化しただけで、すべての資源が管理できなくなっちゃうんで
>>すか? 今までだってレジスタ割り付けとかスタックとかは自動でやってました
>>が。
>
>出来なくなるとは言わないけど、難しいですね。レジスタ割り当て
>でも、volatie とか欲しくなるじゃない。スタックでも、alloca
>とか欲しくなるでしょ?
うんうん，凝り性の人は全部自分でやりたくなっちゃうんだよね :-)
結局，まだ gc の技術が不十分なんだと思う．昔はＣでも register とか書
いてたけど，コンパイラとハードが進歩して，そういうのは書かない方が速
い（書いても無視される）時代になったよね．河野さんも今さら
register が使いたいとは言わないよね？
>OS の役割は資源管理なんだけど、言語の機能も、資源管理とみな
>すことも出来ると思う。そうでないとすると、言語は入出力だけを
>制御するってことになるけど、普通は、時間とか領域とか問題にす
>るよね。問題にならない場合の方が少ないと思う。そういう場合が
>ないとは言わないけど。
つらつら考えるに，，一つのアプリケーション（と言うかタスク）にはこ
ちょこちょやらないといけないところとと鷹揚に構えてかまわないところが
混在してて，それを一つの言語（と言うか，runtime environment）の上で
走らせてるのが根本的な原因なんだと思う．この辺りにもう一レベル階層を
追加するというのは，実際どうなんだろう？
＃昔からあるアイデアでは gc の対象外領域，ってのがあるけど，余り流行
＃らなかった．．．低レベル過ぎるからか？
--
Hideki Kato <mailto:ka...@pop12.odn.ne.jp>
Shinji KONO
In article <412d9bf8.6984%ka...@pop12.odn.ne.jp>, Hideki Kato <ka...@pop12.odn.ne.jp> writes
> ＃しかし何で lang.c なの？
(歴史的理由 :-)
> 結局，まだ gc の技術が不十分なんだと思う．
GCの前提って、
new は明示的に行う
reference は、複製可、持ち運び可
reference の消滅は、上書きによって暗黙に行う
って感じですよね。このあたりの前提が間違っているんじゃないかなぁ。
あきらかに scalability のない前提って感じでさ。
GCする言語で再利用する工夫をすると余計遅くなるってことは、なんか
プログラミングに対する制約、あるいは、隠された実行モデルが導入
されているってことなんだよね。そのあたりが、組込みとかメモリ制約
が強い場合、あるいは、下位ライブラリでは厳しい。
> 昔はＣでも register とか書
> いてたけど，コンパイラとハードが進歩して，そういうのは書かない方が速
> い（書いても無視される）時代になったよね．河野さんも今さら
> register が使いたいとは言わないよね？
ところが最近、復活していて、しかも、aliasing に関するコンパ
イラ指示みたいなものもあって...
Linux Kernel 2.6 では、大域変数のレジスタ割当てまで復活して
いるみたいですね。どれだけ効果があるのか知らんが...
> つらつら考えるに，，一つのアプリケーション（と言うかタスク）にはこ
> ちょこちょやらないといけないところとと鷹揚に構えてかまわないところが
> 混在してて，それを一つの言語（と言うか，runtime environment）の上で
> 走らせてるのが根本的な原因なんだと思う．この辺りにもう一レベル階層を
> 追加するというのは，実際どうなんだろう？
その階層は、おそらく水平な階層ではないでしょうね。面白いと思うけど。
> ＃昔からあるアイデアでは gc の対象外領域，ってのがあるけど，余り流行
> ＃らなかった．．．低レベル過ぎるからか？
実は、GC抜き + データ構造の工夫でなんとかなるからかなぁ。メモリ Pool
なんかはそんなものだし。
Hideki Kato
In article <3990340...@insigna.ie.u-ryukyu.ac.jp>, Shinji KONO wrote:
>河野真治 @ 琉球大学情報工学です。
>
>In article <412d9bf8.6984%ka...@pop12.odn.ne.jp>, Hideki Kato <ka...@pop12.odn.ne.jp> writes
>> ＃しかし何で lang.c なの？
>
>(歴史的理由 :-)
>
>> 結局，まだ gc の技術が不十分なんだと思う．
>
>GCの前提って、
> new は明示的に行う
> reference は、複製可、持ち運び可
> reference の消滅は、上書きによって暗黙に行う
>って感じですよね。このあたりの前提が間違っているんじゃないかなぁ。
>あきらかに scalability のない前提って感じでさ。
この辺りもまだ研究が不十分だってことなのかな？ 下に書いたコンパイラ
の（自動変数の）レジスタ割り付けなんてトンでもない人月で研究した結
果，ここまで来たんだから，GC（＋言語屋の一部？）の研究者の数を考える
と，まぁこんなものかな，と．
GC の必要性が高まってきた，というか，そう認識されてきたのもつい最近
だし．＃オブジェクト＋マルチスレッド＋弱い実時間性絡みね．
>GCする言語で再利用する工夫をすると余計遅くなるってことは、なんか
>プログラミングに対する制約、あるいは、隠された実行モデルが導入
>されているってことなんだよね。そのあたりが、組込みとかメモリ制約
>が強い場合、あるいは、下位ライブラリでは厳しい。
実装メモリが少ないマシンなら，GC で停まってる時間はかなり短くできる
から，かなりきつい処理でなければなんとかなる事も多いと思うんだけどね
ぇ．．．
昔々，UtiLisp 上のエキスパートシステム on Lisp マシン or Unix box を
プラントの制御に実際に使った例がいくつかあるんですが，下の方はＣや
FORTRAN で書いたプログラムを realtime task として走らせて，UtiLisp
とはパイプの類で通信してた様な気がする．GC の時間に関しては，，，確
か，やはり制限がきつくて使いにくいから実時間 GC にして欲しいって要望
は上がってきたけど，全部ではなかったと覚えています（セクションが違っ
たので詳しい事は知らない)．
>> 昔はＣでも register とか書
>> いてたけど，コンパイラとハードが進歩して，そういうのは書かない方が速
>> い（書いても無視される）時代になったよね．河野さんも今さら
>> register が使いたいとは言わないよね？
>
>ところが最近、復活していて、しかも、aliasing に関するコンパ
>イラ指示みたいなものもあって...
>
>Linux Kernel 2.6 では、大域変数のレジスタ割当てまで復活して
>いるみたいですね。どれだけ効果があるのか知らんが...
この二つに関しては，確かに，まだ研究が足りない（今後に期待）ですね．
＃結局コンパイラの最適化とハードとは車の両輪なんだなぁ．．．
>> つらつら考えるに，，一つのアプリケーション（と言うかタスク）にはこ
>> ちょこちょやらないといけないところとと鷹揚に構えてかまわないところが
>> 混在してて，それを一つの言語（と言うか，runtime environment）の上で
>> 走らせてるのが根本的な原因なんだと思う．この辺りにもう一レベル階層を
>> 追加するというのは，実際どうなんだろう？
>
>その階層は、おそらく水平な階層ではないでしょうね。面白いと思うけど。
フラットじゃないのは確かでしょうねぇ．．．OS にも係わる話なんだろう
なぁ．＃最近の OS は良く知らない．
>> ＃昔からあるアイデアでは gc の対象外領域，ってのがあるけど，余り流行
>> ＃らなかった．．．低レベル過ぎるからか？
>
>実は、GC抜き + データ構造の工夫でなんとかなるからかなぁ。メモリ Pool
>なんかはそんなものだし。
そんなに大きくないアプリなら頑張ればなんとかなるのは確かだけど，それ
で思考停止しちゃうのは，なんでも中華鍋で料理するって話と同じだし．
＃何でも箸で済むってのも確かだが．．．名人こそ道具を選ぶ．．．
MAEDA Atusi
>GCの前提って、
> new は明示的に行う
> reference は、複製可、持ち運び可
> reference の消滅は、上書きによって暗黙に行う
>って感じですよね。このあたりの前提が間違っているんじゃないかなぁ。
>あきらかに scalability のない前提って感じでさ。
上の前提は「GCの」じゃなくて、現状のほとんどのプログラミング言語がそう
なってるんですよね。GCってのは単なる「動的に割り付けたメモリの自動的再
利用」のことで、割り付け方や参照の扱い方みたいな言語の意味論にまで口は
出さないですよ。
もちろん実装の制限が意味論とかプログラミングスタイルに影響しちゃうこと
はあるでしょうけど。極端な例では、初期のSmalltalkのGC(サイクルは作っちゃ
ダメ)とか。
> new は明示的に行う
そうでない言語というと…うーん、思いつかない。
> reference は、複製可、持ち運び可
linear (unique) typeとか、Region推論とかのアプローチもありますけど、主
流の言語は全部↑のとおりでしょ。
> reference の消滅は、上書きによって暗黙に行う
暗黙はその通りですね。上書きだけでなく、リターンとかスレッド消滅で消え
ることも多いけど。(つーか、ここが「暗黙」じゃないと「自動的」とは言え
ないわけで。)
>GCする言語で再利用する工夫をすると余計遅くなるってことは、なんか
>プログラミングに対する制約、あるいは、隠された実行モデルが導入
>されているってことなんだよね。そのあたりが、組込みとかメモリ制約
>が強い場合、あるいは、下位ライブラリでは厳しい。
実行モデルっていうか、実際のプログラムの振舞いを観察して得られた経験則
ですね。「参照の局所性」とか「世代別仮説」とか。
昔のSmalltalkのGCほど強い制約はないですが、確かに使うコツはあります。
先に挙げた記事
http://www-106.ibm.com/developerworks/library/j-jtp01274.html なんかは
すごくよくまとまってると思います。
現在のGCは、
・割り付けコストは安い
・「長生きするオブジェクトの割合が少ない」なら回収も安い
・ヒープへのポインタ書き込みは高くつく
という特徴があります。
だから、「自分でオブジェクトをプールして使い回そう」とかすると、(長生
きするオブジェクトが増え、何度も書き換えられるので)高くつきます。
ポインタを含むデータは、割り付け時に初期化したらあとはなるべく書き換え
ないで(immutableにしておく)、値が変わるならどんどん作り直すのが吉です。
使えるメモリの総量を固定した場合、「生きてるデータの割合」がオーバーヘッ
ドに効いてきます。割り付け回数が多少増えても、余計なデータをなるべく持
たないのが重要。
前田敦司
MAEDA Atusi
> GC の必要性が高まってきた，というか，そう認識されてきたのもつい最近
> だし．＃オブジェクト＋マルチスレッド＋弱い実時間性絡みね．
世界中のGC研究者にとってJavaはありがたい飯の種を提供してくれてると思い
ます。
> 実装メモリが少ないマシンなら，GC で停まってる時間はかなり短くできる
> から，かなりきつい処理でなければなんとかなる事も多いと思うんだけどね
> ぇ．．．
うーん。それは「CPUが速いからたいてい間に合う」ってのと似たようなもん
で、本当のリアルタイム制御にはそれじゃやっぱり無理ですよね。
> 昔々，UtiLisp 上のエキスパートシステム on Lisp マシン or Unix box を
> プラントの制御に実際に使った例がいくつかあるんですが，下の方はＣや
> FORTRAN で書いたプログラムを realtime task として走らせて，UtiLisp
> とはパイプの類で通信してた様な気がする．GC の時間に関しては，，，確
> か，やはり制限がきつくて使いにくいから実時間 GC にして欲しいって要望
> は上がってきたけど，全部ではなかったと覚えています（セクションが違っ
> たので詳しい事は知らない)．
うむむ。Facom αとかの話でしょうか。広告に「プラント制御」とか書いてあ
るのを見て心配になったことがあります。
> >> つらつら考えるに，，一つのアプリケーション（と言うかタスク）にはこ
> >> ちょこちょやらないといけないところとと鷹揚に構えてかまわないところが
> >> 混在してて，それを一つの言語（と言うか，runtime environment）の上で
> >> 走らせてるのが根本的な原因なんだと思う．この辺りにもう一レベル階層を
> >> 追加するというのは，実際どうなんだろう？
OSとかHPC用のライブラリとか書くならともかく、ワープロとかブラウザなら
全体的に鷹揚に構えていて良いんじゃないでしょうか。
> >> ＃昔からあるアイデアでは gc の対象外領域，ってのがあるけど，余り流行
> >> ＃らなかった．．．低レベル過ぎるからか？
Real-time JavaのRegionはそんな感じですね。割と低レベル。
前田敦司
Shinji KONO
In article <m3acwhr...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda...@ialab.is.tsukuba.ac.jp> writes
> > reference は、複製可、持ち運び可
> linear (unique) typeとか、Region推論とかのアプローチもありますけど、主
> 流の言語は全部↑のとおりでしょ。
局所変数へのポインタは持ち運びに制限がありますよね。なので、
消滅は関数脱出に同期するわけだけど。
> 昔のSmalltalkのGCほど強い制約はないですが、確かに使うコツはあります。
> 先に挙げた記事
> http://www-106.ibm.com/developerworks/library/j-jtp01274.html なんかは
> すごくよくまとまってると思います。
なるほど。
> 現在のGCは、
> ・割り付けコストは安い
> ・「長生きするオブジェクトの割合が少ない」なら回収も安い
> ・ヒープへのポインタ書き込みは高くつく
> という特徴があります。
ってことは、Java では、頻繁に生成消滅するconstructor に複雑
なことをやらしちゃいけないんだな。複雑な初期データを持つオブ
ジェクトをプールして使うってのはだめなのか。なんとなくわかって
きたかな。
これって、本当に今のアプリケーションの特徴に合っているんですかね。
例えば、Tab Browser とか、Word とかでもいいんだけど。
> ポインタを含むデータは、割り付け時に初期化したらあとはなるべく書き換え
> ないで(immutableにしておく)、値が変わるならどんどん作り直すのが吉です。
この手のプログラムには割りと慣れている方なんだけどなぁ。プロ
グラミングスタイルだとすれば、それを教える必要があるのか...
(ってよりは、自分が勉強し直す必要があるってわけか) うーん。
Hideki Kato
In article <m37jrlr...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi wrote:
>Hideki Kato <ka...@pop12.odn.ne.jp> writes:
>
>> GC の必要性が高まってきた，というか，そう認識されてきたのもつい最近
>> だし．＃オブジェクト＋マルチスレッド＋弱い実時間性絡みね．
>
>世界中のGC研究者にとってJavaはありがたい飯の種を提供してくれてると思い
>ます。
大いに同感．って事は GC 研究者も増えてるんでしょうか？
＃Lisp も長いこと触ってないなぁ．．．
>> 実装メモリが少ないマシンなら，GC で停まってる時間はかなり短くできる
>> から，かなりきつい処理でなければなんとかなる事も多いと思うんだけどね
>> ぇ．．．
>
>うーん。それは「CPUが速いからたいてい間に合う」ってのと似たようなもん
>で、本当のリアルタイム制御にはそれじゃやっぱり無理ですよね。
とは言え，ここまでコンピュータの適用範囲が広がった一番の理由は「CPU
が速くなったから」であることもまた事実．
＃今 1 MIPS の「スーパーミニコン」が有っても誰も拾わない．．．
＃Java だって CPU が速くなったから使われるようになったわけで．．．
「本当のリアルタイム制御」と言っても，許される遅れ時間には色々あるわ
けで，実際問題として「1 ms じゃダメ」ってレベルの応用はそう多くない
と思います．
＃プラントでもセンサ信号をサンプルする頻度はそう高くない場合が多い．
＃車の EFI 辺りも同程度じゃないかな？
＃そう言えば，ケータイも Java 使ってるとか．．．
>> 昔々，UtiLisp 上のエキスパートシステム on Lisp マシン or Unix box を
>> プラントの制御に実際に使った例がいくつかあるんですが，下の方はＣや
>> FORTRAN で書いたプログラムを realtime task として走らせて，UtiLisp
>> とはパイプの類で通信してた様な気がする．GC の時間に関しては，，，確
>> か，やはり制限がきつくて使いにくいから実時間 GC にして欲しいって要望
>> は上がってきたけど，全部ではなかったと覚えています（セクションが違っ
>> たので詳しい事は知らない)．
>
>うむむ。Facom αとかの話でしょうか。広告に「プラント制御」とか書いてあ
>るのを見て心配になったことがあります。
私なんかも最初は心配だったんですが，プラントは「長時間の連続運転に耐
える」事が最優先で，処理が停まっていられる時間の制約は緩いものも多い
ようです．
＃詳しくは知らないが，要は内部状態の変化速度との兼ね合いでしょう．
この点では，（ゆっくりした）メモリーリークの方がずっとずっと問題だと
思われます．
>> >> つらつら考えるに，，一つのアプリケーション（と言うかタスク）にはこ
>> >> ちょこちょやらないといけないところとと鷹揚に構えてかまわないところが
>> >> 混在してて，それを一つの言語（と言うか，runtime environment）の上で
>> >> 走らせてるのが根本的な原因なんだと思う．この辺りにもう一レベル階層を
>> >> 追加するというのは，実際どうなんだろう？
>
>OSとかHPC用のライブラリとか書くならともかく、ワープロとかブラウザなら
>全体的に鷹揚に構えていて良いんじゃないでしょうか。
人間絡みの場合，マウス，キーボード等からの入力に対して 0.1 秒以内に
何らかの反応を返さないとまずいという問題があります．これはアプリケー
ションが介在しないといけないので，「全部」鷹揚ってわけにはいきません
ねぇ．
＃素人さんは，反応が無いと慌ててキーを連打したりして，さらに処理を遅
＃らせてしまうんだよね．
>> >> ＃昔からあるアイデアでは gc の対象外領域，ってのがあるけど，余り流行
>> >> ＃らなかった．．．低レベル過ぎるからか？
>
>Real-time JavaのRegionはそんな感じですね。割と低レベル。
古く（ルーツ？）は MacLisp の BOX 演算辺りでしょうか．UtiLisp の
GC に関しても，要望は結構有ったんだけど，大きくいじらないといけない
からやらなかった．実際，GC に無関係で構わないデータってのもたくさん
あるんだけど，スマートな見せ方（機能仕様レベル）が難しくて．．．
＃実行中のある時点で，今生きているものは回収不要と宣言するってアイデ
＃アもありましたねぇ，そう言えば．実装は簡単なんだけど，なんで作らな
＃かったんだったか．．．
MAEDA Atusi
> > 現在のGCは、
> > ・割り付けコストは安い
> > ・「長生きするオブジェクトの割合が少ない」なら回収も安い
> > ・ヒープへのポインタ書き込みは高くつく
> > という特徴があります。
あと1個Javaでの特徴を忘れてました。
・finalizerは高くつく
(http://www-106.ibm.com/developerworks/library/j-jtp01274.html#2.0)
> これって、本当に今のアプリケーションの特徴に合っているんですかね。
> 例えば、Tab Browser とか、Word とかでもいいんだけど。
対話的なプログラムの特徴はどんなのかっていう解析は、あんまり見たことな
いですね。面白い課題だと思うけど、どういう入力データを与えて測定するか
難しそう。
ghostscriptとかlispインタプリタとかは良く(C言語の)メモリ割り付けの測定
対象になってますけどね。あとはバッチ的なプログラムやサーバ側アプリっぽ
いのが多いですかね。
なんでGCがこういう風にチューンされたかっていうと、少なくとも↑のような
ベンチマークだと、
・単位時間あたりにオブジェクトが死ぬ確率は、寿命が若いうちの方が高い
(弱い世代別仮説)
・ヒープへのポインタの書き込みは読み出しよりかなり少ない(1対3とか)
というのが成り立っているので、それを利用してGCの平均コストを下げるよう
なアルゴリズムにしてあるからです。
> > ポインタを含むデータは、割り付け時に初期化したらあとはなるべく書き換え
> > ないで(immutableにしておく)、値が変わるならどんどん作り直すのが吉です。
>
> この手のプログラムには割りと慣れている方なんだけどなぁ。プロ
> グラミングスタイルだとすれば、それを教える必要があるのか...
> (ってよりは、自分が勉強し直す必要があるってわけか) うーん。
うーん。素直に関数型っぽく書けばだいたいOKだと思うんですが。
まあ、再利用しないっていってもでかい配列とかは当然 書き換えた方がコピー
するより安いですね。その辺は常識的に。
前田敦司
MAEDA Atusi
> >世界中のGC研究者にとってJavaはありがたい飯の種を提供してくれてると思い
> >ます。
>
> 大いに同感．って事は GC 研究者も増えてるんでしょうか？
> ＃Lisp も長いこと触ってないなぁ．．．
イエ、ソレホドデハないと思います。
(応用寄りの研究者は増えていても、システム寄りの研究の人気は下がってい
る気がします。)
> 「本当のリアルタイム制御」と言っても，許される遅れ時間には色々あるわ
> けで，実際問題として「1 ms じゃダメ」ってレベルの応用はそう多くない
> と思います．
> ＃プラントでもセンサ信号をサンプルする頻度はそう高くない場合が多い．
> ＃車の EFI 辺りも同程度じゃないかな？
> ＃そう言えば，ケータイも Java 使ってるとか．．．
そうなんですけどお。たとえば
「たいてい1ms以内で応答するけど、10秒止まる可能性がないわけではない」
システムは、
「1秒以内なら十分だけど、5秒止まると工場が爆発する可能性がないわけでは
ない」プラントでは使えませんよねえ。
「上限の保証がないと困る」と言われた時に、UnixやWindowsでは保証のしよ
うがないわけで…
(ケータイJavaも、実時間性の不要な対話的アプリにしか使ってないのでは。)
> >うむむ。Facom αとかの話でしょうか。広告に「プラント制御」とか書いてあ
> >るのを見て心配になったことがあります。
>
> 私なんかも最初は心配だったんですが，プラントは「長時間の連続運転に耐
> える」事が最優先で，処理が停まっていられる時間の制約は緩いものも多い
> ようです．
> ＃詳しくは知らないが，要は内部状態の変化速度との兼ね合いでしょう．
> この点では，（ゆっくりした）メモリーリークの方がずっとずっと問題だと
> 思われます．
最適化のためのプランニングとかをLispでやって、それはリアルタイム性がな
くても良いと言うことなんでしょうかねえ。まあ、リアルタイム応用とは言え
ないような。
> >OSとかHPC用のライブラリとか書くならともかく、ワープロとかブラウザなら
> >全体的に鷹揚に構えていて良いんじゃないでしょうか。
>
> 人間絡みの場合，マウス，キーボード等からの入力に対して 0.1 秒以内に
> 何らかの反応を返さないとまずいという問題があります．これはアプリケー
> ションが介在しないといけないので，「全部」鷹揚ってわけにはいきません
> ねぇ．
> ＃素人さんは，反応が無いと慌ててキーを連打したりして，さらに処理を遅
> ＃らせてしまうんだよね．
ただ、そういうのは反応が遅くても仕様通りであることは違いないし、せいぜ
い「qualityが低い」という程度であって、エラーではないですよねえ。そこ
がハードリアルタイムな応用とは違うところで。
> >> >> ＃昔からあるアイデアでは gc の対象外領域，ってのがあるけど，余り流行
> >> >> ＃らなかった．．．低レベル過ぎるからか？
> >
> >Real-time JavaのRegionはそんな感じですね。割と低レベル。
>
> 古く（ルーツ？）は MacLisp の BOX 演算辺りでしょうか．UtiLisp の
> GC に関しても，要望は結構有ったんだけど，大きくいじらないといけない
> からやらなかった．実際，GC に無関係で構わないデータってのもたくさん
> あるんだけど，スマートな見せ方（機能仕様レベル）が難しくて．．．
Javaだとprimitive type (char, int, float…)はGCに無関係ですね。
C#だとvalue type (int等の他structも含む)があって、これはGCされません。
GCされるreference type (object等) との間でboxing, unboxingが行なえます。
> ＃実行中のある時点で，今生きているものは回収不要と宣言するってアイデ
> ＃アもありましたねぇ，そう言えば．実装は簡単なんだけど，なんで作らな
> ＃かったんだったか．．．
そういう処理系もありますね。Emacs Lispのpure領域とか。最初はSymbolics
かなあ。
前田敦司
MAEDA Atusi
ku...@gssm.otsuka.tsukuba.ac.jp writes:
> ハードリアルタイム→応答時間の制約厳守で守れないとfail
>
> ソフトリアルタイム→できるかぎりフルスピードで動く(ゲームとか)
>
> これくらいが普通の定義と思う。
リアルタイムでない
→出力結果が正しければ100点
そうでなければ0点
ハードリアルタイム
→出力結果が正しく、かつ〆切より以前に出力されれば100点
そうでなければ0点
ソフトリアルタイム
→出力結果が正しく、かつ〆切より以前に出力されれば100点
そうでなければ、時間経過とともに減点
っていう定義でどうでしょう。
> 河野さんが普通じゃないのは普通なんだけど :-) 久野
河野さんがおっしゃるのが「たいていのプログラムはソフトリアルタイムとみ
なせる」という主張なら理解できなくもないです。はっきりした根拠のある〆
切がないやつは、普通はソフトリアルタイムに入れないですけどね。
「ソフトリアルタイム」で想定してるのは、たとえばDVDの再生とか。1/24秒
とか1/60秒とかで1コマ処理する必要があるけど、ときどき1コマ飛ぶくらいで
は0点にはならない。
> P.S. 真夜中に動くバックアップジョブは河野さんワールドではリアル
> タイムなんですね? :-P
〆切(翌朝8時とか)が決まっていれば立派なハードリアルタイムですよね。
ただ、この場合、リアルタイムOSでない ふつーのOSでも、デッドラインをミ
スする可能性がほぼ0とみなせるような設計はできるでしょうね。(平均1msで
最悪だと秒単位ってことはあるかもしれないけど、バックアップがたとえば平
均3時間なら、それが数倍になったりはしなさそう。)
前田敦司
Hideki Kato
In article <m3wtzlp...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi wrote:
>Hideki Kato <ka...@pop12.odn.ne.jp> writes:
>
>> >世界中のGC研究者にとってJavaはありがたい飯の種を提供してくれてると思い
>> >ます。
>>
>> 大いに同感．って事は GC 研究者も増えてるんでしょうか？
>> ＃Lisp も長いこと触ってないなぁ．．．
>
>イエ、ソレホドデハないと思います。
>
>(応用寄りの研究者は増えていても、システム寄りの研究の人気は下がってい
>る気がします。)
あら残念．これからどんどん重要性が増すと思いますけどねぇ．．．＜GC
＃まぁ，地味なのは否めないが．．．（謝
>> 「本当のリアルタイム制御」と言っても，許される遅れ時間には色々あるわ
>> けで，実際問題として「1 ms じゃダメ」ってレベルの応用はそう多くない
>> と思います．
>> ＃プラントでもセンサ信号をサンプルする頻度はそう高くない場合が多い．
>> ＃車の EFI 辺りも同程度じゃないかな？
>> ＃そう言えば，ケータイも Java 使ってるとか．．．
>
>そうなんですけどお。たとえば
>「たいてい1ms以内で応答するけど、10秒止まる可能性がないわけではない」
>システムは、
>「1秒以内なら十分だけど、5秒止まると工場が爆発する可能性がないわけでは
>ない」プラントでは使えませんよねえ。
>
>「上限の保証がないと困る」と言われた時に、UnixやWindowsでは保証のしよ
>うがないわけで…
α のホストは FSP，WS は Unix＋realtime 拡張 を使ってましたが，それ
は兎も角，copying gc の場合，ヒープのサイズが決まれば，gc に掛かる時
間の上限は見積もれます（でしたよね？）から，大丈夫だったような．
>(ケータイJavaも、実時間性の不要な対話的アプリにしか使ってないのでは。)
OS は TRON 系でしったか，確か．でも，仮名漢字変換辺りだと，0.1 秒を
超えたら０点って仕様もありそう．
＃要求仕様でいいんですよね？＜ハード/ソフトの区別
>> >うむむ。Facom αとかの話でしょうか。広告に「プラント制御」とか書いてあ
>> >るのを見て心配になったことがあります。
>>
>> 私なんかも最初は心配だったんですが，プラントは「長時間の連続運転に耐
>> える」事が最優先で，処理が停まっていられる時間の制約は緩いものも多い
>> ようです．
>> ＃詳しくは知らないが，要は内部状態の変化速度との兼ね合いでしょう．
>> この点では，（ゆっくりした）メモリーリークの方がずっとずっと問題だと
>> 思われます．
>
>最適化のためのプランニングとかをLispでやって、それはリアルタイム性がな
>くても良いと言うことなんでしょうかねえ。まあ、リアルタイム応用とは言え
>ないような。
（オフラインの）プランニングではなく，実際の運用（スケジューリング）
です．処理に許される時間はけっこう長いけど，仕様としてはハードです．
＃担当者も「100%」を満たすのに色々苦労してたような記憶が．．．
＃まぁ，駄目な確率がハードの故障確率より低ければ十分なわけですが．
>> 人間絡みの場合，マウス，キーボード等からの入力に対して 0.1 秒以内に
>> 何らかの反応を返さないとまずいという問題があります．これはアプリケー
>> ションが介在しないといけないので，「全部」鷹揚ってわけにはいきません
>> ねぇ．
>> ＃素人さんは，反応が無いと慌ててキーを連打したりして，さらに処理を遅
>> ＃らせてしまうんだよね．
>
>ただ、そういうのは反応が遅くても仕様通りであることは違いないし、せいぜ
>い「qualityが低い」という程度であって、エラーではないですよねえ。そこ
>がハードリアルタイムな応用とは違うところで。
パソコン（情報/家電屋）とケータイ（通信屋）では要求仕様も違う可能性
もあります．
＃私ならエラーにするだろうなぁ．．．でないと悪評が立ちそうだもん．
>> 古く（ルーツ？）は MacLisp の BOX 演算辺りでしょうか．UtiLisp の
>> GC に関しても，要望は結構有ったんだけど，大きくいじらないといけない
>> からやらなかった．実際，GC に無関係で構わないデータってのもたくさん
>> あるんだけど，スマートな見せ方（機能仕様レベル）が難しくて．．．
>
>Javaだとprimitive type (char, int, float…)はGCに無関係ですね。
ここが Java の特徴でしたね．タグを無くすとはなんと大胆な，，，GC が
大変，と思ったものです．
>C#だとvalue type (int等の他structも含む)があって、これはGCされません。
>GCされるreference type (object等) との間でboxing, unboxingが行なえます。
結局 BOX から進歩してないのね（嘆．
>> ＃実行中のある時点で，今生きているものは回収不要と宣言するってアイデ
>> ＃アもありましたねぇ，そう言えば．実装は簡単なんだけど，なんで作らな
>> ＃かったんだったか．．．
>
>そういう処理系もありますね。Emacs Lispのpure領域とか。最初はSymbolics
>かなあ。
多分もっと古いと思います．その pure に相当する機能は Lisp1.5 の処理
系にもありましたから．
＃ユーザーに開放していたかどうかは不明ですが．
Hideki Kato
In article <m33c29q...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi wrote:
>ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
>> この手のプログラムには割りと慣れている方なんだけどなぁ。プロ
>> グラミングスタイルだとすれば、それを教える必要があるのか...
>> (ってよりは、自分が勉強し直す必要があるってわけか) うーん。
>
>うーん。素直に関数型っぽく書けばだいたいOKだと思うんですが。
^^^^^^ Java は関数型言語だったのね!?
Shinji KONO
In article <412f3ad6.6991%ka...@pop12.odn.ne.jp>, Hideki Kato <ka...@pop12.odn.ne.jp> writes
> >うーん。素直に関数型っぽく書けばだいたいOKだと思うんですが。
> ^^^^^^ Java は関数型言語だったのね!?
ってよりは、GC を使う言語では、ポインタの書き換えを避けるために、
できるだけ単一代入的なデータ構造を使うってことですよね。非破壊
っていうのかな。確かにそうすれば、C と同等の速度が出るとか言う
説もあったような記憶がある。
Smalltalk では、そういうことはあんまりやらなかったような気もする
けど、気のせいなんだろうな。Java では、そうなのか。むむむ。
MAEDA Atusi
> > >うーん。素直に関数型っぽく書けばだいたいOKだと思うんですが。
> > ^^^^^^ Java は関数型言語だったのね!?
>
> ってよりは、GC を使う言語では、ポインタの書き換えを避けるために、
> できるだけ単一代入的なデータ構造を使うってことですよね。非破壊
> っていうのかな。
そうゆうことです。関数型言語じゃなくても関数型っぽくimmutableなデータ
を多用する方がGCにやさしいプログラムです。
# 皮肉な話ですが、ユーザに見える副作用のない純関数型言語では、中では
# ヒープ上のグラフ構造をばしばし書き換えるので、GCにはやさしくなかった
# りします。
> 確かにそうすれば、C と同等の速度が出るとか言う
> 説もあったような記憶がある。
>
> Smalltalk では、そういうことはあんまりやらなかったような気もする
> けど、気のせいなんだろうな。Java では、そうなのか。むむむ。
XeroxのSmalltalk実装は今とGCのアルゴリズムが違いますね(deferred
reference counting)。これもヒープへのポインタ書き込みにはコストがかか
りますが、最近の世代別GCほどではないかも。でも、Smalltalkでは別の意味
でポインタ書き込みがdiscourageされてたんじゃないですか(サイクルを作っ
てしまうとコストが高い)。
前田敦司
Yasushi Shinjo
In article <m33c29q...@nospam.maedapc.cc.tsukuba.ac.jp>
MAEDA Atusi <maeda...@ialab.is.tsukuba.ac.jp> writes:
> ghostscriptとかlispインタプリタとかは良く(C言語の)メモリ割り付けの測定
> 対象になってますけどね。あとはバッチ的なプログラムやサーバ側アプリっぽ
> いのが多いですかね。
PostScript は、GC 要らないと思ったんだけど。明示的にsave で
マークして restore すればその場所まできれいに忘れる。
Forth だと forget なんとかで、定義(alloc)したワードを全部忘れます。
GC というと、PHP とかめちゃくちゃだと聞きました。どうなんで
すか。
> うーん。素直に関数型っぽく書けばだいたいOKだと思うんですが。
対象が関数ぽいものは、そんな感じです。XML を SAX で処理する
時なんか。
Java の VM の GC ですが、メモリ余っているのに動き出しちゃい
ますね。GC 走らせないで実行時間を計りたいのに。ただ、GC が
頻繁に発生しても、OS レベルで見た時の仮想記憶のワーキング・
セットが小さくなるなら、その方がいいみたい。
というわけで、ニュースグループ再開発ということで、
Followup-To: fj.comp.lang.implementation です。
＼＼ 新城 靖 （しんじょう やすし） ＼＼
＼＼ 筑波大学 電子・情報 ＼＼
MAEDA Atusi
> >「上限の保証がないと困る」と言われた時に、UnixやWindowsでは保証のしよ
> >うがないわけで…
>
> α のホストは FSP，WS は Unix＋realtime 拡張 を使ってましたが，それ
> は兎も角，copying gc の場合，ヒープのサイズが決まれば，gc に掛かる時
> 間の上限は見積もれます（でしたよね？）から，大丈夫だったような．
えーっと、user CPU時間では見積もれても、実時間では難しいのでは。
(ページフォルトが起きて、プロセスが寝てしまうと…)
ページをロックして、スケジューリングも変えておくんでしょうかね。
で、ディスクI/Oはしないとか。
> >最適化のためのプランニングとかをLispでやって、それはリアルタイム性がな
> >くても良いと言うことなんでしょうかねえ。まあ、リアルタイム応用とは言え
> >ないような。
>
> （オフラインの）プランニングではなく，実際の運用（スケジューリング）
> です．処理に許される時間はけっこう長いけど，仕様としてはハードです．
> ＃担当者も「100%」を満たすのに色々苦労してたような記憶が．．．
> ＃まぁ，駄目な確率がハードの故障確率より低ければ十分なわけですが．
なるほど。夜のバックアップと同じような話ですかね。
(少し引用の順番変えてます。)
> >(ケータイJavaも、実時間性の不要な対話的アプリにしか使ってないのでは。)
>
> OS は TRON 系でしったか，確か．でも，仮名漢字変換辺りだと，0.1 秒を
> 超えたら０点って仕様もありそう．
> ＃要求仕様でいいんですよね？＜ハード/ソフトの区別
客観的に根拠のあるデッドライン(NTSC規格で決まっているコマ数だとか、工
場のラインの速度とか)じゃないと、うまくないと思います(後述) 。0.1秒っ
てのは別に101ms でも95msでもかまわない、恣意的な値ですよね。
> >ただ、そういうのは反応が遅くても仕様通りであることは違いないし、せいぜ
> >い「qualityが低い」という程度であって、エラーではないですよねえ。そこ
> >がハードリアルタイムな応用とは違うところで。
>
> パソコン（情報/家電屋）とケータイ（通信屋）では要求仕様も違う可能性
> もあります．
> ＃私ならエラーにするだろうなぁ．．．でないと悪評が立ちそうだもん．
それを言い出すとバッチ処理だろうが対話処理だろうが何だろうが「速い方が
ユーザの評判は良い」わけですから、すべてのコンピュータプログラムはリア
ルタイム処理ということになって、「リアルタイム」という言葉の実体がなく
なっちゃうと思います。
たとえば「100msを越えなければ悪評が立つ可能性は0%」とかはっきり決まっ
ているものだけに使うのが良いのでは。
前田敦司
Hideki Kato
In article <m3isb4p...@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi wrote:
>Hideki Kato <ka...@pop12.odn.ne.jp> writes:
>
>> >「上限の保証がないと困る」と言われた時に、UnixやWindowsでは保証のしよ
>> >うがないわけで…
>>
>> α のホストは FSP，WS は Unix＋realtime 拡張 を使ってましたが，それ
>> は兎も角，copying gc の場合，ヒープのサイズが決まれば，gc に掛かる時
>> 間の上限は見積もれます（でしたよね？）から，大丈夫だったような．
>
>えーっと、user CPU時間では見積もれても、実時間では難しいのでは。
>(ページフォルトが起きて、プロセスが寝てしまうと…)
>ページをロックして、スケジューリングも変えておくんでしょうかね。
>で、ディスクI/Oはしないとか。
あ，ちょっと誤解させてしまいました．クリティカルな奴にはα（GC 等全
てマイクロコードで実メモリ）を使ってましたから，その心配はありませ
ん．
＃WS でもやる気になれば可能かも知れませんが．．．
＃OS のメモリ管理とくっつける？
>> >最適化のためのプランニングとかをLispでやって、それはリアルタイム性がな
>> >くても良いと言うことなんでしょうかねえ。まあ、リアルタイム応用とは言え
>> >ないような。
>>
>> （オフラインの）プランニングではなく，実際の運用（スケジューリング）
>> です．処理に許される時間はけっこう長いけど，仕様としてはハードです．
>> ＃担当者も「100%」を満たすのに色々苦労してたような記憶が．．．
>> ＃まぁ，駄目な確率がハードの故障確率より低ければ十分なわけですが．
>
>なるほど。夜のバックアップと同じような話ですかね。
失礼，ちょっと意味が分かりません．
＃長いってのは前に書いたように，数十 ms 程度だったと思います．
>> OS は TRON 系でしったか，確か．でも，仮名漢字変換辺りだと，0.1 秒を
>> 超えたら０点って仕様もありそう．
>> ＃要求仕様でいいんですよね？＜ハード/ソフトの区別
>
>客観的に根拠のあるデッドライン(NTSC規格で決まっているコマ数だとか、工
>場のラインの速度とか)じゃないと、うまくないと思います(後述) 。0.1秒っ
>てのは別に101ms でも95msでもかまわない、恣意的な値ですよね。
およよ，けっこう厳しいんですね．
＃0.1 秒ってのは，昔々 IBM がプログラマの生産性の測定からはじき出し
＃た値です．
>> パソコン（情報/家電屋）とケータイ（通信屋）では要求仕様も違う可能性
>> もあります．
>> ＃私ならエラーにするだろうなぁ．．．でないと悪評が立ちそうだもん．
>
>それを言い出すとバッチ処理だろうが対話処理だろうが何だろうが「速い方が
>ユーザの評判は良い」わけですから、すべてのコンピュータプログラムはリア
>ルタイム処理ということになって、「リアルタイム」という言葉の実体がなく
>なっちゃうと思います。
そこで実際の要求仕様がどうか？って話でいいような気がしますけどねぇ．
コスト等が大きく異なるわけですから，自ずと無茶な事にはならないと期待
します．．．が．．．
>たとえば「100msを越えなければ悪評が立つ可能性は0%」とかはっきり決まっ
>ているものだけに使うのが良いのでは。
研究用の分類だから，何らかのコンセンサスが得られないと意味が無いのは
確かで，客観的な数値じゃないと難しいかな．．．
Hideki Kato
In article <3990348...@insigna.ie.u-ryukyu.ac.jp>, Shinji KONO wrote:
>河野真治 @ 琉球大学情報工学です。
>
>In article <412f3ad6.6991%ka...@pop12.odn.ne.jp>, Hideki Kato <ka...@pop12.odn.ne.jp> writes
>> >うーん。素直に関数型っぽく書けばだいたいOKだと思うんですが。
>> ^^^^^^ Java は関数型言語だったのね!?
>
>ってよりは、GC を使う言語では、ポインタの書き換えを避けるために、
>できるだけ単一代入的なデータ構造を使うってことですよね。非破壊
>っていうのかな。確かにそうすれば、C と同等の速度が出るとか言う
>説もあったような記憶がある。
う～ん，(故）後藤先生も書かれてましたが，副作用を使わないと計算量の
オーダーが変わる処理がある（と強く推定される）んですよね．
＃KMP もそうじゃなかったかな？（朧な記憶）
>Smalltalk では、そういうことはあんまりやらなかったような気もする
>けど、気のせいなんだろうな。Java では、そうなのか。むむむ。
Prolog はこのお陰で構造体のメモリの回収が速く（正確には，速い実装が
可能で)，Lisp と比べて優る（唯一の？）点でしたが．．．
＃Java では配列は基本型だけに使おう．．．（？）
＃＃本末転倒ですね，これは．
Shinji KONO
In article <41301f08.6993%ka...@pop12.odn.ne.jp>, Hideki Kato <ka...@pop12.odn.ne.jp> writes
> う～ん，(故）後藤先生も書かれてましたが，副作用を使わないと計算量の
> オーダーが変わる処理がある（と強く推定される）んですよね．
> ＃KMP もそうじゃなかったかな？（朧な記憶）
例えば、キューとか木構造とかでは変わらないんだけど、グラフ構
造だと厳しいってな所かなぁ。
> Prolog はこのお陰で構造体のメモリの回収が速く（正確には，速い実装が
> 可能で)，Lisp と比べて優る（唯一の？）点でしたが．．．
> ＃Java では配列は基本型だけに使おう．．．（？）
> ＃＃本末転倒ですね，これは．
でも、結局、頻繁に書き換えるのは、基本型の配列ってことになっ
ていることが多いみたいですね。そういう言語ってことか。
Hideki Kato
In article <3990356...@insigna.ie.u-ryukyu.ac.jp>, Shinji KONO wrote:
>河野真治 @ 琉球大学情報工学です。
>
>In article <41301f08.6993%ka...@pop12.odn.ne.jp>, Hideki Kato <ka...@pop12.odn.ne.jp> writes
>> う～ん，(故）後藤先生も書かれてましたが，副作用を使わないと計算量の
>> オーダーが変わる処理がある（と強く推定される）んですよね．
>> ＃KMP もそうじゃなかったかな？（朧な記憶）
>
>例えば、キューとか木構造とかでは変わらないんだけど、グラフ構
>造だと厳しいってな所かなぁ。
ふむ，そういう見方はしてなかったから確かな事は言えないけれど，取りあ
えず私が知ってる実例は，HLISP の連想記憶絡みと KMP の UtiLisp での一
実装でのデータ構造（確かグラフ構造だったと思う）だから，該当してます
ね．
>> Prolog はこのお陰で構造体のメモリの回収が速く（正確には，速い実装が
>> 可能で)，Lisp と比べて優る（唯一の？）点でしたが．．．
>> ＃Java では配列は基本型だけに使おう．．．（？）
>> ＃＃本末転倒ですね，これは．
>
>でも、結局、頻繁に書き換えるのは、基本型の配列ってことになっ
>ていることが多いみたいですね。そういう言語ってことか。
まぁ，グラフ構造を必要とする応用はそんなに多くないと思うから，それほ
ど困る事は無いんでしょうけどね．言語の問題じゃなくて，メモリーが線形
でポインタを使う限りしょうがないんじゃないかなぁ．．．？
＃連想メモリとか逆ポインタを包含するメモリとかなら違ってくるような気
＃が．