ToDo:
以前から glibc qsort て std::sort より速いこと多い気がするなーとか思ってたんだけど、まあ今回もそれで、ただ Mac だと std::sort の方が速いぽい (Apple qsort が遅いのか libc++ std::sort が速いのかどちらかは謎) し、うーんとか思ってて。
まあそもそも文字列は汎用ソートにかけるべきじゃないだろーということで、色々調べてて、なんかなるほどこういうのがあるのかーとか思ってたりしたんだけど、その全てがこのリポジトリに入っていた
https://github.com/bingmann/parallel-string-sorting
感動的すぎるね。。秋葉さん作のソートも入ってる
(01:35)
立って仕事してたら腰痛くないなーと思ってたけど、先週末からひどく痛い。マッサージの人が立ってても腰痛くなるのはスタンディングデスクあるあるですよー気をつけてね、て言ってた翌日くらいから痛くなったので、なんかの呪いをかけられたのだろうか。
今の状態だと立っても痛くて、座るともっとひどくて、寝ると大丈夫ではあるので最悪という感じではないが、まあつらい。筋弛緩剤飲むと結構効いてるぽいのでまあそれでほっときゃマシになるかな
(19:34)
あっ終わってしまいそうだ。なんかあのスレ流し見するのが日課になってた。
こいうのでいうと、在特会 vs しばき隊とかも似た構図かなあと思っていて、被害を被るのは、「うーん、どっちも、えー…」と思ってる人達ってのが。そいう人ってどっちかよりの意見を持ってたりもすることもあるのに、先鋭化した人達は俺より敵側にいるやつは全部敵、てなっちゃうんだよなあ
ちょっとずれて、なんとなく手塚治虫のマンガとかに出てきた、百姓が「おさむらいさんがいつも戦争してるけど損するのは百姓ばっかだべ……」とかぼやいてるシーンを思い出すのだけど、大きな違いは百姓がバカじゃないってことがあると思う。がまあ見るからに matz 以上に喋った人は被害は被ってるんだよなー
(22:42)
今日もらったバグレポをエアデバッグしてて、あーこういうことだなってアタリがついた事例
(gdb) p main $1 = {int ()} 0x400596 <main>
つまりシンボルのある綺麗なバイナリです
(gdb) r Starting program: /ssd/test/a.out Program terminated with signal SIGABRT, Aborted. The program no longer exists. (gdb) bt No stack.
abort してるのに "The program no longer exists." ヘンすぎるやろ。というわけで以下のコードがこういう挙動を起こすことに気付いた。なるほどねー
$ cat vfork_fail.c #include <stdlib.h> #include <unistd.h> int main() { if (vfork()) sleep(1); else abort(); }
(20:33)
なんじゃこれ
https://bugs.ruby-lang.org/issues/12004
全体的に良い自転車小屋だなーと思いながら流し読みしてたら、極右によるなりすましまで現われてすごい
(06:42)
で、その極右は実は当初のやつを採用させたい派による、なりすましのなりすましであり、ほら code of conduct committee 必要でしょー、と実演してるという陰謀論
(06:46)
アンドロ、完全にビルドするもの無い時に make て叩くとむっちゃ速い時で 6 秒くらいかかる。普通は 8 秒とかそのくらい。 kati 以前は 2 分だったので、まあいいちゃいいんだけど、やっぱり 8 秒はちょっとイラっとくる…気がする。
2分から10秒にするならすごく頑張る価値があるけど、 8 秒のものを速くするならちょっとした努力ですむと嬉しい。
むっちゃ速い時の 6 秒、内訳を見ると大雑把に言って、 4.5 秒が ninja で 1.5 秒が kati の責任。
ということでとりあえず ninja でしょ、ということで書いた ninja のパース結果をバイナリとして保存するパッチ。入ってくれると 3.5 秒かかっているパース部分 1 秒になるので、合計で 4.5 秒だったのが 2 秒くらいになる。もうちょっと速くすることもできる(が相対的な嬉しさはたいして無い)。
https://github.com/shinh/ninja/commit/1ac857f8ca7ce5dcc8999b9b6d270bbae6074af4
これを入れてもらえると ninja 2秒 kati 1.5 秒となって、 kati 側の方が気になる。こっちは thread で並列で処理すると速くなるに決まってる処理なので、やってみたら 0.4 秒ほどになった。
https://github.com/google/kati/commit/6bbf9e29fcb069871a9153e845242ed6fe0e1b94
2つひっくるめると 6 秒が 2.5 秒ほど、まあそりゃ、もちょっと速い方がいいけど、費用対効果としてはこんなもんかなって感じ。
C++11 の lambda+thread で thread pool 書いてみたりした。書きやすい感ある…がまあ pthread は基本的な API はだいたい使い方覚えてるので、ぶっちゃけこっち書く方が時間かかるというのはある
https://github.com/google/kati/blob/6bbf9e29fcb069871a9153e845242ed6fe0e1b94/thread.cc
thread_local キーワードて Mac だとサポートされてないのかー、と今気付いた。修正しないとか。まあだいぶ前に書いたこれ使えばすぐできるだろ
https://chromium.googlesource.com/arc/arc/+/master/src/common/thread_local.h
さて
Makefile が書き変わったりして kati がこれは処理しなおさなあかんなーと気付いた場合、 Makefile をパースして評価しなおすんだけど、こっちはもっと時間がかかる。大雑把に言って
てとこ。最初の部分、これは一番気合が入ってる場所なので、まあそれなりに速いと思う。 GNU make が2分かけてる部分だし。
残りは割と適当なんだよな。こっちはまあ、 23 秒の部分は速くするの難しいと思ってて、残りの 21 秒頑張ってもたいした効果ではないので、ラクに速くできる部分があればやる…くらいかなと思う。
まあ普通に考えてスレッドで散らせ、ってことになると思う…がまあ、これはめんどくさい部分も多い。コードが汚なすぎるんだよな。あと順番が重要な処理もある。
グラフ構造みたいなのをトラバースするのを並列にやる必要がある。一つ一つのノードを処理するのはすごく速いけどノード数が多いので、新しいノードを見つけるたびにタスクキューに入れる、みたいなことすると待ち合わせの時間ばかりかかることになると思う。
たぶん分岐があったら、一定の確率で分岐先をタスクとして実行させる、とかでいいんだと思う。って parallel GC てそんな感じなんだっけ?
(20:28)
実装した。で測ってみると 140816 サイクルで、 50MHz なのでたぶん 2.81632ms 。シリアルのオーバヘッド 5,6ms くらいだと思ってたけどそれよりデカいななんか。。まあ命令数はコンテストサイトと比較すると妥当な感じなので、まあそんなもんな気がする。
2サイクルかかる命令があるので、GDBのシミュレータだと 121322 サイクルで、 2.426ms の計算。
そういえば授業でやってる人達に比べてずるい点として、コンパイラ自分で作ってなくて clang が最適化してるので、サイクル数少なめってのがある。ソートも glibc のやつ使ってるだけだし。
(01:42)
http://www.lab3.kuis.kyoto-u.ac.jp/~ktakagi/le3a/
を教えてもらった。これは FPGA がだいたい同じスペックなのと
http://www.lab3.kuis.kyoto-u.ac.jp/~ktakagi/le3a/contest/index.html
このコンテストが東大と違って浮動小数の実装がいらないので、目標としてはとても良い気がした。
とりあえず実機で測ってみると、 9.98ms ということで 28 倍遅い。シミュレータによるとサイクル数はだいたい 300k で 6ms ほどで終わって欲しいところなんだけど、たぶん RS232C で測定終了マーカ送ってる部分で遅れが出てるか。
それ以外にもいろいろ違いがあって、まず記録の数字はサイクル数少なすぎる。僕が libc の qsort 使ってるせいでムダなオーバヘッドあるのかなーと思うので、とりあえずそれは直そう。
あと京大のやつは 16bit より広いバス使っちゃダメ、て言ってるのに僕のは使ってる。まあこれは C 言語側で 32bit int 使って計算するようにしてるから、基本的には僕に不利に働くか同条件と言えるんじゃないかな…
(22:19)
このへんちゃんとやってからパイプラインに進んだ方がよさげ。
(22:56)
たいていの命令は dest, src1, src2 と並んでるわけだけど、一部の命令、というか論理演算は src1, dest, src2 と並ぶ。これヘンだなむかつくなって思ってたんだけど、きっと設計時のスーパースカラから来てるんだな。
たぶん計算の命令と load or store or 論理演算が同時に実行できるようになってて、 load/store アドレスのレジスタて書き変わるかもしれないので(要は push/pop だ)、ぱっと見不自然に見えるけど、真ん中が dest になるんだなあ。
(21:47)
前 | 2025年 7月 |
次 | ||||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。