第8章：計算機アーキテクチャと性能最適化の科学
8.1 計算機アーキテクチャの歴史と基礎
8.1.1 フォン・ノイマン・アーキテクチャ
現代のほぼ全てのコンピュータは、1945年にJohn von Neumannが提案したアーキテクチャに基づいている。このアーキテクチャの核心的な特徴を理解することは、性能最適化の第一歩である。
フォン・ノイマン・アーキテクチャの5大コンポーネント：
graph TD
subgraph CPU
CU[Control Unit]
DP[Datapath]
ALU
Reg[Registers]
DP --- ALU
DP --- Reg
CU --- DP
end
CPU <-->|Bus| MEM[Main Memory]
MEM <-->|Bus| IO[Input/Output]
フォン・ノイマン・ボトルネック：
この古典的設計には根本的な性能限界がある。CPUとメモリ間のデータ転送が単一のバスを通じて行われるため、メモリ帯域幅がシステム全体の性能を制限する。
CPUの進化（クロック速度）：
1971年: Intel 4004 740 kHz
1985年: Intel 386 16 MHz （約20倍）
2000年: Pentium 4 1.5 GHz （約100倍）
2024年: Modern CPU 5+ GHz （約3倍）
メモリ速度の進化：
1980年: DRAM ~200 ns
2000年: DDR SDRAM ~50 ns （約4倍）
2024年: DDR5 ~14 ns （約3倍）
結論：CPUはメモリより遥かに速く進化
→ メモリアクセスが最大のボトルネック
8.1.2 メモリ階層の理論
局所性の原理（Principle of Locality）は、メモリ階層設計の基礎である。
時間的局所性（Temporal Locality）： 最近アクセスされたデータは、近い将来に再びアクセスされる可能性が高い。
// 時間的局所性の例
int sum = 0;
for (int i = 0; i < 1000; i++) {
sum += i; // 'sum' は何度もアクセスされる
}
空間的局所性（Spatial Locality）： アクセスされたデータの近くにあるデータは、近い将来にアクセスされる可能性が高い。
// 空間的局所性の例
int arr[1000];
for (int i = 0; i < 1000; i++) {
arr[i] = i; // 連続したメモリ位置にアクセス
}
メモリ階層ピラミッド：
block-beta
columns 1
Reg["Registers (<1ns)"]
L1["L1 Cache (1-2ns)"]
L2["L2 Cache (3-10ns)"]
L3["L3 Cache (10-40ns)"]
Mem["Main Memory (50-100ns)"]
SSD["SSD (10-100us)"]
HDD["HDD (ms)"]
style Reg fill:#f9f
style L1 fill:#ff9
style L2 fill:#ff9
style L3 fill:#ff9
style Mem fill:#9f9
style SSD fill:#99f
style HDD fill:#99f
8.1.3 キャッシュの動作原理
キャッシュは、CPUとメインメモリの速度差を埋める重要な役割を果たす。
キャッシュライン（Cache Line）：
典型的なキャッシュライン = 64バイト
メモリアドレスの分解：
例：64バイトラインの場合
- Offset: 6ビット（64 = 2^6）
- 1バイトをアクセス → 64バイト全体がロード
キャッシュの構造：
1. 直接マップ（Direct Mapped）
- 各メモリブロックは1箇所にしかマッピングできない
- 単純だが衝突しやすい
2. 全連想（Fully Associative）
- 任意の位置にマッピング可能
- 最も柔軟だがハードウェアが複雑
3. セット連想（Set Associative）
- N-way: N箇所のいずれかにマッピング
- 現代のCPUは8-way〜16-wayが一般的
キャッシュミスの種類：
1. 強制ミス（Compulsory Miss）
- 初回アクセス時に必ず発生
- 対策：プリフェッチ
2. 容量ミス（Capacity Miss）
- キャッシュが小さすぎる
- 対策：データ分割、ブロッキング
3. 競合ミス（Conflict Miss）
- 同じキャッシュセットへのマッピング衝突
- 対策：データ配置の調整
8.1.4 現代CPUのマイクロアーキテクチャ
パイプライン処理（Pipelining）：
命令の実行を複数のステージに分割し、並列処理を実現する。
クラシック5段パイプライン（MIPS）：
IF = Instruction Fetch（命令フェッチ）
ID = Instruction Decode（命令デコード）
EX = Execute（実行）
MEM = Memory Access（メモリアクセス）
WB = Write Back（書き戻し）
理想的にはN命令がN+4サイクルで完了（スループット向上）
パイプラインハザード：
1. 構造ハザード（Structural Hazard）
- 複数の命令が同じハードウェア資源を要求
- 対策：ハードウェアの複製
2. データハザード（Data Hazard）
- 命令間のデータ依存関係
- 対策：フォワーディング、ストール
例：
ADD R1, R2, R3 ; R1 = R2 + R3
SUB R4, R1, R5 ; R1 を使用（まだ書き込まれていない！）
3. 制御ハザード（Control Hazard）
- 分岐命令による実行フローの不確定性
- 対策：分岐予測
分岐予測（Branch Prediction）：
分岐予測器の進化：
1. 静的予測
- 常に taken または not taken と予測
- 予測精度: 約50-70%
2. 2ビット飽和カウンタ
- 履歴に基づいて予測
- 状態: Strong Not Taken → Weak Not Taken →
Weak Taken → Strong Taken
- 予測精度: 約85-90%
3. 相関予測器（Two-Level Predictor）
- 他の分岐の結果を考慮
- 予測精度: 約95%
4. ニューラル分岐予測器
- 機械学習ベース
- 予測精度: 約99%
誤予測のペナルティ：10-20サイクル
スーパースカラーとアウトオブオーダー実行：
スーパースカラー：
- 1サイクルで複数の命令を発行
- 現代のCPUは4-8命令/サイクル
アウトオブオーダー実行：
- 依存関係のない命令を先に実行
- 命令ウィンドウ（ROB）で順序を追跡
例：
1: LOAD R1, [mem] ; メモリアクセス（遅い）
2: ADD R2, R3, R4 ; R1に依存しない → 先に実行可能
3: SUB R5, R1, R6 ; R1に依存 → LOADを待つ
実行順序: 2 → 1 → 3 （プログラム順序: 1 → 2 → 3）
8.2 漸近的計算量と実際の性能
8.2.1 Big-O表記の限界
アルゴリズムの計算量（Big-O）は重要だが、実際の性能を完全には予測できない。
定数因子の影響：
// 両方とも O(n) だが、実行時間は大きく異なる
// 実装A：単純なループ
size_t strlen_naive(const char *s)
{
size_t len = 0;
while (s[len])
len++;
return len;
}
// 実装B：8バイトずつ処理
size_t strlen_word(const char *s)
{
// アラインメント調整 + 8バイト処理
// 約5-10倍高速
}
// Big-Oは同じ O(n) でも、
// 実際の時間は T_A(n) = c₁ × n
// T_B(n) = c₂ × n （c₂ << c₁）
メモリアクセスパターンの影響：
// 両方とも O(n×n) だが、性能は大きく異なる
// 行優先アクセス（良い）
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += matrix[i][j]; // 連続したメモリアクセス
// 列優先アクセス（悪い）
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += matrix[i][j]; // 不連続なメモリアクセス
// N = 1000 の場合：
// 行優先: キャッシュヒット率 ~99%
// 列優先: キャッシュヒット率 ~10%（100倍以上遅い可能性）
8.2.2 キャッシュ効率の数学
キャッシュミス率と実行時間：
実行時間 = ヒットサイクル + ミスペナルティ × ミス率
例：
- L1ヒット: 4サイクル
- L1ミス、L2ヒット: 12サイクル
- L2ミス: 100サイクル
アルゴリズムA: ミス率 1%
平均サイクル = 4 + 0.01 × 100 = 5サイクル
アルゴリズムB: ミス率 10%
平均サイクル = 4 + 0.10 × 100 = 14サイクル
→ ミス率10%で約3倍遅い
ワーキングセットサイズ：
ワーキングセット = プログラムが頻繁にアクセスするデータの集合
L1に収まる（<32KB）: 最速
L2に収まる（<256KB）: 高速
L3に収まる（<8MB）: 中速
メモリのみ: 低速
libft関数のワーキングセット：
- ft_isalpha: 1バイト（常にL1ヒット）
- ft_strlen(短い文字列): <1KB（L1ヒット）
- ft_memcpy(大きなデータ): サイズ依存
8.2.3 Rooflineモデル
Rooflineモデルは、性能のボトルネックを視覚的に理解するためのツールである。
性能 (FLOPS)
│
│ ┌──────────── Compute Bound
│ ╱
│ ╱
│ ╱
│ ╱
│ ╱
│ ╱
│ ╱
│ ╱
│ ╱ Memory Bound
│ ╱
└─────────────────────────────────────
算術強度 (FLOPS/Byte)
算術強度 = 計算量 / メモリ転送量
libft関数の分類：
メモリバウンド（低い算術強度）：
- ft_memcpy: 算術強度 ≈ 0（単純なコピー）
- ft_memset: 算術強度 ≈ 0（単純な書き込み）
- ft_strlen: 算術強度 ≈ 0.1（比較のみ）
計算バウンド（高い算術強度）：
- ft_atoi: 算術強度 > 1（多くの算術演算）
- ft_itoa: 算術強度 > 1（除算と変換）
ほとんどのlibft関数はメモリバウンド
→ メモリ帯域幅の最大化が重要
8.3 SIMDとベクトル化の理論
8.3.1 SIMD（Single Instruction, Multiple Data）
SIMDは、単一の命令で複数のデータを並列処理する技術である。
フリンの分類（Flynn's Taxonomy）：
| | Single Data | Multiple Data | |:-|:------------|:--------------| | Single Instruction | SISD（従来のスカラ処理） | SIMD（ベクトル処理） | | Multiple Instruction | MISD（稀なアーキテクチャ） | MIMD（マルチコア/マルチプロセッサ） |
x86 SIMD拡張の歴史：
1996年: MMX 64ビットレジスタ（整数のみ）
1999年: SSE 128ビットレジスタ（浮動小数点追加）
2001年: SSE2 128ビット整数演算強化
2004年: SSE3 水平演算追加
2006年: SSSE3 バイトシャッフル追加
2007年: SSE4 文字列処理命令追加
2011年: AVX 256ビットレジスタ
2013年: AVX2 256ビット整数演算
2017年: AVX-512 512ビットレジスタ
SIMDの動作原理：
スカラー演算 vs SIMD演算
スカラー（1つずつ処理）：
A[0] + B[0] → C[0]
A[1] + B[1] → C[1]
A[2] + B[2] → C[2]
A[3] + B[3] → C[3]
= 4命令
SIMD（並列処理）：
*1命令で4つのデータを同時処理（理論上4倍高速）*
8.3.2 ベクトル化の条件
コンパイラが自動ベクトル化を行うには、いくつかの条件が必要である。
ベクトル化可能なループの条件：
// ベクトル化可能
for (int i = 0; i < n; i++)
a[i] = b[i] + c[i]; // 各反復が独立
// ベクトル化困難（ループ運搬依存性）
for (int i = 1; i < n; i++)
a[i] = a[i-1] + b[i]; // 前の反復結果に依存
// ベクトル化困難（関数呼び出し）
for (int i = 0; i < n; i++)
a[i] = unknown_function(b[i]); // 副作用の可能性
// ベクトル化困難（条件分岐）
for (int i = 0; i < n; i++)
if (b[i] > 0)
a[i] = b[i]; // 分岐あり（マスク処理で対応可能）
手動ベクトル化 vs コンパイラ自動ベクトル化：
// コンパイラへのヒント
#pragma GCC ivdep // 依存関係がないことを保証
for (int i = 0; i < n; i++)
a[i] = b[i] + c[i];
// 手動ベクトル化（SSE2）
#include <emmintrin.h>
void add_sse2(float *a, float *b, float *c, int n)
{
int i;
for (i = 0; i + 4 <= n; i += 4)
{
__m128 va = _mm_loadu_ps(&a[i]);
__m128 vb = _mm_loadu_ps(&b[i]);
__m128 vc = _mm_add_ps(va, vb);
_mm_storeu_ps(&c[i], vc);
}
// 残りをスカラー処理
for (; i < n; i++)
c[i] = a[i] + b[i];
}
8.3.3 null終端文字列のSIMD処理
文字列操作はSIMDの典型的な応用である。
SIMDによるnull検出の原理：
/*
* 問題: 16バイトの中からnull（0x00）を見つける
*
* SSE2命令を使用:
* 1. _mm_load_si128: 16バイトをロード
* 2. _mm_cmpeq_epi8: 各バイトを0と比較
* 3. _mm_movemask_epi8: 比較結果をビットマスクに変換
*
* 例:
* データ: "Hello World\0abc"
* H e l l o W o r l d \0 a b c ?
* 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 ← 比較結果
* マスク: 0b0000100000000000 = 0x0800
* __builtin_ctz(0x0800) = 11 ← nullの位置
*/
8.4 性能測定の科学
8.4.1 時間測定の理論
時間測定の階層：
1. wall-clock time（実時間）
- 実世界での経過時間
- OSのスケジューリングを含む
2. CPU time
- プロセスがCPUを使用した時間
- user time + system time
3. cycle count
- CPUサイクル数
- 最も詳細な測定
測定の不確実性：
測定誤差の要因：
1. タイマーの解像度（通常 1-100 ns）
2. 割り込みによる遅延
3. コンテキストスイッチ
4. キャッシュの状態
5. 周波数スケーリング（Turbo Boost等）
6. 熱スロットリング
対策：
- 複数回測定して統計処理
- コールドキャッシュ/ウォームキャッシュの区別
- 周波数を固定（ベンチマーク時）
- 外れ値の除去
8.4.2 統計的ベンチマーク
信頼性のある測定のための統計手法：
// 統計的に信頼性のある測定
typedef struct s_measurement {
double mean; // 平均
double std_dev; // 標準偏差
double median; // 中央値
double min; // 最小値
double max; // 最大値
double p95; // 95パーセンタイル
int n_samples; // サンプル数
} t_measurement;
t_measurement measure_function(void (*func)(void), int iterations)
{
double *samples = malloc(iterations * sizeof(double));
t_measurement result;
// ウォームアップ（キャッシュを温める）
for (int i = 0; i < 100; i++)
func();
// 測定
for (int i = 0; i < iterations; i++)
{
struct timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start);
func();
clock_gettime(CLOCK_MONOTONIC, &end);
samples[i] = (end.tv_sec - start.tv_sec) * 1e9 +
(end.tv_nsec - start.tv_nsec);
}
// ソート（中央値とパーセンタイル用）
qsort(samples, iterations, sizeof(double), compare_double);
// 統計計算
result.min = samples[0];
result.max = samples[iterations - 1];
result.median = samples[iterations / 2];
result.p95 = samples[(int)(iterations * 0.95)];
// 平均と標準偏差
double sum = 0, sq_sum = 0;
for (int i = 0; i < iterations; i++)
sum += samples[i];
result.mean = sum / iterations;
for (int i = 0; i < iterations; i++)
sq_sum += (samples[i] - result.mean) * (samples[i] - result.mean);
result.std_dev = sqrt(sq_sum / iterations);
result.n_samples = iterations;
free(samples);
return result;
}
8.4.3 ハードウェア性能カウンタ
現代のCPUには、詳細な性能分析のためのカウンタが内蔵されている。
主要な性能カウンタ：
1. サイクル数（Cycles）
- 消費されたCPUサイクル
2. 命令数（Instructions）
- 実行された命令数
- IPC = Instructions / Cycles
3. キャッシュミス
- L1, L2, L3 各レベルのミス
4. 分岐ミス予測
- 予測を外した分岐の数
5. TLBミス
- ページテーブル参照が必要になった回数
Linux perfを使った測定：
# 基本的な統計
perf stat ./test_program
# 詳細なカウンタ
perf stat -e cycles,instructions,cache-misses,branch-misses ./test_program
# 典型的な出力:
# 1,234,567,890 cycles
# 2,345,678,901 instructions # 1.90 IPC
# 123,456 cache-misses
# 12,345 branch-misses # 0.05%
8.5 libft関数の最適化実装
8.5.1 ft_strlen の最適化
段階的な最適化アプローチ：
// レベル0：ナイーブ実装
size_t ft_strlen_v0(const char *s)
{
size_t len = 0;
while (s[len])
len++;
return len;
}
// レベル1：ポインタ演算
size_t ft_strlen_v1(const char *s)
{
const char *ptr = s;
while (*ptr)
ptr++;
return ptr - s;
}
// レベル2：ループ展開
size_t ft_strlen_v2(const char *s)
{
const char *ptr = s;
// 4バイトずつチェック
while (ptr[0] && ptr[1] && ptr[2] && ptr[3])
ptr += 4;
// 残りを処理
while (*ptr)
ptr++;
return ptr - s;
}
// レベル3：ワード単位処理
size_t ft_strlen_v3(const char *s)
{
const char *ptr = s;
// アラインメント調整
while ((uintptr_t)ptr & 7)
{
if (!*ptr)
return ptr - s;
ptr++;
}
// 8バイト単位で処理
const uint64_t *word = (const uint64_t *)ptr;
/*
* ゼロバイト検出の原理：
*
* 0x0101010101010101 を減算すると、
* 各バイトが 0x00 の場合のみ最上位ビットが立つ。
*
* ~word で反転後、0x8080808080808080 とAND。
* 結果が非ゼロなら、どこかにnullがある。
*/
const uint64_t lo = 0x0101010101010101ULL;
const uint64_t hi = 0x8080808080808080ULL;
while (1)
{
uint64_t w = *word;
if (((w - lo) & ~w & hi) != 0)
{
// nullバイトを含むワード
ptr = (const char *)word;
while (*ptr)
ptr++;
return ptr - s;
}
word++;
}
}
// レベル4：SIMD (SSE2)
#ifdef __SSE2__
#include <emmintrin.h>
size_t ft_strlen_sse2(const char *s)
{
const char *ptr = s;
// 16バイトアラインメントまで
while ((uintptr_t)ptr & 15)
{
if (!*ptr)
return ptr - s;
ptr++;
}
const __m128i zero = _mm_setzero_si128();
const __m128i *block = (const __m128i *)ptr;
while (1)
{
// 16バイトをロードしてゼロと比較
__m128i data = _mm_load_si128(block);
__m128i cmp = _mm_cmpeq_epi8(data, zero);
int mask = _mm_movemask_epi8(cmp);
if (mask != 0)
{
// nullの位置を特定
int pos = __builtin_ctz(mask);
return (const char *)block - s + pos;
}
block++;
}
}
#endif
// レベル5：AVX2
#ifdef __AVX2__
#include <immintrin.h>
size_t ft_strlen_avx2(const char *s)
{
const char *ptr = s;
// 32バイトアラインメントまで
while ((uintptr_t)ptr & 31)
{
if (!*ptr)
return ptr - s;
ptr++;
}
const __m256i zero = _mm256_setzero_si256();
const __m256i *block = (const __m256i *)ptr;
while (1)
{
__m256i data = _mm256_load_si256(block);
__m256i cmp = _mm256_cmpeq_epi8(data, zero);
int mask = _mm256_movemask_epi8(cmp);
if (mask != 0)
{
int pos = __builtin_ctz(mask);
return (const char *)block - s + pos;
}
block++;
}
}
#endif
8.5.2 ft_memcpy の最適化
// メモリコピーの最適化戦略
// 小さなコピー: インライン展開
// 中サイズ: ワード単位コピー
// 大サイズ: SIMD + プリフェッチ
// 巨大サイズ: 非テンポラルストア
void *ft_memcpy_optimized(void *restrict dst, const void *restrict src, size_t n)
{
unsigned char *d = dst;
const unsigned char *s = src;
// 小さなコピー（<= 16バイト）: バイト単位
if (n <= 16)
{
while (n--)
*d++ = *s++;
return dst;
}
// 中サイズ（<= 128バイト）: 8バイト単位
if (n <= 128)
{
// 先頭をアラインメント調整
size_t align = (8 - ((uintptr_t)d & 7)) & 7;
n -= align;
while (align--)
*d++ = *s++;
// 8バイトずつコピー
uint64_t *d64 = (uint64_t *)d;
const uint64_t *s64 = (const uint64_t *)s;
while (n >= 8)
{
*d64++ = *s64++;
n -= 8;
}
d = (unsigned char *)d64;
s = (const unsigned char *)s64;
while (n--)
*d++ = *s++;
return dst;
}
#ifdef __AVX2__
// 大サイズ: AVX2 (256ビット = 32バイト)
if (n <= 1024 * 1024)
{
// アラインメント調整
size_t align = (32 - ((uintptr_t)d & 31)) & 31;
n -= align;
while (align--)
*d++ = *s++;
__m256i *d256 = (__m256i *)d;
const __m256i *s256 = (const __m256i *)s;
while (n >= 128)
{
// プリフェッチ
_mm_prefetch((const char *)s256 + 256, _MM_HINT_T0);
// 4 × 32バイト = 128バイトずつ
__m256i v0 = _mm256_loadu_si256(s256);
__m256i v1 = _mm256_loadu_si256(s256 + 1);
__m256i v2 = _mm256_loadu_si256(s256 + 2);
__m256i v3 = _mm256_loadu_si256(s256 + 3);
_mm256_storeu_si256(d256, v0);
_mm256_storeu_si256(d256 + 1, v1);
_mm256_storeu_si256(d256 + 2, v2);
_mm256_storeu_si256(d256 + 3, v3);
s256 += 4;
d256 += 4;
n -= 128;
}
d = (unsigned char *)d256;
s = (const unsigned char *)s256;
// 残りを処理
while (n--)
*d++ = *s++;
return dst;
}
// 巨大サイズ: 非テンポラルストア（キャッシュをバイパス）
{
size_t align = (32 - ((uintptr_t)d & 31)) & 31;
n -= align;
while (align--)
*d++ = *s++;
__m256i *d256 = (__m256i *)d;
const __m256i *s256 = (const __m256i *)s;
while (n >= 128)
{
_mm_prefetch((const char *)s256 + 512, _MM_HINT_NTA);
__m256i v0 = _mm256_loadu_si256(s256);
__m256i v1 = _mm256_loadu_si256(s256 + 1);
__m256i v2 = _mm256_loadu_si256(s256 + 2);
__m256i v3 = _mm256_loadu_si256(s256 + 3);
// 非テンポラルストア
_mm256_stream_si256(d256, v0);
_mm256_stream_si256(d256 + 1, v1);
_mm256_stream_si256(d256 + 2, v2);
_mm256_stream_si256(d256 + 3, v3);
s256 += 4;
d256 += 4;
n -= 128;
}
_mm_sfence(); // ストアフェンス
d = (unsigned char *)d256;
s = (const unsigned char *)s256;
while (n--)
*d++ = *s++;
return dst;
}
#else
// フォールバック
while (n--)
*d++ = *s++;
return dst;
#endif
}
8.5.3 ft_memset の最適化
void *ft_memset_optimized(void *s, int c, size_t n)
{
unsigned char *ptr = s;
unsigned char val = c;
// 小さなサイズ
if (n <= 16)
{
while (n--)
*ptr++ = val;
return s;
}
// パターンを8バイトに拡張
uint64_t pattern = val;
pattern |= pattern << 8;
pattern |= pattern << 16;
pattern |= pattern << 32;
// アラインメント調整
size_t align = (8 - ((uintptr_t)ptr & 7)) & 7;
n -= align;
while (align--)
*ptr++ = val;
// 8バイトずつ書き込み
uint64_t *ptr64 = (uint64_t *)ptr;
#ifdef __AVX2__
// AVX2で32バイトパターンを作成
__m256i pattern256 = _mm256_set1_epi8(val);
if (n >= 256)
{
__m256i *ptr256 = (__m256i *)ptr64;
// 巨大サイズは非テンポラルストア
if (n >= 1024 * 1024)
{
while (n >= 128)
{
_mm256_stream_si256(ptr256, pattern256);
_mm256_stream_si256(ptr256 + 1, pattern256);
_mm256_stream_si256(ptr256 + 2, pattern256);
_mm256_stream_si256(ptr256 + 3, pattern256);
ptr256 += 4;
n -= 128;
}
_mm_sfence();
}
else
{
while (n >= 128)
{
_mm256_storeu_si256(ptr256, pattern256);
_mm256_storeu_si256(ptr256 + 1, pattern256);
_mm256_storeu_si256(ptr256 + 2, pattern256);
_mm256_storeu_si256(ptr256 + 3, pattern256);
ptr256 += 4;
n -= 128;
}
}
ptr64 = (uint64_t *)ptr256;
}
#endif
// 残りを8バイトずつ
while (n >= 8)
{
*ptr64++ = pattern;
n -= 8;
}
// 最後のバイト
ptr = (unsigned char *)ptr64;
while (n--)
*ptr++ = val;
return s;
}
8.6 コンパイラ最適化
8.6.1 最適化レベル
# GCC/Clang 最適化オプション
-O0 # 最適化なし（デバッグ用）
-O1 # 基本的な最適化
-O2 # 標準的な最適化（推奨）
-O3 # 積極的な最適化（コードサイズ増加）
-Os # サイズ最適化
-Ofast # 数値精度を犠牲にした最適化
主要な最適化手法：
1. インライン展開（-finline-functions）
- 関数呼び出しオーバーヘッドを削減
- コードサイズとのトレードオフ
2. ループ展開（-funroll-loops）
- ループオーバーヘッドを削減
- 並列実行の機会を増加
3. デッドコード削除（-fdce）
- 実行されないコードを削除
4. 共通部分式削除（-fgcse）
- 同じ計算を一度だけ実行
5. 定数畳み込み（-fconstant-folding）
- コンパイル時に定数式を評価
6. レジスタ割り当て最適化
- メモリアクセスを最小化
7. 自動ベクトル化（-ftree-vectorize）
- SIMDコードの自動生成
8.6.2 分岐予測ヒント
// 分岐予測をコンパイラに伝える
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
// 使用例
void *ft_memcpy_hinted(void *dst, const void *src, size_t n)
{
// NULLチェック（通常は起こらない）
if (unlikely(dst == NULL || src == NULL))
return NULL;
// 小さなコピー（よくある）
if (likely(n <= 16))
{
// インラインで高速処理
unsigned char *d = dst;
const unsigned char *s = src;
while (n--)
*d++ = *s++;
return dst;
}
// 大きなコピー（稀）
return ft_memcpy_large(dst, src, n);
}
8.6.3 関数属性
// 関数属性による最適化ヒント
// 常にインライン化
__attribute__((always_inline))
static inline int ft_isdigit_fast(int c)
{
return (unsigned int)(c - '0') < 10u;
}
// ホットパス（頻繁に呼ばれる）
__attribute__((hot))
size_t ft_strlen_hot(const char *s);
// コールドパス（稀に呼ばれる）
__attribute__((cold))
void handle_error(const char *msg);
// 純粋関数（副作用なし、同じ入力に同じ出力）
__attribute__((pure))
size_t ft_strlen_pure(const char *s);
// const関数（メモリを読まない純粋関数）
__attribute__((const))
int ft_isalpha_const(int c);
// noreturn（戻らない関数）
__attribute__((noreturn))
void ft_exit(int status);
8.7 ベンチマークフレームワーク
8.7.1 プロファイラの実装
// profiler.h
#ifndef PROFILER_H
# define PROFILER_H
# include <time.h>
# include <stdint.h>
# include <stdio.h>
// 高精度タイマー
typedef struct s_timer {
struct timespec start;
struct timespec end;
double elapsed_ns;
} t_timer;
// タイマー操作
static inline void timer_start(t_timer *t)
{
clock_gettime(CLOCK_MONOTONIC, &t->start);
}
static inline void timer_stop(t_timer *t)
{
clock_gettime(CLOCK_MONOTONIC, &t->end);
t->elapsed_ns = (t->end.tv_sec - t->start.tv_sec) * 1e9 +
(t->end.tv_nsec - t->start.tv_nsec);
}
// CPUサイクルカウンタ（x86_64）
#ifdef __x86_64__
static inline uint64_t rdtsc(void)
{
unsigned int lo, hi;
__asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
return ((uint64_t)hi << 32) | lo;
}
static inline uint64_t rdtscp(void)
{
unsigned int lo, hi, aux;
__asm__ __volatile__ ("rdtscp" : "=a" (lo), "=d" (hi), "=c" (aux));
return ((uint64_t)hi << 32) | lo;
}
#endif
// ベンチマーク結果
typedef struct s_bench_result {
const char *name;
size_t data_size;
int iterations;
double total_time_ns;
double avg_time_ns;
double min_time_ns;
double max_time_ns;
double throughput_gbps; // GB/s
uint64_t cycles_per_byte;
} t_bench_result;
// キャッシュ操作
void flush_cache(void);
void warm_cache(void *data, size_t size);
// ベンチマーク実行
t_bench_result run_benchmark(
const char *name,
void (*func)(void *data, size_t size),
void *data,
size_t size,
int iterations
);
// 結果表示
void print_benchmark_results(t_bench_result *results, int count);
#endif
8.7.2 ベンチマーク実行
// benchmark_suite.c
#include "profiler.h"
#include "libft.h"
#include <stdlib.h>
#include <string.h>
// キャッシュをフラッシュ
void flush_cache(void)
{
// 大きなデータで上書き（32MB）
const size_t size = 32 * 1024 * 1024;
volatile char *buffer = malloc(size);
if (buffer)
{
for (size_t i = 0; i < size; i += 64)
buffer[i] = i & 0xFF;
free((void *)buffer);
}
}
// キャッシュを温める
void warm_cache(void *data, size_t size)
{
volatile char *ptr = data;
volatile char sum = 0;
for (size_t i = 0; i < size; i++)
sum += ptr[i];
(void)sum;
}
t_bench_result run_benchmark(
const char *name,
void (*func)(void *data, size_t size),
void *data,
size_t size,
int iterations)
{
t_bench_result result;
t_timer timer;
double *samples = malloc(iterations * sizeof(double));
result.name = name;
result.data_size = size;
result.iterations = iterations;
result.min_time_ns = 1e18;
result.max_time_ns = 0;
// ウォームアップ
for (int i = 0; i < 10; i++)
func(data, size);
// 測定
uint64_t total_cycles = 0;
for (int i = 0; i < iterations; i++)
{
// キャッシュの状態を一定に
if (i % 100 == 0)
{
flush_cache();
warm_cache(data, size);
}
uint64_t start_cycles = rdtscp();
timer_start(&timer);
func(data, size);
timer_stop(&timer);
uint64_t end_cycles = rdtscp();
samples[i] = timer.elapsed_ns;
total_cycles += end_cycles - start_cycles;
if (samples[i] < result.min_time_ns)
result.min_time_ns = samples[i];
if (samples[i] > result.max_time_ns)
result.max_time_ns = samples[i];
}
// 統計計算
double sum = 0;
for (int i = 0; i < iterations; i++)
sum += samples[i];
result.total_time_ns = sum;
result.avg_time_ns = sum / iterations;
result.throughput_gbps = (size * iterations) / sum; // バイト/ns = GB/s
result.cycles_per_byte = total_cycles / (size * iterations);
free(samples);
return result;
}
void print_benchmark_results(t_bench_result *results, int count)
{
printf("\n%-25s %10s %12s %12s %12s %10s %10s\n",
"Function", "Size", "Avg(ns)", "Min(ns)", "Max(ns)",
"GB/s", "Cyc/Byte");
printf("%s\n", "────────────────────────────────────────────────────────────────────────────────────");
for (int i = 0; i < count; i++)
{
printf("%-25s %10zu %12.2f %12.2f %12.2f %10.2f %10lu\n",
results[i].name,
results[i].data_size,
results[i].avg_time_ns,
results[i].min_time_ns,
results[i].max_time_ns,
results[i].throughput_gbps,
results[i].cycles_per_byte);
}
}
8.7.3 包括的なベンチマーク
// run_benchmarks.c
#include "profiler.h"
#include "libft.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// strlen ベンチマーク用のラッパー
static void bench_strlen_naive(void *data, size_t size)
{
(void)size;
volatile size_t len = ft_strlen((const char *)data);
(void)len;
}
static void bench_strlen_libc(void *data, size_t size)
{
(void)size;
volatile size_t len = strlen((const char *)data);
(void)len;
}
// memcpy ベンチマーク用のラッパー
typedef struct s_memcpy_data {
void *src;
void *dst;
size_t size;
} t_memcpy_data;
static void bench_memcpy_ft(void *data, size_t size)
{
(void)size;
t_memcpy_data *d = data;
ft_memcpy(d->dst, d->src, d->size);
}
static void bench_memcpy_libc(void *data, size_t size)
{
(void)size;
t_memcpy_data *d = data;
memcpy(d->dst, d->src, d->size);
}
void run_strlen_benchmark(void)
{
printf("\n=== strlen Benchmark ===\n");
size_t sizes[] = {10, 100, 1000, 10000, 100000, 1000000};
int n_sizes = sizeof(sizes) / sizeof(sizes[0]);
for (int i = 0; i < n_sizes; i++)
{
size_t size = sizes[i];
// テストデータ準備
char *str = malloc(size + 1);
memset(str, 'A', size);
str[size] = '\0';
printf("\nSize: %zu bytes\n", size);
t_bench_result results[2];
results[0] = run_benchmark("ft_strlen", bench_strlen_naive,
str, size, 1000);
results[1] = run_benchmark("strlen (libc)", bench_strlen_libc,
str, size, 1000);
print_benchmark_results(results, 2);
// スピードアップ計算
double speedup = results[1].avg_time_ns / results[0].avg_time_ns;
printf("ft_strlen is %.2fx %s than libc\n",
speedup > 1 ? speedup : 1/speedup,
speedup > 1 ? "faster" : "slower");
free(str);
}
}
void run_memcpy_benchmark(void)
{
printf("\n=== memcpy Benchmark ===\n");
size_t sizes[] = {64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 16777216};
int n_sizes = sizeof(sizes) / sizeof(sizes[0]);
for (int i = 0; i < n_sizes; i++)
{
size_t size = sizes[i];
t_memcpy_data data;
data.src = aligned_alloc(64, size);
data.dst = aligned_alloc(64, size);
data.size = size;
// ランダムデータで初期化
for (size_t j = 0; j < size; j++)
((char *)data.src)[j] = rand() & 0xFF;
printf("\nSize: ");
if (size < 1024)
printf("%zu B\n", size);
else if (size < 1024 * 1024)
printf("%zu KB\n", size / 1024);
else
printf("%zu MB\n", size / (1024 * 1024));
t_bench_result results[2];
int iters = size < 100000 ? 10000 : (size < 10000000 ? 1000 : 100);
results[0] = run_benchmark("ft_memcpy", bench_memcpy_ft,
&data, size, iters);
results[1] = run_benchmark("memcpy (libc)", bench_memcpy_libc,
&data, size, iters);
print_benchmark_results(results, 2);
free(data.src);
free(data.dst);
}
}
void run_alignment_test(void)
{
printf("\n=== Alignment Impact Test ===\n");
const size_t size = 4096;
char *buffer = aligned_alloc(64, size + 64);
printf("\n%-10s %12s %12s\n", "Offset", "Time(ns)", "Throughput");
printf("──────────────────────────────────────\n");
for (int offset = 0; offset < 64; offset += 8)
{
char *ptr = buffer + offset;
memset(ptr, 'A', size);
ptr[size - 1] = '\0';
t_bench_result result = run_benchmark("strlen", bench_strlen_naive,
ptr, size, 10000);
printf("%-10d %12.2f %12.2f GB/s\n",
offset, result.avg_time_ns, result.throughput_gbps);
}
free(buffer);
}
void run_cache_test(void)
{
printf("\n=== Cache Effects Test ===\n");
// L1, L2, L3 キャッシュ境界をまたぐサイズ
size_t sizes[] = {
16 * 1024, // L1に収まる
32 * 1024, // L1境界
64 * 1024, // L1を超える
256 * 1024, // L2境界
1024 * 1024, // L2を超える
8 * 1024 * 1024, // L3境界
32 * 1024 * 1024 // L3を超える
};
const char *labels[] = {
"16 KB (L1)", "32 KB (L1 boundary)", "64 KB (> L1)",
"256 KB (L2 boundary)", "1 MB (> L2)",
"8 MB (L3 boundary)", "32 MB (> L3)"
};
printf("\n%-25s %12s %12s\n", "Size", "Time(ns)", "Throughput");
printf("────────────────────────────────────────────────────\n");
for (int i = 0; i < 7; i++)
{
char *data = malloc(sizes[i] + 1);
memset(data, 'A', sizes[i]);
data[sizes[i]] = '\0';
int iters = sizes[i] < 1000000 ? 1000 : 100;
// キャッシュをフラッシュしてからテスト（コールドキャッシュ）
flush_cache();
t_bench_result result = run_benchmark("strlen", bench_strlen_naive,
data, sizes[i], iters);
printf("%-25s %12.2f %12.2f GB/s\n",
labels[i], result.avg_time_ns, result.throughput_gbps);
free(data);
}
}
int main(void)
{
printf("╔════════════════════════════════════════════════════╗\n");
printf("║ LIBFT PERFORMANCE BENCHMARK ║\n");
printf("╚════════════════════════════════════════════════════╝\n");
run_strlen_benchmark();
run_memcpy_benchmark();
run_alignment_test();
run_cache_test();
printf("\nBenchmark complete.\n");
return 0;
}
8.8 実践的な最適化ガイドライン
8.8.1 最適化のチェックリスト
【アルゴリズムレベル】
□ より効率的なアルゴリズムを選択したか？
□ 不要な処理を削除したか？
□ 早期終了条件を活用しているか？
【データ構造】
□ キャッシュフレンドリーなレイアウトか？
□ データのアラインメントは適切か？
□ パディングは最小化されているか？
【メモリアクセス】
□ 連続的なアクセスパターンか？
□ キャッシュラインを意識しているか？
□ プリフェッチは適切か？
□ 大きなコピーに非テンポラルストアを使用しているか？
【CPU最適化】
□ SIMD命令を活用しているか？
□ 分岐を最小化しているか？
□ 分岐予測ヒントを使用しているか？
□ ループ展開は適切か？
【コンパイラ】
□ 適切な最適化フラグを使用しているか？
□ インライン化ヒントは適切か？
□ リンク時最適化（LTO）を検討したか？
【測定】
□ 正確なベンチマークを実施したか？
□ 複数のデータサイズでテストしたか？
□ キャッシュの状態を考慮しているか？
□ 標準ライブラリと比較したか？
8.8.2 最適化の落とし穴
/*
* 避けるべき最適化パターン
*/
// 1. 早すぎる最適化
// BAD: 測定前に最適化
for (int i = 0; i < n; i += 4) { ... } // 本当に必要？
// GOOD: まず測定、問題があれば最適化
for (int i = 0; i < n; i++) { ... }
// 2. 可読性の犠牲
// BAD: 理解困難なビット演算
x = (x | (x >> 1)) | ((x | (x >> 1)) >> 2);
// GOOD: コメント付きで理解可能に
// 最も近い2のべき乗に切り上げ
x = next_power_of_two(x);
// 3. プラットフォーム依存の過信
#ifdef __AVX512__
// AVX-512を使用
#endif
// AVX-512は熱問題で周波数が下がることがある
// 4. ベンチマークの誤り
// BAD: 1回だけ測定
start = clock();
func();
end = clock();
// GOOD: 統計的に有意な測定
for (int i = 0; i < 1000; i++) { ... }
// 5. 最適化の過剰適用
// BAD: すべての関数にSIMD
__m128i ft_isalpha_sse(int c); // 1文字に対してSIMD？
// GOOD: 効果がある場所に集中
size_t ft_strlen_sse(const char *s); // 長い文字列には効果的
まとめ
この章では、コンピュータアーキテクチャの基礎から実践的な最適化技法まで、包括的に学んだ。
学んだ概念
- 計算機アーキテクチャの基礎
- CPUマイクロアーキテクチャ
- 性能分析
- SIMD技術
- 実践的最適化
重要な教訓
- 最適化は測定から始める
- アルゴリズムの選択が最も重要
- メモリアクセスパターンが性能を決定する
- 可読性と性能のバランスを取る
- プラットフォーム固有の最適化は条件付きで