プロフィール

kosaki

Author:kosaki
連絡先はコチラ

ブログ検索
最近の記事
最近のコメント
最近のトラックバック
リンク
カテゴリー
月別アーカイブ
RSSフィード
FC2ブログランキング

スポンサーサイト このエントリーをはてなブックマークに追加

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)

x86でもmallocを8byte alignにするのは最適解か? このエントリーをはてなブックマークに追加

「第67回カーネル読書会のビデオと資料」でnoocyteさんが素晴らしいコメントを寄せてくださっている。

一見の価値ありと思うので、ぜひ見てみて欲しい。


で、僕なりにちょっと補足させてもらうと

まずRISCにおいては mallocは8byte alignが事実上必須だよね。という指摘には完全に同意。
で、POSIXに書いてないのはCISCだと必須じゃないじゃーん。って事だと理解してる。
んで、noocyteさんはプラットフォーム非依存のmallocを書くとしたら、結局RISCの制約に引きずられて8byte align必須になるよねー
という話をしているように見える。

一方、みんな大好き僕らのx86はCISCの子孫なのでミスアラインアクセスが発生してもバスエラーにはならないが、SSE命令は16byte alignされてないと性能でないので、性能を意識するなら16byte alignにする必要がある。

じゃあ、なんで glibc malloc がそうなっていないの?
という疑問が沸くが、これがどうもよく分からない。

元々のdlmallocはlibcとは別の yet another malloc なので、CPU毎に#ifdefするのがイヤで
可搬性を考えて8byte alignにした。というのは十分にありえる話だが、
libc でそれをやる理由は解せない。

昔はSSE命令がなかったので、その時代の名残というセンも考えられるが、
SSE命令の使用頻度まで考えて、メモリ使用効率とのトレードオフまで考え抜いたすえに
8byte alignを選択した可能性も0ではない、と。そういう考え方もあるわけで

いや、実はこの問題は7月にLMSで話をしたときにも指摘されていたので既知の話で
かなり確信犯的に、当日は話をわざとぼやかして
聞かれたら答えるけども、自分からは言わないモードにしたわけだね。

