コードチューニングのための時間計測

 C++でコード実行時間をナノ秒(ns)単位で計測する場合は、通常 std::chrono::steady_clock を使います。

#include <chrono>

#include <iostream>

 

int main()

{

auto start = std::chrono::steady_clock::now();

 

// 計測対象

volatile int sum = 0;

for (int i = 0; i < 1000000; ++i)

sum += i;

 

auto end = std::chrono::steady_clock::now();

 

auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(

end - start).count();

 

std::cout << ns << " ns\n";

}

関数化

template<class F>

long long measure_ns(F&& func)

{

auto start = std::chrono::steady_clock::now();

 

func();

 

auto end = std::chrono::steady_clock::now();

 

return std::chrono::duration_cast<

std::chrono::nanoseconds>(end - start).count();

}

使用例:

auto ns = measure_ns([]{

volatile int x = 0;

for (int i = 0; i < 1000000; ++i)

x += i;

});

 

std::cout << ns << " ns\n";

注意点

極めて短いコード（数ns～100ns程度）を計測する場合、

_mm_store_si128(...)

1回だけの計測ではタイマ精度やOS割込みの影響が大きくなります。

そのため、

constexpr int N = 1000000;

 

auto start = std::chrono::steady_clock::now();

 

for (int i = 0; i < N; ++i)

{

target_code();

}

 

auto end = std::chrono::steady_clock::now();

 

double ns_per_call =

std::chrono::duration_cast<std::chrono::nanoseconds>(

end - start).count()

/ static_cast<double>(N);

のように大量ループして1回当たりの時間を求める方が正確です。

さらにSIMD命令やCPUサイクル単位で測るなら、RDTSC/RDTSCP を使う方法もあります。

#include <x86intrin.h>

 

uint64_t t0 = __rdtsc();

 

target_code();

 

uint64_t t1 = __rdtsc();

 

std::cout << (t1 - t0) << " cycles\n";

ただし __rdtsc() は命令の並べ替えの影響を受けるため、ベンチマーク用途では通常

_mm_lfence();

t0 = __rdtsc();

 

target_code();

 

unsigned aux;

t1 = __rdtscp(&aux);

_mm_lfence();

のように LFENCE + RDTSC + RDTSCP + LFENCE を組み合わせます。

SSE/AVXレベルの最適化を評価するなら、chrono よりも RDTSCP で「サイクル数」を測定する方が有用です。例えば _mm_store_si128 と memcmp の比較などでは、nsよりcyclesの方が差が見えやすくなります。

サイクル数を時間に換算するには？

CPUサイクル数から時間への換算は、

$$\text{時間[s]}=\frac{\text{cycles}}{\text{CPU周波数[Hz]}}$$時間[s]=CPU周波数[Hz]cycles​

です。

例えば 4.0GHz のCPUで、

400 cycles

なら

$$400\mathrm{/}(4.0\times {10}^9)=100𝑛𝑠$$400/(4.0×109)=100ns

となります。

nsへ直接換算

$$\text{時間[ns]}=\frac{\text{cycles}\times {10}^9}{\text{CPU周波数[Hz]}}$$時間[ns]=CPU周波数[Hz]cycles×109​

4GHzなら

double ns = cycles / 4.0;

になります。

なぜなら4 GHz = 4 cycles/ns

だからです。

---

実際にはTurboで周波数が変わる

最近のCPUは

3.0GHz → 5.3GHz

のように動的に変化します。

そのため

cycles / CPU_GHz

で計算しても誤差があります。

ベンチマークでは通常、

cycles

のまま比較します。

実装A : 12 cycles

実装B : 18 cycles

のように。

---

TSCがInvariantの場合

最近のIntel/AMDでは TSC(Time Stamp Counter) が一定速度です。

例えば

t0 = __rdtsc();

sleep(1);

t1 = __rdtsc();

なら

t1 - t0 ≒ TSC周波数

です。

TSC周波数は実クロックとは異なり、

Base Clock

に固定されていることが多いです。

---

正確な換算方法

chrono と rdtsc を同時に計測して較正します。

auto t0 = std::chrono::steady_clock::now();

