概要 / Overview
同一のアルゴリズム「最小自由数（Minimum Free Number）」を、C++, Common Lisp, Rust, Mojoで実装し、各言語の実行速度を比較しました。
「最小自由数」は、重複のない整数列から最小の空き番号を求めるというシンプルな問題ですが、言語ごとの設計思想・最適化・実行モデルの違いが如実に現れる題材です。
This article compares the execution speed of the same algorithm — Minimum Free Number — implemented in C++, Common Lisp, Rust, and Mojo.
The task is simple: find the smallest unused integer in a list of unique integers.
However, it’s a fascinating benchmark that reveals the design philosophies and runtime characteristics of each language.
We’ll look not only at raw performance but also at code expressiveness, type safety, and compilation behavior,
to see how each language approaches the same computational challenge.
最小自由数とは何か / What Is the Minimum Free Number?
書籍「関数プログラミング 珠玉のアルゴリズムデザイン」（Richard Bird著, 吉田和樹訳, オーム社, 2006年）の第1章『最小自由数』で登場する“最小自由数 (minimum free number)”の問題。
重複のない自然数リストから、存在しない最小の番号を見つける——ただそれだけ。
しかし、その単純さの中にアルゴリズム設計の奥義が潜んでいる。 /
This problem appears in Chapter 1 of the book "Pearls of Functional Algorithm Design" by Richard Bird.
Given a list of unique natural numbers, find the smallest non-existent number.
A deceptively simple problem that reveals deep insights into algorithm design.
[8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]
→ 最小自由数 = 15
簡単に書けるけど遅いという例で紹介されていたHaskellプログラム / The Simple but Slow Haskell Implementation
以下のHaskellコードは、書籍『関数プログラミング 珠玉のアルゴリズムデザイン』（Richard Bird著, 吉田和樹訳, オーム社, 2006年）第1章「最小自由数」より引用しています。 /
The following Haskell code is quoted from Chapter 1 of the same book.
minfree1 :: [Int] -> Int
minfree1 xs = head ([0..] \\ xs)
美しい1行実装。だが、リスト全探索ゆえに遅い。 /
A beautifully concise one-liner — but slow due to full list traversal.
こう書くと速い！と書かれていたHaskellプログラム「分割統治法」 / The Faster Divide-and-Conquer Implementation
以下のHaskellコードも、同書第1章「最小自由数」より引用しています。 /
Also quoted from the same source.
minfree4 :: [Int] -> Int
minfree4 xs = minfrom 0 (length xs, xs)
minfrom a (n, xs) | n == 0 = a
| m == b - a = minfrom b (n - m, vs)
| otherwise = minfrom a (m, us)
where (us, vs) = partition (<b) xs
b = a + 1 + n `div` 2
m = length us
“舞”から“武”へ。分割統治法という得物で探索範囲を半分ずつ斬ることで速度を実戦レベルへ昇華。 / From elegance to efficiency — divide and conquer halves the search space for speed.
(分割統治法は、partition関数で配列を二分し、再帰的に探索範囲を狭めていく実装です。図による説明はこちらを参照。)
Haskellプログラムの速度比較結果 / Performance Comparison in Haskell
最初のプログラムと分割統治法の速度差を体感するため、99999件の入力データを用意し、速度を比較。 / Both methods were tested with 99,999 elements.
-入力データ / Input data
[8, 23, 9, 0, 12, 11, 1, 10, 13, 7, ... 99999, 91384]
→最小自由数=69918
これを下表の環境でHaskellプログラムに入力して実行。 / Enter this into a Haskell program in the environment shown in the table below and run it.
| 項目 / Item | 内容 / Contents |
|---|---|
| OS | Fedora 41 (x86_64) |
| CPU | Intel(R) Core(TM) i3-4130 CPU @ 3.40GHz |
| Memory | 8GB |
| GHC | The Glorious Glasgow Haskell Compilation System, version 8.6.5 |
- 最初のプログラム / Simple version
245秒(sec) - 分割統治法 / Divide & Conquer
0.02秒(sec) (約20ミリ秒)
分割統治法、おそるべし！Haskellおそるべし！──では、他の言語ではどうか？ /
Over 10,000× faster — Haskell’s power revealed. So what about other languages?
C++, Common Lisp, Rust, Mojo, お前ら、やれんのか！
ということで‥ /
C++, Common Lisp, Rust, Mojo, can you guys do it?! So...
最小自由数 最速王決定戦 開幕！ / The Minimum Free Number Grand Prix Begins!
選手(言語)、入場ッ！！ / Enter players (language)!!
C++
速度で俺に敵うものなどいないッ！今日の勝利があれば明日など要らぬ！破壊的再代入と最適化で全てを凌駕ッ！ C++ァァッ！！ /
No one can match my speed! Destructive reassignment and ruthless optimization — that’s C++!
画像出典： LLVM Project
© The LLVM Project. Used under the Apache 2.0 License with LLVM exceptions.
C++の象徴的存在として、LLVM（Clang）のドラゴンを引用しました。
Common Lisp
柔軟無敵、動的だが極めて危険ッ！世界を自在に操るマクロの魔術師！わかるヤツだけついて来い！ Common Lispゥゥッ！！ /
Flexible yet formidable! The macro sorcerer — Common Lisp!!
画像出典： Public Domain Lisp Logo Set
Conrad Barski, M.D.氏が公開してくれているLisp Alienです。キモカワユス（褒め言葉です）。
Rust
安全だから速い！速いから安全！所有権の管理が生み出す最強の盾！ Rustォォッ！！ /
Safe because it’s fast, fast because it’s safe! The shield of ownership — Rust!!
画像出典： Wikimedia Commons File:Original Ferris.svg
Ferris (Rust mascot), CC0 1.0 Public Domain
みんな大好き俺たちのFerrisたんです。可愛すぎだろ。
Mojo 🔥
新星、だが恐るべき戦闘力ッ！Pythonの柔らかさを備えつつ、ネイティブ速度で猛攻！未来を駆ける超新星！ Mojoォォッ！！ /
Pythonic syntax, native-like speed — the rising star of the future, Mojo!!
ルール説明と結果発表！ / Results
Haskellと同じ99999件のデータを入力し、正しい答え69918にたどり着く処理を、各言語で10万回ずつ行い、平均処理速度を競いました！ /
The participants input the same 99,999 data items as in Haskell, and ran the process to arrive at the correct answer of 69,918, 100,000 times in each language, competing to see who could achieve the best average processing speed!
結果は以下の通り！
- 比較条件（計測方法）
各プログラムの呼び出し、clock関数など(言語によって異なる)で処理時間の測定、蓄積を10万回繰り返し、平均処理時間を算出。
| 言語 / Language | バージョン / Version | 10万回の平均処理速度[μs] / Avg Time | 実装 / Implementation |
|---|---|---|---|
| C++ | gcc (GCC) 14.3.1 20250808 (Red Hat 14.3.1-3) | 718 | C++ code |
| Common Lisp | SBCL 2.5.9-1.fc41 | 792 | Common Lisp code |
| Rust | rustc 1.92.0-nightly (57ef8d642 2025-10-15) | 835 | Rust code |
| Mojo | Mojo 0.25.7.0.dev2025101205 (e67ffadb) | 1100 | Mojo code |
C++ プログラム説明 / Implementation Highlights
私の環境では、C++が処理速度1位でした。
結果報告の表にはgccでコンパイルした結果を載せていますが、clang version 19.1.7 (Fedora 19.1.7-5.fc41)でコンパイルした実行ファイルも同程度の速度でした。
Haskellのpartition関数は入力データをコピーして新しいリストを生成しますが、C++で使用しているstd::partitionでは、入力データを書き換えるためデータコピーよりも速度が出ていると考えます。 /
std::partition modifies input data in-place, reducing overhead and achieving top performance.
#include <iostream>
#include <vector>
#include <algorithm>
extern std::vector<int> v;
static int minfrom(int a,
int n,
std::vector<int, std::allocator<int> >::iterator begin,
std::vector<int, std::allocator<int> >::iterator end)
{
int b = a + 1 + n / 2;
auto pos = std::partition(begin,
end,
[b](int x) { return x < b; });
int m = pos - begin;
if(n == 0){
return a;
}else if (m == b - a){
return (minfrom(b, n - m, pos, end));
}else{
return (minfrom(a, m, begin, pos));
}
}
static int minfree (std::vector<int> *xs)
{
return minfrom(0, xs->size(), xs->begin(), xs->end());
}
// … プログラム全文はgist参照
- コンパイルコマンド / Compilation Command
g++ -O3 minfree.cpp inputMinFree.cpp -o minfree
Common Lispプログラム説明 / Implementation Highlights
Haskellの分割統治法をC++に移植して最適化したら爆速だったのですが、私は以下の言葉が気になり、Common Lispの本気を見てみたくなりました。
Cで書くコードの方がCommon Lispで書くより速いって人がいたら、それは彼のCの技量が高すぎるってことだね。
“If you can't outperform C in CL, you're too good at C.” — Eric Naggum
- 引用元URL
https://blog.practical-scheme.net/shiro/20100620a-lisp-speed
https://groups.google.com/g/comp.lang.lisp/c/x79wPngeIRU/m/y-mmTcYVGdEJ
変数の型をコンパイル時に予め指定することにより、プログラム実行時のオーバーヘッドを減らしました。
HaskellのpartitionやC++のstd::partitionに相当するものは、私のCommon Lisp環境では見つからなかったためpartitionを自作しました。図による説明はこちらを参照。 /
With explicit type declarations and a custom partition, Lisp nearly matches C++ speed.
(declaim (optimize (speed 3) (safety 0) (debug 0)))
(defmacro while (test &rest body)
`(do () ((not ,test)) ,@body))
(defun partition (vec p l r)
(declare (type (simple-array fixnum (*)) vec)
(type fixnum p l r))
(let ((i l) (j r))
(declare (type fixnum i j))
(while (<= i j)
(while (< (aref vec i) p) (incf i))
(while (>= (aref vec j) p) (decf j))
(when (<= i j)
(let ((tmp (aref vec i)))
(setf (aref vec i) (aref vec j))
(setf (aref vec j) tmp))
(incf i)
(decf j)))
j))
; … プログラム全文はgist参照
- コンパイルコマンド / Compilation Command
sbcl --noinform --no-sysinit --no-userinit --load inputMinFree.lsp --load minfree.lsp
Rustプログラム説明 / Implementation Highlights
C++より安全でC++並みに速い、のような謳い文句をよく見かけるRustが本気を出したらどれくらい速いのか見てみました。
最初はVecのiter().partitionを使ったのですが、これは入力データを変更せずに新しいデータを作るため、C++のように入力データを書き換える処理に比べて遅いため、partition関数(入力データ書き換えバージョン)を作成し、速度を追求しました。 /
Balanced safety and speed; a custom partition brings it close to C++.
use std::time::{Duration, Instant};
mod input_min_free;
fn partition(xs: &mut [i32], b: i32) -> usize {
let mut l = 0;
let mut r = xs.len() - 1;
while l <= r {
while l < xs.len() && xs[l] < b {
l += 1;
}
while r > 0 && xs[r] >= b {
r -= 1;
}
if l <= r {
xs.swap(l, r);
l += 1;
if r == 0 {
break;
}
r -= 1;
}
}
r
}
// … プログラム全文はgist参照
- コンパイルコマンド / Compilation Command
rustc -C opt-level=3 minfree.rs
Mojoプログラム説明 / Implementation Highlights
Pythonのように書けてRust並みに速い、のような謳い文句を見かけるMojoを触ってみたくて分割統治法を作ってみました。
入力データはPythonで作り、それをMojoが読み込む形にしました。
HaskellのpartitionやC++のstd::partitionに相当するものは現状の私の環境のMojo(Mojo 0.25.7.0.dev2025101205 (e67ffadb))では見つからなかったので、partitionに相当する処理をminfrom関数内に自作しました。
Mojoで入力データを変更する方法が見つけられなかったため、入力データは変更せず、新しいデータを作る方式にしています。 /
Pythonic syntax, yet near-native performance.
from python import Python
def minfrom(a: Int, n: Int, xs: List[Int]) -> Int:
if n == 0:
return a
var b: Int = a + 1 + n
var us = List[Int]()
var vs = List[Int]()
# 2分割
for i in range(n):
if xs[i] < b:
us.append(xs[i])
else:
vs.append(xs[i])
var m = len(us)
if m == b - a:
return minfrom(b, n - m, vs)
else:
return minfrom(a, m, us)
# … プログラム全文はgist参照
- コンパイルコマンド / Compilation Command
pixi run mojo build minfree.mojo -O3
- SIMD型について / About SIMD Type
MojoにはSIMD型というデータ型があり、今回使ったList[Int]（Pythonでいうlistに相当）の代わりにこれを用いてList[SIMD[DType.int64, 1024]]のようにすれば速くなるのでは？と考え、SIMD版分割統治法も作ってみたのですが、今回作った案ではList[Int]版の50倍近く遅くなってしまいました。
今回はSIMD型をうまく活用できなかったため、List[Int]型を採用しました。 /
I am currently investigating and considering ways to utilize it.
今後の展望 / Future Work
今回は「最小自由数」を題材に比較しましたが、他のアルゴリズムでも同様の傾向が見られるのか気になっています。特にMojoには注目していきたいです。 /
I plan to test other algorithms — especially keeping an eye on Mojo’s evolution.
参考文献
- Richard Bird（著）, 吉田和樹（訳）
『関数プログラミング 珠玉のアルゴリズムデザイン』
オーム社, 2006年
ISBN: 978-4274050640