hakmem/WORKLOAD_COMPARISON_20251205.md

ワークロード条件別パフォーマンス比較レポート (HAKMEM vs mimalloc vs libc)

測定日: 2025年12月5日 目的: 異なるワークロード条件でHAKMEMとmimalloc/libcの性能差を定量化し、madvise 58%問題の原因特定

---

エグゼクティブサマリー

衝撃的な発見

HAKMEM is 27x slower than mimalloc (baseline条件)

1. 決定的証拠: straceでmadviseシステムコールが1081回検出（mimalloc: 0回）
2. sys時間の異常: HAKMEM 272ms vs mimalloc 3ms (91倍の差)
3. ページフォルト: HAKMEM 6,780回 vs mimalloc 147回 (46倍)
4. Cycles消費: HAKMEM 1.25B vs mimalloc 35M (35倍)

根本原因の特定

madvise(MADV_DONTNEED)の過剰呼び出しが性能劣化の主犯。1M iterationsでたった400個のワーキングセットに対して1081回のmadviseは異常。

発見した重大バグ

1. 10M iterations OOM: Shared Poolが枯渇 → Tiny laneが完全停止
2. ws=40000 Segmentation Fault: メモリ限界を超えてクラッシュ

---

測定結果詳細

1. スループット比較（全条件）

条件 (iterations, ws)	HAKMEM (ops/s)	mimalloc (ops/s)	libc (ops/s)	HAKMEM/mimalloc比
1M, ws=400 (baseline)	4.5M	122M	84M	3.7% (27x slower)
1M, ws=4000	4.3M	99M	61M	4.3% (23x slower)
1M, ws=10000	4.3M	83M	53M	5.2% (19x slower)
1M, ws=40000	SEGFAULT	54M	34M	N/A
10M, ws=400	OOM	(未測定)	(未測定)	N/A

傾向: ワーキングセットが大きくなるほど、HAKMEMとmimallocの差は縮まるが、依然として19-27倍遅い。

---

2. perf stat詳細比較 (ws=400条件)

スループットと実行時間

アロケータ	Throughput (ops/s)	実行時間 (秒)	user時間	sys時間
HAKMEM	4.6M	0.304	0.031s	0.272s (89.5%)
mimalloc	95M	0.016	0.013s	0.003s (18.8%)
libc	92M	0.021	0.019s	0.002s (9.5%)

決定的証拠: HAKMEMのsys時間が異常に高い（272ms = 総時間の89.5%）

CPU性能カウンタ

メトリクス	HAKMEM	mimalloc	libc	HAKMEM/mimalloc比
cycles	1,250M	35M	56M	35.7x
instructions	1,257M	51M	96M	24.6x
page-faults	6,780	147	134	46.1x
cache-misses	9.2M	50K	46K	184x
L1-dcache-load-misses	18.8M	590K	411K	31.9x
branch-misses	23.9M	592K	648K	40.4x
IPC (insn/cycle)	1.01	1.46	1.98	0.69x

ハイライト:

• Page faults: HAKMEMが46倍多い → ページング処理でカーネル時間増大
• Cache misses: 184倍の差 → メモリアクセスパターンの非効率性
• IPC: HAKMEMが最低（1.01） → CPU stall頻発

---

3. システムコール分析 (strace -c)

HAKMEM (ws=400, 1M iterations)

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 91.68    0.185384         171      1081           madvise      ← ★ 主犯
  4.94    0.009981           9      1092           munmap
  2.95    0.005967           5      1113           mmap
  0.13    0.000260           5        48        40 openat
  ...
------ ----------- ----------- --------- --------- ----------------
100.00    0.202208          58      3437        78 total

決定的証拠:

• madvise: 1081回、総時間の91.68% (185ms)
• mmap/munmap: 合計2205回 → SuperSlab割り当て/解放が頻繁
• システムコール総数: 3437回（mimalloc: 44回、78倍）

mimalloc (ws=400, 1M iterations)

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  0.00    0.000000           0        10           mmap
  0.00    0.000000           0         1           munmap
  0.00    0.000000           0         1           brk
  ...
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000           0        44         3 total

madviseは0回 → ページ解放しない戦略

---

ワーキングセットサイズの影響

スループット vs ワーキングセット

