課題23: ベンチマーク駆動最適化
マンダトリー要件
問題1: パフォーマンス分析の理解（15点）
- プロファイリングツール（5点）
- 最適化の原則（5点）
- ベンチマークの注意点（5点）
black_boxが必要な理由を説明しなさい。
- 正確なベンチマークを行うための3つのポイントを挙げなさい。問題2: 実装とベンチマーク（40点）
以下のアルゴリズムを複数の方法で実装し、ベンチマークで比較しなさい。
2.1 文字列検索（15点）
// 実装1: 素朴な実装
fn find_naive(text: &str, pattern: &str) -> Vec<usize> {
// 実装
}
// 実装2: 最適化版
fn find_optimized(text: &str, pattern: &str) -> Vec<usize> {
// 実装
}
// 実装3: Boyer-Moore法（ボーナス）
fn find_boyer_moore(text: &str, pattern: &str) -> Vec<usize> {
// 実装
}
ベンチマーク:
fn bench_string_search(c: &mut Criterion) {
let text = "..."; // 大きなテキスト
let pattern = "search";
let mut group = c.benchmark_group("string_search");
group.bench_function("naive", |b| {
b.iter(|| find_naive(black_box(text), black_box(pattern)));
});
group.bench_function("optimized", |b| {
b.iter(|| find_optimized(black_box(text), black_box(pattern)));
});
group.finish();
}
要件:
- 最低2つの実装
- Criterionを使ったベンチマーク
- 結果の分析レポート
2.2 ソートアルゴリズム（15点）
fn bubble_sort(data: &mut [i32]) {
// 実装
}
fn quick_sort(data: &mut [i32]) {
// 実装
}
fn merge_sort(data: &mut [i32]) {
// 実装
}
パラメータ化ベンチマーク:
fn bench_sort(c: &mut Criterion) {
let mut group = c.benchmark_group("sort");
for size in [10, 100, 1000, 10000].iter() {
let data: Vec<i32> = (0..*size).rev().collect();
group.bench_with_input(
BenchmarkId::new("bubble", size),
size,
|b, _| {
let mut data_copy = data.clone();
b.iter(|| bubble_sort(&mut data_copy));
},
);
// quick_sort, merge_sortも同様
}
group.finish();
}
要件:
- 3つのソートアルゴリズム実装
- 複数のデータサイズでベンチマーク
- O記法と実測値の比較
2.3 メモリ最適化（10点）
以下のコードを最適化しなさい:
// 最適化前
fn process_data_before(data: &[String]) -> Vec<String> {
let mut results = Vec::new();
for item in data {
let upper = item.to_uppercase();
let trimmed = upper.trim().to_string();
results.push(trimmed);
}
results
}
// 最適化後
fn process_data_after(data: &[String]) -> Vec<String> {
// 改善実装
}
測定項目:
- 実行時間
- メモリ使用量（valgrind massif使用）
- アロケーション回数
問題3: プロファイリング実践（25点）
3.1 フレームグラフ分析（10点）
以下のプログラムをプロファイリングし、ボトルネックを特定しなさい:
fn main() {
let data = generate_data(10000);
let result = process_pipeline(&data);
println!("Result: {}", result);
}
fn generate_data(n: usize) -> Vec<i32> {
(0..n).map(|i| expensive_calc(i)).collect()
}
fn process_pipeline(data: &[i32]) -> i32 {
let filtered = filter_data(data);
let transformed = transform_data(&filtered);
aggregate_data(&transformed)
}
fn expensive_calc(n: usize) -> i32 {
// 意図的に重い処理
(0..n).sum::<usize>() as i32
}
// 他の関数も実装
提出物:
- flamegraph.svg
- ボトルネック分析レポート
- 最適化提案
- 並列化
3.2 最適化実装（15点）
プロファイリング結果に基づいて最適化を実施しなさい:
use rayon::prelude::*;
fn generate_data_parallel(n: usize) -> Vec<i32> {
(0..n).into_par_iter()
.map(|i| expensive_calc(i))
.collect()
}
- キャッシュ
use std::cell::RefCell;
use std::collections::HashMap;
thread_local! {
static CACHE: RefCell<HashMap<usize, i32>> = RefCell::new(HashMap::new());
}
fn expensive_calc_cached(n: usize) -> i32 {
CACHE.with(|cache| {
*cache.borrow_mut()
.entry(n)
.or_insert_with(|| expensive_calc(n))
})
}
要件:
- 最低2つの最適化手法
- ビフォア・アフターのベンチマーク
- 改善率の計算
---
ボーナス課題
ボーナス1: SIMD最適化（10点）
SIMDを使った最適化を実装しなさい:
#![feature(portable_simd)]
use std::simd::*;
// スカラー版
fn sum_scalar(data: &[f32]) -> f32 {
data.iter().sum()
}
// SIMD版
fn sum_simd(data: &[f32]) -> f32 {
let (chunks, remainder) = data.as_chunks::<4>();
let sum = chunks
.iter()
.map(|&chunk| f32x4::from_array(chunk))
.fold(f32x4::splat(0.0), |acc, x| acc + x);
sum.reduce_sum() + remainder.iter().sum::<f32>()
}
ベンチマーク要件:
- 複数のデータサイズ（100, 1000, 10000, 100000）
- スカラー版との比較
- 高速化率の測定
ボーナス2: カスタムアロケータ（10点）
カスタムアロケータを実装し、パフォーマンスを比較しなさい:
use std::alloc::{GlobalAlloc, Layout, System};
struct CountingAllocator;
static mut ALLOCATION_COUNT: usize = 0;
unsafe impl GlobalAlloc for CountingAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
ALLOCATION_COUNT += 1;
System.alloc(layout)
}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
System.dealloc(ptr, layout)
}
}
#[global_allocator]
static ALLOCATOR: CountingAllocator = CountingAllocator;
fn get_allocation_count() -> usize {
unsafe { ALLOCATION_COUNT }
}
測定項目:
- アロケーション回数
- メモリ使用量
- 実行時間
ボーナス3: マルチスレッド最適化（10点）
マルチスレッドを使った最適化を実装しなさい:
use rayon::prelude::*;
use std::sync::Arc;
// シングルスレッド版
fn process_single(data: &[Vec<i32>]) -> Vec<i32> {
data.iter()
.map(|chunk| chunk.iter().sum())
.collect()
}
// マルチスレッド版
fn process_parallel(data: &[Vec<i32>]) -> Vec<i32> {
data.par_iter()
.map(|chunk| chunk.iter().sum())
.collect()
}
// Work Stealing版
fn process_work_stealing(data: &[Vec<i32>]) -> Vec<i32> {
use rayon::ThreadPoolBuilder;
let pool = ThreadPoolBuilder::new()
.num_threads(4)
.build()
.unwrap();
pool.install(|| {
data.par_iter()
.map(|chunk| chunk.iter().sum())
.collect()
})
}
要件:
- スレッド数を変えてベンチマーク（1, 2, 4, 8）
- スケーラビリティの分析
- オーバーヘッドの測定
- 初期状態の分析
ボーナス4: 包括的な最適化レポート（10点）
実際のアプリケーションを最適化し、詳細なレポートを作成しなさい。
レポート内容:
- 最適化戦略
- 実装
- 結果
- 考察
---
評価基準
マンダトリー部分（80点）
| 項目 | 配点 | 評価ポイント |
|---|---|---|
| 問題1: 基礎理解 | 15点 | 正確な説明 |
| 問題2: 実装とベンチマーク | 40点 | 複数の実装と比較 |
| 問題3: プロファイリング | 25点 | 分析と最適化 |
ボーナス部分（20点）
| 項目 | 配点 | 評価ポイント |
|---|---|---|
| ボーナス1: SIMD | 10点 | 正しい実装と測定 |
| ボーナス2: カスタムアロケータ | 10点 | 詳細な分析 |
| ボーナス3: マルチスレッド | 10点 | スケーラビリティ分析 |
| ボーナス4: 包括レポート | 10点 | 詳細で実用的な内容 |
注: ボーナスは最大20点まで加算されます。
---
提出方法
ファイル構成
rust-foundations-23/
├── Cargo.toml
├── src/
│ ├── lib.rs
│ ├── string_search.rs
│ ├── sort.rs
│ └── profiling.rs
├── benches/
│ ├── string_search.rs
│ ├── sort.rs
│ └── optimization.rs
├── flamegraph.svg
├── answers.md # 問題1の回答
└── optimization_report.md # 最適化レポート
実行方法
# ベンチマーク実行
cargo bench
# フレームグラフ生成
cargo flamegraph
# メモリプロファイリング
valgrind --tool=massif cargo run --release
---
ヒント
問題2.1のヒント
最適化のアイデア:
- バイトスライスを使う（
&str→&[u8]） - マッチ失敗時のスキップ量を増やす
- SIMDを使った並列比較
問題3のヒント
プロファイリング手順:
# 1. リリースビルドで実行
cargo build --release
# 2. フレームグラフ生成
cargo flamegraph --release
# 3. ボトルネック特定
# フレームグラフで横幅が広い関数を見つける
# 4. 最適化実装
# 5. 再度測定して効果を確認
cargo bench
---
学習の確認
この課題を通じて、以下を理解できたか確認してください:
次の章では、これまで学んだすべてを統合した実践プロジェクトに取り組みます。