tw.log

https://twitter.com/kinaba のログ (twilog の方が便利です。)

<<newer (latest) older>>

20100719 01:10 @kikairoya 規格はさておくとして「deque::push_backは真に定数時間で処理」できてる"実装"ってあるんでしょうか。
20100719 01:11 reallocがmremap http://shinh.skr.jp/m/?date=20100706#p01 ならdequeの場合PODしか動かさないのでvectorと違っていける気がするけど、現状インターフェイス的に結局allocatorを通してるのでC++レベルでO(N/Pagesize)のコピーしちゃってる気が
20100719 01:13 @kikairoya 追加した1ページへのポインタ(std::array<T, PageSize> * 的なもの)を、上位の std::vector<std::array<T, PageSize> *> 的な物にpush_back的なことをする必要があります
20100719 02:56 http://d.hatena.ne.jp/nuc/20100716/p17 理論的に実行時の動きを考えるとO(n**2)「…回の加算とcons/de-consを行う」まで言えても、それ以上(例えばO(n**2)の実行時間となる等)はこのレイヤでは何も言えぬので言わぬが吉と思うの
20100719 03:30 @ainsophyao 最初8行は同意するのですが、はい、「理論的に実行時の動きを考えるとO(n**2)」という部分、直前まで時間の話をしているのでここも「(理論的には)時間のオーダがO(n**2)」と読めてしまうのですが計算モデルを示さず時間の話をするのは危ういなあと思いました
20100719 03:34 適当なGCの実装を仮定すると実行時間がO(n**2.6)になるようなモデルは作れると思いますし、実際、例のコードでもマイナーGCヒープを思いっきり大きくすると綺麗に演算回数に比例した実行時間になる(なったはず)ので、その辺考えずに"時間の"理論評価をしても意味が薄いと思う
20100719 03:52 @ainsophyao アーキテクチャ依存のような気がします。自分の手元の環境だとfibではそんなに"遅く"ならなかったのですが、1:1: を 0:0: に変えてみたところ superlinear な実行時間に見える実験結果になったのでそれで実験したりしてました。
20100719 04:01 一見O(n)に見えるコードの裏で、メモリアロケータがそれ以上に時間かかっていた事例 http://blade.nagaokaut.ac.jp/cgi-bin/vframe.rb/ruby/ruby-dev/13652?13515-14611
20100719 12:09 @gusmachine はい。なので「かかっていた」と書きました。GCかInteger加算かメモリ階層が原因かわかりませんが、fibがO(N^2)の実行時間にならないのは修正された方が良いというのも同意ですが、そう簡単に「まずい」と斬れるほど自明になしとげられる条件とも思えない…
20100719 12:16 @TuvianNavy CFGは全部DLINSPACEに入ります [Lewis&Stearns 1965] http://rjlipton.wordpress.com/2009/04/05/savitchs-theorem/
20100719 12:49 ところでこれ http://twitter.com/kinaba/statuses/18855101576 は言っていることが全然おかしかった。加算もconsもO(N)回で1回1回の加算がO(N)桁の加算である云々かんぬんだ
20100719 14:10 fib::[Int] にして -O2 -prof http://gyazo.com/649b31900dad5c7460b1af3c05d6ee68.png ヒープサイズ変えると、こう、アロケーションの段階は大差ないけどその後に長々し尾が。
20100719 14:22 あら +RTS -S とかいう素晴らしいオプションがあるじゃない
20100719 14:44 http://www.kmonos.net/wlog/sub/fibrep.txt 745行目辺り(おそらくzipWith終わった辺り)からのマイナーGCが、「恐怖!全オブジェクトが生存するコピーGC」になってるっぽいのを差引いてもそれ以上に遅くなってる気がするんだけど何故だろな
20100719 14:47 @kikairoya @Cryolite たとえば ringbuffer<T*> 1つで実装できますよね、という話かな
20100719 14:49 いかんプロファイル用コードが混ざっていた修正版up。505行目辺りが真ん中 RT http://twitter.com/kinaba/statuses/18894023788
20100719 15:34 ((!!).zipWith)の段階では、consする計算用サンクが即死して他が生存するので3/4が生き延びる。足し算実行する段階では、consセルや足し算結果のIntが先頭から次々不要となるように一見見えるがこの頃にはconsセルが全部親世代に昇格してるのでマイナGCでは消えない
20100719 15:36 で、しかもそうするとつまり新世代ヒープに居る足し算結果のInt達(リストってunboxされてないですよね確か)が全員旧世代のconsセルから指されてる感じになるので、すごい大量に旧→新ポインタがある状態での新世代GCは漸近オーダのレベルで遅くなったりする事もあるんじゃないですかね
20100719 15:38 という仮説を立てたがGCの実装とか読む気力がないしghcでのIntの扱いもよくわかってない…
20100719 15:55 fibの件 http://shinh.skr.jp/m/?date=20100719#p08 ほへー
20100719 16:25 すごく夏バテ状態
20100719 18:51 スーパーで安くなってたペットボトル飲料何本かとボトルのシャンプー1本を買ってレジに並ぶときの、「僕は決してこのシャンプーを飲み物と間違えているわけではないので、決してこれをゴクゴク飲んだりしたいわけではないですから心配しないで下さいおねがいします」 と念じてしまう度は異常
20100719 18:59 "音声認識用の自然言語を作るとしたら。" http://d.hatena.ne.jp/tihara/20100501#p1 読んでた。初めてPalm http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E3%82%A3%E3%83%86%E3%82%A3_(Palm) を使った時に、アルゴリズムのために文字すら変える!未来っぽい!!と思ったのを思い出す

<<newer (latest) older>>

presented by k.inaba (kiki .a.t. kmonos.net) under CC0