Files

Moe Charm (CI) 677030d699 Document new Mixed baseline and C7 header dedup A/B

2025-12-10 14:38:49 +09:00

29 KiB

Raw Permalink Blame History

16-1024B パフォーマンス分析レポート

分析日: 2025年12月5日 ベンチマーク: bench_random_mixed (1M iterations, ws=400, seed=1) サイズ範囲: 16-1024 bytes (Tiny allocator: 8 size classes)

Quick Baseline Refresh (2025-12-10, current HEAD, C7-only v3 / front v3 ON)

ENV (Release): HAKMEM_PROFILE=MIXED_TINYV3_C7_SAFE HAKMEM_BENCH_MIN_SIZE=16 HAKMEM_BENCH_MAX_SIZE=1024
（bench_profile により TINY_HEAP_PROFILE=C7_SAFE TINY_C7_HOT=1 TINY_HOTHEAP_V2=0 SMALL_HEAP_V3_ENABLED=1 SMALL_HEAP_V3_CLASSES=0x80 POOL_V2_ENABLED=0 TINY_FRONT_V3_ENABLED=1 TINY_FRONT_V3_LUT_ENABLED=1 TINY_PTR_FAST_CLASSIFY_ENABLED=1 が自動注入される。FREE_POLICY/THP は未設定のまま）。

Allocator	Throughput (ops/s)	備考
HAKMEM (current HEAD, C7-only v3, dedup OFF)	44,384,651	baseline (`HAKMEM_PROFILE=MIXED_TINYV3_C7_SAFE`)
HAKMEM + C7 header dedup ON	44,303,895	`HAKMEM_TINY_C7_HEADER_DEDUP_ENABLED=1`（ほぼ誤差）

Note: 一時的に同プロファイルで ~36M ops/s まで落ち込んでいたが、その後の Tiny front v3 snapshot の遅延・LUT 判定の整理・C7 ヘッダまわりの配置見直しにより、現 HEAD では同条件でおおよそ 44M ops/s レンジに戻っている。以降の最適化はこの数値を新しい Mixed 基準ラインとして扱う。

Quick Baseline Refresh (2025-12-05, C7-only v3 / front v3 ON)

ENV (Release): HAKMEM_BENCH_MIN_SIZE=16 MAX_SIZE=1024 TINY_HEAP_PROFILE=C7_SAFE TINY_C7_HOT=1 TINY_HOTHEAP_V2=0 SMALL_HEAP_V3_ENABLED=1 SMALL_HEAP_V3_CLASSES=0x80 POOL_V2_ENABLED=0（front v3/LUT デフォルト ON, SMALL_HEAP_V3_STATS=1）。

Allocator	Throughput (ops/s)	Ratio vs mimalloc
HAKMEM (C7-only v3)	44,447,714	38.0%
mimalloc	117,204,756	100%
glibc malloc	90,952,144	77.6%

SmallObject v3 stats (cls7): route_hits=283,170 alloc_refill=2,446 alloc_fb_v1=0 free_fb_v1=0 page_of_fail=0。segv/assert なし。

エグゼクティブサマリー

HAKMEMの16-1024Bサイズ範囲でのパフォーマンスは、競合アロケータと比較して著しく低い。主要原因は、SuperSlabアロケーション時の過剰なページフォルト（約46-50倍多い）であり、これによりカーネル時間が全体の約86%（237ms / 276ms）を占めている。

測定結果サマリー

アロケータ	スループット (ops/s)	相対性能	ページフォルト	サイクル数
mimalloc	120,698,029	100%	146	35,872,448
libc malloc	83,321,226	69.0%	134	48,695,085
HAKMEM	4,844,380	4.0%	6,762	1,138,338,103

性能差の規模

HAKMEMはmimallocの約1/25の性能（25倍遅い）
HAKMEMはlibc mallocの約1/17の性能（17倍遅い）
ページフォルト数は約46-50倍多い（mimalloc: 146, HAKMEM: 6,762）
CPU サイクル数は約32倍多い（mimalloc: 35.8M, HAKMEM: 1.14B）

Phase 1: ベンチマーク測定（詳細）

測定条件

# テスト構成
iterations: 1,000,000
working set: 400 slots
seed: 1
サイズ分布: 16 + (rand() & 0x3FF) = 16～1040 bytes (均等分布)

HAKMEM測定結果（3回実行）

