add128-benchmark.cc

add128-benchmark.cc

// Small standalone C++ benchmark for 128-bit addition.
// Supports native __uint128_t, 2x64-bit limb addition with carry,
// compiler builtins (__builtin_add_overflow), and x86 ADC intrinsics.

#include <chrono>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <memory>
#include <random>
#include <string>
#include <vector>

#if defined(__x86_64__) && __has_include(<immintrin.h>)
#include <immintrin.h>
#define HAVE_X86_INTRINSICS 1
#endif

#if defined(__SIZEOF_INT128__) || defined(__EMSCRIPTEN__)
using uint128_t = __uint128_t;
#define HAVE_NATIVE_UINT128 1
#endif

// Prevent the compiler from optimizing away benchmark expressions.
template <typename T>
[[gnu::always_inline]] inline void DoNotOptimize(T& value) {
#if defined(__clang__)
  asm volatile("" : "+r,m"(value) : : "memory");
#elif defined(__GNUC__)
  asm volatile("" : "+m,r"(value) : : "memory");
#else
  volatile char* p = reinterpret_cast<volatile char*>(&value);
  (void)*p;
#endif
}

[[gnu::always_inline]] inline void ClobberMemory() {
#if defined(__GNUC__) || defined(__clang__)
  asm volatile("" : : : "memory");
#endif
}

// 128-bit integer representation as two 64-bit limbs.
struct alignas(16) Uint128Struct {
  uint64_t lo;
  uint64_t hi;

  bool operator==(const Uint128Struct& o) const {
    return lo == o.lo && hi == o.hi;
  }
  bool operator!=(const Uint128Struct& o) const { return !(*this == o); }
};

#if HAVE_NATIVE_UINT128
inline uint128_t ToNative(Uint128Struct v) {
  return (static_cast<uint128_t>(v.hi) << 64) | v.lo;
}

inline Uint128Struct FromNative(uint128_t v) {
  return Uint128Struct{static_cast<uint64_t>(v),
                        static_cast<uint64_t>(v >> 64)};
}
#endif

// -----------------------------------------------------------------------------
// Addition Implementations
// -----------------------------------------------------------------------------

#if HAVE_NATIVE_UINT128
// 1. Native __uint128_t addition
[[gnu::always_inline]] inline uint128_t AddNative(uint128_t a, uint128_t b) {
  return a + b;
}
#endif

// 2. Manual 2-limb 64-bit addition with branchless carry comparison
[[gnu::always_inline]] inline Uint128Struct AddLimbCarry(Uint128Struct a,
                                                        Uint128Struct b) {
  Uint128Struct r;
  r.lo = a.lo + b.lo;
  r.hi = a.hi + b.hi + (r.lo < a.lo ? 1ULL : 0ULL);
  return r;
}

// 3. 2-limb 64-bit addition using __builtin_add_overflow
[[gnu::always_inline]] inline Uint128Struct AddBuiltinOverflow(Uint128Struct a,
                                                             Uint128Struct b) {
  Uint128Struct r;
  uint64_t carry = __builtin_add_overflow(a.lo, b.lo, &r.lo);
  r.hi = a.hi + b.hi + carry;
  return r;
}

#if HAVE_X86_INTRINSICS
// 4. 2-limb 64-bit addition using _addcarry_u64 (ADC instruction)
[[gnu::always_inline]] inline Uint128Struct AddAdcIntrinsic(Uint128Struct a,
                                                          Uint128Struct b) {
  Uint128Struct r;
  unsigned char carry =
      _addcarry_u64(0, a.lo, b.lo, reinterpret_cast<unsigned long long*>(&r.lo));
  _addcarry_u64(carry, a.hi, b.hi,
                reinterpret_cast<unsigned long long*>(&r.hi));
  return r;
}
#endif

// -----------------------------------------------------------------------------
// Correctness Verification
// -----------------------------------------------------------------------------

