code-optimization

コード最適化スキル

標準ライブラリの実装を超えるコードパフォーマンスの向上に注力する、コード最適化のエキスパートアシスタントです。

このスキルを使用するタイミング

次のことが必要な場合に、このスキルを使用します。

• 既存のコードを最適化し、標準ライブラリの実装より優れたパフォーマンスを実現する
• コードの実行時間とメモリ使用量をベンチマークして測定する
• 複数回の最適化ラウンドを経て、コードのパフォーマンスを段階的に向上させる（最大2回）
• 最適化したコードのパフォーマンスをベースライン実装と比較する
• 改善内容を記録した詳細な最適化レポートを生成する

最適化の制約

重要：

• 最適化の最大反復回数：2ラウンド
• さらなる改善が可能な場合でも、2つのバージョン（v1、v2）の後で最適化を終了します
• 各反復では、効果の大きい最適化に重点を置きます
• 早い段階で大幅な改善（50%超の高速化）を達成した場合は、上限に達する前に終了できます

最適化ワークフロー

ステップ1：コードを読み、分析する

ファイル関連のツールを使用して、次の作業を行います。

• ユーザーのコードファイルをローカルファイルシステムから読み取る
• 最適化対象の関数を理解する
• パフォーマンスのボトルネックを特定する
• 最適化を実装する

例：

# Read code file
content = read_file("topk_benchmark.cpp")

# Analyze and implement optimization
# Fill in the my_topk_inplace function with optimized implementation

ステップ2：コンパイルして実行する

コマンドラインからコードを実行し、パフォーマンスを測定します。

C++ コードの場合：

# Compile with optimization flags
g++ -O3 -std=c++17 topk_benchmark.cpp -o topk_benchmark

# Run and capture output
./topk_benchmark

Python コードの場合：

python3 optimization_benchmark.py

その他の言語の場合：

# Java
javac MyOptimization.java && java MyOptimization

# Rust
rustc -O optimization.rs && ./optimization

# Go
go build optimization.go && ./optimization

ステップ3：パフォーマンス指標を抽出する

実行結果から、次の情報を抽出します。

• 実行時間：壁時計時間、CPU 時間
• メモリ使用量：ピークメモリ、メモリ差分
• ベースラインとの比較：高速化率、時間差
• 正しさの検証：テスト結果、精度チェック

解析対象の出力例：

N=160000, K=16000
std::nth_element time: 1234 us (1.234 ms)
my_topk_inplace time: 567 us (0.567 ms)
Verification: PASS
Speedup: 2.18x faster

ステップ4：反復して改善する

最適なパフォーマンスを実現するため、ステップ1〜3を最大2回まで繰り返します。

• 反復1：アルゴリズムの改善に重点を置きます（効果が最も大きいもの）
• 反復2：低レベルの最適化（SIMD、コンパイラフラグ）または並行処理を適用します

終了基準：

• 最適化の反復回数が2回に達した（上限）
• ベースラインから10倍超の高速化を達成した（優れた結果のため、早期終了可能）
• さらなる最適化による改善が5%未満である（効果が逓減）
• 最適化によってパフォーマンスが低下し始めた（元に戻して終了）

ステップ5：結果を保存する

最適化済みコードを保存し、レポートを生成します。

最適化済みコードの保存：

# Save to code_optimization directory
write_file("code_optimization/topk_benchmark_optimized.cpp", optimized_code)

最適化レポートの生成（code_optimization/report.md）：

# Code Optimization Report

## 【优化版本】v1

### 【优化内容】
1. 使用 std::partial_sort 替代 std::nth_element，减少额外排序开销
2. 优化内存分配策略，使用 reserve() 预分配空间
3. 原因：partial_sort 对前 K 个元素的局部排序更高效

### 【优化后性能】
- 运行时间：从 1234 us 优化到 567 us
- 性能提升：54% 更快
- 内存占用：640 KB（与基线相同）

### 【和标准库对比】
- 比 std::nth_element 快 667 us（约 2.18x 倍速）
- 验证结果：PASS（输出与标准库完全一致）

---

## 【优化版本】v2

### 【优化内容】
1. 引入快速选择算法（Quick Select）优化分区过程
2. 使用 SIMD 指令加速比较操作（AVX2）
3. 原因：减少分支预测失败，提高 CPU 流水线效率

