FreeCADのトポロジー最適化をGeminiが10倍−15倍高速化した話 その2(Plan 概要編)

一つ前の記事

https://qiita.com/___monta___/items/63ee3da55f70fb0d1af2

# 依頼事項

先ほどの計測で実態がわかったので、さらに高速化処理の計画を立ててもらいます。ここも人間は対して何もしません。

```text:プロンプト
現在のBESOプラグインの問題は処理が遅いことです。
現在のフォルダのコードを一通り確認し、高速化のアイディアをいくつかまとめてください。
それぞれのアイディアに対して実装容易性、効果を検討してください。

結果をSpeedUpPlan.mdとして保存してください。
```
と依頼するだけ。

# BESOプラグイン高速化プラン
## 現状の問題点

コードベースを分析した結果、BESOプラグインの主な性能ボトルネックは以下の部分にあると考えられます：

1. **フィルタリング関数のループ処理**: `beso_filters.py`内の`run1`、`run2`、`run3`などの関数には、多数の要素に対する繰り返し計算が含まれています。現在、`run2`はベクトル化されていますが、イテレーションごとに依然として約5.8秒かかっています。
2. **データ構造の非効率性**: Pythonの辞書型（`dict`）を大量に使用していますが、ベクトル演算に最適化されていません。特に近接要素の検索に時間がかかっています（Filter Preparationに約43-46秒）。
3. **計算の冗長性**: 同じ計算が繰り返し行われている箇所があります。
4. **並列処理の不足**: CPU負荷の高い計算が直列処理されています。

## 高速化の提案

以下に高速化のための提案と、それぞれの予想される効果および実装の容易さを示します。

### 1. フィルタリング関数のベクトル化 

**説明**: `run2`などの関数内のループ処理をNumPyのベクトル演算に置き換える。  

**実装例**:
```python
# 元のコード（ループ処理）
for en in opt_domains:
    numerator = 0
    denominator = 0
    for en2 in near_elm[en]:
        ee = (min(en, en2), max(en, en2))
        numerator += weight_factor2[ee] * sensitivity_number[en2]
        denominator += weight_factor2[ee]
    sensitivity_number_filtered[en] = numerator / denominator

# ベクトル化したコード
for en in opt_domains:
    neighbors = near_elm[en]
    weights = np.array([weight_factor2[(min(en, en2), max(en, en2))] for en2 in neighbors])
    sens_values = np.array([sensitivity_number[en2] for en2 in neighbors])
    sensitivity_number_filtered[en] = np.sum(weights * sens_values) / np.sum(weights)
```

**効果**: 
- 特に多数の要素を持つモデルで効果大

**実装の容易さ**: ★★★☆☆（中程度）
- 既存コードの構造を維持しつつ実装可能
- テスト容易性のためにフラグでオン/オフ切り替え可能

### 2. 空間データ構造（k-dツリー）の導入 

**説明**: 近接要素の検索に効率的な空間データ構造（k-dツリー）を導入する。  

**実装案**:
```python
from scipy.spatial import KDTree

# 要素中心点をk-dツリーに格納
element_centers = np.array([cg[en] for en in opt_domains])
element_indices = np.array(list(opt_domains))
kdtree = KDTree(element_centers)

# 範囲検索で近接要素を効率的に特定
for en in opt_domains:
    # 指定半径内の要素インデックスを取得
    indices = kdtree.query_ball_point(cg[en], r_min)
    # 実際の要素番号に変換
    near_elm[en] = [element_indices[i] for i in indices if element_indices[i] != en]
```

**予想される効果**: 
- 特に要素数が多いモデルで効果が顕著

**実装の容易さ**: ★★★☆☆（中程度）
- SciPyライブラリが必要
- 既存のデータ構造との統合に注意が必要
- インデックス変換ロジックが必要

### 3. 計算のキャッシング導入 

**説明**: 繰り返し計算される値をキャッシュし、再計算を避ける。  

**候補となる箇所**:
- フィルタリング前準備の計算値
- 繰り返し計算される距離や重み値

**予想される効果**: 
- Sensitivity Filtering: さらに10-20%改善
- Filter Preparation: 10-15%改善
- 特に大規模モデルで効果的
- メモリ使用量増加のトレードオフあり

**実装の容易さ**: ★★☆☆☆（やや難しい）
- キャッシュの無効化条件を適切に設定する必要あり
- キャッシュのライフサイクル管理が複雑

### 4. 並列処理の導入 

**説明**: `multiprocessing`を使って計算負荷の高いタスクを並列化。

**候補となる箇所**:
- 各要素の感度数値計算
- フィルタリングの前処理計算
- 独立した最適化ドメインの並列処理

**予想される効果**: 
- コア数に比例した高速化
- 4コアシステムの場合：
  - Filter Preparation: 最大70%改善
  - Sensitivity Filtering: 最大70%改善
- I/O依存の処理では効果が限定的

**実装の容易さ**: ★☆☆☆☆（難しい）
- データの共有と同期が複雑
- 競合状態の回避が必要
- デバッグが困難

### 5. Cython/Numbaによる低レベル最適化 

**説明**: 計算負荷の高い関数をCythonやNumbaで最適化。

**候補となる箇所**:
- フィルタリング関数
- 距離計算
- 座標変換

**予想される効果**: 
- フィルタリングや距離計算: 5〜20倍の高速化
- 合計実行時間: 10分以下も可能
- 実行環境への依存性増加

**実装の容易さ**: ★☆☆☆☆（難しい）
- Cython使用の場合はコンパイル環境の設定が必要
- FreeCAD環境でのNumba/Cythonの動作検証が必要
- 環境依存性が高まるリスク

### 6. データ構造の最適化 

**説明**: 大規模な辞書やリストをより効率的なデータ構造（NumPy配列、SciPyのスパース行列など）に置き換える。

**候補となる箇所**:
- 近接要素情報の格納
- 重み係数の管理
- 感度数値の格納

**予想される効果**: 
- メモリ使用効率の改善
- アクセス時間の短縮
- k-dツリーと組み合わせた場合: 
  - 5〜10倍のメモリアクセス効率改善
  - Filter Preparation: 80-90%の改善

**実装の容易さ**: ★★☆☆☆（やや難しい）
- コード全体の広範囲な変更が必要
- データ構造の変更に伴うロジック調整が複雑

## 実装の優先順位

現在の処理時間分析と期待される効果に基づき、優先順位を再評価しました：

1. **フィルタリング関数のベクトル化** - 最も効果的な次のステップ
2. **空間データ構造（k-dツリー）の導入**  - 最も効果的な次のステップ、特にFilter Preparationの大幅な時間短縮
3. **データ構造の最適化** - k-dツリーと部分的に統合して実装
4. **計算のキャッシング導入** - 追加の改善として
5. **並列処理の導入** - 大規模モデルで大きな効果が期待できる
6. **Cython/Numbaによる最適化** - 最終段階の最適化