RPythonとPyPyとJITについてのメモ

始めに

これはインターネットアーカイブのためのメモです。

中身

Pythonインタプリタ by Pythonを記述する。 そうすると、RPythonのプログラムが書けるようになる。 RPythonでPythonインタプリタを作成することができる。 できたものは、「RPythonによるPythonインタプリタ……で、それはPythonで書かれている」ということになる。これ全体をFという関数とする。 そうすると、Fに対してPythonコードとinputを持ってくれば実行ができる。

ここもう少し一般化して、RPythonのインタプリタ by Pythonの役割を考える。

例えば、RPythonによるhoge言語インタプリタを持ってくるとする。 そうすると、RPythonのインタプリタ by Pythonに対して、RPythonによるhoge言語インタプリタと、hoge言語プログラム、inputを以てくれば、outputが得られる。 ここで関数の部分適用を考える。 つまり、RPythonのインタプリタ by Pythonに対して、RPythonによるhoge言語インタプリタを与えた状態を考える。 残り必要なのは、hoge言語プログラムとinputであり、これはちょうどコンパイラの動作と同じである。 (コンパイラも、hoge言語プログラムを与えてできたものに、入力を与えれば実行される。) つまり、RPythonのインタプリタ by Pythonというのはインタプリタ by RPythonを与えれば、コンパイラを生成してくれる何かになる。 ただ、実際はRPythonのインタプリタ by Pythonというのは、hoge言語プログラムだけ部分適用みたいなことをできないので、実際はインタプリタ生成みたいなものである。

PyPyとJITの話に移る。 Python処理系をRPythonで記述することを考える。(これがPyPyの実態ともいえる?) RPythonで書かれた処理系のプログラムは、順番にPythonプログラムと入力をちょっとずつ受け取って評価するみたいな処理になるはずである。 ここでRPythonのインタプリタ by Pythonが役に立つ。RPythonのインタプリタ by Pythonに対して、JITコンパイルの機能を与える。そうすると、Python処理系をRPythonで記述し、RPythonのインタプリタ by Python上で動かせば自動的にJITコンパイルの機能が備わることになる。 (RPythonのインタプリタ by Pythonにとっては、RPythonプログラムと入力としか見えない。) これの何がうれしいかというと、 PythonJITコンパイルを考える必要がなくなりRPythonのJITをすればよい。 RPythonはどこででも動く。 処理系を書く側はRPythonでインタプリタを書けば自動的にJITコンパイルの機能を持てる。 ということがある。

まとめ

PyPyは、RPythonで書かれたPython処理系だよ。 RPythonはPythonのsubsetでインタプリタを記述する言語であり、RPythonの処理系にはJITの機能があるよ。

参考

これが良い。 Motivating JIT Compiler Generation — RPython Documentation

これもよい。 Partial Evaluation, Futamura Projection And Their Applications · GitHub

これは図がよくわからない。 RPythonについて軽く | κeenのHappy Hacκing Blog

Github Education申請の学生証のアップロードで詰まったときの対処方法

概要

症状

Github Educationで学生証アップロードで画像をアップロードしても、同じページが再度表示され、目に見えるエラーが出てこない。

対処方法

(ページに書かれている基準内であっても、)画像サイズが大きいため、はじかれている可能性がある。 基準ギリギリまで画像サイズを小さくすることによって申請ができる場合がある。

経緯

Github Educationにて、「Please upload proof of your academic status」と書かれ、学生証のアップロードが求められる。 その際、適切に画像ファイルは選択できるが、いざSubmitボタンを押すと同じ画面に戻ってくる。この際、画面には特にエラーが出てこない。

開発者コンソール->Networkで、Preserve logをオンにして見てみると、POST通信でPayload too largeとはじかれていることがわかる。 これを調べると、同様に Payload too largeで困っている人 が見つかり、画像サイズが大きいとだめらしい。

今は確認できないが、そのページに書かれている最大サイズは1.2MBとかでそれを満たしていたはずだが、もう少しぎりぎりまで画像サイズを落とす必要がある。 実際に、画像サイズとその画素をぎりぎりまで落とすと申請ができたので、たぶんこれが原因で合っている。

Ubuntuに入れたNVIDIA driverのupdate

はじめに

update前の環境は以下の通り。

問題

本当は次のようにしたかったが不可能だった。

  1. 「ソフトウェアのアップデート」というUbuntuのアプリ->追加のドライバーで新しいドライバを選択
  2. 再起動

