java-topology/defects/dolphin-0001/test/test_dolphin_breakpoints.cpp

// Unit test for dolphin-0001: BreakPoints::GetRegularBreakpoint O(N) linear
// scan over std::vector -> O(1) unordered_map lookup.
//
// During a debug session, every CPU instruction executed in the interpreter
// (and every JIT block compiled) calls IsAddressBreakPoint -> GetBreakpoint ->
// GetRegularBreakpoint. With N breakpoints, that is O(N) per instruction.
// At 30 MHz emulated clock with N=50 breakpoints, this multiplies CPU time
// by 50x in the hot path.
//
// Fix: maintain an unordered_map<u32, size_t> index alongside m_breakpoints.
// Rebuild on every Add/Remove/Clear (rare). Lookup is O(1) amortized.

#include <cassert>
#include <chrono>
#include <cstdio>
#include <optional>
#include <string>
#include <unordered_map>
#include <vector>

// Minimal TBreakPoint mirroring Dolphin's struct.
struct TBreakPoint
{
  unsigned int address = 0;
  bool is_enabled = false;
  bool break_on_hit = false;
  bool log_on_hit = false;
};

// Original implementation: O(N) linear scan.
struct BreakPointsOriginal
{
  std::vector<TBreakPoint> m_breakpoints;

  void Add(unsigned int address)
  {
    TBreakPoint bp;
    bp.address = address;
    bp.is_enabled = true;
    bp.break_on_hit = true;
    m_breakpoints.push_back(bp);
  }

  const TBreakPoint* GetRegularBreakpoint(unsigned int address) const
  {
    for (const auto& bp : m_breakpoints)
    {
      if (bp.address == address)
        return &bp;
    }
    return nullptr;
  }
};

// Patched implementation: O(1) hash index.
struct BreakPointsPatched
{
  std::vector<TBreakPoint> m_breakpoints;
  std::unordered_map<unsigned int, std::size_t> m_bp_index;

  void RebuildIndex()
  {
    m_bp_index.clear();
    m_bp_index.reserve(m_breakpoints.size());
    for (std::size_t i = 0; i < m_breakpoints.size(); ++i)
      m_bp_index[m_breakpoints[i].address] = i;
  }

  void Add(unsigned int address)
  {
    TBreakPoint bp;
    bp.address = address;
    bp.is_enabled = true;
    bp.break_on_hit = true;
    m_breakpoints.push_back(bp);
    RebuildIndex();
  }

  const TBreakPoint* GetRegularBreakpoint(unsigned int address) const
  {
    auto it = m_bp_index.find(address);
    if (it == m_bp_index.end())
      return nullptr;
    return &m_breakpoints[it->second];
  }
};

int main()
{
  const int N_BREAKPOINTS = 64;
  const int N_LOOKUPS = 2000000;

  // --- Correctness ---
  {
    BreakPointsOriginal orig;
    BreakPointsPatched patched;

    for (int i = 0; i < N_BREAKPOINTS; ++i)
    {
      unsigned int addr = 0x80000000u + i * 4;
      orig.Add(addr);
      patched.Add(addr);
    }

    // Every address present in both implementations.
    for (int i = 0; i < N_BREAKPOINTS; ++i)
    {
      unsigned int addr = 0x80000000u + i * 4;
      const TBreakPoint* o = orig.GetRegularBreakpoint(addr);
      const TBreakPoint* p = patched.GetRegularBreakpoint(addr);
      assert(o != nullptr && "original: should find breakpoint");
      assert(p != nullptr && "patched: should find breakpoint");
      assert(o->address == addr);
      assert(p->address == addr);
    }

    // Address not in list returns nullptr in both.
    assert(orig.GetRegularBreakpoint(0xDEADBEEFu) == nullptr);
    assert(patched.GetRegularBreakpoint(0xDEADBEEFu) == nullptr);

    printf("Correctness: PASS\n");
  }

  // --- Performance ---
  {
    BreakPointsOriginal orig;
    BreakPointsPatched patched;

    for (int i = 0; i < N_BREAKPOINTS; ++i)
    {
      unsigned int addr = 0x80000000u + i * 4;
      orig.Add(addr);
      patched.Add(addr);
    }

    // Simulate per-instruction lookup: address not in breakpoints (common case).
    unsigned int probe_miss = 0x90000000u;
    // Also probe a hit address.
    unsigned int probe_hit = 0x80000000u + (N_BREAKPOINTS / 2) * 4;

    auto t0 = std::chrono::steady_clock::now();
    volatile int sink_orig = 0;
    for (int i = 0; i < N_LOOKUPS; ++i)
    {
      unsigned int addr = (i & 1) ? probe_hit : probe_miss;
      const TBreakPoint* bp = orig.GetRegularBreakpoint(addr);
      sink_orig += (bp != nullptr) ? 1 : 0;
    }
    auto t1 = std::chrono::steady_clock::now();
    volatile int sink_patched = 0;
    for (int i = 0; i < N_LOOKUPS; ++i)
    {
      unsigned int addr = (i & 1) ? probe_hit : probe_miss;
      const TBreakPoint* bp = patched.GetRegularBreakpoint(addr);
      sink_patched += (bp != nullptr) ? 1 : 0;
    }
    auto t2 = std::chrono::steady_clock::now();

    double ms_orig =
        std::chrono::duration<double, std::milli>(t1 - t0).count();
    double ms_patched =
        std::chrono::duration<double, std::milli>(t2 - t1).count();
    double ratio = ms_orig / ms_patched;

    assert(sink_orig == sink_patched && "hit counts must match");

    printf("Original  (O(N) vector scan):  %.2f ms for %d lookups (N=%d)\n",
           ms_orig, N_LOOKUPS, N_BREAKPOINTS);
    printf("Patched   (O(1) hash map):      %.2f ms for %d lookups\n",
           ms_patched, N_LOOKUPS);
    printf("Speedup: %.1fx\n", ratio);
    assert(ratio >= 2.0 && "patched must be at least 2x faster");
    printf("Performance: PASS\n");
  }

  printf("ALL TESTS PASSED\n");
  return 0;
}