uint64_t c0 = __rdtsc();

 

std::this_thread::sleep_for(std::chrono::milliseconds(100));

 

auto t1 = std::chrono::steady_clock::now();

uint64_t c1 = __rdtsc();

 

double sec =

std::chrono::duration<double>(t1 - t0).count();

 

double tsc_hz = (c1 - c0) / sec;

すると

C++

ns = cycles * 1e9 / tsc_hz;

で高精度に換算できます。

SIMDコード（_mm_store_si128、memcmp、8byte比較など）の性能評価なら、ユーザーさんの用途では ns換算せず cycles のまま比較するのが一般的 です。CPU周波数変動の影響を受けず、

Plain Text

実装A : 3.2 cycles

実装B : 5.8 cycles

のように直接性能差が分かります。さらに命令単位で評価する場合は、ループ展開して「cycles/iteration」または「cycles/op」を見るのが定番です。

インクリメンタル アクセスとデクリメンタルアクセス

データ構造を作り直すことにしました。ついては、アクセス方法の違いについて聞きました。 

インクリメンタル　アクセスとデクリメンタルアクセスで、キャッシュヒット特性に差はありますか？

インクリメンタルアクセス（アドレスが順方向に増加）とデクリメンタルアクセス（アドレスが逆方向に減少）では、キャッシュヒット特性に明らかな差が出ることがあります。

この差は主に、現代のプロセッサに搭載されているハードウェアプリフェッチャ（事前読み込み機能）の挙動や設計に起因します。

主な違いと特性は以下の通りです。

---

1. ハードウェアプリフェッチャの対応度

現代のCPUは、次にアクセスされるデータを予測してキャッシュに先読みします。

• インクリメンタル（順方向）：
  • ほぼすべてのプロセッサのプリフェッチャが完璧に対応しています。
  • 連続的な順方向アクセス（A, A+1, A+2...）を検出すると、自動的に先読みが行われるため、キャッシュヒット率は非常に高くなります。
• デクリメンタル（逆方向）：
  • 多くの近代的なCPU（IntelやAMD、ARMの高性能コアなど）は逆方向のストライド（A, A-1, A-2...）も検出できます。
  • しかし、古いアーキテクチャや、低消費電力向けの簡易なプロセッサ（一部の組み込み向けコアなど）では、逆方向のプリフェッチに対応していない、あるいは順方向に比べて検出の優先度が低い場合があります。この場合、デクリメンタルアクセスではキャッシュミスが多発します。

---

2. 空間局所性とキャッシュラインのマッピング

メモリは「キャッシュライン（一般的に64バイト）」という単位でキャッシュに読み込まれます。

• インクリメンタル：
  • キャッシュラインの先頭（オフセット0）から末尾に向かってアクセスが進むため、1度のキャッシュミスで読み込んだラインをフルに活用できます。
• デクリメンタル：
  • キャッシュラインの末尾から先頭に向かって逆順にアクセスします。
  • プリフェッチが効かない環境では、「新しいキャッシュラインにまたがった瞬間（境界を越えたとき）」に必ずキャッシュミス（レイテンシ）が発生し、その後そのラインの残りのデータを逆向けに消化していく形になります。データの利用効率自体は同じですが、ミスの発生するタイミングやプリフェッチの起動タイミングが狂いやすくなります。

---

まとめ（比較表）

特性	インクリメンタルアクセス (順方向)	デクリメンタルアクセス (逆方向)
一般的なヒット率	非常に高い（安定）	高〜中（CPUのプリフェッチ能力に依存）
ハードウェア先読み	確実に動作する	CPUによっては動作しない・遅れる場合がある
不利益を被る環境	特になし	古いCPU、組み込み向けCPU、GPUの一部など

結論として：
最新のPCやサーバー向けCPUであれば、どちらも高いヒット率を維持できるよう設計されていますが、ハードウェアの最適化は常に「インクリメンタル（順方向）」を最優先に設計されているため、迷った場合はインクリメンタルなアクセス経路（例：多次元配列をループさせる際の順序など）を選択するのが安全です。