したがって、とりあえず追加のドライバーをaptでinstallしてみたが次のエラーで無理だった。

問題を解決することができません。壊れた変更禁止パッケージがあります。

解決

aptitudeに任せた。 するといくつかのパッケージ(cudaを含む)を削除して、driverをアップデートしてくれる。

再起動後、確認すると、aptitude先生によってversion 10.1のCUDA Toolkitが入れられたので、apt remove cuda-toolkitを行い、適切なバージョンのCUDAを適切な手順でインストールした。

今考えると、cuda-toolkitについては、removeとやるよりpurgeしたほうがよかったかもしれない。おそらくこれの影響でCUDAを入れなおしたらPATHを手動で通す必要があった。

今から予想する原因

おそらくもともとの環境にcuda-11-8をinstallしており、それがNVIDIA driverに依存しているから上のエラーを出していたのだと思う。 おそらく適切な手順は、

  • CUDAのremove(というかpurge?)
  • driverのupdate

と思われる。

NVIDIA driverをUbuntuに入れる

はじめに

NVIDIA driverをUbuntu 20.04 LTSに入れた際の手順です。 備忘録として残します。

手順

  1. ubuntu-driver devicesによる必要なdriverを確認とinstall
    • open, serverなしの無印版を選択
  2. Nouveauの削除
    • 適切に行う。OS起動のconfigに何かを記述した。
  3. reboot

cudaのinstall

適切なバージョンのcudaを見る。 今回は、localで入れた。 基本はそのままでよいが、最終行だけsudo apt-get install cuda-xx-xと変更し、正しいcuda versionが入るかを確認。

おわり

たぶん以上で行けたはず。

Windowsで自動でssh再接続~Bitvise SSH Clientを用いる~

はじめに

自宅にWindows PCがあり、Windows PCへ接続するためにssh ポートフォワーディングを用いて、踏み台サーバ経由で外出先からsshしています。

Ubuntuであれば、autosshコマンドを用いて、sshが切れた際に自動的に再接続させることが簡単にできます。 Windows PCで同じことをやりたいということで行ったことの備忘録です。

取りうる選択肢

次のことを行えば、自動で再接続させることができると思います。

  • Cygwinを用いて、autosshを用いる
  • Bitvise ssh clientを用いる
  • PuTTYというSSH Clientを用いて、接続が切れたときに再接続するバッチを何らかの方法で走らせる

今回は2番目のBitvise SSH Clientを用いる方法で行きます。 個人的にはこれが簡単だと思います。

Bitvise SSH ClientでSSHを行う

Bitvise SSH Clientのインストール

Bitvise SSH Clientのダウンロードページに行き、SSH Clientをダウンロード、インストールします。

ここは難しいことはないと思います。

Bitvise SSH clientでSSH接続する

今回は、SSH keyで接続する方法を説明します。

鍵を作る

まず、起動しLoginタブのClient key managerを開きます。

image.png

ここで、下のほうにGenerate newというボタンがあると思うので、そこを押し、いい感じに設定し鍵を作ります。

image.png

鍵を作ると、先ほどのClient key manager上で作成した鍵が表れていると思います。それを選択し、Exportと押すと、Public keyを得ることができます。 それをサーバに登録します。

SSHする

先ほどのLoginタブに戻り、いい感じにServerAuthenticationの欄を埋めます。 この状態で、Log inとするとSSHすることができます。

この状態でもうサーバが一時的にダウンしたとしても自動的に再接続される状態になっていると思います。

Port forwardingする

サーバ側の3389番ポートへの通信を、Windows PCの3389番ポートへ転送します。 この場合は、S2Cのタブを開き次のように設定します。

image.png

これでLog inすると、ポートフォワードができると思います。

PC起動時に自動的にSSH接続するようにする

プロファイルを保存する

左側のSave Profile Asで適当な場所に、clientの設定を保存します。

コマンドからClientを起動する

コマンドからClientを起動させることができます。 具体的には次のようになると思います。

BvSsh.exe -profile=C:\Path\to\hoge.bscp -loginOnStartup

これでバックでClientが立ち上がり、SSH loginした状態になると思います。

スタートアップに登録する

先ほどのコマンドをWindowsのスタートアップに登録します。 こうすることで、Windowsの起動時に自動的にClientが立ち上がりサーバに接続されます。 サービスとして登録するほうが正統らしいですが、いまのところこれで十分なのでokです。

おそらくスタートアップに登録する方法はいろいろあると思いますが、自分はショートカットを作成しました。