Run 1: 4,838,027 ops/s (time=0.207s)
Run 2: 4,893,096 ops/s (time=0.204s)
Run 3: 4,802,016 ops/s (time=0.208s)
平均: 4,844,380 ops/s
標準偏差: 37,851 ops/s (0.78%)

mimalloc測定結果（3回実行）

Run 1: 124,653,448 ops/s (time=0.008s)
Run 2: 118,312,154 ops/s (time=0.008s)
Run 3: 119,128,485 ops/s (time=0.008s)
平均: 120,698,029 ops/s
標準偏差: 2,810,883 ops/s (2.33%)

libc malloc測定結果（3回実行）

Run 1: 89,740,104 ops/s (time=0.011s)
Run 2: 82,601,696 ops/s (time=0.012s)
Run 3: 77,621,877 ops/s (time=0.013s)
平均: 83,321,226 ops/s
標準偏差: 4,947,858 ops/s (5.94%)

Phase 2: 性能比較分析

相対性能（mimallocを100%として）

アロケータ	スループット比	性能ギャップ
mimalloc	100.0%	ベースライン
libc malloc	69.0%	-31.0%
HAKMEM	4.0%	-96.0%

実行時間の内訳（perf stat）

HAKMEM (16-1024B)

Total time: 0.276s
  User time: 0.038s (13.8%)
  Sys time:  0.238s (86.2%)  ← カーネル時間が支配的
Page faults: 6,762
Cycles: 1,138,338,103

mimalloc (16-1024B)

Total time: 0.011s
  User time: 0.010s (90.9%)
  Sys time:  0.001s (9.1%)
Page faults: 146
Cycles: 35,872,448

libc malloc (16-1024B)

Total time: 0.013s
  User time: 0.012s (92.3%)
  Sys time:  0.001s (7.7%)
Page faults: 134
Cycles: 48,695,085

重要な発見: HAKMEMの実行時間の86%がカーネル時間（システムコール）であり、これはページフォルトとmadvise()呼び出しによるものです。

Phase 3: perf profiling分析

CPU時間トップ10（cycles event）

58.62%  カーネル: madvise() syscall
  ├─ 53.19%  __x64_sys_madvise
  │   ├─ 44.53%  follow_page_mask (ページテーブルウォーク)
  │   └─ 8.66%   handle_mm_fault (ページフォルト処理)
  │       ├─ 7.60%  do_anonymous_page (新規ページアロケーション)
  │       │   ├─ 5.23%  alloc_anon_folio
  │       │   │   └─ 4.18%  __alloc_pages
  │       │   │       ├─ 2.07%  clear_page_erms (ページゼロクリア)
  │       │   │       ├─ 1.06%  cond_accept_memory
  │       │   │       └─ 1.04%  rmqueue
  │       │   ├─ 1.06%  folio_add_lru_vma
  │       │   └─ 1.02%  folio_add_new_anon_rmap
  │       └─ 1.05%  pte_offset_map_nolock
  ├─ 4.00%  __x64_sys_exit_group (終了処理)
  │   └─ 2.06%  tlb_flush_mmu
  └─ 1.01%  __x64_sys_munmap

ページフォルト統計（perf stat）

メトリック	HAKMEM	mimalloc	libc	HAKMEM/mimalloc比
Page faults	6,762	146	134	46.3倍
Minor faults	6,762	146	134	46.3倍
Major faults	0	0	0	-

重要: すべてのページフォルトはminor faults（既にメモリ内にあるがページテーブルエントリが未設定）であり、ディスクI/Oは発生していない。しかし、カーネルのページフォルト処理オーバーヘッドが莫大。

Phase 4: サイズクラス分析とコードパス調査

HAKMEMのサイズクラス構成（Tiny allocator）

16-1024Bサイズ範囲は、以下の8つのTinyサイズクラスでカバーされる：

クラス	サイズ	SuperSlab内オブジェクト数	SuperSlabサイズ
C1	16B	65,536	1MB
C2	32B	32,768	1MB
C3	64B	16,384	1MB
C4	128B	8,192	1MB
C5	256B	4,096	1MB
C6	512B	2,048	1MB
C7	1KB	1,024	1MB
(C0)	(8B)	(131,072)	(1MB)

ベンチマークログからの観測:

