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