### 【优化后性能】
- 运行时间：从 567 us 优化到 312 us
- 性能提升：相比 v1 快 45%
- 内存占用：640 KB（无额外开销）

### 【和标准库对比】
- 比 std::nth_element 快 922 us（约 3.95x 倍速）
- 验证结果：PASS

---

## 最终总结

### 最佳版本：v2 (达到最大迭代次数)
- **总体性能提升**：从基线 1234 us 优化到 312 us（74.7% 性能提升）
- **相比标准库**：快 3.95 倍
- **优化策略**：算法改进 + SIMD 向量化
- **迭代次数**：2 轮（已达上限）
- **适用场景**：大规模数据（N > 100K）的 Top-K 查询
- **权衡考虑**：无额外内存开销，代码复杂度适中

### 优化技术总结
1. 算法层面：Quick Select（线性期望时间）
2. 指令级别：SIMD 向量化（AVX2）
3. 编译优化：-O3 -march=native

追跡する主なパフォーマンス指標

実行時間

• 壁時計時間：経過時間の合計
• CPU 時間：実際の CPU 計算時間
• 高速化率：ベースラインとの比較（例：2.5倍高速）

メモリ使用量

• ピークメモリ：最大メモリ消費量
• メモリ差分：ベースラインと比較した追加メモリ量
• メモリ効率：MB あたりのパフォーマンス

正しさ

• 検証ステータス：PASS/FAIL
• 精度：該当する場合は数値精度
• エッジケース：境界条件の処理

スケーラビリティ

• 入力サイズのスケーリング：データサイズの変化に応じたパフォーマンス
• スレッド数のスケーリング：スレッド数の違いに応じたパフォーマンス（該当する場合）
• キャッシュの動作：L1/L2/L3 キャッシュのヒット率

最適化戦略（2回の反復を前提とした優先順位）

反復1：アルゴリズムの改善（最も効果が大きい — 必須）

• O(n log n) を O(n) アルゴリズムに置き換える
• 専用のデータ構造（ヒープ、ツリー）を使用する
• 分割統治法を実装する
• 動的計画法を適用する
• 最初からより優れたアルゴリズムを選択する

イテレーション 2：低レベル最適化または並行処理（問題に応じて選択）

オプション A：低レベル最適化（CPU バウンドのタスク向け）

• コンパイラフラグ：-O3、-march=native、-flto
• SIMD 命令：SSE、AVX2、AVX-512
• 分岐の削減：条件分岐をなくします
• メモリアライメント：ベクトル化のためにデータをアラインメントします
• キャッシュ最適化：データの局所性を高めます

オプション B：並行処理（並列化できるタスク向け）

• マルチスレッド処理：スレッドプール、ワークスティーリング
• ロックフリーアルゴリズム：アトミック操作、CAS
• SIMD とスレッド処理：両方のアプローチを組み合わせます
• GPU アクセラレーション：高い並列性を持つタスク向けの CUDA、OpenCL

メモリ最適化（全体を通して適用）

• キャッシュフレンドリーなアクセス：逐次読み取り、プリフェッチ
• メモリプーリング：メモリ割り当てのオーバーヘッドを削減します
• データレイアウト：構造体の配列（SoA）と配列の構造体（AoS）
• ゼロコピー：不要なデータの複製を避けます

ベストプラクティス

1. まず測定する：最適化の前に、必ずベースラインのパフォーマンスをベンチマークします
2. 正しさを検証する：最適化したコードを参照実装と照らし合わせてテストします
3. 変更は段階的に行う：改善点を特定できるよう、一度に 1 つの側面を最適化します
4. すべてを記録する：最適化の試みをすべてレポートに記録します
5. トレードオフを考慮する：パフォーマンス、メモリ、コードの複雑さのバランスを取ります
6. プラットフォームを考慮する：対象ハードウェア（CPU アーキテクチャ、キャッシュサイズ）でテストします
7. コンパイラ最適化：適切なフラグを使い、その効果を理解します
8. プロファイルに基づいて最適化する：プロファイリングツール（perf、valgrind）を使ってボトルネックを特定します
9. イテレーション数の上限を守る：2 回のイテレーションを戦略的に計画します（まずアルゴリズム、その後に低レベル最適化または並行処理）

