Pythonで最速のULIDライブラリを作った話(C++拡張)

TL;DR

卍爆速卍なPythonのULIDライブラリ"fast_ulid"を作った
使い方はここ

ULIDとは

みなさんはULIDをご存知でしょうか？
ULIDはUUIDの代替となるべく策定されたもので

• UUIDと128ビット互換
• 1ミリ秒ごとに1.21e24のユニークなULIDを作成できる
• 辞書順にソート可能
• 36文字のUUIDに対して、26文字でエンコードされる
• Crockford's base32という、可読性の高いエンコード方式
• ケースインセンシティブ
• 特殊文字を使わないので、URLセーフ
• 単調増加なバイト列(正しい生成順にソートされる)

というものです。上と被る部分もありますが、現状最新とされるUUID4は

• 文字効率が悪い(128bitを36文字で表す)
• ソート不可能

ということで、少々使い勝手が悪いようです。

ULIDの何がうれしいのか

純粋に文字長が短いことで、より可読性が高くなります。
さらには、そのものにミリ秒単位でタイムスタンプが含まれていることで、例えばデータベースのPrimary Keyにしながらタイムスタンプのカラムを減らすことができます。
また、ULIDをPrimary Keyに使うと自動的にソータブルになるのでインデックスが挿入順に綺麗に並び、さらに挿入時のパフォーマンスがauto_incrementと同様に高速です。

少々問題が

ありました。

データベースのPrimary Keyにするべく使っており、テストデータの生成を行っていたのですが、Python内でのデータ生成段階からなんとなく... 遅い？

PythonでULIDを使おうと思った時には、大体

• python-ulid (mdomkeさん)
• ulid-py (ahawkerさん)
• ulid (mdipierroさん)

のどれかになると思います。
2022/2/23時点でそれぞれのスターの数は、上から76, 289, 34となっており、ulid-pyが優勢なので私もこれを使っていたのですが、大体ULIDを1,000,000個生成してstrにするときに私の環境では5, 6秒かかっていました。

プログラマというのは技術に対して貪欲で、作れると思ったものは作らないとうずうずしてしまいますので、もっと高速なULIDライブラリを作ってみようと思い立ちました。

C++拡張

Pythonには、複数の拡張方法があります。
純粋にPythonでコードを書いてもいいですし、もしパフォーマンスにこだわるのであれば、CやC++拡張を使うのも手です。

今回は(私の技術力の範囲内で)全力で高速化するために、後者の拡張方法を用いたいと思います。

初めはCで拡張しようと思っていましたが、どうやらタイムスタンプに用いるミリ秒取得が環境によって上手くいったりいかなかったり、非推奨だったりでよくわかんないことになっているので、C++を使うことにしました。

以下に技術的につまったところを上げていこうと思います。

METH_FASTCALL

Python3.7から追加された引数の受け取り方です。以前まではMETH_VARARGSを使用していました。
METH_FASTCALLを用いることで、かなり高速になりました(2倍程度)

しかし、この受け取り方を用いることによって、かなりコードを書き換える必要が出てきます。
具体的にいうと、METH_VARARGSを用いる際は引数に引数のTupleを表すPyObjectが与えられますが、METH_FASTCALLでは引数のPyObjectの配列が与えられます。
ですので、引数をパースする便利関数のPyArg_ParseTupleなどが使えず、そのあたりを手作業で行う必要があります。

Python3.6以下でUTC Timezone

Python3.7からはPyDateTime_TimeZone_UTCでUTCを表すタイムゾーンのシングルトンを取得できるのですが、Python3.6ではそういった機能はありません。
Pythonにおけるdatetime.datetime.fromtimestampはタイムゾーンを指定した方が断然早いので、パフォーマンスを重視する今回はつけない選択肢はありませんでした。

そこで今回は、PythonをC++から呼び出して、タイムゾーンオブジェクトを取得する方式としました(なんかもっといい方法ありそう。。。)

PyObject* timezone_utc;

void create_utc_tz() {
  PyObject* pytz = PyImport_ImportModule("datetime");
  if (!pytz) {
    return;
  }
  PyObject* pytz_tz = PyObject_GetAttrString(pytz, "timezone");  // datetime.timezone を取得
  Py_DECREF(pytz);                                               // datetime自体の参照を減らす
  if (!pytz_tz) {
    return;
  }
  PyObject* pytz_tz_utc = PyObject_GetAttrString(pytz_utc, "utc"); // datetime.timezone.utc を取得
  Py_DECREF(pytz_tz);                                              // datetime.timezoneも同様
  timezone_utc = pytz_tz_utc;
  Py_DECREF(pytz_tz_utc);
}

という感じになってます。
もっといい方法あるよって方がいらっしゃれば、是非コメントで教えてください。

完成したのでベンチマーク

完成しました。
血と汗と涙と睡眠時間と等価交換で、ライブラリ一つを錬成するのは非常に効率が悪いですね
GitHub Copilotくん、README.mdからコードを自動生成してくれ。

さて、ここでベンチマークを行ってみます。
Python実装の5倍程度で及第点、10倍で御の字ですかね。今回作成したライブラリがfast-ulidで、他の二つが比較対象です。ulidだけ群を抜いて遅かった(いいえ、他二つがPythonなのに早すぎるだけ)ので、二つのみを比較対象にしました。

それぞれ左から

• ULID文字列作成
• datetime.datetimeオブジェクトからULID文字列作成
• タイムスタンプ(float)からULID文字列作成
• ULID文字列からdatetime.datetimeオブジェクト作成
• ULID文字列からタイムスタンプ(float)作成

となっており、1,000,000の連続試行を10回繰り返した平均時間です。

俺うれしい...😢
もっともスコアの低い"datetime.datetimeオブジェクトからULID文字列作成" でも10倍弱、もっともスコアの良い"ULID文字列からタイムスタンプ(float)作成"では50倍程度の速度になっています。
総じてスコアが低めなのはdatetime.datetimeオブジェクトを用いるもので、どうしてもPythonとしてオブジェクトの操作を行う必要があるところから、オーバーヘッドとなってしまっています。

ちなみに、内部的にULIDを作成したりパースしたりする部分はC++しか絡んでないので、(当然といえば当然ですが)これのfast_ulidの数十倍速いです。

使い方

以下モロマ(モロマーケティング)です。
GitHub: fast_ulid

$ pip install fast_ulid

でインストール
実行例は以下の通り

import fast_ulid
import time
import datetime

# ulid.ulid()で、現在のタイムスタンプからULIDを作成
ulid = fast_ulid.ulid()

# timestamp や datetime オブジェクトを与えることも可能
# timestampのミリ秒部は小数点以下に配置しなければなりません
# JavaScriptのようなほかの言語では、整数部に来ます
ulid = fast_ulid.ulid(datetime.datetime.now())
ulid = fast_ulid.ulid(time.time())

print(ulid) # str が返されます
# 01FVY4F1TYP63XM1YVHBVVCBSB

# timestamp や datetime.datetime を ULID から取得することも可能
print(fast_ulid.decode_timestamp(ulid))
# 1644910053.214
print(fast_ulid.decode_datetime(ulid))
# 2022-02-15 07:27:33.214000+00:00

これですべての機能説明ですが、Simple is better than Complex ですよね！

是非便利にお使いください！