[Mew-dist 09777] Re: hash on Emacs (toward threading)
Shun-ichi GOTO ( 後藤 俊一 )
gotoh at example.com
1999年 7月 20日 (火) 00:08:02 JST
後藤＠太陽計測です
ちょっと長文です
# まごまごしているうちに、かずさんがthread化へ動き出してしまったか!?
# ごめんなさい、最近チョー忙しくて、どこのMLも読み流し(さえもしてない？)
>>>>> at Mon, 19 Jul 1999 21:41:04 +0900, kazu <kazu at example.com> said,
kazu> ここから本題ですが、obarray を使うと簡易 DB が作成できるので、thread
kazu> を実装する際に役に立ちます。(Message-ID: に対し、In-Reply-To: を登録す
kazu> るなど。)しかし、メッセージの数が大きくなると効率が落ちるんじゃないで
kazu> しょうか？ 真剣に探しましたが、ハッシュを大きくする方法はないようです。
体感的には、ハッシュの大きさはあまり問題になっているように思いません。
ハッシュの大きさが問題になるよりもデータ保持のメモリのための
スワップや保存処理のコストのほうが大きいように感じます。
kazu> 後藤さんが obarray で thread を実現していたと思うのですが、
kazu> - ソースは公開していますか？
MUEという名前を付けてあります。
公開は可能ですが、ドキュメント不備と一人よがりな機能のため、まだpublicに
は公開していません。ここ最近、公開へ向けてコードの整備とドキュメント書き
をしていたのですが、最近突発的なJOBと休日の予定が増えてしまい、滞ってい
ます。(;_;)
ソースはMewにadviceで取り付くためのコードや、追加した機能などが混在して
いるため、見ると混乱する可能性が大ですが、その余計な部分も含めてよければ
すぐにでも提供できます(後述)。その代わりといってはナニですが、概要の説明
をしておきます。
kazu> - ハッシュの大きさはいくらですか？
2039を使ってます。
適当に大き目に選びました。
妥当性はあまり有りません。
kazu> - ハッシュは動的に大きくしていますか？
していません。
以前考えましたが、あまり劇的な変化が見られなかったようだったので
固定で使っています。
kazu> - たくさんメッセージを扱うと遅くなりませんか？
メッセージ数が多いとおそくなるとは思いますが、
ハッシュの操作を毎回多量に行うわけではないので、
あまり問題ではないように思います。
それよりも、シンボルを多量に使うため、そのメモリ消費量のせいで
遅くなる方が支配的だと思います。
現在の私の+inboxには 8850のメッセージが有りますが、
Meadowを使っていてNTのタスクマネージャでメモリ消費量を観察していると、
MUEを使わない素直なMewに比べ、MUEの機能を追加し、+inboxのDBを読み込んだ
時点で、約 +10MBのメモリを消費します。
また、+inboxのための保存したDBファイルの大きさは、Emacsのalist形式で
3.8MBです。現時点でのハッシュ(db)中のシンボルの数は14791でした。
これを多いと見るかどうかはお任せしますが、現在のMUEはメモリを節約するの
にあまり注力していません。メモリ節約は後からやればいいというスタンスで、
どちらかというと贅沢を前提としているのが現状です。
で、ソースを読んで理解するのは手間だし、無茶なので、概要を以下に述べます。
興味の無い方は以降は無視してください。
[シンボル(key)の種類]
ハッシュ(DB)にキーとして登録している(internしている)データは、
* msym : メッセージ構造ベクタを保持するシンボル(メッセージ番号から作る)
* idsym : Message-Id:, References:, In-Reply-To: の Message-Id: 文字列
* addrsym : address (From:, To:, Cc: )
* subjsym : spaceを削除したSubject: 文字列のシンボル。
* hdsym : MLのヘディング文字列
* grpsym : List Group (X-Ml-Name:などの)の文字列
です。
それぞれはsymbol-valueを持ちますが、valueとして文字列、ベクタ、
リストなどが保持されます。
[メッセージ情報ベクタ]
個々のメッセージはベクタで情報保持し、
これによりElispだけでsummaryを一通り描画できます。
msym => mvec
mvec => [ message number (integer)
date (cons)
message id (idsym)
parent (idsym)
From: person (addrsym)
To: person (addrsym ... 複数)
Cc: person (addrsym ... 複数)
subject : [simplified-subject, "re" flag, heading, seqno]
group (grpsym)
seqno (integer)
body (string ... 40byte 程度)
]
idsym => ((msym msym ...) ## message of this id
. (msym ...)) ## childs of this id (referenced)
addrsym => ( "Shun-ichi Goto" . "ごとー" ) ## for example
subjsym => "mail and news" ## symbolname is "Smailandnews"
[シンボルの値]
各シンボルは、それぞれ値をもちます。
msym は 値として mvecを保持します。
mvec は多くのシンボルを保持します。
idsymは それを Message-Id:とするメッセージ(複数)のmsymのリストと、
それを親とするメッセージのmsymのリストを保持します。
addrsym は アドレス文字列中の名前 (i.e. "Shun-ichi Goto") などを保持します。
subjsym はSubject:文字列から[mew-dist: xxx]などの接頭文字列と、Re:, Fw:など
を取り除いたものを保持します。そのシンボルはさらに空白/TABを削除した文字列で
internされます。(同一性を調べるのに役に立つため)
grpsymは単純にリストグループ名の文字列を保持します。
[スレッドの構築]
msym、そしてそれに対応するmvecが個々のメッセージそのものとなります。
親を辿るには ベクタ中のrefidスロットのシンボルから親メッセージの
msymを取り出す事で行います。
threadを作るには、threadのtopとなる全メッセージからメッセージを選び出し、
topからchildへと再帰的に描画する事で作ります。
全メッセージと、topのメッセージのリストはメモリ上およびdbファイルに
保持しておきます。
ちなみに、idsymではなく、msymというモノを用いるのは、同一Message-Id:をも
つ複数のメールファイルが存在し得るからです。唯一のメッセージを特定するた
めに、メッセージファイル(+folder/111) を表すmsymを使うわけです。そして、
idsymは複数のmsymへのリンクを持ちます。
[dbの保存/読込]
obarrayの保存はそのものズバリの処理はないため、いったんkeyとvalueのペア
のalistを作り、これをファイルにprincで書き出します。読み込みはその逆です。
読み込んだalistの各要素の
本来はalistの要素のcarは文字列として、dbロード時にinternすべきなのですが、
高速化のためにちょっとトリッキーなことをしてます。現状ではcar部は
シンボルそのものです。alistのread()時にグローバルなobarrayをすり替えて
そのままread()することで、db用のobarrayにEmacsが勝手にinternしてくれます。
とまぁ、DB構造を大雑把に説明してみました。論ずるよりxxxというならば、以
下からコードと書きかけのinfoを入手してください。
# ただし未整備のため、責任がもてませんので、ご使用は気合の有る方だけにし
# ておいてくださいね。
http://www.imasy.or.jp/~gotoh/lisp/mue.el.gz
http://www.imasy.or.jp/~gotoh/lisp/mue.info
書きかけのinfoはチュートリアルだけしか読む価値は有りませんが、お試しする
ための方法と、基本操作方法は分かると思います。
なお、自分がMeadow主体なもので、現在のところ Emacs20.2, 3 でしか動作しな
いと思われます。Emacs19はダメです。 19.34でも多分ダメです。XEmacsは試し
てません。ごめんなさい。
# 明日は知人の結婚式/2次会なので即応しにくいです。
いじょ
--- Regards,
Shun-ichi Goto <gotoh at example.com>
R&D Group, TAIYO Corp., Tokyo, JAPAN
Mew-dist メーリングリストの案内