[WARMUP] SuperSlab prefault: 100000 warmup iterations (not timed)...
[SP_INTERNAL_ALLOC] class_idx=2   ← 32Bクラス
[SS_ALLOC_PATH] pf_policy=0 populate=0 size_class=2
[SS_REG_DEBUG] class=2 ss=0x727500b00000 reg_ok=1 map_count=1
[SP_INTERNAL_ALLOC] class_idx=6   ← 512Bクラス
[SS_ALLOC_PATH] pf_policy=0 populate=0 size_class=6
[SS_REG_DEBUG] class=6 ss=0x727500a00000 reg_ok=1 map_count=2
[SP_INTERNAL_ALLOC] class_idx=7   ← 1KBクラス
[SS_ALLOC_PATH] pf_policy=0 populate=0 size_class=7
[SS_REG_DEBUG] class=7 ss=0x727500900000 reg_ok=1 map_count=3
[SP_INTERNAL_ALLOC] class_idx=7   ← 1KBクラス（2つ目）
[SS_REG_DEBUG] class=7 ss=0x727500800000 reg_ok=1 map_count=4
[WARMUP] Complete. Allocated=50098 Freed=49902 SuperSlabs populated.

割り当てパス（アロケーションフロー）

malloc(size)
  → tiny_alloc(size)
    → class_idx = size_to_class(size)    // 8クラスのいずれか
    → tiny_fast_pop(class_idx)            // Fast cache (per-class front cache)
      → HIT: return block
      → MISS: tiny_tls_mag_refill()       // TLS magazine refill
        → sll_pop() or shared_pool_acquire()
          → SuperSlab refill required
            → superslab_alloc()           // ← ここでページフォルト発生
              → mmap(1MB, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS)
                → カーネル: 256ページフォルト (1MB / 4KB = 256)

ページフォルトの発生源

1. SuperSlabアロケーション時（主要）

各サイズクラスで初めてSuperSlabをアロケートする際に発生：

1SuperSlabあたり256ページフォルト（1MB / 4KB = 256ページ）
ベンチマークで観測された4つのSuperSlab: 4 × 256 = 1,024ページフォルト

2. Partial Release機能（副次的）

superslab_partial_release() 関数（hakmem_tiny_intel.inc:685-698）:

static inline void superslab_partial_release(SuperSlab* ss, uint32_t epoch) {
#if defined(MADV_DONTNEED)
    if (!g_ss_partial_enable) return;
    if (!ss || ss->magic != SUPERSLAB_MAGIC) return;
    uint32_t prev = ss->partial_epoch;
    if (epoch != 0 && (epoch - prev) < g_ss_partial_interval) return;
    size_t len = (size_t)1 << ss->lg_size;
    if (madvise(ss, len, MADV_DONTNEED) == 0) {  // ← SuperSlab全体(1MB)をmadvise
        ss->partial_epoch = epoch;
    }
#endif
}

問題点:

SuperSlab全体（1MB = 256ページ）に対してmadvise(MADV_DONTNEED)を呼び出す
これにより、次回アクセス時に再度256ページフォルトが発生
refill間隔（g_ss_partial_interval）のたびに実行される可能性がある

3. Warmup中のページフォルト内訳

Total page faults: 6,762
  - Initial SuperSlab allocation: ~1,024 (4 SuperSlabs × 256)
  - Additional faults: ~5,738
    - Partial release後の再アクセス
    - 他のTinyクラスやPool/SmallMidアロケーション
    - カーネルのメタデータページ

Phase 4.5: Partial Release無効化A/Bテスト

仮説

Partial Release機能が過剰なmadvise()呼び出しとページフォルトを引き起こしているのでは？

実験設定

# Partial Release無効化
HAKMEM_TINY_SS_PARTIAL=0 ./bench_random_mixed_hakmem 1000000 400 1

結果

設定	スループット (ops/s)	ページフォルト	改善率
Partial Release有効 (デフォルト)	4,844,380	6,762	ベースライン
Partial Release無効	4,942,831	6,778	+2.0%

結論

Partial Release機能は主要な性能ボトルネックではない。

スループット改善はわずか2.0%（誤差範囲内）
ページフォルト数もほぼ同じ（6,762 vs 6,778）
主要なページフォルトは初期SuperSlabアロケーション時に発生している

Phase 5: 根本原因分析

性能差の根本原因（重要度順）

1. SuperSlabアロケーション戦略の非効率性（最重要）

