文字列の先頭への追加に対する最適化を期待していいか？

paulownia.hatenablog.com

文字列型が immutable な言語では、文字列にループで文字を追加していくようなコードは、 Java でいえば StringBuilder などの方法を使えというのが昔から言われていた。しかし、 Java でも Python でも、文字列の右側に追加していくコードは最適化されるようになっており、現代では処理系の最適化を前提に出来るなら、読みやすくなる方が良いという風に常識が変わってきていると思う。

しかし、今回クソコード呼ばわりした left-pad のループは、文字列の左側への追加だ。静的型を元にコンパイル時に最適化出来る言語ならともかく、実行時に振る舞いを見ながら最適化するような言語で、処理系が文字列の先頭への追加を最適化してくれることを前提にして良いものだろうか？少なくとも Python はそこまではやってくれない。node.jsではどうだろう？

追記：記事を公開した時に書いていたコードにバグがあり、結論が180度変わりました！

'use strict';

function leftpad1(str, len, ch) {
  //str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

function leftpad2(str, len, ch) {
  str = String(str);
  if (!ch && ch !== 0) ch = ' ';

  len -= str.length;
  if (len < 1) {
    return str;
  }
  var pad = "";
  for (var i=0; i<len; i++) {
    pad += ch;
  }
  return pad + str
}

function leftpad_repeat(str, len, ch) {
  str = String(str);
  ch = String(ch);
  if (!ch && ch !== 0) ch = ' ';

  len -= str.length;
  if (len < 1) {
    return str;
  }
  return ch.repeat(len) + str;
}

const count = 1000000;

for (var len=4; len<=128; len*=2) {
  console.log("pad length", len);

  console.log("leftpad1", leftpad1('aaaa', len, 0));
  console.log("leftpad2", leftpad2('aaaa', len, 0));
  console.log("repeat  ", leftpad_repeat('aaaa', len, 0));

  console.time('leftpad1');
  for (let i = 0; i < count; i++) {
    leftpad1('aaaa', len, 0);
  }
  console.timeEnd('leftpad1');

  console.time('leftpad2');
  for (let i = 0; i < count; i++) {
    leftpad2('aaaa', len, 0);
  }
  console.timeEnd('leftpad2');

  console.time('leftpad_repeat');
  for (let i = 0; i < count; i++) {
    leftpad_repeat('aaaa', len, 0);
  }
  console.timeEnd('leftpad_repeat');
}

結果 [ms]

padding len	4	8	16	32	64	128
left-pad	21	118	265	491	959	1755
左追加除去版	19	81	273	483	875	1623
repeat	38	98	145	171	197	215

結論: やはり左追加を最適化してくれることを前提にするのは間違っている。

結論: 元の実装でも十分速い。JS処理系の文字列処理最適化は相当賢い。クソコードとか言ってごめんなさい。

Wheel が Linux でもバイナリパッケージに対応しました

PEP 0513 -- A Platform Tag for Portable Linux Built Distributions | Python.org

今まで Windows と Mac では、ビルド済みのバイナリ形式の拡張モジュールを wheel にして配布することができました。

WindowsやMacに比べてLinuxは環境の差が激しいのでバイナリ wheel に対応していなかったのですが、有名なディストリであればだいたい動くようにするためにどうすればいいか (glibc の古いAPIしか使わないなど) を勧告としてまとめて、十分実用的だと判断されたようです。（ただしこれは勧告であって、実際に pip や PyPI でこのルールに則っているかチェックされるわけではないようです）

manylinux1 policy

性質上、何らかのライブラリのバインディングを提供する拡張モジュール (例えば libxml を使う lxml など) で利用するのは難しそうですが、スピードアップのために重い処理を拡張モジュール化しているケースでは利用しやすいはずです。

特に今 Python を盛り上げているデータ・計算系は、ユーザーが専門のプログラマとは限らず、CやC++が難しいからPythonを使ってる人も多いので、インストールするのに必要な（トラブルシュートにCの知識を要求する）ステップが不要になるのはとても良いことです。

個人的に期待しているのは、今までインストールのしやすさのためにできるかぎりC言語オンリーで書いていた拡張が、RustやGoなどで書いて配布しやすくなることです。ヘッダーオンリーの pybind11 を使って C++ も使えるかも。

とりあえず PEP をよく読んで、自分の作ってるライブラリがこの勧告に準拠できるかよく確認するところから始めましょう。

依存するパッケージは厳選しよう

japan.zdnet.com

JS界隈が大騒ぎになった事件だけど、こういった事件自体は完全に防ぐことは不可能だと思う。

今回は依存ライブラリが削除されるだけで済んだけど、 npm install するだけで ~/.ssh ディレクトリを zip にしてどこかに送信するような悪質な攻撃であれば、単にCIが止まるどころでなく、世界中のエンジニアの秘密鍵がばらまかれてあちこちのサーバーにssh可能な事態になったわけで、そんな悪質な攻撃を bugfix なマイクロバージョンアップとして公開される事もありえたわけだ。

第三者のパッケージに依存するということは、それだけのリスクを背負い込むということだ。だが、逆に外部のライブラリに依存しないようにすると、生産性が落ちてしまう。 なので、コードを読む、信頼できるメンテナの公開しているパッケージを選ぶなどといった方法で、リスクとメリットのバランスを取って行かないといけない。

信頼できるパッケージを選ぶ手段の一つとして、既に信頼を集めている人やプロジェクトが信頼しているものを信頼するという方法がある。例えば Babel を使うことを選択した場合、 Babel が依存してる全部のパッケージも信頼して自分のマシンにインストールするということを選んだ訳で、なら自分のプロジェクトでも同じパッケージに依存するというのは合理的な選択のはずだ。

さて、今回の問題で驚いたのは、大混乱を招いた left-pad が、ある程度の技術があるプログラマが見たら一目でクソコードだと判断するような代物だったことだ。

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

渡された文字列 str に、 ch で指定されたパディング文字を左に追加することで、指定された長さの文字列にする（右寄せする）コードなのだが、「文字列の左側に1文字ずつ追加する」コードがクソなのは多くの言語で共通の認識だろう。実際、事件の後、パフォーマンスを改善するプルリクエストが4件も立て続けに来ている。 https://github.com/azer/left-pad/pulls

問題は、たった17行のコードに、こんなに明らかな問題があるのに、事件が起こるまで誰にも気づかれずに、 Babel を始めとした大量のプロジェクトで利用されていたことだ。 僕は JSer じゃないので憶測だが、この開発者がJS界で超有名人で信頼されていたというよりも、「Babelも使ってるし」といった感じでどんどん依存が広まっていったのでは無いだろうか？ Babel の中の人はそこまで考えて依存するライブラリを選んでいただろうか。（Babelよりも先に left-pad に依存していた有名プロジェクトがあったらごめんなさい）

外部のパッケージに依存することには大きなリスクが有ることを認識した上で、それでも利用することで得られるメリットが上回っているか、良く考えよう。

特に多くの人に利用されるOSSプロジェクトでは、そのメリット・デメリットがそのプロジェクトだけでなくコミュニティ全体に「◯◯が使ってるからウチも使おう」という基準で広まることまで考えて、より厳選しよう。

できれば依存するライブラリのコードを読んで、他人におすすめできるコードかどうか確かめ、そうでないならより良い別のライブラリを探すなり、プルリクエストを出すなりしよう。

あわせて読みたい: postd.cc

GAE が Python 3 に対応しました

今日、 GAE が Ruby と node.js をサポートするという発表がありましたが、実際のところ、今まであった Managed VM が GAE flexible environment と名前を変えたようです。

そして GAE flexible environment の公式イメージとして、 Ruby, node.js などに加えて、 Python 2.7, 3.4 もあります。 つまり、「GAE が node.js に対応した」と同じレベルで「GAE が Python 3 に対応」しました。 「Ruby や node.js に対応したのに Python 3 対応しないのかよ！」ということはありません。

とはいえ、昔からあるGAE (GAE standard environment) では、Python 2.7, Java, PHP, Go のサポートだけで、 GAE の大きな魅力だった無料枠が使えるのもこれらの言語だけです。

無料枠が提供できた理由は、インスタンスをゼロまでスケールダウンできる（リクエストが来てからインスタンスを立ち上げられる）からなので、今後 flexible environment の起動速度が改善されたらまた状況は変わるかもしれません。

最近出たPython本2冊紹介

1冊めは入門書。結城さんの Tweet を見て知った。 www.amazon.co.jp

プログラミング自体が初めてという人向けの入門書なので真面目に読む気は無いんだけど、応援のために買ってみた。

中身をかいつまんで読んでみたんだけど、例えばよくある間違いのコードを表示されるエラーメッセージまでセットで紹介していたりして、周りに聞ける人が居ない入門者がこの本を読みながら勉強するときに困ることを極力減らそうという親切さが伝わってきた。

入門書を読む機会が無いのでおすすめ本を聞かれても答えられなかったんだけど、これからはこの本をおすすめしようと思う。

2冊めは「入門書の次に読む本」（ただし、この場合の入門書はプログラミング非初心者向けの入門書だと思う）

www.amazon.co.jp

中上級者向けの本も最近増えて嬉しい限りだけど、この本は Effective Python よりは広く、 パーフェクト Python よりは狭い。 たとえば PHP や C# 書いてた人が Python を始めるときに、Python オンラインドキュメントのチュートリアルを読んだあとにこの本を読めばいい感じのバランスになると思う。