未来のいつか/hyoshiokの日記 このページをアンテナに追加 RSSフィード Twitter

2006-09-26

祝400000ページビュー

皆様の愛顧のおかげで40万ページビューを達成しました。

いつからPVを張ったか覚えていないので詳しいことはよくわからないのですが(とほほ)、地味に地道にときどきの日記を記していきたいと思います。ありがとうございます(ぺこり)

一日平均500〜1000PVくらいかなあ。月間25000〜30000PVくらいの地味目の日記ですね。ページビューは少ないより多い方が励みになるけど、ページビューだけを狙うということはするつもりもないですね。日記は自分のために書くものだから。

コメント感想、叱咤激励、ご批判そのたお待ちしております〜

あらいしゅんいちあらいしゅんいち 2006/09/26 17:06 普段はRSSで見て終わりなので、そのような読者はPVにはカウントされてないかもしれません。

hyoshiokhyoshiok 2006/09/26 18:17 あらいしゅんいちさま、コメントありがとうございます。RSS経由の読者はカウントできないですね。

okdtokdt 2006/09/26 18:36 malloc、興味深いですね。Google Videoで公開してもらえてうれしいです。
コンパイラに実装がなければallocaを作ったりしていた時代を遠い目で思い出しました。

Ponda BabaPonda Baba 2006/09/26 18:41 40万カウントおめでとうございます。
hyoshiokさんの日記は難しくてなかなかコメントできませんが、
ひそかに応援させていただきます。

hyoshiokhyoshiok 2006/09/27 06:55 okdtさま、コメントありがとうございます。GoogleVideo意外といけますね。すごいすごい。

hyoshiokhyoshiok 2006/09/27 06:56 Ponda Babaさま、コメントありがとうございます。これからもよろしくお願いします〜

こてつこてつ 2006/09/27 08:45 おめでとうございま〜す!! これからも頑張ってくださいねっ。 (^^)

かれにつかれにつ 2006/09/27 23:57 こつこつ...コツコツ....

noocytenoocyte 2006/09/28 04:40 ビデオ拝見しました.
勉強会なんて,もう20年くらいやったことがなかったので,
自分も参加している気になって見て面白かったです.
(会場の参加者の声がよく聞き取れなかったのが残念ですが.)

私の場合,「malloc() 作りたい病」はまだ軽いのですが,
本格的に使った言語はCよりも Lisp が先なので,
「Lisp 処理系作りたい病」にかかってしまい,
20年ほど前 Lisp 処理系の実装方法を色々考えた時期が
ありました.そのことを思い出して懐かしかったです.
(結局作りませんでしたが.(^^;))

当時のことなので,メモリ利用効率を徹底して追求し,
ビデオで説明されていた「8バイトアラインされたサイズ
(またはポインタ) の下位3ビットを転用する方法」とか,
「1MB アラインされたブロックを得る方法」とか
当然のこととして考えていたので,ビデオでの会場の反応に
「えっ,何でこの話がそんなにウケ(?)るの?
ちょっと気合い入れて考えれば誰でも思いつくでしょ?」と
逆に驚いてしまいました.
(もっともマルチスレッド対応やキャッシュへの影響については
考えたことがなかったので勉強になりました.)

余談ですが,ポインタの下位ビットを転用する話には
オマケがあります.どの Lisp 処理系だか忘れましたが,
下位ビットの判定にビットテスト命令+条件分岐命令を
使わないものがあったそうです.下位ビットがどれもセット
されていない場合,普通にポインタ参照できますが,
いずれかのビットがセットされている場合に参照しようと
するとアラインメント割込みが発生します.
その割込み処理として下位ビットがセットされている
場合の処理を記述するのです.こうすると,
(リストの cdr チェーンを辿っていくなど)
下位ビットがリセットされている確率が高い場合に
高速化が図れるわけです.
この方法を聞いたときは「そんな方法があったのか!」と
驚きました.

hyoshiokhyoshiok 2006/09/28 09:00 こてつさま、コメントありがとうございます。ぼちぼちがんばりまっす。

hyoshiokhyoshiok 2006/09/28 09:00 かれにつさま、コメントありがとうございます。こつこつ。