問題:

HAKMEMは各サイズクラスに対して1MBのSuperSlabをmmap()でアロケート
mmap()直後、ページはカーネルにマッピングされているが物理メモリは未割り当て
初回アクセス時にページフォルトが発生し、カーネルがページを割り当て
1MB SuperSlab = 256ページ × 4KB = 256ページフォルト

mimalloc/libcとの違い:

mimallocはより小さいチャンク（4KB-64KB）を使用し、段階的に拡張
libcはsbrk()やより効率的なmmap()戦略を使用
両者とも初期アロケーションのページフォルトが少ない

証拠:

HAKMEM:      6,762 page faults / 1M operations = 6.76 faults/1000 ops
mimalloc:    146 page faults / 1M operations = 0.15 faults/1000 ops
libc:        134 page faults / 1M operations = 0.13 faults/1000 ops

2. カーネル時間の支配（システムコールオーバーヘッド）

perf stat分析:

HAKMEM実行時間: 0.276s
  User time: 0.038s (13.8%)
  Sys time:  0.238s (86.2%)  ← カーネル時間が支配的

内訳:

58.62%の時間がmadvise()システムコール内で消費
ページフォルト処理にかかる時間が莫大
ページテーブルウォーク、ページアロケーション、TLBフラッシュなど

対比:

mimalloc: User 90.9%, Sys 9.1%   ← ユーザー空間で完結
libc:     User 92.3%, Sys 7.7%   ← ユーザー空間で完結
HAKMEM:   User 13.8%, Sys 86.2%  ← カーネルで大半を消費

3. ページフォルトあたりのコスト

1ページフォルトあたりのコスト推定:

HAKMEM総CPU時間: 276ms
ページフォルト数: 6,762
1ページフォルトあたり: 276ms / 6,762 = 40.8μs

対比:
mimalloc: 11ms / 146 = 75.3μs per fault
libc:     13ms / 134 = 97.0μs per fault

HAKMEMのページフォルトコストがやや低いのは、カーネルが連続した領域のフォルトを効率的に処理しているため。しかし、フォルト数自体が46倍多いため、総コストは莫大。

4. ワーキングセット効率の低さ

HAKMEMの問題:

小規模ベンチマーク（ws=400, 1M iterations）でも4つのSuperSlabをアロケート
各SuperSlabは1MB = 256ページ = 合計**1,024ページ（4MB）**を消費
しかし、実際に使用されるメモリはごくわずか（400オブジェクト × 平均サイズ ~500B = ~200KB）

メモリ効率:

割り当てメモリ: 4MB (4 SuperSlabs)
実使用メモリ:   ~200KB
効率:          200KB / 4MB = 5%  ← 95%が無駄

mimalloc/libcの戦略:

必要な分だけ段階的にアロケート（demand paging）
より小さい粒度でメモリを管理
ページフォルトが発生する前にprefetchやMAP_POPULATEなどの最適化を活用

5. madvise()呼び出しの頻度（Partial Release）

Partial Release機能がオンの場合、定期的にSuperSlab全体にmadvise()を実行：

// hakmem_tiny_intel.inc:685-698
if (madvise(ss, 1MB, MADV_DONTNEED) == 0) { ... }

影響:

madvise()はシステムコールであり、カーネルモードへの遷移コストがかかる
MADV_DONTNEEDは物理ページを解放し、次回アクセス時に再度ページフォルト
しかし、A/Bテストの結果、この影響はわずか2%（副次的）

比較: 8-128B vs 16-1024B

8-128Bサイズ範囲での測定

./bench_tiny_hot_hakmem 1000000 400 1

結果:

Throughput: ~88M ops/s  (16-1024Bの約18倍速い)
Page faults: 6,734      (16-1024Bとほぼ同じ)
Cycles: 742,201,607     (16-1024Bの約65%)

比較分析

メトリック	8-128B	16-1024B	比率
スループット	~88M ops/s	4.84M ops/s	18.2倍
ページフォルト	6,734	6,762	1.00倍
CPUサイクル	742M	1,138M	0.65倍

重要な発見:

