第4章：メモリの深淵 - コンピュータアーキテクチャの核心
4.1 メモリ階層の歴史と設計原理
4.1.1 なぜメモリ階層が必要か
コンピュータの歴史において、プロセッサの速度向上とメモリの速度向上には大きな差がありました。これは「メモリウォール問題」と呼ばれています。
プロセッサとメモリの速度差（歴史的推移）
年代 | CPU速度向上率 | メモリ速度向上率 | 差
----------|--------------|-----------------|--------
1980年代 | 年25% | 年7% | 18%/年
1990年代 | 年52% | 年7% | 45%/年
2000年代 | 年23% | 年7% | 16%/年
2010年以降| マルチコア化 | 年7% | 拡大中
1980年には、メモリアクセスとCPU演算がほぼ同じ速度でした。しかし2024年現在、CPUはメモリの200-300倍高速です。この差を埋めるために、メモリ階層が発展しました。
4.1.2 局所性の原理
メモリ階層が効果的に機能するのは、プログラムが示す「局所性（Locality）」のおかげです。
時間的局所性（Temporal Locality）
一度アクセスされたデータは、近い将来再びアクセスされる可能性が高い。
// ループカウンタ i は何度もアクセスされる
for (int i = 0; i < 1000; i++) {
sum += array[i];
// i は時間的局所性が高い
}
空間的局所性（Spatial Locality）
あるアドレスがアクセスされると、その近くのアドレスも近い将来アクセスされる可能性が高い。
// 配列の連続したアクセスは空間的局所性が高い
for (int i = 0; i < 1000; i++) {
sum += array[i]; // array[i], array[i+1], ... は近接
}
局所性を意識したコード
// 悪い例：空間的局所性が低い
int bad_sum(int matrix[1000][1000]) {
int sum = 0;
for (int col = 0; col < 1000; col++) {
for (int row = 0; row < 1000; row++) {
sum += matrix[row][col]; // 列方向のアクセス
}
}
return sum;
}
// 良い例：空間的局所性が高い
int good_sum(int matrix[1000][1000]) {
int sum = 0;
for (int row = 0; row < 1000; row++) {
for (int col = 0; col < 1000; col++) {
sum += matrix[row][col]; // 行方向のアクセス
}
}
return sum;
}
// 性能差：good_sumはbad_sumの10-100倍高速になりうる
4.1.3 現代のメモリ階層
4.2 キャッシュの設計と動作原理
4.2.1 キャッシュの歴史
キャッシュの概念は1960年代に登場しました。
1967年：IBM System/360 Model 85
最初の商用キャッシュを搭載。容量は16-32KB、メインメモリより約12倍高速でした。
1970年代-1980年代
- 1979年：Motorola 68000（キャッシュなし、外部キャッシュをサポート）
- 1982年：Motorola 68020（256バイトの命令キャッシュ）
- 1989年：Intel 486（8KBの統合L1キャッシュ）
- L2キャッシュの登場
- 分離キャッシュ（命令/データ）
- L3キャッシュの登場
- 現代：複数レベル、数十MBのキャッシュ
1990年代以降
4.2.2 キャッシュの構造
キャッシュは「キャッシュライン」という単位でデータを管理します。
キャッシュラインの構成
一般的なキャッシュライン（64バイト）:
例：64ビットアドレス、4-wayセット連想キャッシュ、32KBキャッシュ
アドレス: 0x00007fff5fbff8a0
分解:
- Tag: 0x00007fff5fbff (上位部分)
- Set Index: 0x22 (どのセットか)
- Block Offset: 0x20 (キャッシュライン内の位置)
キャッシュの種類
- 直接マップキャッシュ（Direct-Mapped）
メモリアドレス → 唯一のキャッシュ位置
利点：単純で高速
欠点：衝突ミスが多い
アドレス 0x1000 → セット 0
アドレス 0x2000 → セット 0 （衝突！）
メモリアドレス → 複数のキャッシュ位置のいずれか
4-way セット連想:
各セットに4つの「ウェイ」
アドレスは4つの場所のいずれかに格納可能
セット 0: [Way0] [Way1] [Way2] [Way3]
セット 1: [Way0] [Way1] [Way2] [Way3]
...
メモリアドレス → 任意のキャッシュ位置
利点：衝突ミスが最小
欠点：検索が遅い（全エントリをチェック）
通常はTLBなど小さいキャッシュに使用
4.2.3 キャッシュミスの種類
// 強制ミス（Cold/Compulsory Miss）
// 初めてのアクセスは必ずミス
int array[1000];
for (int i = 0; i < 1000; i++) {
array[i] = i; // 各要素への最初のアクセスはミス
}
// 容量ミス（Capacity Miss）
// ワーキングセットがキャッシュサイズを超える
int large_array[1000000]; // 4MBのデータ
for (int i = 0; i < 1000000; i++) {
sum += large_array[i];
}
// L2キャッシュ(256KB)に収まらない → 容量ミス
// 衝突ミス（Conflict Miss）
// 同じセットに複数のアドレスがマップされる
int array1[1024];
int array2[1024]; // array1と同じセットにマップされる可能性
for (int i = 0; i < 1024; i++) {
sum += array1[i] + array2[i]; // 交互アクセスで衝突
}
4.2.4 キャッシュを意識したプログラミング
ストライドアクセスパターン
// ストライド1（最適）
for (int i = 0; i < N; i++) {
sum += array[i]; // 連続アクセス
}
// ストライドが大きい（キャッシュ効率が悪い）
for (int i = 0; i < N; i += 64) {
sum += array[i]; // 64要素おきにアクセス
}
// ストライドがキャッシュラインサイズの倍数だと最悪
// ベンチマーク結果の例
void measure_stride_effect() {
const size_t N = 64 * 1024 * 1024 / sizeof(int); // 64MB
int *array = malloc(N * sizeof(int));
// ウォームアップ
for (size_t i = 0; i < N; i++) array[i] = 1;
int strides[] = {1, 2, 4, 8, 16, 32, 64, 128};
for (int s = 0; s < 8; s++) {
int stride = strides[s];
volatile int sum = 0;
clock_t start = clock();
for (size_t i = 0; i < N; i += stride) {
sum += array[i];
}
clock_t end = clock();
double ops = N / stride;
double time = (double)(end - start) / CLOCKS_PER_SEC;
printf("Stride %3d: %.2f ns/access\n",
stride, time * 1e9 / ops);
}
free(array);
}
// 典型的な結果:
// Stride 1: 0.5 ns/access
// Stride 2: 0.6 ns/access
// Stride 4: 0.8 ns/access
// Stride 8: 1.2 ns/access
// Stride 16: 2.5 ns/access ← キャッシュラインをまたぐ
// Stride 32: 5.0 ns/access
// Stride 64: 10.0 ns/access
// Stride 128: 15.0 ns/access
キャッシュブロッキング（タイリング）
// 行列乗算の例
// ナイーブな実装（キャッシュ効率が悪い）
void matrix_multiply_naive(double *C, double *A, double *B, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
C[i*n + j] += A[i*n + k] * B[k*n + j];
}
}
}
}
// 問題: B の列方向アクセスでキャッシュミスが多発
// キャッシュブロッキングを適用
#define BLOCK_SIZE 64 // L1キャッシュに収まるサイズ
void matrix_multiply_blocked(double *C, double *A, double *B, int n) {
for (int ii = 0; ii < n; ii += BLOCK_SIZE) {
for (int jj = 0; jj < n; jj += BLOCK_SIZE) {
for (int kk = 0; kk < n; kk += BLOCK_SIZE) {
// ブロック内の計算
int i_end = (ii + BLOCK_SIZE < n) ? ii + BLOCK_SIZE : n;
int j_end = (jj + BLOCK_SIZE < n) ? jj + BLOCK_SIZE : n;
int k_end = (kk + BLOCK_SIZE < n) ? kk + BLOCK_SIZE : n;
for (int i = ii; i < i_end; i++) {
for (int j = jj; j < j_end; j++) {
double sum = C[i*n + j];
for (int k = kk; k < k_end; k++) {
sum += A[i*n + k] * B[k*n + j];
}
C[i*n + j] = sum;
}
}
}
}
}
}
// 改善: 3-10倍の高速化が可能
4.3 仮想メモリとページング
4.3.1 仮想メモリの歴史
仮想メモリは1960年代に発明された革命的な概念です。
1961年：Ferranti Atlas
世界初の仮想メモリを実装。物理メモリは96KB、仮想アドレス空間は576KBでした。
1970年代-1980年代
仮想メモリの目的
4.3.2 ページングの仕組み
仮想アドレス（64ビットシステム）:
4レベルページテーブル（x86-64）:
ページテーブルエントリ（PTE）の構造
x86-64 PTE（64ビット）:
主要なビットの意味:
- P (Present): ページがメモリ上に存在
- R/W (Read/Write): 書き込み許可
- U/S (User/Supervisor): ユーザーモードでのアクセス許可
- A (Accessed): アクセスされた
- D (Dirty): 書き込まれた
- NX (No Execute): 実行禁止
ページフォルトの処理
// カーネルのページフォルトハンドラ（概念的なコード）
void page_fault_handler(struct pt_regs *regs, unsigned long error_code) {
unsigned long fault_addr = read_cr2(); // フォルトしたアドレス
// エラーコードを解析
int present = error_code & 0x1;
int write = error_code & 0x2;
int user = error_code & 0x4;
int reserved = error_code & 0x8;
int instruction_fetch = error_code & 0x10;
if (reserved) {
// 予約ビットの違反
panic("Reserved bit set in page table entry");
}
if (!present) {
// ページが存在しない
// メモリマップされた領域か確認
struct vm_area_struct *vma = find_vma(current->mm, fault_addr);
if (!vma || fault_addr < vma->vm_start) {
// 不正なアドレス → SIGSEGV
send_signal(SIGSEGV);
return;
}
// デマンドページング：物理ページを割り当て
struct page *page = alloc_page(GFP_USER);
if (!page) {
// メモリ不足 → OOM killer
out_of_memory();
return;
}
// ページテーブルを更新
set_pte(fault_addr, page_to_pfn(page), vma->vm_flags);
return;
}
if (write && !(vma->vm_flags & VM_WRITE)) {
// 書き込み禁止領域への書き込み
send_signal(SIGSEGV);
return;
}
// その他のフォルト処理...
}
4.3.3 TLB（Translation Lookaside Buffer）
TLBはページテーブルのキャッシュです。
TLBの構造（一般的なx86-64）:
L1 DTLB（データ）: 64エントリ、4-way連想
L1 ITLB（命令）: 128エントリ、8-way連想
L2 TLB（統合）: 1536エントリ、12-way連想
アドレス変換のコスト:
- TLBヒット: 1サイクル
- TLBミス: 10-100サイクル（ページウォーク）
- ページフォルト: 数百万サイクル（ディスクアクセス）
TLBを意識したプログラミング
// ヒュージページの使用（Linux）
#include <sys/mman.h>
void *alloc_huge_pages(size_t size) {
// 2MB のヒュージページを要求
void *ptr = mmap(NULL, size,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
-1, 0);
if (ptr == MAP_FAILED) {
// フォールバック：通常のページ
ptr = mmap(NULL, size,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS,
-1, 0);
}
return (ptr == MAP_FAILED) ? NULL : ptr;
}
// ヒュージページの利点:
// - TLBエントリ数が減少（2MB/4KB = 512倍効率的）
// - ページウォークのコストが減少
// - 大規模データ処理で10-30%の性能向上
4.4 ポインタとメモリアドレッシング
4.4.1 ポインタの本質
ポインタはメモリアドレスを格納する変数です。これはC言語の最も強力で危険な機能です。
ポインタの宣言と基本操作
// ポインタの宣言
int value = 42;
int *ptr = &value; // ptr は value のアドレスを保持
// メモリ上のレイアウト
// アドレス 値 変数名
// 0x7ffd1234 42 value
// 0x7ffd1238 0x7ffd1234 ptr
// ポインタのサイズ
printf("sizeof(int*) = %zu\n", sizeof(int*)); // 64ビット: 8
printf("sizeof(char*) = %zu\n", sizeof(char*)); // 64ビット: 8
printf("sizeof(void*) = %zu\n", sizeof(void*)); // 64ビット: 8
// すべてのポインタは同じサイズ（アドレスのサイズ）
ポインタ演算
int array[] = {10, 20, 30, 40, 50};
int *ptr = array;
// ポインタ演算はポイント先の型のサイズを考慮
ptr++; // ptr は sizeof(int) = 4 バイト進む
// ptr は array[1] を指す
ptr += 2; // ptr は 2 * 4 = 8 バイト進む
// ptr は array[3] を指す
// ポインタの差
int *p1 = &array[1];
int *p2 = &array[4];
ptrdiff_t diff = p2 - p1; // 3 (要素数)
// 異なる型のポインタ
char *char_ptr = (char *)array;
// char_ptr++ は 1 バイトだけ進む
void ポインタ
// void* は型情報を持たない汎用ポインタ
void *generic_ptr;
int x = 42;
double y = 3.14;
char z = 'A';
generic_ptr = &x;
// 使用時にはキャストが必要
printf("x = %d\n", *(int *)generic_ptr);
generic_ptr = &y;
printf("y = %f\n", *(double *)generic_ptr);
// void* の演算は許可されない（サイズが不明）
// generic_ptr++; // エラー
// malloc/free は void* を使用
void *buffer = malloc(100);
free(buffer);
4.4.2 ポインタと配列の関係
int array[5] = {10, 20, 30, 40, 50};
int *ptr = array;
// 配列名は先頭要素へのポインタに「減衰」する
// ただし、配列とポインタは同一ではない
printf("sizeof(array) = %zu\n", sizeof(array)); // 20 (5 * 4)
printf("sizeof(ptr) = %zu\n", sizeof(ptr)); // 8
// これらはすべて等価
array[2]
*(array + 2)
ptr[2]
*(ptr + 2)
2[array] // 可読性のため非推奨
// 多次元配列
int matrix[3][4];
// matrix は int[4] 配列へのポインタに減衰
// matrix[i] は i 番目の行の先頭
// matrix[i][j] は (i, j) の要素
// ポインタの配列 vs 配列へのポインタ
int *ptr_array[5]; // int ポインタの配列
int (*array_ptr)[5]; // 5要素の int 配列へのポインタ
int row[5] = {1, 2, 3, 4, 5};
array_ptr = &row; // 配列全体へのポインタ
(*array_ptr)[2] = 99; // row[2] = 99
4.4.3 関数ポインタ
// 関数ポインタの宣言
int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }
int (*operation)(int, int); // 関数ポインタの宣言
operation = add;
printf("add(5, 3) = %d\n", operation(5, 3)); // 8
operation = subtract;
printf("subtract(5, 3) = %d\n", operation(5, 3)); // 2
// typedef を使うと読みやすい
typedef int (*BinaryOp)(int, int);
BinaryOp op = add;
printf("Result: %d\n", op(10, 4));
// コールバックとして使用
void process_array(int *arr, int n, BinaryOp op) {
for (int i = 0; i < n - 1; i++) {
arr[i] = op(arr[i], arr[i + 1]);
}
}
// 関数ポインタの配列
BinaryOp operations[] = {add, subtract};
printf("operations[0](5, 3) = %d\n", operations[0](5, 3)); // 8
printf("operations[1](5, 3) = %d\n", operations[1](5, 3)); // 2
4.4.4 ポインタの危険性
// 1. ダングリングポインタ
int *create_dangling_pointer() {
int local_var = 42;
return &local_var; // 警告: ローカル変数のアドレスを返す
}
// 関数終了後、local_var は無効
// 2. NULLポインタの参照
int *null_ptr = NULL;
// int value = *null_ptr; // セグメンテーションフォルト
// 3. メモリリーク
void memory_leak() {
int *ptr = malloc(1000);
// ... 使用 ...
// free(ptr); // 忘れるとリーク
}
// 4. 二重解放
void double_free() {
int *ptr = malloc(100);
free(ptr);
// free(ptr); // 未定義動作
// 対策: 解放後に NULL を代入
ptr = NULL;
}
// 5. バッファオーバーフロー
void buffer_overflow() {
int array[10];
for (int i = 0; i <= 10; i++) { // <= ではなく < を使うべき
array[i] = i; // array[10] はオーバーフロー
}
}
// 6. 型パニング（厳格なエイリアシング違反）
void type_punning() {
float f = 3.14f;
// int i = *(int *)&f; // 未定義動作
// 正しい方法: memcpy または union
int i;
memcpy(&i, &f, sizeof(f));
}
4.5 メモリアライメント
4.5.1 アライメントとは
アライメントルール:
- char: 1バイト境界（任意のアドレス）
- short: 2バイト境界（アドレスが2の倍数）
- int: 4バイト境界（アドレスが4の倍数）
- long: 8バイト境界（アドレスが8の倍数）
- double: 8バイト境界（アドレスが8の倍数）
構造体のパディング
// パディングなしの構造体（理論上）
struct Unpadded {
char a; // 1 バイト
int b; // 4 バイト
char c; // 1 バイト
}; // 合計: 6 バイト?
// 実際のメモリレイアウト（パディングあり）
struct Padded {
char a; // 1 バイト
// 3 バイトのパディング
int b; // 4 バイト
char c; // 1 バイト
// 3 バイトのパディング
}; // 合計: 12 バイト
printf("sizeof(struct Padded) = %zu\n", sizeof(struct Padded)); // 12
// パディングの可視化
void show_struct_layout() {
struct Padded s = {'A', 42, 'B'};
unsigned char *ptr = (unsigned char *)&s;
printf("Struct layout:\n");
for (size_t i = 0; i < sizeof(struct Padded); i++) {
printf(" [%zu]: 0x%02X", i, ptr[i]);
if (i == 0) printf(" <- a");
else if (i >= 4 && i <= 7) printf(" <- b");
else if (i == 8) printf(" <- c");
else printf(" <- padding");
printf("\n");
}
}
構造体のパッキング最適化
// 悪い順序（パディングが多い）
struct BadOrder {
char a; // 1 + 7 padding = 8
double b; // 8
char c; // 1 + 3 padding = 4
int d; // 4
}; // 合計: 24 バイト
// 良い順序（パディングを最小化）
struct GoodOrder {
double b; // 8
int d; // 4
char a; // 1
char c; // 1 + 2 padding = 4
}; // 合計: 16 バイト
printf("sizeof(BadOrder) = %zu\n", sizeof(struct BadOrder)); // 24
printf("sizeof(GoodOrder) = %zu\n", sizeof(struct GoodOrder)); // 16
// 一般的なルール: 大きい型から順に配置
アライメントの明示的な制御
// パディングを無効化（パフォーマンスへの影響あり）
#pragma pack(push, 1)
struct Packed {
char a; // 1
int b; // 4
char c; // 1
}; // 合計: 6 バイト
#pragma pack(pop)
// 特定のアライメントを要求
struct __attribute__((aligned(16))) Aligned16 {
int a;
int b;
}; // 16バイト境界にアライメント
// SIMD用の厳密なアライメント
struct __attribute__((aligned(32))) SIMDFriendly {
float data[8]; // AVX用に32バイトアライメント
};
4.6 Libftメモリ関数の実装
4.6.1 ft_memset - メモリの初期化
これまでの理論を基に、実際の実装に入りましょう。
void *ft_memset(void *b, int c, size_t len)
{
unsigned char *ptr = (unsigned char *)b;
unsigned char value = (unsigned char)c;
while (len--)
*ptr++ = value;
return (b);
}
なぜ unsigned char を使うのか
// int を unsigned char にキャストする理由
void demonstrate_memset_behavior() {
unsigned char buffer[4];
// c = 256 の場合
ft_memset(buffer, 256, 4);
// 256 & 0xFF = 0
// buffer = {0, 0, 0, 0}
// c = 0x12345678 の場合
ft_memset(buffer, 0x12345678, 4);
// 0x12345678 & 0xFF = 0x78
// buffer = {0x78, 0x78, 0x78, 0x78}
}
最適化版（ワード単位処理）
void *ft_memset_fast(void *b, int c, size_t len)
{
unsigned char *ptr = (unsigned char *)b;
unsigned char byte_val = (unsigned char)c;
// 小さいサイズは単純に処理
if (len < sizeof(size_t) * 4)
{
while (len--)
*ptr++ = byte_val;
return b;
}
// ワード値を構築（各バイトに同じ値）
size_t word_val = byte_val;
word_val |= word_val << 8;
word_val |= word_val << 16;
if (sizeof(size_t) == 8)
word_val |= word_val << 32;
// アライメント調整
size_t head = (sizeof(size_t) - ((uintptr_t)ptr & (sizeof(size_t) - 1)))
& (sizeof(size_t) - 1);
if (head > 0)
{
len -= head;
while (head--)
*ptr++ = byte_val;
}
// ワード単位で処理
size_t *word_ptr = (size_t *)ptr;
size_t words = len / sizeof(size_t);
while (words >= 4)
{
word_ptr[0] = word_val;
word_ptr[1] = word_val;
word_ptr[2] = word_val;
word_ptr[3] = word_val;
word_ptr += 4;
words -= 4;
}
while (words--)
*word_ptr++ = word_val;
// 残りのバイトを処理
ptr = (unsigned char *)word_ptr;
len &= sizeof(size_t) - 1;
while (len--)
*ptr++ = byte_val;
return b;
}
4.6.2 ft_bzero - メモリのゼロクリア
void ft_bzero(void *s, size_t n)
{
ft_memset(s, 0, n);
}
bzero の歴史
- BSD UNIX で誕生（1980年代）
- POSIX.1-2001 で非推奨
- POSIX.1-2008 で削除
- 現代では memset(s, 0, n) を推奨
セキュアなゼロクリア
// volatile を使用してコンパイラ最適化を防止
void ft_bzero_secure(void *s, size_t n)
{
volatile unsigned char *ptr = (volatile unsigned char *)s;
while (n--)
*ptr++ = 0;
}
// または explicit_bzero（一部のシステムで利用可能）
// #include <strings.h>
// void explicit_bzero(void *s, size_t n);
// セキュアなクリアが必要な場面
typedef struct {
char password[64];
unsigned char key[32];
unsigned char iv[16];
} SensitiveData;
void cleanup_sensitive(SensitiveData *data)
{
// 通常の bzero はコンパイラに最適化される可能性がある
// （使用されないメモリへの書き込みは削除されうる）
ft_bzero_secure(data, sizeof(SensitiveData));
}
4.6.3 ft_memcpy - メモリコピー
void *ft_memcpy(void *dst, const void *src, size_t n)
{
unsigned char *d = (unsigned char *)dst;
const unsigned char *s = (const unsigned char *)src;
if (d == NULL && s == NULL)
return NULL;
while (n--)
*d++ = *s++;
return dst;
}
重複に関する未定義動作
void demonstrate_overlap_issue()
{
char buffer[20] = "Hello, World!";
// 重複するコピー - 未定義動作
// memcpy(buffer + 2, buffer, 10);
// 前方向に重複
// src: H e l l o , W o r l d !
// dst: ? ? ? ? ? ? ? ? ? ?
// コピー中に src が上書きされる:
// Step 1: dst[0] = src[0] = 'H' → "HeHlo, World!"
// Step 2: dst[1] = src[1] = 'e' → "HeHlo, World!"
// Step 3: dst[2] = src[2] = 'H' (すでに上書きされた!) → 誤り
}
最適化版
void *ft_memcpy_fast(void *dst, const void *src, size_t n)
{
unsigned char *d = (unsigned char *)dst;
const unsigned char *s = (const unsigned char *)src;
// 小さいサイズは単純にコピー
if (n < sizeof(size_t) * 4)
{
while (n--)
*d++ = *s++;
return dst;
}
// アライメント調整
size_t head = (sizeof(size_t) - ((uintptr_t)d & (sizeof(size_t) - 1)))
& (sizeof(size_t) - 1);
if (head > 0)
{
n -= head;
while (head--)
*d++ = *s++;
}
// ワード単位でコピー
size_t *dw = (size_t *)d;
const size_t *sw = (const size_t *)s;
size_t words = n / sizeof(size_t);
// アンロールループ
while (words >= 4)
{
dw[0] = sw[0];
dw[1] = sw[1];
dw[2] = sw[2];
dw[3] = sw[3];
dw += 4;
sw += 4;
words -= 4;
}
while (words--)
*dw++ = *sw++;
// 残りのバイトをコピー
d = (unsigned char *)dw;
s = (const unsigned char *)sw;
n &= sizeof(size_t) - 1;
while (n--)
*d++ = *s++;
return dst;
}
4.6.4 ft_memmove - 重複安全なコピー
void *ft_memmove(void *dst, const void *src, size_t len)
{
unsigned char *d = (unsigned char *)dst;
const unsigned char *s = (const unsigned char *)src;
if (d == s || len == 0)
return dst;
if (d < s)
{
// 前方向にコピー（src が後ろにある場合安全）
while (len--)
*d++ = *s++;
}
else
{
// 後方向にコピー（dst が src より後ろの場合）
d += len;
s += len;
while (len--)
*--d = *--s;
}
return dst;
}
なぜ方向が重要か
void explain_copy_direction()
{
char buffer[20] = "Hello, World!";
// ケース1: dst < src（前方向コピーが安全）
// src: [H][e][l][l][o][,][ ][W][o][r][l][d][!]
// ^
// dst: [ ][ ][H][e][l][l][o][,][ ][W][o][r]
// ^
// 左から右にコピーしても問題なし
// ケース2: dst > src（後方向コピーが必要）
// src: [H][e][l][l][o][,][ ][W][o][r][l][d][!]
// ^
// dst: [H][e][l][l][o][,][ ][W][o][r][l][d][!][ ][ ]
// ^
// 左からコピーすると src が壊れる
// 右から左にコピーする必要がある
}
4.6.5 ft_memchr - メモリ内検索
void *ft_memchr(const void *s, int c, size_t n)
{
const unsigned char *ptr = (const unsigned char *)s;
unsigned char ch = (unsigned char)c;
while (n--)
{
if (*ptr == ch)
return (void *)ptr;
ptr++;
}
return NULL;
}
SIMD最適化版
#ifdef __SSE2__
#include <emmintrin.h>
void *ft_memchr_sse2(const void *s, int c, size_t n)
{
const unsigned char *ptr = (const unsigned char *)s;
unsigned char ch = (unsigned char)c;
// 小さいサイズは単純な検索
if (n < 16)
return ft_memchr(s, c, n);
__m128i needle = _mm_set1_epi8(ch);
// アライメントまで単純検索
while (((uintptr_t)ptr & 15) && n > 0)
{
if (*ptr == ch)
return (void *)ptr;
ptr++;
n--;
}
// 16バイト単位で検索
while (n >= 16)
{
__m128i haystack = _mm_load_si128((__m128i *)ptr);
__m128i cmp = _mm_cmpeq_epi8(haystack, needle);
int mask = _mm_movemask_epi8(cmp);
if (mask != 0)
{
int pos = __builtin_ctz(mask);
return (void *)(ptr + pos);
}
ptr += 16;
n -= 16;
}
// 残りを単純検索
while (n--)
{
if (*ptr == ch)
return (void *)ptr;
ptr++;
}
return NULL;
}
#endif
4.6.6 ft_memcmp - メモリ比較
int ft_memcmp(const void *s1, const void *s2, size_t n)
{
const unsigned char *p1 = (const unsigned char *)s1;
const unsigned char *p2 = (const unsigned char *)s2;
while (n--)
{
if (*p1 != *p2)
return (*p1 - *p2);
p1++;
p2++;
}
return 0;
}
最適化版
int ft_memcmp_fast(const void *s1, const void *s2, size_t n)
{
const unsigned char *p1 = (const unsigned char *)s1;
const unsigned char *p2 = (const unsigned char *)s2;
// 同じアドレスなら等しい
if (p1 == p2)
return 0;
// ワード単位で比較（不一致の早期発見）
while (n >= sizeof(size_t))
{
if (*(const size_t *)p1 != *(const size_t *)p2)
{
// 詳細な比較
for (size_t i = 0; i < sizeof(size_t); i++)
{
if (p1[i] != p2[i])
return (p1[i] - p2[i]);
}
}
p1 += sizeof(size_t);
p2 += sizeof(size_t);
n -= sizeof(size_t);
}
// 残りをバイト単位で比較
while (n--)
{
if (*p1 != *p2)
return (*p1 - *p2);
p1++;
p2++;
}
return 0;
}
4.7 動的メモリ割り当て
4.7.1 malloc/free の内部構造
// mallocの典型的な実装（概念）
// メモリブロックのヘッダ
typedef struct s_block {
size_t size;
int is_free;
struct s_block *next;
struct s_block *prev;
} t_block;
// フリーリスト（空きブロックのリスト）
static t_block *free_list = NULL;
void *simple_malloc(size_t size)
{
// アライメント調整
size = (size + sizeof(size_t) - 1) & ~(sizeof(size_t) - 1);
// フリーリストから適切なブロックを探す
t_block *block = free_list;
while (block)
{
if (block->is_free && block->size >= size)
{
// 十分なサイズのブロックを発見
block->is_free = 0;
// ブロックが大きすぎる場合は分割
if (block->size >= size + sizeof(t_block) + 16)
{
t_block *new_block = (t_block *)((char *)(block + 1) + size);
new_block->size = block->size - size - sizeof(t_block);
new_block->is_free = 1;
new_block->next = block->next;
new_block->prev = block;
block->size = size;
block->next = new_block;
}
return (void *)(block + 1);
}
block = block->next;
}
// 新しいメモリをシステムから取得
size_t total = size + sizeof(t_block);
block = (t_block *)sbrk(total);
if (block == (void *)-1)
return NULL;
block->size = size;
block->is_free = 0;
block->next = NULL;
block->prev = NULL;
// フリーリストに追加
if (!free_list)
free_list = block;
else
{
t_block *last = free_list;
while (last->next)
last = last->next;
last->next = block;
block->prev = last;
}
return (void *)(block + 1);
}
void simple_free(void *ptr)
{
if (!ptr)
return;
t_block *block = (t_block *)ptr - 1;
block->is_free = 1;
// 隣接する空きブロックとの統合
if (block->next && block->next->is_free)
{
block->size += sizeof(t_block) + block->next->size;
block->next = block->next->next;
if (block->next)
block->next->prev = block;
}
if (block->prev && block->prev->is_free)
{
block->prev->size += sizeof(t_block) + block->size;
block->prev->next = block->next;
if (block->next)
block->next->prev = block->prev;
}
}
4.7.2 ft_calloc の実装
void *ft_calloc(size_t count, size_t size)
{
size_t total;
void *ptr;
// オーバーフローチェック
if (count != 0 && size > SIZE_MAX / count)
return NULL;
total = count * size;
ptr = malloc(total);
if (ptr)
ft_bzero(ptr, total);
return ptr;
}
4.7.3 メモリリークの検出と防止
// デバッグ用メモリトラッカー
typedef struct s_alloc_record {
void *ptr;
size_t size;
const char *file;
int line;
struct s_alloc_record *next;
} t_alloc_record;
static t_alloc_record *g_allocs = NULL;
static size_t g_total_allocated = 0;
static size_t g_total_freed = 0;
void *debug_malloc(size_t size, const char *file, int line)
{
void *ptr = malloc(size);
if (!ptr)
return NULL;
t_alloc_record *record = malloc(sizeof(t_alloc_record));
record->ptr = ptr;
record->size = size;
record->file = file;
record->line = line;
record->next = g_allocs;
g_allocs = record;
g_total_allocated += size;
return ptr;
}
void debug_free(void *ptr, const char *file, int line)
{
if (!ptr)
return;
t_alloc_record **current = &g_allocs;
while (*current)
{
if ((*current)->ptr == ptr)
{
t_alloc_record *record = *current;
*current = record->next;
g_total_freed += record->size;
free(record);
free(ptr);
return;
}
current = &(*current)->next;
}
fprintf(stderr, "ERROR: Freeing unallocated pointer %p at %s:%d\n",
ptr, file, line);
}
void print_memory_leaks(void)
{
printf("\n=== Memory Leak Report ===\n");
printf("Total allocated: %zu bytes\n", g_total_allocated);
printf("Total freed: %zu bytes\n", g_total_freed);
printf("Leaked: %zu bytes\n", g_total_allocated - g_total_freed);
t_alloc_record *current = g_allocs;
while (current)
{
printf(" Leak: %zu bytes at %p (allocated at %s:%d)\n",
current->size, current->ptr, current->file, current->line);
current = current->next;
}
}
#define malloc(size) debug_malloc(size, __FILE__, __LINE__)
#define free(ptr) debug_free(ptr, __FILE__, __LINE__)
4.8 実践的なアプリケーション
4.8.1 効率的なバッファ管理
typedef struct s_buffer {
unsigned char *data;
size_t capacity;
size_t size;
} t_buffer;
t_buffer *buffer_create(size_t initial_capacity)
{
t_buffer *buf = malloc(sizeof(t_buffer));
if (!buf)
return NULL;
buf->data = malloc(initial_capacity);
if (!buf->data)
{
free(buf);
return NULL;
}
buf->capacity = initial_capacity;
buf->size = 0;
return buf;
}
int buffer_append(t_buffer *buf, const void *data, size_t len)
{
// 容量不足の場合は拡張
if (buf->size + len > buf->capacity)
{
size_t new_capacity = buf->capacity * 2;
while (new_capacity < buf->size + len)
new_capacity *= 2;
unsigned char *new_data = malloc(new_capacity);
if (!new_data)
return -1;
ft_memcpy(new_data, buf->data, buf->size);
free(buf->data);
buf->data = new_data;
buf->capacity = new_capacity;
}
ft_memcpy(buf->data + buf->size, data, len);
buf->size += len;
return 0;
}
void buffer_destroy(t_buffer *buf)
{
if (buf)
{
free(buf->data);
free(buf);
}
}
4.8.2 メモリプール
// 固定サイズブロックのメモリプール
typedef struct s_pool_block {
struct s_pool_block *next;
} t_pool_block;
typedef struct s_memory_pool {
void *memory;
t_pool_block *free_list;
size_t block_size;
size_t num_blocks;
} t_memory_pool;
t_memory_pool *pool_create(size_t block_size, size_t num_blocks)
{
t_memory_pool *pool = malloc(sizeof(t_memory_pool));
if (!pool)
return NULL;
// ブロックサイズはポインタサイズ以上必要
if (block_size < sizeof(t_pool_block))
block_size = sizeof(t_pool_block);
// アライメント調整
block_size = (block_size + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
pool->memory = malloc(block_size * num_blocks);
if (!pool->memory)
{
free(pool);
return NULL;
}
pool->block_size = block_size;
pool->num_blocks = num_blocks;
// フリーリストを構築
pool->free_list = NULL;
char *ptr = pool->memory;
for (size_t i = 0; i < num_blocks; i++)
{
t_pool_block *block = (t_pool_block *)ptr;
block->next = pool->free_list;
pool->free_list = block;
ptr += block_size;
}
return pool;
}
void *pool_alloc(t_memory_pool *pool)
{
if (!pool->free_list)
return NULL;
t_pool_block *block = pool->free_list;
pool->free_list = block->next;
return (void *)block;
}
void pool_free(t_memory_pool *pool, void *ptr)
{
if (!ptr)
return;
t_pool_block *block = (t_pool_block *)ptr;
block->next = pool->free_list;
pool->free_list = block;
}
void pool_destroy(t_memory_pool *pool)
{
if (pool)
{
free(pool->memory);
free(pool);
}
}
// 使用例
void demo_memory_pool()
{
// 100個の64バイトブロックをプール
t_memory_pool *pool = pool_create(64, 100);
// 高速な割り当て（malloc よりずっと速い）
void *blocks[50];
for (int i = 0; i < 50; i++)
{
blocks[i] = pool_alloc(pool);
ft_memset(blocks[i], 0, 64);
}
// 解放
for (int i = 0; i < 50; i++)
pool_free(pool, blocks[i]);
pool_destroy(pool);
}
4.9 パフォーマンス測定とベンチマーク
4.9.1 メモリ操作のベンチマーク
#include <time.h>
typedef struct s_benchmark_result {
const char *name;
size_t size;
double time_ns;
double bandwidth_gbps;
} t_benchmark_result;
void benchmark_memset(void)
{
size_t sizes[] = {64, 256, 1024, 4096, 16384, 65536, 262144, 1048576};
const int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
const int iterations = 100000;
printf("=== ft_memset Benchmark ===\n");
printf("%-10s %-15s %-15s\n", "Size", "Time (ns)", "Bandwidth (GB/s)");
for (int s = 0; s < num_sizes; s++)
{
size_t size = sizes[s];
void *buffer = malloc(size);
// ウォームアップ
for (int i = 0; i < 10; i++)
ft_memset(buffer, 0x42, size);
// 計測
clock_t start = clock();
for (int i = 0; i < iterations; i++)
ft_memset(buffer, 0x42, size);
clock_t end = clock();
double elapsed = (double)(end - start) / CLOCKS_PER_SEC;
double time_ns = elapsed * 1e9 / iterations;
double bandwidth = (double)size * iterations / elapsed / 1e9;
printf("%-10zu %-15.2f %-15.2f\n", size, time_ns, bandwidth);
free(buffer);
}
}
void benchmark_memcpy(void)
{
size_t sizes[] = {64, 256, 1024, 4096, 16384, 65536, 262144, 1048576};
const int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
const int iterations = 100000;
printf("\n=== ft_memcpy Benchmark ===\n");
printf("%-10s %-15s %-15s\n", "Size", "Time (ns)", "Bandwidth (GB/s)");
for (int s = 0; s < num_sizes; s++)
{
size_t size = sizes[s];
void *src = malloc(size);
void *dst = malloc(size);
// 初期化
ft_memset(src, 0xAB, size);
// ウォームアップ
for (int i = 0; i < 10; i++)
ft_memcpy(dst, src, size);
// 計測
clock_t start = clock();
for (int i = 0; i < iterations; i++)
ft_memcpy(dst, src, size);
clock_t end = clock();
double elapsed = (double)(end - start) / CLOCKS_PER_SEC;
double time_ns = elapsed * 1e9 / iterations;
double bandwidth = (double)size * 2 * iterations / elapsed / 1e9;
printf("%-10zu %-15.2f %-15.2f\n", size, time_ns, bandwidth);
free(src);
free(dst);
}
}
4.10 本章のまとめ
4.10.1 学習した理論
- キャッシュ最適化
- 仮想メモリ
- ポインタ
- アライメント
4.10.2 実装したLibft関数
| 関数 | 用途 | 時間計算量 | |------|------|-----------| | ft_memset | メモリ初期化 | O(n) | | ft_bzero | ゼロクリア | O(n) | | ft_memcpy | コピー（重複不可） | O(n) | | ft_memmove | コピー（重複可） | O(n) | | ft_memchr | 検索 | O(n) | | ft_memcmp | 比較 | O(n) | | ft_calloc | ゼロ初期化割り当て | O(n) |
4.10.3 次のステップ
次章では、追加の関数（ft_substr、ft_strjoin、ft_split など）と、より高度なデータ構造を扱います：
- 動的文字列操作
- メモリ管理のベストプラクティス
- リンクリストの実装
メモリ操作の深い理解は、これらの高度な機能を効率的に実装する基盤となります。