大人って汚いね(^^;

#いいわけしとくと、当日は内容が多かったので時間が押していて
#講師自ら話を脱線させていくのは、厳しい状況だったんですよぅ(^^;;;


と、いうわけで、x86で16byte alignにするパッチを書けば性能改善する余地はあると思うので誰か試してみない?


しかし、かえすがえすも残念なのはnoocyteさんが当日来てくれていたら、その後の宴会で盛り上がれたのは間違いないと確信できるところ。
いつかぜひお会いしたいものである。



働く車_前働く車_後ろ
にげろーーー、ランキング!
関連記事


linux | 【2006-10-02(Mon) 10:26:48】 | Trackback:(3) | Comments:(12)
コメント

#define MALLOC_ALIGNMENT 16
とハードコードしちゃったらいかがざんしょ。
oprofile/Rubyでベンチマークじゃ。
2006-10-01 日 21:13:46 | URL | hyoshiok #OLXj00Ls [ 編集]

いや、RubyだとSSE命令とかはあんまり使わないんじゃ・・・・(^^;;
2006-10-01 日 21:27:37 | URL | kosaki #- [ 編集]

>RISCにおいては mallocは8byte alignが事実上必須

必須なのは
・64bit(以上の)CPU
・32bitかつ浮動小数点ユニットに直接転送というケースの話で、32bitで汎用レジスタにロードしてから処理するタイプだとバスエラーにならないし、データバスが32bitのRISCならペナルティもない、と思っていたんですが、どうなんでしょうか。

「必須じゃないけど8bytesならふつー大丈夫だし文句ないでしょ」という感じで決まった値なのかなあと。

あとなぜ16バイトアラインにしないかという理由ですが、ユーザーデータの前に管理領域を置くとすると、高い確率でキャッシュラインが別になる可能性があるからではないでしょうか。
2006-10-01 日 23:11:34 | URL | firewood #- [ 編集]

いまどきデータバスが32bitのCPUなんてあるんだっけ?
組み込みCPUではあるけど、glibcのメインターゲットではないですしねぇ・・・
あと、今話しているアラインの話は管理領域込みのブロックの話をしているので、さらにその前に管理領域が、って話にはならないっす(^^;
2006-10-02 月 00:15:33 | URL | kosaki #- [ 編集]

単純に「memalign()があるからmalloc()は最小アラインメントにあわせとけばいいよね?」な気がしてます。気がするだけですが。
2006-10-02 月 03:53:56 | URL | KAME #- [ 編集]

規格的にはそうなんだけど、それだと速度的によそのmallocに負けちゃうので、事実上ありえない選択肢ちゃうかなぁ・・・
たとえばx86だったらアライメントまったくしないと言っていますよね?
性能にすごいインパクトありそう・・・
2006-10-02 月 04:23:40 | URL | kosaki #- [ 編集]

noocyte です.おそれいります.

私も読書会参加したかったのですが,関西在住ですから….残念! (古)
最後に東京 (といっても本当の目的地は鎌倉) に行ったのは確か6年前….
私もお会いしたいのですが,いつになったらその機会が来るやら.
読書会,今後もビデオで拝見させていただけるとありがたいです.

といいつつ,実は今回の読書会のことを知ったのは
事前だったか事後だったかよく覚えていない.(^^;
えーっと確か,文字コードがらみのことを検索していてぇ,
hyoshiok さんのページに漂着してぇ,
あたりをうろついていたときに知ったんだったかな.
どえれゃーおもろそうやけど,どーせ遠いから参加でけへんわ,
と思っていたらビデオがあることを知って….

hyoshiok さんのページにコメントした内容については,
もう一度整理して自分のブログに書くつもりです.
そのときにはこちらにもトラックバックさせていただきます.
(もっとも,昨日は長い待機状態が明けて久しぶりに仕事にありついたので,
今後の忙しさによっては最悪週末ぐらいになるかもしれません.(苦笑))
2006-10-02 月 11:22:25 | URL | noocyte #CQQQRm1Y [ 編集]

>あと、今話しているアラインの話は管理領域込みのブロックの話をしているので、さらにその前に管理領域が、って話にはならないっす(^^;

え、SSEの例はユーザーに渡す領域が16bytesアラインされているってことですよね。
そうするとglibc mallocのsizeメンバーは一つ前の前の16bytesアライン領域にいるから、キャッシュラインが別になる確率が上がる、と思ったんですが。
2006-10-02 月 11:47:52 | URL | firewood #- [ 編集]

noocyte さん>
そうですか・・・
では、いずれ関西のイベントででも(*^-^*

fireweedさん>
これは僕の早とちり。もうしわけない
2006-10-02 月 19:07:31 | URL | kosaki #- [ 編集]

む、最小アラインメント=8バイトね。
2006-10-02 月 20:07:15 | URL | KAME #- [ 編集]

KAMEさん>
x86話でそれを行間から読み取るのはツラいっすよ(^^;
で、話をもどすと、たしかに現状のようなSSE命令使おうと思ったらアセンブラがほぼ必須の状況だとmemalignするぐらい全然苦にならないと思います。
いつもながら、議論のキレがいいっすね。
でも、現在Intelコンパイラとかが微妙に進めているように普通のC言語のコードからMMX, SSEコードを生成するようになると、コードを書く人はSSEとかをまったく意識していない状況が考えうるので、そのぐらいコンパイラが進化したら16byte alignに変更していくべきかな?
と思いました。
どうでしょうかね?
2006-10-02 月 22:31:30 | URL | kosaki #- [ 編集]

う~ん、メモリをセコセコ使いたい人もいますからねぇ。空間消費も無料じゃないわけで。スタック等の扱いが解決して一般に使えるようならSSEに対応したアラインメントもありなのかなぁ。とか言うものの、実はあまり判ってません(;_;
2006-10-03 火 03:50:40 | URL | KAME #- [ 編集]
本当は「malloc() が返すアドレスは8の倍数って知ってます?」にしたかったんだけど,「8」というのは CPU 依存の数字だし,一般には2の冪乗なのでこういうタイトルにした.そもそもこの記事を書くきっかけは,YLUG の「第67回カーネル読書会 (glibc malloc について)」
【2006-10-08 Sun 07:37:02】 | 生涯一プログラマの不定期日記:SHINOBI.JPのアクセスログ→CSV変換ツール公開中
YLUG の「第67回カーネル読書会 (glibc malloc について)」のビデオで,「mmap()/munmap() を使って 1MB アラインされたメモリ領域を得る方法」が紹介されていた.発表者のkosaki さんは,その方法を知って「腰を抜かした」と言っていたが,私は20年ほど前に同じようなこと
【2006-10-08 Sun 07:39:39】 | 生涯一プログラマの不定期日記:SHINOBI.JPのアクセスログ→CSV変換ツール公開中
前回の記事では,glibc malloc()がアラインメントの大きなメモリ領域を確保するために使用している方法について解説したが,今回はその領域を使って何をしているかということを,問題を一般化した形で解説する.問題非常に多数の要素 (子) を持つ集合 (親) を実現するデータ
【2006-10-08 Sun 07:41:18】 | 生涯一プログラマの不定期日記:SHINOBI.JPのアクセスログ→CSV変換ツール公開中
  1. 無料アクセス解析
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。