ページフォルト数はほぼ同じ（サイズ範囲に依存しない）
- これは、ページフォルトがSuperSlabアロケーション時に集中していることを示す
8-128Bが18倍速い理由:
- サイズクラスが少ない（C0-C4の5クラス vs C0-C7の8クラス）
- オブジェクトサイズが小さく、キャッシュ効率が高い
- より少ないSuperSlabで済む（メモリ効率が良い）
16-1024Bが遅い理由:
- 大きなオブジェクト（512B, 1KB）のキャッシュ効率が低い
- より多くのSuperSlabが必要（クラスが多い）
- 同じページフォルト数でも、処理するデータ量が多い

推奨される次の最適化

優先度1: SuperSlabプリフォールト最適化【即効性: 高】

現状の問題:

mmap()後、ページは仮想アドレス空間にマッピングされるが物理メモリは未割り当て
初回アクセス時にページフォルトが発生
1MB SuperSlab = 256ページフォルト

提案:

1-A. MAP_POPULATE使用（最優先）

// hakmem_tiny_superslab.c: superslab_alloc()
void* ptr = mmap(NULL, SUPERSLAB_SIZE,
                 PROT_READ | PROT_WRITE,
                 MAP_PRIVATE | MAP_ANONYMOUS | MAP_POPULATE,  // ← 追加
                 -1, 0);

効果:

mmap()時にカーネルがページを事前割り当て
ページフォルトをバッチ処理（TLBフラッシュが1回で済む）
期待効果: 5-10倍の性能向上（カーネル時間を86% → 10%以下に削減）

トレードオフ:

初期mmap()が遅くなる（ただし、warmup中なので問題ない）
RSS（物理メモリ使用量）が増える（ただし、現在も4MBは使っているので変わらない）

1-B. madvise(MADV_WILLNEED)による明示的プリフェッチ

// SuperSlabアロケーション直後
void* ss = mmap(...);
madvise(ss, SUPERSLAB_SIZE, MADV_WILLNEED);  // カーネルにページ事前準備を通知

効果:

カーネルがバックグラウンドでページを準備
ページフォルトを事前に解決
期待効果: 3-5倍の性能向上

1-C. 手動メモリタッチ（fallback）

// SuperSlabアロケーション直後
void* ss = mmap(...);
// 各ページの最初のバイトに書き込んでページフォルトを強制
for (size_t i = 0; i < SUPERSLAB_SIZE; i += 4096) {
    ((volatile char*)ss)[i] = 0;
}

効果:

確実にページフォルトを強制
MAP_POPULATEが使えない環境でも動作
期待効果: 2-4倍の性能向上

推奨実装順序:

MAP_POPULATEを試す（最も効果が高い）
効果が不十分ならMADV_WILLNEEDを追加
古いカーネルではfallbackとして手動タッチ

優先度2: SuperSlabサイズのチューニング【即効性: 中】

現状の問題:

1MB SuperSlabは大きすぎる（小規模ワークロードで無駄が多い）
小規模ベンチマーク（ws=400）で4MB使うのは非効率（実使用は200KB）

提案:

2-A. サイズクラス別SuperSlabサイズ

// 大きなオブジェクトほど小さいSuperSlabを使う
size_t superslab_size_for_class(int class_idx) {
    if (class_idx <= 2) return 1024 * 1024;  // 16-32B: 1MB
    if (class_idx <= 4) return 512 * 1024;   // 64-128B: 512KB
    return 256 * 1024;                       // 256B-1KB: 256KB
}

効果:

大きなオブジェクトクラスのページフォルトを削減（1KB: 256→64ページフォルト）
RSS削減（4MB → ~1.5MB）
期待効果: 1.5-2倍の性能向上

2-B. アダプティブSuperSlabサイズ

// ワークロードに応じてSuperSlabサイズを動的調整
// 小規模ワークロード: 256KB
// 大規模ワークロード: 1MB-2MB

効果:

ワークロードに最適化
期待効果: 1.3-1.8倍の性能向上

優先度3: Partial Release戦略の見直し【即効性: 低】

現状の問題:

SuperSlab全体（1MB）にmadvise()を実行
次回アクセス時に再度256ページフォルト

提案:

3-A. Partial Releaseのデフォルト無効化

// hakmem_tiny_config.h
#define TINY_SS_PARTIAL_ENABLE_DEFAULT 0  // 現在: 1

効果:

A/Bテストで2%の改善を確認済み
期待効果: 1.02倍の性能向上（すでに測定済み）

3-B. 粒度の細かいPartial Release