bool VerifyImplementations() {
  // Test edge cases: carry from low to high, and high overflow
  Uint128Struct e1{0xFFFFFFFFFFFFFFFFULL, 0ULL};
  Uint128Struct e2{1ULL, 0ULL};
  Uint128Struct expected_e{0ULL, 1ULL};

  if (AddLimbCarry(e1, e2) != expected_e ||
      AddBuiltinOverflow(e1, e2) != expected_e) {
    std::cerr << "Verification failed on edge carry!\n";
    return false;
  }
#if HAVE_X86_INTRINSICS
  if (AddAdcIntrinsic(e1, e2) != expected_e) {
    std::cerr << "Verification failed on ADC edge carry!\n";
    return false;
  }
#endif
#if HAVE_NATIVE_UINT128
  if (FromNative(AddNative(ToNative(e1), ToNative(e2))) != expected_e) {
    std::cerr << "Verification failed on native uint128 edge carry!\n";
    return false;
  }
#endif

  // Random tests
  std::mt19937_64 rng(1337);
  for (int i = 0; i < 10000; i++) {
    Uint128Struct a{rng(), rng()};
    Uint128Struct b{rng(), rng()};

    Uint128Struct r1 = AddLimbCarry(a, b);
    Uint128Struct r2 = AddBuiltinOverflow(a, b);
    if (r1 != r2) {
      std::cerr << "Mismatch between LimbCarry and BuiltinOverflow!\n";
      return false;
    }
#if HAVE_X86_INTRINSICS
    Uint128Struct r3 = AddAdcIntrinsic(a, b);
    if (r1 != r3) {
      std::cerr << "Mismatch between LimbCarry and ADC intrinsic!\n";
      return false;
    }
#endif
#if HAVE_NATIVE_UINT128
    Uint128Struct r4 = FromNative(AddNative(ToNative(a), ToNative(b)));
    if (r1 != r4) {
      std::cerr << "Mismatch between LimbCarry and Native uint128!\n";
      return false;
    }
#endif
  }
  return true;
}

// -----------------------------------------------------------------------------
// Benchmark Runner
// -----------------------------------------------------------------------------

struct BenchmarkResult {
  std::string name;
  double elapsed_ms;
  double ns_per_op;
  double million_ops_per_sec;
  uint64_t checksum;
};

class Add128Benchmark {
 public:
  Add128Benchmark(size_t size, size_t iterations)
      : size_(size), iterations_(iterations) {
    std::mt19937_64 rng(42);
    a_struct_.resize(size_);
    b_struct_.resize(size_);
#if HAVE_NATIVE_UINT128
    a_native_.resize(size_);
    b_native_.resize(size_);
#endif
    for (size_t i = 0; i < size_; i++) {
      a_struct_[i] = {rng(), rng()};
      b_struct_[i] = {rng(), rng()};
#if HAVE_NATIVE_UINT128
      a_native_[i] = ToNative(a_struct_[i]);
      b_native_[i] = ToNative(b_struct_[i]);
#endif
    }
  }

  void RunAll() {
    std::vector<BenchmarkResult> results;

    std::cout << "\n==========================================================\n";
    std::cout << " Running 128-bit Addition Benchmarks\n";
    std::cout << " Elements: " << size_ << ", Iterations: " << iterations_
              << " (" << (size_ * iterations_) << " total additions per test)\n";
    std::cout << "==========================================================\n";

    // 1. Throughput Benchmarks (Buffer stream: C[i] = A[i] + B[i])
    std::cout << "\n--- 1. Throughput Benchmarks (Array Stream C[i] = A[i] + B[i]) ---\n";

#if HAVE_NATIVE_UINT128
    results.push_back(BenchmarkNativeThroughput());
#endif
    results.push_back(BenchmarkLimbCarryThroughput());
    results.push_back(BenchmarkBuiltinOverflowThroughput());
#if HAVE_X86_INTRINSICS
    results.push_back(BenchmarkAdcThroughput());
#endif

    PrintTable(results);
    results.clear();

    // 2. Latency / Serial Dependency Chain Benchmarks (acc = acc + A[i])
    std::cout << "\n--- 2. Latency Benchmarks (Serial Chain: acc = acc + A[i]) ---\n";

#if HAVE_NATIVE_UINT128
    results.push_back(BenchmarkNativeLatency());
#endif
    results.push_back(BenchmarkLimbCarryLatency());
    results.push_back(BenchmarkBuiltinOverflowLatency());
#if HAVE_X86_INTRINSICS
    results.push_back(BenchmarkAdcLatency());
#endif

    PrintTable(results);
  }

