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を完全無効化**
   ```c
   // 既存のHAKMEM_NO_MADVISEフラグを確認
   // 存在しない場合は追加実装
   if (getenv("HAKMEM_NO_MADVISE")) {
       // madvise呼び出しをスキップ
   }
   ```
   - **期待効果**: 27x遅延 → mimalloc並みに改善（理論値）

2. **Partial Releaseの閾値を大幅に引き上げ**
   ```c
   // 現在: 個別Slabごとに即時解放
   // 提案: 最低100 Slabs溜まるまで解放しない
   #define PARTIAL_RELEASE_MIN_SLABS 100
   ```
   - **期待効果**: madvise頻度を1/100に削減

#### ⚠️ Priority 2: OOM修正

3. **Shared Pool動的拡張**
   ```c
   // shared_pool_acquire_slab() 失敗時
   // 1. LRU SuperSlabを強制解放
   // 2. 新しいSuperSlabを追加
   // 3. 上限に達したらlibc mallocにfallback
   ```

4. **メモリプレッシャー検出**
   ```c
   // /proc/self/status の VmRSS を監視
   // 閾値を超えたら積極的解放モードに切り替え
   ```

#### 🛠️ Priority 3: Segfault修正

5. **TLS free list境界チェック**
   ```c
   // 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: ベンチマーク実行コマンド

```bash
# ベースライン (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実装に着手