// SuperSlab全体ではなく、未使用Slabのみをリリース
for (int slab_idx = 0; slab_idx < SLABS_PER_SUPERSLAB; slab_idx++) {
    if (slab_is_empty(ss, slab_idx)) {
        madvise(ss->slabs[slab_idx], SLAB_SIZE, MADV_DONTNEED);
    }
}

効果:

より細かい粒度でメモリ解放
ページフォルトを最小化
期待効果: 1.1-1.3倍の性能向上

優先度4: アロケーションパスの最適化【即効性: 中】

提案:

4-A. Fast Cache容量の増加（大きなオブジェクト）

// hakmem_tiny_config.h
// 512B-1KBクラスのFast Cache容量を増やす
g_fast_cap_defaults[6] = 128;  // 512B: 64 → 128
g_fast_cap_defaults[7] = 128;  // 1KB:  64 → 128

効果:

SuperSlabへのアクセス頻度削減
ページフォルトトリガーの減少
期待効果: 1.2-1.5倍の性能向上

4-B. TLS Magazine容量の動的調整

// ACE学習を活用して、16-1024Bワークロードに最適化
// 現在のACEは8-128Bに最適化されている可能性

効果:

より効率的なキャッシング戦略
期待効果: 1.1-1.3倍の性能向上

総合最適化の期待効果

段階的最適化シナリオ

フェーズ	最適化内容	期待スループット	累積改善
現状	ベースライン	4.8M ops/s	1.0x
Phase 1	MAP_POPULATE追加	24-48M ops/s	5-10x
Phase 2	SuperSlabサイズ調整	36-86M ops/s	7.5-18x
Phase 3	Partial Release無効化	37-88M ops/s	7.7-18.2x
Phase 4	Cache容量最適化	44-110M ops/s	9.2-23x
目標	mimalloc並み	120M ops/s	25x

現実的な改善予測

保守的見積もり（Phase 1のみ）:

MAP_POPULATE実装: 5倍の性能向上 → 24M ops/s
これだけでlibcの29%、mimallocの20%まで到達

楽観的見積もり（Phase 1-4全実装）:

累積効果: 15-20倍の性能向上 → 72-96M ops/s
libcを上回り、mimallocの60-80%まで到達

mimalloc並みを達成するには:

上記最適化に加えて、アロケーションパス全体の根本的な見直しが必要
より小さい粒度のメモリ管理（4KB-64KBチャンク）
madvise()呼び出しの完全排除（またはバックグラウンド化）

技術メモ

SuperSlabアーキテクチャの設計トレードオフ

現在の設計（1MB SuperSlab）の利点:

アドレス空間の効率的管理: 1MBアラインメントで高速なポインタ→SuperSlab逆引き
メタデータの局所性: SuperSlabヘッダーと実データが同じ1MB領域に格納
キャッシュフレンドリー: 大きなチャンクでTLBエントリを節約

現在の設計の欠点（本分析で判明）:

初期ページフォルトコストが高い: 1MB = 256ページフォルト
小規模ワークロードで非効率: ws=400でも4MB使う（実使用200KB）
Partial Releaseの粒度が粗い: 1MB全体をリリースすると次回256ページフォルト

mmap()とページフォルトのメカニズム

Linuxカーネルの動作:

1. mmap()呼び出し
   ↓
2. カーネルが仮想アドレス空間を予約（VMA作成）
   ← この時点では物理メモリは未割り当て
   ↓
3. ユーザー空間でメモリアクセス
   ↓
4. ページフォルト発生（CPUがMMUを通じてカーネルにトラップ）
   ↓
5. カーネルがdo_anonymous_page()を呼び出し
   ├─ 物理ページをアロケート（__alloc_pages）
   ├─ ページをゼロクリア（clear_page_erms）
   ├─ ページテーブルエントリを設定
   └─ TLBにエントリを追加
   ↓
6. ユーザー空間に戻る

ページフォルトのコスト:

CPU: ~1000-3000サイクル（約0.3-1.0μs @ 3GHz）
カーネル処理: ~40μs（本分析の測定値）
合計: 約40μs/ページフォルト

1MB SuperSlab = 256ページフォルト = 10.2msのオーバーヘッド

MAP_POPULATEの効果

MAP_POPULATEの動作:

void* ptr = mmap(NULL, size, PROT_READ|PROT_WRITE,
                 MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, -1, 0);