HAKMEM:    ws=400 → 4.5M ops/s, ws=4000 → 4.3M ops/s, ws=10000 → 4.3M ops/s
mimalloc:  ws=400 → 122M ops/s, ws=4000 → 99M ops/s, ws=10000 → 83M ops/s
libc:      ws=400 → 84M ops/s, ws=4000 → 61M ops/s, ws=10000 → 53M ops/s

観察結果:

1. HAKMEM: ワーキングセットに鈍感（4.3-4.5M ops/s、±5%）
   • 理由: madviseのオーバーヘッドが支配的 → ワークロードの変化に鈍感
2. mimalloc: ワーキングセットに敏感（122M → 83M ops/s、32%低下）
   • 理由: キャッシュミス増加が性能に直接影響
3. libc: ワーキングセットに最も敏感（84M → 53M ops/s、37%低下）
   • 理由: ptmallocのロック競合とフラグメンテーション

重要な含意

HAKMEMがワーキングセットに鈍感な理由 = システムコールオーバーヘッドがボトルネック

良い設計なら「ワーキングセットが小さい → キャッシュヒット率高い → 高速」のはずだが、HAKMEMは逆にmadviseの嵐でワーキングセットの利点を活かせていない。

---

発見したバグと制限事項

バグ1: 10M iterations OOM (Out of Memory)

症状:

[SS_BACKEND] shared_fail→NULL (OOM) cls=7
[HAKMEM] BUG: Tiny lane failed for size=1010 (should not happen)
/bin/bash: 1 行: 699668 強制終了

根本原因:

• shared_pool_acquire_slab() が失敗 → Shared Poolが枯渇
• 10M iterationsの長時間実行でSuperSlabが不足
• hak_tiny_alloc_superslab_backend_shared() がNULLを返し続ける

影響:

• Tiny laneが完全停止 → 全allocがNULLを返す
• プロセスが強制終了 (exit code 137 = SIGKILL)

修正方針:

1. Partial Releaseの実装が不十分 → 使用済みSuperSlabを再利用できない
2. Shared Poolのサイズ上限を動的に拡張する仕組みが必要
3. メモリプレッシャー検出とfallback戦略（例: libc mallocへの委譲）

---

バグ2: ws=40000 Segmentation Fault

症状:

[WARMUP] Complete. Allocated=59935 Freed=40065 SuperSlabs populated.
[TEST] Main loop completed. Starting drain phase...
[TLS_SLL_NORMALIZE_USERPTR] cls=6 node=0x7331e50b3001 -> base=0x7331e50b3000 stride=512
./bench_random_mixed_hakmem(+0xd29c)[0x5dd96048e29c]
/bin/bash: 1 行: 700716 Segmentation fault

推定原因:

1. メモリ限界到達: 40,000スロット × 平均512バイト = 20MB + メタデータ
2. TLS free list破損: TLS_SLL_NORMALIZE_USERPTR でポインタ正規化中にクラッシュ
3. class_idx=6 (stride=512)の問題: フリーリストのリンク操作中にアクセス違反

修正方針:

1. TLS free listの境界チェック強化
2. メモリマップの上限設定とエラーハンドリング
3. ws > 10000での動作検証とテスト追加

---

性能劣化の根本原因分析

1. madvise過剰呼び出しの証拠チェーン

証拠	データ
strace	madvise 1081回 (91.68% sys時間)
perf stat	sys時間 272ms (総時間の89.5%)
page-faults	6,780回 (mimalloc: 147回の46倍)
cycles	1.25B (mimalloc: 35Mの35倍)

2. なぜmadviseが1081回も呼ばれるのか？

仮説: Partial Releaseが発動していない

• 前回の測定 (PERF_PROFILE_ANALYSIS_20251204.md): madvise 58%を確認
• 今回の測定: madvise 92% → さらに悪化
• 原因: 1M iterationsではPartial Release条件を満たさない
  • 期待: 空きSlabが溜まったら一括解放
  • 実際: 個別Slabごとに即座にmadvise実行

3. mimallocとの戦略比較

アロケータ	メモリ解放戦略	madvise頻度	トレードオフ
HAKMEM	Eager Release (即時解放)	1081回/1M ops	CPU時間 ↑↑↑, メモリ ↓
mimalloc	Lazy Release (遅延保持)	0回/1M ops	CPU時間 ↓↓↓, メモリ ↑
libc	Medium (ある程度保持)	(未測定)	バランス型

HAKMEMの設計ミス: メモリ効率を重視しすぎてCPU効率を犠牲にしている

---

結論

主要発見

