Clojureのパスワード問い合わせシステムを高速化する

Feb 11, 2014

こんな記事が話題になって、その後、徳丸先生がこんな記事を書きました。

さすがに遅いだろうと僕も思ったので高速化しました。

まず、もとのclojureのコードを再掲。

(ns six-length.core
  (:require [clojure.core.reducers :as r])
  (:import [java.security MessageDigest]))

(defn hexdigest [s]
  (let [digester (MessageDigest/getInstance "MD5")]
    (. digester update (.getBytes s))
    (apply str (map #(format "%02x" (bit-and % 0xff)) (. digester digest)))))

(defn find-password [salt pw]
  (->> (range 0 1000000)
       (map #(format "%06d" %))
       (map (fn [_] [_ (hexdigest (str salt "$" _))]))
       (filter #(= pw (second %)))))

reducersは使いません。

six-length.core> (time (into [] (find-password "hoge" "4b364677946ccf79f841114e73ccaf4f")))
"Elapsed time: 37026.464 msecs"
[["567890" "4B364677946CCF79F841114E73CCAF4F"]]

僕の環境だと37秒かかりました。順を追って高速化していきましょう。

DatatypeConverterを使う

まずhexdigestが遅いっぽいですね。strを使ってdigestの結果から文字列を生成してますがこれに時間がかかってるのでJavaのDatatypeConverterを使って高速化しましょう。

(ns six-length.core
  (:require [clojure.string :as s])
  (:import [java.security MessageDigest]
           [javax.xml.bind DatatypeConverter]))

(defn hexdigest [s]
  (let [digester (MessageDigest/getInstance "MD5")]
    (. digester update (.getBytes s))
    (DatatypeConverter/printHexBinary (.digest digester))))

実行。DatatypeConverter/printHexBinaryがアルファベットを大文字で返すのでclojure.string/upper-caseを使ってます。

six-length.core> (time (into [] (find-password "hoge" (s/upper-case "4b364677946ccf79f841114e73ccaf4f"))))
"Elapsed time: 7490.276 msecs"
[["567890" "4B364677946CCF79F841114E73CCAF4F"]]

7.5秒。5倍くらい速くなりました。

Type Hintsを使う

hexdigestにType Hintsを付けて高速化します。

(defn ^String hexdigest [^String s]
  (let [digester (MessageDigest/getInstance "MD5")]
    (. digester update (.getBytes s))
    (DatatypeConverter/printHexBinary (.digest digester))))

実行。

six-length.core> (time (into [] (find-password "hoge" (s/upper-case "4b364677946ccf79f841114e73ccaf4f"))))
"Elapsed time: 2340.055 msecs"
[["567890" "4B364677946CCF79F841114E73CCAF4F"]]

2.3秒。さらに3倍くらい速くなりました。

formatが遅いので自作する。

いろいろプロファイリングしてたらclojure.core/formatがメチャクチャ遅いことが判明しました。ので、0パディング専用の関数を作って高速化します。

(defn ^String pad [^Integer n x]
  (if (> n (.length (str x)))
    (recur n (str 0 x))
    (str x)))

(defn find-password [salt pw]
  (->> (range 0 1000000)
       (map #(pad 6 %))
       (map (fn [_] [_ (hexdigest (str salt "$" _))]))
       (filter #(= pw (second %)))))

実行。

six-length.core> (time (into [] (find-password "hoge" (s/upper-case "4b364677946ccf79f841114e73ccaf4f"))))
"Elapsed time: 1097.641 msecs"
[["567890" "4B364677946CCF79F841114E73CCAF4F"]]

約1.1秒。さらに2倍くらいになりました。

微妙な高速化

find-passwordがやや煩雑な処理になってるので少し改善します。

(defn ^Boolean match? [^String salt ^String pass ^String digest]
  (= digest (hexdigest (str salt "$" pass))))

(defn find-password [salt pw]
  (->> (range 1000000)
       (map #(pad 6 %))
       (filter #(match? salt % pw))))

実行。

six-length.core> (time (into [] (find-password "hoge" (s/upper-case "4b364677946ccf79f841114e73ccaf4f"))))
"Elapsed time: 959.146 msecs"
["567890"]

150ms程度改善されました。当初に比べると37倍以上の高速化が実現できましたね。

ここまでやってめんどくさくなってやめました。ちなみに徳丸先生のコードをシングルスレッドで実行すると約800msだったので、ここまで無理やり高速化してもPHPに速度で敵わないのか、という徒労感だけが残って辛いです。

コード全体はここに置いてます。

辛いのでだれかもっと速くしてください。