tqdmをムリヤリprocess safeっぽくするdirty hack

生物界で最大の目(光を検知する器官)を持っているのはダイオウイカおよびダイオウホウズキイカと言われ、その大きさは30〜35cmほどにもなるのだそうです。

さて、世界70億人のPythonプログラマが手放せないのが、tqdmというプログレスバーを簡単に表示できるようにしてくれるライブラリです。
しかしながらtqdmは(当然と言えば当然ですが)複数のプロセスから1つのプログレスバーを管理することができるような設計にはなっていません。
たとえば高速化のためにmultiprocessingを用いて並列処理をしながらプログレスバーを出したいとき、tqdmはそのままでは使えないことになります。

例えば、下記のようなコードで単にtqdmのインスタンスを子プロセスに渡して中でupdateをすると…

import tqdm
import multiprocessing

def worker(pbar):
    pbar.update()

ar = [i for i in range(100)]
with tqdm.tqdm(ar) as pbar:
    jobs = []
    for t in ar:
        job = multiprocessing.Process(target=worker, args=(pbar,))
        job.start()
        jobs.append(job)
    for job in jobs:
        job.join()

実行結果はこんな感じ。

% python usage.py
  1%|▉                                                                                                 | 1/100 [00:00<00:25,  3.89it/s]

こんなふうに、100%まで行ってくれません。
端的に説明すると、100個forkされた内部カウント0の状態をそれぞれ+1するのが100回走るだけ、だからです。

じゃあ内部カウントが常によろしく増えるために、内部カウントを無視して共有メモリで常に正しくカウントしてればいいよね、っていう単純な発想による汚いハックをしてみました。

Continue reading

大量のサーバに同じファイル(でかい)を効率的にコピーする

インド洋では、夏頃にイワシの大群が押し寄せるサーディンラン現象というのがあるのだそうです。その個体数、にわかには信じがたいですが億のオーダーにもなるとのことです。すげーな!

さて、あるサーバ1台が数百GBにもなる巨大なファイル(群)を持っているとします。
このファイル群を、そのサーバに接続された他の複数(大量)のサーバのローカルディスクにコピーしたいです。
以後これを便宜的にbcast cpと呼ぶことにします。

rsyncを1台ずつ回すのが頭悪い方法なのは明らか。当然NFSなどを立てて共有するというのも本質的にはそれと同じ。
同僚のiwiwiさんがちょうど集団通信アルゴリズムの話をしていたのを聞いて、それを活用して効率的にファイルをバラまくようなアドホックなスクリプトを書いて、ときどき使えそうなのでまとめておきました。

「やってみた」ぐらいの話なのでガチ勢の方たちにはƱ”-ʓ飲んで寝ていてほしいです。

Continue reading

2行N列のndarrayを一発で(1行目≦2行目)にするnumpy芸

各国における国民1人当たりの魚の年間消費量をランク付けすると、1位はモルディブなんだそうです。土地柄を考えると妥当な結果と言えそうで、6位の日本の2倍以上です。

Numpyにて、行同士の大小関係を強制したい、つまり「2行N列のndarrayがあるんだけど、各列ごとに、常に1行目の値が2行目よりも小さい値を取る必要がある」「そうでない列の値を強制的に上下交換させたい」という状況に遭遇しました。
生ループ回してひとつひとつチェックしては…とやってもいいんですが、それをPython側でやっていてはパフォーマンス上どうかなということで、Numpyのインデクス芸・スライス芸・ブロードキャスト芸あたりを駆使してやってみました。

もちろん、N行2列のndarrayの列間の大小関係を統一するのも同様に可能。

インデクシングなどの詳細の説明はここではしません。
日本語であればこのあたりがわかりやすそう(まだ見てない)。

性能やいかに?

Benchmarker.pyを使って、実行時間を比べてみました。
比較対象は、まぁ何も考えずに書くとそうなりますわな、というような雰囲気のコード(だとおもう)。
#ところで標準の時間計測モジュールtimeitが最高に嫌いなんだけどあれなんであんなふうになってしまったのかな。。。

こちらが実行結果。
proposedが本記事で紹介した黒魔術、conventionalがシンプルな方法。

##                             real    (total    = user    + sys)
col-proposed                 3.6327    3.6200    2.8100    0.8100
row-proposed                 3.6977    3.6900    2.8700    0.8200
col-conventional            49.9127   49.8600   49.7600    0.1000
row-conventional            51.3075   51.2600   51.1600    0.1000

だいたい14倍高速ですね。
メモリ上では行オーダーで格納される都合上、row-*とcol-*の間で速度差が出るのかなと思いましたが、たかだか2行/2列なので、関係ない模様(σが未知なのでなんともいえませんが。。)。

Pythonの高速化の鉄則は『生Python書くな』に尽きますが、それが改めて示された形になりましたとさ。

ただこのようなコード、後から読んだり他人に読ませたりするのはとても困難なので、あまり多用しないようにしましょう。

SSEとAVXで高次元ベクトルの内積計算を高速化してみた

世界最速のお魚と言えばカジキ類で,泳ぐ速度は時速100km/hを超えるとか.55ノット程になるのでこれはMk-48魚雷にも匹敵するほどです.
一方ちょっとチートな高速お魚としては,お馴染みトビウオが飛行中に最大70km/hほどに達するとか.
今日はそんな若干チートな高速化のお話(?)ということで,SSE組み込み命令について.

SSEやAVXといえばお馴染みSIMD命令で,それをプログラムから構造体と関数の形式で高移殖に記述する方法がSIMD組み込み関数(SIMD Intrinsic)なわけですが,これを使ってごく典型的なベクトルの内積計算を高速化してみました.

ベクトルの内積の高速化と言えば星の数ほどもされてる話なわけで,いまさら魚の情報なんか役に立つ気は全くしないのですが,純粋に自分でやらないとわかんない>< ということで,

  • とにかく書いてみよう
  • 効果の程はいかに?

を調べてみたくて,やってみました.
もちろん完全に最適化されたコードでもなく,この記事の内容は無保証です.

参考は主に
SSE.浮動小数点演算手動最適化は本当に効果的なのか – デー
インテル(R) Advanced Vector Extensions (インテル(R) AVX) の組み込み関数
です.

Continue reading