なぜ、ナーススケジューリング問題では、絶対指標ベンチマークへの言及がないか？

 VRP等の新しい論文では、各ベンチマークの言及が必ずあると思いますが、最近のナーススケジューリング問題の論文では、ないのが不思議です。以下は、AIの回答ですが、本当の理由は別なところにあると思います。

ナーススケジューリング問題（NSP: Nurse Scheduling Problem、またはNRP: Nurse Rostering Problem）の最近の論文で、VRP（車両ルーティング問題）のような「統一された絶対的な標準ベンチマーク」への言及や共通データでの比較が少なく見えるのは、研究者の間でもよく指摘される非常に鋭い着眼点です。

VRPではCVRPTWやGehring & Hombergerなどの決定版ベンチマークが存在し、全員が同じ土俵で競いますが、ナーススケジューリング問題でそれが難しいのには、この問題特有の背景や構造的な要因があります。

主な理由は以下の4点に集約されます。

1. 法規制や現場ルールが「国・病院ごとに違いすぎる」

VRPは「容量制限」や「時間枠」など、物理的・数学的にモデルを標準化しやすい特徴があります。しかし、ナーススケジューリングは「人間（労働者）」を対象としているため、制約が極めてローカルかつ複雑です。

• 国による法規制の違い: 週の最大労働時間、夜勤後のインターバル（休息時間）の法的義務などが国ごとに全く異なります。
• 病院・病棟ごとのローカルルール: 「AさんとBさんは仲が悪いので同じシフトにしない」「この病棟はベテランを必ず1人配置する」といった、数式化しにくいソフト制約（Soft Constraints）が無限に存在します。

結果として、ある論文が提案した優れたアルゴリズムも、別のデータセット（別の国のルール）にはそのまま適用できないケースが多く、共通のベンチマークで横並び比較する意義が薄れてしまうのです。

2. インスタンス（問題データ）の寿命とプラットフォームの断絶

過去に国際コンペティションなどで標準ベンチマークが作られなかったわけではありません。

• INRC (International Nurse Rostering Competition): 2010年（INRC2010）や2015年（INRC2015）に世界大会が開催され、標準データセットが公開されました。
• 第一線での風化: VRPのベンチマークが何十年も使われ続けるのに対し、NSPのコンペデータは「制約が当時の特定のモデルに依存しすぎている」ため、新しい解法（例えば最新の深層強化学習やLLMベースのメタヒューリスティクス）を適用しようとすると、データのパースや制約の再現が非常に難しく、敬遠されがちです。

3. 近年の論文の関心が「実用性・動的対応」にシフトしている

最近のNSPの論文では、静的な標準データをいかに速く解くかよりも、「現実の運用で使えるか」に焦点が当たっています。

• 動的・確率的アプローチ: 急な欠勤（看護師の体調不良）や患者数の変動に対応する「リロスタリング（再スケジューリング）」や「確率的プログラミング」の研究が増えています。
• 独自データの使用: そのため、著者が所属する国の実際の病院から提供された「リアルだけど独自のデータセット」を使って評価を行う論文が多くなり、結果として共通のベンチマークへの言及が減っています。

4. 評価指標（目的関数）を統一できない

VRPの目的関数は基本的に「総移動距離の最小化」や「車両台数の最小化」であり、明確です。
一方、NSPでは「病院側のコスト最小化（超過勤務手当の削減）」と「看護師側の満足度最大化（希望休の反映）」という相反する多目的最適化になります。何を最優先（あるいはどう重み付け）するかは病院ごとに異なるため、あるベンチマークスコアで「勝利」したとしても、それが本当に優れたアルゴリズムなのかを測るのが本質的に難しいという問題があります。

---

💡 まとめると
VRPが「綺麗に舗装されたサーキットでタイムを競うレース」だとすれば、ナーススケジューリングは「病院ごとに地形が変わる泥道を走るラリー」のようなものです。そのため、最近の論文では共通ベンチマークのスコアよりも、「いかに複雑で現実的な制約の組み合わせを破綻させずに解けるか（表現力と柔軟性）」に重きが置かれているのが、ベンチマークへの言及が少なく見える最大の理由です。