Windows+Rshell:startupを実行します。

image.png

そうすると、ファイルエクスプローラが起動するので、そこにBitvise SSH Clientのショートカットを作成します。 自分の環境では、リンク先として次を指定しました。

"C:\Program Files (x86)\Bitvise SSH Client\BvSsh.exe" -profile=C:\Path\to\hoge.bscp -loginOnStartup

この状態でタスクマネージャのスタートアップアプリを見ると、BvSsH.exeみたいにBitvise SSH Clientが登録されています。

以上で、外出する際は、PCの電源ボタンを入れていくだけでSSHされた状態になります。

おわりに

参考になれば幸いです。

参考文献

https://laubit.blogspot.com/2017/01/putty.html https://www.mazn.net/2020/10/2085.html https://yohei-a.hatenablog.jp/entry/20140902/1409629766 https://www.kmc.gr.jp/advent-calendar/ssh/2013/12/11/autossh.html#fn:bitvise

ISUCONに参加しました

はじめに

Twitter(現 X) で、ISUCONに参加する人が多く気になっていたことと、追加募集していたので応募して初めて参加しました。 参加した際にISUCONの当日にどのようなことを行ったかを記録する意味で記事を書きました。

また、自分はWebバックエンドについては初心者であり、あんまりWeb技術がわからないけどISUCON参加して大丈夫かなという人の参考になればうれしいです。ソロで参加したのでチームプレイみたいなところは全く参考にならないけど。

自分のスペック

タイトルのWeb初心者というのは語弊があり、NuxtやNextといったフレームワークJavaScript等を用いて、サイト作成は行ったことはあります。 また、基本的なプログラミングをする技術、CSの知識はあるので、その辺は全くの初心者とは違うと思います。

逆に次のことは全くやったことがないです。 - SQLを記述すること、SQL-likeなDBを用いること - Nginxをいじること - Goを読み書きすること - AWSを触ること

当日まで

流石に何をすればいいかわからないまま当日を迎えるのはまずいので、ISUCON本を読むことにしました。 当日まではデータベースを高速化する章までしか読めませんでしたが、いろいろな計測の方法と何を改善するか等がわかったので、かなり役に立ちました。

具体的には、次の知識が当日役に立ったと思います。

  • MySQLのslow queryのpt-digest-queryの使用の仕方
  • MySQLのindexについて
  • MySQLのexplainコマンドについて
  • Nginxのある程度の仕組み

また、過去のISUCONの解法を眺めてどういうことをやればいいんだということを把握見ていました。 初心者だしDBのindexを張るのと、N+1(いまだに何かわかっていない)を改善すればよいだろう!という印象を持ちました。

当日

初期スコアを出すまで

AWSには、Cloud Formationというスクリプトを用いて自動でサーバやらなんやら設定してくれるサービスがあるらしいです。 まず、それにyamlファイルを与えてサーバを立ててログインしました。 事前のAWS環境確認でもCloud Formationを使っていたのですが、その時は記事を参考に何が何だかわからないままyamlファイルを入れてスタックを削除していました。

とりあえず3つサーバを立てた後ポータルを見ると、ベンチマークのjobを提出するために「サーバを選択してください」という文字があったので、よくわからないまま1つを選択し、とりあえず出しました。

そうしたら3,471というスコアがつきました。

システムの把握と改善点の把握

3つのサーバがあるのはいいが、「3つのサーバをどうやって使っているんだ?」となって、まずサーバの中を眺めることにしました。 そうして3つのサーバのhomeを見るとすべてにwebappgolocalの3つのフォルダがあることに気づきました。 ここから、どうやら3つのサーバはすべて同じで、1つのサーバでベンチを回しているんだろうなと推測しました。

システムを把握した後、まずtopを用いてベンチを回している最中のCPUを使用率を見ると、MySQLのプロセスが高い使用率(9割ぐらい?)で推移し、かつCPU使用率が100%だったので、MySQLのクエリが悪さしているんだろうなということで、そこから改善することにしました。

SQLの改善

ISUCON本の通り、slow queryを吐き出させることにしました。 ISUCON本では、slow queryの閾値を0にすることを強くお勧めしていたのでそのように設定し、pt-digest-queryでlogを解析させました。

そうすると次のように出てきました。