1. madvise過剰呼び出しが性能劣化の主犯 (91.68% sys時間)

   • 1M operationsで1081回のmadvise → 平均925 ops/madvise
   • mimalloc (0回) との比較で明確

2. Partial Releaseが機能していない

   • 1M iterationsでは発動せず → 個別Slabごとに即座解放
   • 長時間実行 (10M) → OOMでクラッシュ → 実装が不完全

3. ワーキングセットに鈍感 = ボトルネックの証拠

   • ws=400も10000もほぼ同じ性能 → システムコールが支配的
   • 本来はws小 → キャッシュヒット高 → 高速のはず

4. 重大バグ2件

   • 10M iterations OOM (Shared Pool枯渇)
   • ws=40000 Segfault (TLS free list破損)

推奨アクション（優先度順）

🔥 Priority 1: madvise緊急対策

1. 環境変数でmadviseを完全無効化

   // 既存のHAKMEM_NO_MADVISEフラグを確認
   // 存在しない場合は追加実装
   if (getenv("HAKMEM_NO_MADVISE")) {
       // madvise呼び出しをスキップ
   }
   

   • 期待効果: 27x遅延 → mimalloc並みに改善（理論値）

2. Partial Releaseの閾値を大幅に引き上げ

   // 現在: 個別Slabごとに即時解放
   // 提案: 最低100 Slabs溜まるまで解放しない
   #define PARTIAL_RELEASE_MIN_SLABS 100
   

   • 期待効果: madvise頻度を1/100に削減

⚠️ Priority 2: OOM修正

3. Shared Pool動的拡張

   // shared_pool_acquire_slab() 失敗時
   // 1. LRU SuperSlabを強制解放
   // 2. 新しいSuperSlabを追加
   // 3. 上限に達したらlibc mallocにfallback
   

4. メモリプレッシャー検出

   // /proc/self/status の VmRSS を監視
   // 閾値を超えたら積極的解放モードに切り替え
   

🛠️ Priority 3: Segfault修正

5. TLS free list境界チェック

   // TLS_SLL_NORMALIZE_USERPTR の前に
   if (node < slab_base || node >= slab_end) {
       fprintf(stderr, "Invalid free list node\n");
       abort();
   }
   

6. ws > 10000テストケース追加

---

技術的洞察

なぜmimallocは速いのか？

1. Lazy Memory Management: ページを手放さない → syscall 0回
2. TLS-first Design: ロックフリーなTLSキャッシュ → 競合なし
3. シンプルなメタデータ: 複雑なSuperSlab管理なし

HAKMEMの設計哲学の問題点

「メモリ効率重視」が裏目に出ている

• 設計意図: 細かくメモリを返却 → RSS削減
• 実際の結果: madviseでCPU消費 → スループット1/27
• 教訓: プリマチュア最適化は諸悪の根源

今後の方針

Phase 1: 緊急止血

• madvise無効化フラグの実装（今日中）
• ベンチマークで効果検証

Phase 2: 根本治療

• Partial Releaseの完全再実装
• Shared Pool動的拡張
• メモリプレッシャー対応

Phase 3: 再設計検討

• mimalloc的Lazy戦略の導入
• 環境変数でEager/Lazy切り替え可能に
• メモリ効率 vs CPU効率のトレードオフをユーザーに選ばせる

---

付録A: 測定環境

• OS: Linux 6.8.0-87-generic
• CPU: (perf statから推定) 4.1 GHz max
• コンパイラ: GCC (詳細不明)
• ベンチマーク: bench_random_mixed (16-1024B random allocations)
• 乱数シード: 1 (再現性確保)

付録B: ベンチマーク実行コマンド

# ベースライン (ws=400)
./bench_random_mixed_hakmem 1000000 400 1
./bench_random_mixed_mi 1000000 400 1
./bench_random_mixed_system 1000000 400 1

# perf stat比較
perf stat ./bench_random_mixed_hakmem 1000000 400 1
perf stat ./bench_random_mixed_mi 1000000 400 1

# strace分析
strace -c ./bench_random_mixed_hakmem 1000000 400 1
strace -c ./bench_random_mixed_mi 1000000 400 1

# OOM再現（失敗）
./bench_random_mixed_hakmem 10000000 400 1  # → OOM crash

# Segfault再現
./bench_random_mixed_hakmem 1000000 40000 1  # → Segfault

---

次のアクション: Priority 1実装に着手