hyoshiokhyoshiok 2006/09/28 09:07 noocyteさま、コメントありがとうございます。
カーネル読書会はいわゆる「勉強会」と違って、みんなでわいわいリナックスとかオープンソースを肴に楽しむというコンセプトのもと運営しています。勉強すること(?)とかをトッププライオリティにおいていないので(少なくともわたしは)、楽しければなんでもいいのだ〜。
で、メモリアライメントの話なんですが、昨今の若い人は「3ビット節約してどうするんだよ、メモリなんてじゃぶじゃぶあるじゃん」とかいう空気なんじゃないでしょうか。
キャッシュの話が良く出てくるのは、単にわたしがその話を好きだから。
割り込みでビットがセットされている事を知るというのはかなり強烈な方式ですね。しかし、割り込みのコストが高すぎるような気がするけど、どうなんでしょうね。

noocytenoocyte 2006/09/28 10:44 > カーネル読書会は (中略) 楽しければなんでもいいのだ〜。

うらやましいですね.
私の近くで,大好きなアルゴリズムとデータ構造の
勉強会があれば喜んで参加するのですが….
読書会の他の回のビデオも後で拝見 …
と思って検索したけどないんですね.残念!
ぜひ今後の回も公開してください.m(_ _)m

> 昨今の若い人は「3ビット節約してどうするんだよ、
> メモリなんてじゃぶじゃぶあるじゃん」とかいう
> 空気なんじゃないでしょうか。

そうでしょうね.それにメモリだけでなく,CPU の速度も.
数年前,仕事で少しかかわった Java のクラスライブラリ
(米国製) は,深刻なメモリ浪費を引き起こし,2GB の
メモリを積んだマシンでも満足に動かない状況でした.
その開発者は,「CPU はどんどん速くなるし,メモリも
どんどん大容量化するので云々 (後半よく覚えていない(^^;))」と
ホザいていたそうですが,そんなことを言う奴に限って,
CPU が100倍速くなろうが,メモリ容量が1024倍になろうが,
それでは到底間に合わないほど効率の悪いプログラムを書く,
というのは私の偏見でしょうか?

Java は言語仕様上,構造体 (インスタンス) をネストさせたり
配列にしたりということができず,代わりに単一の構造体同士を
ポインタで連結するので,Cなどに比べて細かいメモリブロックを
より大量に使用することになる.Java プログラマはこのことを
念頭に置かないと,効率の良いプログラムは書けませんよね.

> 割り込みのコストが高すぎるような気がするけど、どうなんでしょうね。

私もそう思います.開発者は当然クロック数まで計算して
採用したのでしょうが,最近の CPU では却って効率が
悪くなりすぎるでしょうね.

noocytenoocyte 2006/09/28 14:59 ビデオの中で,「なぜ malloc() される領域は8バイト単位なのか」という疑問に
対して,「下位3ビットが欲しかったからそうしたのではないか」という疑惑(笑)
が取り沙汰されていましたが,下記のような理由のはずです.

・malloc() はその仕様上,どんなデータ型にも適合するようアラインされた
アドレスを返さなければならない.
・普通32ビット CPU では,最もアラインメントの厳しいデータ型は double 型
(8バイト・アラインメント) である.
・したがって,malloc() が返すアドレスは8の倍数でなければならない.

ところで以前から,なぜ double 型のアラインメントは8バイトなのか,(バス幅である)
4バイトより大きいアラインメントに何のメリットがあるのか不思議に思っていました.
CPU の回路レベルで考えれば,データにアクセスする際のアドレス送出ロジックが
わずかに簡単になることぐらいしか思いつかなかったからです.
つい最近,何かで「キャッシュラインの境界に合わせるため」というようなことを
読んで,そういうものかなと思ったのですが,そんなに効果あるんでしょうか?

hyoshiokhyoshiok 2006/09/29 08:13 noocyteさま、再度のコメントありがとうございます。
今回が初めてのビデオ公開だったので、他の回のビデオはありません。ごめんなさい。
Javaの実装についてはよくわかりませんが、CPUが速くなっても効率的なプログラミングの必要性はなくならないと思っています。ソフトウェアが益々大規模複雑化している昨今ほど効率的なプログラミングが求められていると思います。