# Profile
# Rank Query ID                     Response time  Calls  R/Call V/M   Ite
# ==== ============================ ============== ====== ====== ===== ===
#    1 0xF7144185D9A142A426A36DC... 282.0526 28.1%  11707 0.0241  0.01 SELECT livestream_tags
#    2 0x84B457C910C4A79FC9EBECB...  97.6360  9.7%  20885 0.0047  0.01 SELECT icons
#    3 0x42EF7D7D98FBCC9723BF896...  96.7173  9.6%  13677 0.0071  0.01 SELECT records
#    4 0xDA556F9115773A1A99AA016...  83.4807  8.3% 251972 0.0003  0.01 ADMIN PREPARE

一番遅かったlivestream_tagsのクエリは以下のものでした。

SELECT * FROM livestream_tags WHERE livestream_id = ?

explainで説明させるとたくさんのrowを見ていたので、これにindexを張るといいのかなということで張りました。 livestream_tagsのテーブルでは、ほかに

SELECT * FROM livestream_tags WHERE tag_id IN (?) ORDER BY livestream_id DESC

というクエリが走っていたので、indexを張る際には、

alter table `livestream_tags` add index `idx_tag_id_livestream_tags`(`livestream_tags` desc, `tag_id`);

としました。

explainで参照するrow数が減ったことを確認して、ベンチを回すと4,760というスコアがつきました。

SQLの改善2

引き続きtopを見るとMySQLプロセスが高いCPU使用率で依然CPU使用率がほぼ100%だったので、再びpt-digest-queryでlogを解析させました。

# Profile
# Rank Query ID                     Response time Calls  R/Call V/M   Item
# ==== ============================ ============= ====== ====== ===== ====
#    1 0x84B457C910C4A79FC9EBECB... 70.7090 16.6%  13069 0.0054  0.01 SELECT icons
#    2 0xDA556F9115773A1A99AA016... 57.1001 13.4% 157650 0.0004  0.01 ADMIN PREPARE
#    3 0x42EF7D7D98FBCC9723BF896... 47.3000 11.1%   6723 0.0070  0.00 SELECT records

今度はまた別のクエリがトップに来ており、goファイルを見るとアイコンを取ってくる関数が問題になっていました。

SELECT image FROM icons WHERE user_id = ?

DBに画像ファイルを載せるのはあんまり良くないと思い、何とかnginxに静的に配信させることを考えました。

Goを読むのは慣れていませんでしたが、func postIconHandlerfunc getIconHandlerでそれぞれ画像を更新、配信していることを見つけ、そこを何とかしようということになりました。 通常、更新がなければ簡単なんですが、そうではないのでここで苦慮しました。

nginxで配信はあきらめ、次にmemcachedを使うのはどうかということで入れてみましたが、これもそんなに効果はなく4,830とか4,382ぐらいのスコアでした。

結局、先ほどのクエリをexplainで見てみると、idで検索しているのにも関わらず数row分見ていることに気づき、user_idでindexを張りました。 これが当たり、スコアが6,196ぐらいまで伸びました。

SQLの改善3

pt-query-digestで確かめながら遅いクエリから順次indexを張っていくことにしました。

1つ目はdnsのクエリです。

SELECT content,ttl,prio,type,domain_id,disabled,name,auth FROM records WHERE disabled=0 and name='pipe.u.isucon.dev' and domain_id=2;

このクエリに対して、disablednamedomain_idにindexを張りました。 スコアはこれで5,300ぐらいまで下がったんですが、名前解決数が2,200程度から7,700程度まで上がりました。

次にこれです。

SELECT IFNULL(SUM(l2.tip), 0) FROM users u
        INNER JOIN livestreams l ON l.user_id = u.id    
        INNER JOIN livecomments l2 ON l2.livestream_id = l.id
        WHERE u.id = 113;

このクエリを改善する必要があるのですが、INNER JOINという初めて見るものを使っているので少し時間がかかりました。 このクエリを各ユーザごとに回しているので、始めはbulk selectみたいなことができないのかなと思いました。 でも、よく見るとusersテーブルを参照する必要がないので、以下のように変えました。

SELECT IFNULL(SUM(l2.tip), 0) FROM livestreams l
        INNER JOIN livecomments l2 ON l2.livestream_id = l.id
        WHERE l.user_id = 145;

これで、スコアは5,566ぐらいで変わらないのですが、pt-query-digestの結果が変わったので良かったかなと思います。

最後にthemesテーブルが一番遅いと出ました。これは単純にuser_idにindexを張りました。

SELECT * FROM themes WHERE user_id = 1049

これでスコアが6,100ぐらいまで伸びました。