 private:
#if HAVE_NATIVE_UINT128
  BenchmarkResult BenchmarkNativeThroughput() {
    std::vector<uint128_t> c(size_);
    // Warmup
    for (size_t i = 0; i < size_; i++) c[i] = AddNative(a_native_[i], b_native_[i]);
    DoNotOptimize(c[0]);

    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        c[i] = AddNative(a_native_[i], b_native_[i]);
      }
      DoNotOptimize(c[size_ - 1]);
      ClobberMemory();
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = 0;
    for (size_t i = 0; i < size_; i++) {
      checksum ^= static_cast<uint64_t>(c[i]) ^ static_cast<uint64_t>(c[i] >> 64);
    }
    return ComputeStats("Native __uint128_t (Stream)", start, end, checksum);
  }

  BenchmarkResult BenchmarkNativeLatency() {
    uint128_t acc = 0;
    // Warmup
    for (size_t i = 0; i < size_; i++) acc = AddNative(acc, a_native_[i]);
    DoNotOptimize(acc);

    acc = 0;
    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        acc = AddNative(acc, a_native_[i]);
      }
      DoNotOptimize(acc);
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = static_cast<uint64_t>(acc) ^ static_cast<uint64_t>(acc >> 64);
    return ComputeStats("Native __uint128_t (Chain)", start, end, checksum);
  }
#endif

  BenchmarkResult BenchmarkLimbCarryThroughput() {
    std::vector<Uint128Struct> c(size_);
    // Warmup
    for (size_t i = 0; i < size_; i++) c[i] = AddLimbCarry(a_struct_[i], b_struct_[i]);
    DoNotOptimize(c[0]);

    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        c[i] = AddLimbCarry(a_struct_[i], b_struct_[i]);
      }
      DoNotOptimize(c[size_ - 1]);
      ClobberMemory();
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = 0;
    for (size_t i = 0; i < size_; i++) {
      checksum ^= c[i].lo ^ c[i].hi;
    }
    return ComputeStats("2-Limb Carry (Stream)", start, end, checksum);
  }

  BenchmarkResult BenchmarkLimbCarryLatency() {
    Uint128Struct acc{0, 0};
    // Warmup
    for (size_t i = 0; i < size_; i++) acc = AddLimbCarry(acc, a_struct_[i]);
    DoNotOptimize(acc);

    acc = {0, 0};
    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        acc = AddLimbCarry(acc, a_struct_[i]);
      }
      DoNotOptimize(acc);
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = acc.lo ^ acc.hi;
    return ComputeStats("2-Limb Carry (Chain)", start, end, checksum);
  }

  BenchmarkResult BenchmarkBuiltinOverflowThroughput() {
    std::vector<Uint128Struct> c(size_);
    // Warmup
    for (size_t i = 0; i < size_; i++) c[i] = AddBuiltinOverflow(a_struct_[i], b_struct_[i]);
    DoNotOptimize(c[0]);

    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        c[i] = AddBuiltinOverflow(a_struct_[i], b_struct_[i]);
      }
      DoNotOptimize(c[size_ - 1]);
      ClobberMemory();
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = 0;
    for (size_t i = 0; i < size_; i++) {
      checksum ^= c[i].lo ^ c[i].hi;
    }
    return ComputeStats("Builtin Overflow (Stream)", start, end, checksum);
  }

  BenchmarkResult BenchmarkBuiltinOverflowLatency() {
    Uint128Struct acc{0, 0};
    // Warmup
    for (size_t i = 0; i < size_; i++) acc = AddBuiltinOverflow(acc, a_struct_[i]);
    DoNotOptimize(acc);

    acc = {0, 0};
    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        acc = AddBuiltinOverflow(acc, a_struct_[i]);
      }
      DoNotOptimize(acc);
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = acc.lo ^ acc.hi;
    return ComputeStats("Builtin Overflow (Chain)", start, end, checksum);
  }