カーネルの処理:

VMA作成（通常のmmapと同じ）
faultin_page_range()を呼び出し、全ページを事前割り当て
ページフォルトをバッチ処理（TLBフラッシュが1回で済む）
ユーザー空間に戻る

利点:

ページフォルトのオーバーヘッドを5-10倍削減
TLBフラッシュを1回に集約
カーネル/ユーザー空間の遷移を削減

欠点:

mmap()の実行時間が長くなる（ただし、warmup中なので問題ない）
RSS（物理メモリ使用量）が即座に増加

競合アロケータの戦略

mimalloc

小さいチャンク: 4KB-64KB（1MBではない）
段階的拡張: 必要に応じて徐々に拡張
ページフォルトの分散: 一度に大量のページフォルトが発生しない
TLS最適化: スレッドローカルキャッシュが非常に効率的

libc malloc (glibc)

arenasベース: スレッドごとにarenaを持つ
small bins/large bins: サイズ別に効率的な管理
sbrk()とmmap()の併用: 小さい割り当てにはsbrk()、大きい割り当てにはmmap()
チューニング済み: 数十年の最適化の蓄積

HAKMEM（改善前）

大きいチャンク: 1MB SuperSlab（最初から大きい）
一括アロケーション: 初期に大量のページフォルト
Partial Release: 積極的なメモリ解放（ただし再フォルトコスト）
最適化余地: 上記提案により5-25倍の改善が可能

次のステップ

Phase 1実装 (優先度: 最高)

# MAP_POPULATEを追加
git checkout -b opt/map-populate
# hakmem_tiny_superslab.c を編集
make bench_random_mixed_hakmem
./bench_random_mixed_hakmem 1000000 400 1
# 期待結果: 24-48M ops/s（5-10倍改善）

Phase 2実装 (優先度: 高)

# サイズクラス別SuperSlabサイズ
git checkout -b opt/adaptive-superslab-size
# hakmem_tiny_config.h を編集
make bench_random_mixed_hakmem
./bench_random_mixed_hakmem 1000000 400 1
# 期待結果: 36-72M ops/s（累積7.5-15倍改善）

Phase 3-4実装 (優先度: 中)
- Partial Release無効化（ENV経由で即テスト可能）
- Cache容量チューニング

統合テスト

# すべての最適化を統合
make bench_random_mixed_hakmem
./bench_random_mixed_hakmem 10000000 400 1  # 10M iterations
# 目標: 70-100M ops/s（mimalloc並み）

参考資料

ソースコード参照

ベンチマークコード: /mnt/workdisk/public_share/hakmem/bench_random_mixed.c
SuperSlabアロケーション: /mnt/workdisk/public_share/hakmem/core/hakmem_tiny_superslab.c
Partial Release: /mnt/workdisk/public_share/hakmem/core/hakmem_tiny_intel.inc:685-698
Tiny設定: /mnt/workdisk/public_share/hakmem/core/hakmem_tiny_config.h
madviseバッチ処理: /mnt/workdisk/public_share/hakmem/core/hakmem_batch.c

測定コマンド

# スループット測定
./bench_random_mixed_hakmem 1000000 400 1
./bench_random_mixed_mi 1000000 400 1
./bench_random_mixed_system 1000000 400 1

# ページフォルト測定
perf stat -e page-faults,cycles ./bench_random_mixed_hakmem 1000000 400 1

# プロファイリング
perf record -F 99 -g -e cycles,page-faults ./bench_random_mixed_hakmem 1000000 400 1
perf report --stdio

# Partial Release無効化テスト
HAKMEM_TINY_SS_PARTIAL=0 ./bench_random_mixed_hakmem 1000000 400 1

Linux カーネル機能

mmap(2): man 2 mmap
madvise(2): man 2 madvise
MAP_POPULATE: Linux 2.5.46以降で利用可能
MADV_WILLNEED: ページプリフェッチヒント
MADV_DONTNEED: ページ解放（次回アクセス時にページフォルト）
MADV_FREE: Linux 4.5以降、MADV_DONTNEEDより軽量

まとめ

主要発見

HAKMEMは16-1024Bサイズ範囲でmimallocの1/25の性能（4.8M vs 120M ops/s）
根本原因はページフォルト（6,762 vs 146 = 46倍）
実行時間の86%がカーネル時間（madvise()とページフォルト処理）
Partial Release機能の影響は軽微（わずか2%の改善）
MAP_POPULATEで5-10倍の改善が期待できる（即効性が高い）