避けるべきよくある落とし穴

• 早すぎる最適化：ボトルネックを特定する前に最適化しないでください
• マイクロベンチマークの誤り：コンパイラがテストコードを最適化によって除去しないようにします
• 正しさを無視すること：速くても誤ったコードに意味はありません
• 過剰な設計：わずかな性能向上のために可読性を犠牲にしないでください
• プラットフォーム固有のコード：ハードウェア依存関係を明確に記録します
• イテレーション数の上限超過：さらに最適化できる場合でも、2 回の最適化ラウンド後に終了します

最適化セッションの例（イテレーション数の上限：2 回）

Baseline: std::nth_element: 1234 us

Iteration 1 (Algorithm): Quick Select with 3-way partitioning
→ my_topk v1: 567 us (54% faster) ✅

Iteration 2 (Low-level): Add SIMD vectorization (AVX2)
→ my_topk v2: 312 us (75% faster than baseline) ✅ BEST

Final result: 3.95x speedup over std::nth_element
Status: Reached maximum 2 iterations, optimization complete ✓

ツールとコマンド

コンパイル

# C++ with optimizations
g++ -O3 -march=native -std=c++17 code.cpp -o code

# Enable warnings
g++ -O3 -Wall -Wextra -pedantic code.cpp -o code

# Link-time optimization
g++ -O3 -flto code.cpp -o code

プロファイリング

# Linux perf
perf stat ./code
perf record ./code && perf report

# Valgrind (memory profiling)
valgrind --tool=massif ./code

# Google benchmark
./code --benchmark_format=console

検証

# Run with sanitizers
g++ -fsanitize=address,undefined code.cpp -o code
./code

# Compare output with reference
diff <(./reference) <(./optimized)

レポートテンプレート

code_optimization/report.md には、次のテンプレートを使用します。

# Code Optimization Report: [Problem Name]

## Baseline Performance
- Implementation: [e.g., std::nth_element]
- Execution time: [X] us
- Memory usage: [Y] KB
- Input size: N=[value], K=[value]

---

## 【优化版本】v1
### 【优化内容】
1. [具体优化措施1]
2. [具体优化措施2]
3. 原因：[为什么这样优化]

### 【优化后性能】
- 运行时间：从 [X] us 优化到 [Y] us
- 性能提升：[百分比]% 更快
- 内存占用：[Z] KB

### 【和标准库对比】
- 比基线快/慢 [差值] us（约 [倍数]x 倍速）
- 验证结果：[PASS/FAIL]

---

## 【优化版本】v2
### 【优化内容】
1. [具体优化措施1]
2. [具体优化措施2]
3. 原因：[为什么这样优化]

### 【优化后性能】
- 运行时间：从 [X] us 优化到 [Y] us
- 性能提升：相比 v1 [百分比]% 更快
- 内存占用：[Z] KB

### 【和标准库对比】
- 比基线快/慢 [差值] us（约 [倍数]x 倍速）
- 验证结果：[PASS/FAIL]

---

## 最终总结 (已达最大迭代次数: 2轮)
- 最佳版本：[vX]
- 总体性能提升：[百分比]%
- 最终加速比：[X]x
- 迭代次数：2 轮（已达上限）
- 优化策略：[列出关键技术]
- 适用场景：[说明最佳使用场景]
- 权衡考虑：[列出 trade-offs]
- 进一步优化建议：[如果时间允许，可以尝试的方向]

リソース

• コンパイラ最適化：https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
• SIMD プログラミング：https://www.intel.com/content/www/us/en/docs/intrinsics-guide/
• パフォーマンス分析：https://perf.wiki.kernel.org/
• アルゴリズムの計算量：https://www.bigocheatsheet.com/

パフォーマンス最適化は反復的なプロセスです。**最適化のイテレーションは最大 2 回までです。**必ず測定し、一度に 1 つのことを最適化し、正しさを検証して、結果を詳しく記録してください。効果を最大化できるよう、2 回のイテレーションを戦略的に計画します。まずアルゴリズムに注力し、その後、問題の特性に応じて低レベル最適化または並行処理を選択してください。