#if HAVE_X86_INTRINSICS
  BenchmarkResult BenchmarkAdcThroughput() {
    std::vector<Uint128Struct> c(size_);
    // Warmup
    for (size_t i = 0; i < size_; i++) c[i] = AddAdcIntrinsic(a_struct_[i], b_struct_[i]);
    DoNotOptimize(c[0]);

    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        c[i] = AddAdcIntrinsic(a_struct_[i], b_struct_[i]);
      }
      DoNotOptimize(c[size_ - 1]);
      ClobberMemory();
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = 0;
    for (size_t i = 0; i < size_; i++) {
      checksum ^= c[i].lo ^ c[i].hi;
    }
    return ComputeStats("ADC Intrinsic (Stream)", start, end, checksum);
  }

  BenchmarkResult BenchmarkAdcLatency() {
    Uint128Struct acc{0, 0};
    // Warmup
    for (size_t i = 0; i < size_; i++) acc = AddAdcIntrinsic(acc, a_struct_[i]);
    DoNotOptimize(acc);

    acc = {0, 0};
    auto start = std::chrono::steady_clock::now();
    for (size_t it = 0; it < iterations_; it++) {
      for (size_t i = 0; i < size_; i++) {
        acc = AddAdcIntrinsic(acc, a_struct_[i]);
      }
      DoNotOptimize(acc);
    }
    auto end = std::chrono::steady_clock::now();

    uint64_t checksum = acc.lo ^ acc.hi;
    return ComputeStats("ADC Intrinsic (Chain)", start, end, checksum);
  }
#endif

  BenchmarkResult ComputeStats(const std::string& name,
                               std::chrono::steady_clock::time_point start,
                               std::chrono::steady_clock::time_point end,
                               uint64_t checksum) {
    uint64_t total_ops = size_ * iterations_;
    double elapsed_ns =
        std::chrono::duration<double, std::nano>(end - start).count();
    double elapsed_ms = elapsed_ns / 1e6;
    double ns_per_op = elapsed_ns / total_ops;
    double million_ops_per_sec = (total_ops / (elapsed_ns / 1e9)) / 1e6;

    return BenchmarkResult{name, elapsed_ms, ns_per_op, million_ops_per_sec,
                           checksum};
  }

  void PrintTable(const std::vector<BenchmarkResult>& results) {
    std::cout << std::left << std::setw(32) << "Implementation"
              << std::right << std::setw(14) << "Time (ms)"
              << std::setw(16) << "Latency (ns/op)"
              << std::setw(18) << "Throughput (Mop/s)"
              << std::setw(20) << "Checksum (hex)" << "\n";
    std::cout << std::string(100, '-') << "\n";

    for (const auto& r : results) {
      std::cout << std::left << std::setw(32) << r.name
                << std::right << std::fixed << std::setprecision(3)
                << std::setw(14) << r.elapsed_ms
                << std::setw(16) << r.ns_per_op
                << std::setw(18) << r.million_ops_per_sec
                << "  0x" << std::hex << std::setw(16) << std::setfill('0')
                << r.checksum << std::dec << std::setfill(' ') << "\n";
    }
  }

  size_t size_;
  size_t iterations_;
  std::vector<Uint128Struct> a_struct_;
  std::vector<Uint128Struct> b_struct_;
#if HAVE_NATIVE_UINT128
  std::vector<uint128_t> a_native_;
  std::vector<uint128_t> b_native_;
#endif
};

// -----------------------------------------------------------------------------
// main
// -----------------------------------------------------------------------------

int main(int argc, char** argv) {
  size_t size = 100000;
  size_t iterations = 500;

  for (int i = 1; i < argc; i++) {
    if (std::strcmp(argv[i], "--help") == 0 || std::strcmp(argv[i], "-h") == 0) {
      std::cout << "Usage: " << argv[0] << " [options]\n"
                << "Options:\n"
                << "  --size N         Number of 128-bit elements (default: 100000)\n"
                << "  --iterations N   Number of iterations (default: 500)\n"
                << "  --help, -h       Show this help message\n";
      return 0;
    } else if (std::strncmp(argv[i], "--size=", 7) == 0) {
      size = std::strtoull(argv[i] + 7, nullptr, 10);
    } else if (std::strcmp(argv[i], "--size") == 0 && i + 1 < argc) {
      size = std::strtoull(argv[++i], nullptr, 10);
    } else if (std::strncmp(argv[i], "--iterations=", 13) == 0) {
      iterations = std::strtoull(argv[i] + 13, nullptr, 10);
    } else if (std::strcmp(argv[i], "--iterations") == 0 && i + 1 < argc) {
      iterations = std::strtoull(argv[++i], nullptr, 10);
    }
  }

  if (!VerifyImplementations()) {
    std::cerr << "Self-test verification failed!\n";
    return 1;
  }

  Add128Benchmark bench(size, iterations);
  bench.RunAll();

  return 0;
}