malloc()が8ビット単位というのは単にglibcの実装がそうなっているからなんじゃないでしょうか?POSIXで規定されているんでしょうか。

キャッシュラインにあわせるのなら、64バイトとか128バイトとかになりそうな気がします。

noocytenoocyte 2006/09/29 15:15 > malloc()が8ビット単位というのは単にglibcの実装が
> そうなっているからなんじゃないでしょうか?

いえ,「丁度」8バイト単位というのは glibc の実装ですが,
8の倍数 (8,16,24,32,…) 単位でなければならないというのは
malloc() の仕様上★絶対★守らなければならない条件です.

もしこれが守られていない malloc() があったとすると,アラインメントが
1バイトである char の配列を malloc() で確保する場合には問題ありませんが,
アラインメントが8バイトである double の配列や,double 型メンバを含む構造体を
確保する場合に問題となります.

仮に malloc() がアラインされていないアドレスを返した場合,その中の double 型
データの一つにアクセスすると,x86 では少し遅くなる程度ですむかもしれませんが,
その他の CPU ではアラインメント割込み (OS が UNIX であれば SIGBUS) を発生する
可能性があります.

アプリケーション側でこれを回避しようとすると,本来必要なサイズより8バイト余分に
領域を確保し,その領域内で最初に8の倍数になっているアドレスを見つけ,そこを
データの先頭アドレスとする処理が必要になります.
(これは,ビデオの中で解説されていた「1MB アラインされた領域を得る方法」と全く
同じ方法です.)

このように,malloc() が任意のデータ型に適合するアドレスを返さない場合,
アプリケーション側でアラインメントを適合させる処理が必要となるため,
malloc() は非常に使いにくいものになると同時に,メモリの利用効率も悪化します.


> POSIXで規定されているんでしょうか。

すみません,POSIX については承知していないのですが,malloc() の汎用性や
使いやすさを考えれば,「任意のデータ型に適合するアドレスを返す」という
仕様はどの規格であれ必須のはずだと思います.
そのアドレスの最小単位がいくつになるかは CPU 依存ですが,
多くの32ビット CPU では8バイトであり,
もちろん glibc malloc() もそれを守っているということです.

ですから,ビデオの中で疑惑 (笑) を持たれていたように,
glibc の実装上3ビット必要
→ サイズの下位3ビットを強制徴用
→ malloc() が返すアドレスは8バイト単位
ではなくて,
malloc() の仕様上,返すアドレスは8バイト (の倍数) 単位でなければならない
→ サイズの下位3ビットは常に0
→ この3ビットを最大限利用してヘッダサイズを節約する
ということなのです.

ただし,将来 glibc malloc() の改良のためにもう1ビット必要になった場合,
16バイト単位になる可能性は,私も否定しません.(笑)
(malloc() の仕様は満たしているわけですから.)

noocytenoocyte 2006/09/29 17:30 > キャッシュラインにあわせるのなら、64バイトとか128バイトとか
> になりそうな気がします。