次のアクション

即座に実施すべき最適化:

MAP_POPULATEの追加（期待: 5-10倍改善）
Partial Releaseのデフォルト無効化（期待: 2%改善）

中期的な最適化: 3. SuperSlabサイズのチューニング（期待: 1.5-2倍改善） 4. Cache容量の最適化（期待: 1.2-1.5倍改善）

長期的な検討: 5. SuperSlabアーキテクチャの根本的見直し（より小さい粒度のメモリ管理） 6. madvise()の完全排除またはバックグラウンド化

目標達成の見通し:

Phase 1-2実装で7.5-15倍の改善（36-72M ops/s）が現実的
mimalloc並み（120M ops/s）を達成するには、さらなるアーキテクチャ改善が必要

報告者: Claude (Anthropic) 分析日時: 2025年12月5日 測定環境: Linux 6.8.0-87-generic, x86_64

29 KiB Raw Permalink Blame History Unescape Escape

16-1024B パフォーマンス分析レポート

Quick Baseline Refresh (2025-12-10, current HEAD, C7-only v3 / front v3 ON)

Quick Baseline Refresh (2025-12-05, C7-only v3 / front v3 ON)

エグゼクティブサマリー

測定結果サマリー

性能差の規模

Phase 1: ベンチマーク測定（詳細）

測定条件

HAKMEM測定結果（3回実行）

mimalloc測定結果（3回実行）

libc malloc測定結果（3回実行）

Phase 2: 性能比較分析

相対性能（mimallocを100%として）

実行時間の内訳（perf stat）

HAKMEM (16-1024B)

mimalloc (16-1024B)

libc malloc (16-1024B)

Phase 3: perf profiling分析

CPU時間トップ10（cycles event）

ページフォルト統計（perf stat）

Phase 4: サイズクラス分析とコードパス調査

HAKMEMのサイズクラス構成（Tiny allocator）

割り当てパス（アロケーションフロー）

ページフォルトの発生源

1. SuperSlabアロケーション時（主要）

2. Partial Release機能（副次的）

3. Warmup中のページフォルト内訳

Phase 4.5: Partial Release無効化A/Bテスト

仮説

実験設定

結果

結論

Phase 5: 根本原因分析

性能差の根本原因（重要度順）

1. SuperSlabアロケーション戦略の非効率性（最重要）

2. カーネル時間の支配（システムコールオーバーヘッド）

3. ページフォルトあたりのコスト

4. ワーキングセット効率の低さ

5. madvise()呼び出しの頻度（Partial Release）

比較: 8-128B vs 16-1024B

8-128Bサイズ範囲での測定

比較分析

推奨される次の最適化

優先度1: SuperSlabプリフォールト最適化 【即効性: 高】

1-A. MAP_POPULATE使用（最優先）

1-B. madvise(MADV_WILLNEED)による明示的プリフェッチ

1-C. 手動メモリタッチ（fallback）

優先度2: SuperSlabサイズのチューニング 【即効性: 中】

2-A. サイズクラス別SuperSlabサイズ

2-B. アダプティブSuperSlabサイズ

優先度3: Partial Release戦略の見直し 【即効性: 低】

3-A. Partial Releaseのデフォルト無効化

3-B. 粒度の細かいPartial Release

優先度4: アロケーションパスの最適化 【即効性: 中】

4-A. Fast Cache容量の増加（大きなオブジェクト）

4-B. TLS Magazine容量の動的調整

総合最適化の期待効果

段階的最適化シナリオ

現実的な改善予測

技術メモ

SuperSlabアーキテクチャの設計トレードオフ

mmap()とページフォルトのメカニズム

MAP_POPULATEの効果

競合アロケータの戦略

mimalloc

libc malloc (glibc)

HAKMEM（改善前）

次のステップ

参考資料

ソースコード参照

測定コマンド

Linux カーネル機能

まとめ

主要発見

次のアクション

29 KiB

Raw Permalink Blame History

優先度1: SuperSlabプリフォールト最適化【即効性: 高】

優先度2: SuperSlabサイズのチューニング【即効性: 中】

優先度3: Partial Release戦略の見直し【即効性: 低】

優先度4: アロケーションパスの最適化【即効性: 中】