Thompson により提案されたオートマトンベースのアルゴリズムは、安定して高速に動作する。 backreference を導入したような拡張正規表現のためにバックトラックベースの正規表現エンジンを使っている言語は、特定の正規表現のマッチに指数的な時間が必要となるが、オートマトンベースであれば O(nm) (正規表現の長さと入力文字列の長さについて線形) で済む。

きわめて単純な C のソースコード付きでアルゴリズムを解説。
普通に NFA を実行するだけのシンプルなもの。そこそこ読みやすい。

続編:

• Regular Expression Matching: the Virtual Machine Approach
• Regular Expression Matching in the Wild
• Regular Expression Matching with a Trigram Index

最近の Rust エコシステムでは no_std 環境でスピンロックを使うような慣習があるが、スピンロックには重大な欠点がある。
よくできた (std や parking_lot crate の) mutex ではスピンロックと同等かそれ以上のパフォーマンスが出るため、安易にスピンロックを使うべきでないという話。
スピンロックで起きる問題のサンプルコード付き。

They (std や parking_lot の mutex) already do a small amount of spinning iterations before calling into the kernel, so they are as fast as a spinlock in the best case, and infinitely faster in the worst case.

(注釈は引用者による)

また、軽量なロックを使いたい場面としてよくあるのが「一回きりの初期化」だが、この場合筆者の作った once_cell crate が有用だとのこと。