確かにキャッシュラインはその程度のサイズが多いと思うのですが,
double 型はアラインメントだけでなくサイズも8バイトなので,
double 型にとってはそれより大きいアラインメントは意味がないはずです.
私が本当に知りたかったことは次のとおりです
…って,具体的なことはたった今考えたんですけど.(^^;

・sizeof(double)=8 はキャッシュラインサイズの約数なので,
それをそのまま double のアラインメントとすれば,
1個の double が複数のキャッシュラインにまたがることがなくなる.
→ たった1個の double を読む場合,アラインされていなければ最悪2つの
キャッシュラインを読まなければならないが,アラインされていれば
1つのキャッシュラインを読めばよいので確かに速度は改善される.
→ しかし double 型配列を読む場合,配列は double 境界にアラインされるが,
キャッシュライン境界にアラインされるとは限らないので,
配列全体が占めるキャッシュライン数を最小化できるわけではない.
(1個余分なキャッシュラインを必要とする場合がある.)
このような場合,double のアラインメントを8バイトにした効果は
ほとんどないのではないか?
→ それならば double のアラインメントが CPU のバス幅 (4バイト) と
同じであっても,ほとんどの場合性能に影響ないのではないか?


なお,前回の投稿で「本来必要なサイズより8バイト余分に」と書きましたが,
より正確には8−1=7バイトです.m(_ _)m
(先頭アドレスを切り上げる場合の最大値が (アラインメント−1バイト) なので.
同様に,ビデオの「1MB アラインされた 1MB 領域を得る方法」では
「最初に 2MB 確保する」と言っていましたが,これも正確には「2M−1 バイト」
確保することが必要十分です.)

noocytenoocyte 2006/09/29 22:33 double のアラインメントが8バイトである理由,わかりました!! (自己完結ですみません.)
結局,キャッシュは無関係でした.

intel のサイトからダウンロードした「IA-32アーキテクチャ・ソフトウェア・
デベロッパーズ・マニュアル上巻」を改めて読んでみたところ,
次のように書かれていました.

「8バイト境界にまたがるクワッドワード・オペランドは、アライメントが合っていない
ものと見なされ、アクセスには2回の別個のメモリ・バス・サイクルが必要になる。」

えっ,なんで? 8バイトデータを32ビット・データバスで読むんだから
アラインメントが合っていようがいまいが2回のメモリサイクルが必要でしょ?
はっ,もしや…

と思って,x86 のデータシートをダウンロードして読んだところ,
なんと,データバスは64ビットじゃないですか!!
ひえーっ,今の今まで知りませんでした.(大恥)
でもこれで長年の謎が急転直下,一瞬にして疑問氷解しました.

おまけに,アドレスバスも32ビットじゃなくて36ビットです.
ここで新たな謎が….

32ビット CPU の「32」って,一体何を指しているんでしょう???

noocytenoocyte 2006/09/30 04:10 ここに書いた double のアラインメントの件を整理して自分のブログで公開するため,
トラックバックさせていただきました.

saoshimasaoshima 2006/09/30 07:50 hyoshiokさま
off-topicで、すみません。

noocyteさま

IA32 archは、pentium pro(p6)以降、物理メモリ(物理アドレス)は36bitをサポートしております。
(pentium-mなどノートPC用のシリーズは除きます)
これは、物理アドレス拡張(Physical Address Extension,PAE)と呼ばれています。
仮想空間は32bitのままです。Linuxでも2.4のころから対応しています。

さらに話題はずれますが、PAEへの対応はなかなか難儀な問題がいろいろありまして、
たとえばDMAに使えるメモリが、メモリ搭載量4GB以下の場合4GBのどの領域からでも
確保できるのに、4GBより1Byteでも多く積むと、ZONE_NORMALからbounce bufferを
確保する必要があるため、実質500MBくらいしかなくなり性能が悪くなったり、out of
memory killが多発したりといったことがあります。

noocytenoocyte 2006/09/30 17:31 saoshimaさま,ご教示ありがとうございます.

x86 のデータバスの方はいつから64ビットなんでしょうか?
最初 (i386) からでしょうか?

「Nビット CPU」のNが何を指すのか,CPU の歴史を考えると統一されていない気がします.
(物理 or 仮想) アドレスのビット数かと思うと,8ビット CPU のアドレス空間は16ビットだったし,
データバスのビット数かと思うと,今回のように32ビット CPU のデータバスが64ビットだったり,
16ビット CPU i8086 の8ビット・データバス版 i8088 があったり….

Linux のカーネルには全然詳しくないので,”bounce buffer” も ”ZONE_NORMAL” も
今検索して初めて知りました.DMA に使うバッファが 500MB でもまだ足りないって,
どういう使われ方なのか想像し難いのですが….

バス幅バス幅 2006/09/30 18:09 64になったのはPentiumからですね。
2命令同時実行できるようになったので、それに合わせて広げたとかでしょう。

noocytenoocyte 2006/09/30 18:42 ↑ありがとうございます.

firewoodfirewood 2006/09/30 20:41 >いえ,「丁度」8バイト単位というのは glibc の実装ですが,
>8の倍数 (8,16,24,32,…) 単位でなければならないというのは
>malloc() の仕様上★絶対★守らなければならない条件です.

Cの仕様(ISO/IEC 9899:1999)を読んだ限りでは、そういう規定はないようです。
あるバージョンのglibcは12バイトを要求すると12バイトきっちり使える領域を返しますし、
これは正しくないと思います。

noocytenoocyte 2006/09/30 21:33 firewood さま

私が舌足らずなせいか誤解されてしまったようですか,
「8バイト単位」というのは malloc() がアプリケーションに提供する領域の
サイズではなく,malloc() が返すアドレスが8の倍数であるということです.

「サイズの下位3ビットが0」と書いたのは,
malloc() が返すアドレスは必ず8の倍数
→ 隣接するメモリ管理ブロックの先頭アドレスの差
(つまりメモリ管理ブロックのサイズ) も8の倍数

ということであり,このサイズは malloc() がアプリケーションに提供する
領域のサイズではなく,malloc() が内部的に使用するメモリ管理ブロックの
サイズです.

私の手元にある glibc は少し古いのですが,malloc() の man page には
「malloc() の返す値は,割り当てられたメモリへのポインタである.
これはあらゆる種類の変数に適するようにアラインメントされている.」
と書かれています.どんなバージョンの malloc() にも,同じ意味のことが
★必ず★書かれているはずです.

既に書いたように,ここでいう「8バイト」という数字は CPU 依存です.
16ビット CPU 用の malloc() では「2バイト」かもしれません.

kosakikosaki 2006/09/30 21:43 うわ! 長文コメントがはてなのサーバーエラーで消えた!!(><

noocytenoocyte 2006/10/01 00:35 前回書いたことがちょっと舌足らずな気がするので,くどいようですが念のため補足します.

> 「malloc() の返す値は,割り当てられたメモリへのポインタである.
> これはあらゆる種類の変数に適するようにアラインメントされている.」

これを翻訳すると,「malloc() が返すアドレスは8の倍数である.」と
いうことになります.つまり,

・32ビット CPU では普通,最もアラインメントの厳しいデータ型は
double 型 (8バイト・アラインメント) である.
・malloc() が返すアドレスはあらゆる種類の変数に適合するようアラインされている.
→ malloc() が返すアドレスは double 型にも適合するようアラインされている.
→ malloc() が返すアドレスは8の倍数である.


kosaki さま

Web ページの投稿フォームに直接長文書いちゃダメです!
Web フォームなんてしょっちゅうエラー起こすので信用できません.
長文はエディタで書いてコピー&ペーストしなきゃ.:)
(私は短文でもそうします.)

noocytenoocyte 2006/10/01 04:25 すみません,もう一度整理させてください.(くどくてすみません.)

Q:あんた (noocyte),盛んに「malloc() が返すアドレスは8の倍数」って
  言ってるけど,その根拠は? C言語の規格書のどこに書いてあんの?

A:私は規格書を見たことはありませんが,そんなことはどこにも書いていないはずです.
  そもそも「8」というのは CPU 依存の数字です.

  しかし glibc であれ,それ以外のCライブラリであれ,すべての malloc() の
  man page には次のような意味の一文が★★★必ず★★★あるはずです.

   「malloc() が返すアドレスは,あらゆる型に適合するようにアラインされている.」

  これを多くの32ビット CPU について翻訳すると
  「malloc() が返すアドレスは8の倍数である」
  となります.理由は前回書いたとおりです.
  また,この「8」という数字は CPU 依存ですから,
  16ビット CPU では「2」になるかもしれませんし,
  128ビット CPU では「16」以上になるでしょう.

Q:本当に malloc() が返すアドレスって8の倍数になってるの?

A:それを確かめたかったら,malloc() が返すアドレスを printf() で表示させて
  みてください.(笑)
  いちいち printf() の出力を見るのが面倒なら,次のようにしてもよいでしょう.

    #include <assert.h>

    void *p = malloc(…);
    if(p == NULL) goto NoMemory;
    assert(((size_t)p & 7) == 0);

Q:もし malloc() が返すアドレスが8の倍数じゃなかったらどうなるの?

A:例えば double 型の配列を確保するコードは次のようにせなあかんようになります.

    void *p; /* malloc() が返すアドレス */
    double *array; /* double 型の配列を指す.*/
    unsigned nElements = 256; /* 配列の要素数 */
    size_t size = sizeof(double) * nElements; /* 確保すべき配列のバイト数 */

    /* malloc() がアラインされていないアドレスを返すので,
     * 確保すべき配列のアラインメント−1バイト余分に確保する必要がある.
     * (__alignof__(type) は type 型のアラインメントを返す GCC 固有の演算子.)
    */
    size += __alignof__(double) - 1;

    /* アラインされていないアドレスを返すダメダメ malloc() */
    p = unaligned_malloc(size);
    if(p == NULL) goto NoMemory;
    
    /* p が double 境界にアラインされている保証はないので,
     * p を __alignof__(double) の倍数に切り上げた値を array とする.
     * (実際にコンパイルしたわけではないので,
     * 下の式はキャストに問題があるかもしれん.(^^;))
    */
    array = (double*)
     (((size_t)p + (__alignof__(double) - 1)) & ~(__alignof__(double) - 1));

    { /* array[] を読み書きする.*/
     unsigned i;

     for(i = 0; i < nElements; i++)
     array[i] = …;
     :
     :
    }

    /* 配列を解放する.*/
    free(p); /* free(array) ではない.*/

Q:なんでこんな面倒なことせなあかんの?
  フツーに malloc() が返したアドレスにそのまま配列書いてもええんちゃうの?

A:そうしたければ私が止めることはでけへんけど,CPU が x86 以外なら配列に
  アクセスした途端に SIGBUS が発生してコアダンプするのがオチやで.
  (ただし malloc() が偶然アラインされたアドレスを返せばフツーに動くけど,
   賭けてみまっか? 勝てる確率は 1/8.)

  あなたはこんな malloc(),使いたいですか?

成功者への道成功者への道 2006/10/01 11:46 400000ページビューおめでとうございます。
私のブログは月間15000pvぐらいです。一度遊びにきてくださいね。http://becomerich.jugem.jp/

firewoodfirewood 2006/10/02 12:45 noocyteさん、返答を
http://d.hatena.ne.jp/firewood/20061002/1159721948
に書きました。
8バイトはglibcの仕様であってANSI/ISOの仕様ではないのではないかという内容です。

noocytenoocyte 2006/10/03 01:18
> noocyteさん、返答を
> http://d.hatena.ne.jp/firewood/20061002/1159721948
> に書きました。
> 8バイトはglibcの仕様であってANSI/ISOの仕様ではないのではないかという内容です。

ブログはまだちらっと見ただけです.後でゆっくり読ませていただきますが,
とりあえず現時点での回答を.

私は規格のことはよく知りませんが,C言語の仕様でないことは確かですね.
では malloc() の仕様かというと,

・アラインメントに厳格な (アラインメント割込みを発生する) CPU については,
malloc() が絶対守るべき最小限のアラインメントがあり,かつそれより大きい
アラインメントにするメリットが何もない (どころかメモリの利用効率が落ちる) ので,
アラインメントは事実上一意に決まる.この値は malloc() の仕様だけでは決まらず,
CPU の仕様もあって初めて決まる.したがって malloc() の仕様ではなく,
「malloc() と CPU の仕様の必然的帰結」と言った方がいいだろう.

・アラインメントに寛容な CPU では,絶対守るべきアラインメントはないが,
ミスアラインには余分なメモリサイクルが発生するので,malloc() の
アラインメントには速度とメモリ効率のトレードオフが存在する.
それを選択するのは実装者なので,実装側 (glibc) の仕様と言えるだろう.

tktk 2006/10/03 11:33 memalign()/posix_memalign() が別に存在するので malloc() はアライメントを気にしなくても良いんじゃないですかね?

noocytenoocyte 2006/10/07 12:16 ↑[posix_]memalign() は Unix だけだから,そういうわけにはいきません.