最終的に何回か提出してよかったものを最終スコアとし、6,400ぐらいでした。

さいごに

最後には、CPU使用率が100%に届いていなかったので、GoのMySQLとのconnection数を増やしてもよかったかもしれません。

また、結局時間がなくマルチサーバに対応することをできませんでした。 なんとなくDBの環境変数を書き換えればできるのかな?と思っていますが、実際にどうなのかはわからないままです。

付け加えると、DBにindexを張っていただけなので、もう少し別の高速化(N+1とかbulk insertとか)について今後理解できたらいいなと思います。

StockhamのFFTについて

はじめに

この記事は、以下の記事の続きで書かれています。 以下の記事を読んでいただき、その後この記事を読まれるのが一番読みやすいと思います。

fushigu.hatenablog.com

記法について

$N$を$2^p$とします。 多項式$F(x)$を数列$A_0,A_1,\ldots,A_{N-1}$を用いて、

\begin{align} F(x) := \sum_{j = 0}^{N-1} A_j x^j \end{align}

と定義します。 また、多項式$E,O$を$F$に依存する形で、

\begin{align} E(x) &:= \sum_{j = 0}^{N/2} A_{2j}x^j\\ O(x) &:= \sum_{j = 0}^{N/2} A_{2j+1}x^j \end{align}

と定義します。

StockhamのFFT

大前提としてFFTは、分割統治法を用いて問題を半分にしていき、一番小さいところまで来たらまとめあげるという形でした。 具体的には、多項式$F(x)$を小さい多項式$E(x),O(x)$に分割し、それぞれにFFTを計算します。 その後、まとめあげるという形を取ります。 まとめる際、用いる漸化式は以下の形をしています。

\begin{align} F(\omega^k) = \left\{\begin{matrix} E(\omega^{2k}) + \omega^kO(\omega^{2k}) & (k\leq N /2 - 1\text{のとき})\\ E(\omega^{2k - N}) - \omega^{k - N/2}O(\omega^{2k - N}) & (k\geq N /2\text{のとき})\\ \end{matrix}\right. \end{align}

Cooley-TurkeyのFFTは、このまとめる際に2つの値から2つの値を導出する点を用いて、in-placeにFFTを計算していくことを行いました。 しかし、うまいこと2つの値から2つの値に導出するために初めに係数$A_k~(0\leq k\leq N - 1)$を並べ変えてから計算を行います。 この点をどうにかしたいというモチベーションがあります。つまり、$A_0,A_1,\ldots,A_{N-1}$という順番で入った状態を入力とし、$F(\omega^{0}),F(\omega^{1}),\ldots,F(\omega^{N-1})$という順番で出力を求めたいです。

さて、これを実現するためにどうすればいいでしょうか。 まず、in-placeで計算を行う点をあきらめます。具体的には係数が入っていた配列のほかに長さ$N$の配列を用意します。これら2つの配列を交互に使いまわすことで漸化式を計算していくことを考えます。 これは、競プロでDPの問題でよく見るメモリ節約術ですね。

はい、以上でStockhamのFFTの説明が終わりました……ということにしてもいいのですが、具体例を見て終わりたいと思います。 ここでは、実際に$N=8$での例を見たいと思います。

係数の分割は次のように行われます。

\begin{align} \text{0段目}&&&&\{0,1,2,3,&4,5,6,7\}&&\\ \text{1段目}&&&&\{0, 2, 4, 6\}, & \{1,3,5,7\}&&&\\ \text{2段目}&&\{0, 4\}, && \{1, 5\}, & \{2, 6\}, &&&\{3, 7\} \end{align}

さて、ここから入力を入れ替えずにどうやって係数をまとめるか?ということが問題になります。

上の分割を見ると2段目では、$A_j, A_{j+4}~(0\leq j\leq 3)$というペアでまとめ、それぞれ$2$のFFTの結果を求めることになります。 同様に1段目では、$A_j, A_{j + 2}, A_{j+4}, A_{j + 6}~(0\leq j\leq 1)$という組み合わせになり、それぞれ$4$個のFFTの結果を持つことになります。

後は、これを管理しやすい方法で1次元の配列に並べればよいです。 具体的には、2段目では$4\times 2$という形で、1段目では$2\times 4$という形で、1次元の配列にパックしてあげればよいです。

おわりに

ちょっと雑になりましたが、名前がついている割に中身はすごいことはやっていないと思います。 ただ、このような計算テクニックで並列化しやすい等のメリットが大きいのだろうと思いました。