ic_min.cpp

// ic_min.cpp
// clang++ -O3 -std=c++20 ic_min.cpp -o ic_min
// ./ic_min
#include <chrono>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>

#if defined(_MSC_VER)
#  define NOINLINE __declspec(noinline)
#else
#  define NOINLINE __attribute__((noinline))
#endif

enum class TypeId : uint32_t { A=1, B=2 };
struct Obj { TypeId type; uint32_t payload; };

using Fn = uint64_t(*)(const Obj&);
static NOINLINE uint64_t fA(const Obj& o){ return (uint64_t)o.payload*3 + 1; }
static NOINLINE uint64_t fB(const Obj& o){ return (uint64_t)o.payload*7 + 2; }

// 「探す処理」：型 -> 関数ポインタ（ここがlookup）
static NOINLINE Fn lookup(TypeId t){
  return (t==TypeId::A) ? &fA : &fB;
}

struct Counters { uint64_t lookups = 0; };

// ICなし：毎回 lookup してから呼ぶ
static uint64_t run_no_ic(const std::vector<Obj>& seq, int rounds, Counters& c){
  volatile uint64_t sink = 0;
  for(int r=0;r<rounds;r++){
    for(const auto& o: seq){
      c.lookups++;
      Fn f = lookup(o.type);
      sink += f(o);
    }
  }
  return (uint64_t)sink;
}

// ICあり（monomorphic）：call site に 1個だけキャッシュ
struct InlineCacheSite { uint32_t cachedType = 0; Fn cachedFn = nullptr; };

static uint64_t run_ic(const std::vector<Obj>& seq, int rounds, Counters& c){
  volatile uint64_t sink = 0;
  InlineCacheSite site;
  for(int r=0;r<rounds;r++){
    for(const auto& o: seq){
      uint32_t t = (uint32_t)o.type;
      if(t == site.cachedType){
        sink += site.cachedFn(o);           // hit: lookupしない
      } else {
        c.lookups++;                        // miss: lookupする
        Fn f = lookup(o.type);
        site.cachedType = t;                // cache更新
        site.cachedFn   = f;
        sink += f(o);
      }
    }
  }
  return (uint64_t)sink;
}

static long long now_ns(){
  return std::chrono::duration_cast<std::chrono::nanoseconds>(
    std::chrono::high_resolution_clock::now().time_since_epoch()
  ).count();
}

// mode 0: 95% A（ICが効く）
// mode 1: A/B交互（ICが効かない）
static std::vector<Obj> make_seq(size_t n, int mode, uint32_t seed=0){
  std::mt19937 rng(seed);
  std::uniform_int_distribution<uint32_t> payload(1, 1000);
  std::uniform_int_distribution<int> p(0, 99);

  std::vector<Obj> seq;
  seq.reserve(n);
  for(size_t i=0;i<n;i++){
    TypeId t;
    if(mode==0){
      t = (p(rng) < 95) ? TypeId::A : TypeId::B;
    } else {
      t = (i%2==0) ? TypeId::A : TypeId::B;
    }
    seq.push_back(Obj{t, payload(rng)});
  }
  return seq;
}

static void bench(const char* title, const std::vector<Obj>& seq, int rounds){
  std::cout << "\n=== " << title << " ===\n";

  Counters c1{};
  auto t1 = now_ns();
  auto s1 = run_no_ic(seq, rounds, c1);
  auto t2 = now_ns();
  double ns1 = (double)(t2-t1) / (seq.size()*(size_t)rounds);
  std::cout << "no IC : " << ns1 << " ns/call, lookups=" << c1.lookups << ", sink=" << s1 << "\n";

  Counters c2{};
  auto t3 = now_ns();
  auto s2 = run_ic(seq, rounds, c2);
  auto t4 = now_ns();
  double ns2 = (double)(t4-t3) / (seq.size()*(size_t)rounds);
  std::cout << "IC    : " << ns2 << " ns/call, lookups=" << c2.lookups << ", sink=" << s2 << "\n";

  uint64_t total = (uint64_t)seq.size()*(uint64_t)rounds;
  double miss = (double)c2.lookups / (double)total;
  std::cout << "IC miss rate ~ " << miss*100.0 << "%\n";
}

int main(){
  const size_t N = 200000;   // データ数（大きいほど安定）
  const int ROUNDS = 50;     // 繰り返し回数（大きいほど安定）

  auto mono = make_seq(N, 0, 123);
  auto alt  = make_seq(N, 1, 123);

  bench("Monomorphic-ish (95% A)", mono, ROUNDS);
  bench("Alternating (A,B,A,B,...)", alt, ROUNDS);
}