如何高效实现__int128与GMP库mpz_class/mpz_t的加法？

在g++环境下，需要实现128位无符号整数unsigned __int128（别名tw_limb_t）与GMP库mpz_class的加法操作：

typedef unsigned __int128 tw_limb_t;

mpz_class a = "1234567890123456789012345678901234567890";
tw_limb_t b = ...;
a += b;

当前实现通过先将__int128转换为mpz_class再执行加法，但性能表现不佳：

typedef unsigned __int128 tw_limb_t;

inline mpz_class& operator+=(mpz_class &lhs, const tw_limb_t &rhs) {
    if (sizeof(tw_limb_t) != 2 * sizeof(mp_limb_t)) {
        throw std::runtime_error("sizeof(tw_limb_t) is not twice sizeof(mp_limb_t)");
    }

    const int LIMB_BITLEN = sizeof(mp_limb_t) * 8;

    mpz_class rhs_mpz = (mp_limb_t) (rhs >> LIMB_BITLEN);
    rhs_mpz <<= LIMB_BITLEN;
    rhs_mpz += (mp_limb_t) rhs;

    lhs += rhs_mpz;

    return lhs;
}

如何提升该操作的性能？

1. 直接操作GMP底层limb数组，避免临时对象开销 #

GMP的mpz_class底层基于mpz_t结构，其中包含指向limb数组的指针。我们可以直接将__int128拆分为两个mp_limb_t，调用GMP的底层多精度加法函数（如mpn_add_1）完成操作，完全避免创建临时mpz_class或mpz_t对象，这是性能提升最显著的方式。

示例代码：

#include <gmp.h>
#include <stdexcept>

typedef unsigned __int128 tw_limb_t;

inline __attribute__((always_inline)) mpz_class& operator+=(mpz_class& lhs, const tw_limb_t& rhs) {
    // 编译期检查大小匹配，避免运行时开销
    static_assert(sizeof(tw_limb_t) == 2 * sizeof(mp_limb_t), 
                  "tw_limb_t must be exactly two mp_limb_t in size");

    mpz_t& lhs_mpz = lhs.get_mpz_t();
    const mp_limb_t rhs_low = static_cast<mp_limb_t>(rhs);
    const mp_limb_t rhs_high = static_cast<mp_limb_t>(rhs >> (sizeof(mp_limb_t) * 8));

    mp_size_t lhs_size = mpz_size(lhs_mpz);
    // 确保limb数组有足够空间存储结果
    mp_limb_t* lhs_limbs = mpz_limbs_write(lhs_mpz, std::max(lhs_size, static_cast<mp_size_t>(2)));

    // 先加低limb，获取进位
    mp_limb_t carry = mpn_add_1(lhs_limbs, lhs_limbs, lhs_size, rhs_low);

    // 处理高limb及进位
    if (carry != 0 || lhs_size < 2) {
        if (lhs_size >= 2) {
            carry = mpn_add_1(lhs_limbs + 1, lhs_limbs + 1, lhs_size - 1, rhs_high + carry);
        } else {
            lhs_limbs[1] = rhs_high + carry;
            carry = 0;
        }
    } else {
        carry = mpn_add_1(lhs_limbs + 1, lhs_limbs + 1, lhs_size - 1, rhs_high);
    }

    // 处理最终进位，更新mpz_t的大小
    if (carry != 0) {
        lhs_limbs[lhs_size] = carry;
        mpz_limbs_finish(lhs_mpz, lhs_size + 1);
    } else {
        mpz_limbs_finish(lhs_mpz, std::max(lhs_size, static_cast<mp_size_t>(2)));
    }

    return lhs;
}

2. 用GMP单limb加法函数简化操作（次优但更易维护） #

如果不想直接操作底层limb数组，可以利用GMP的mpz_add_ui（单limb加法）和位运算，减少临时对象的创建开销。这种方式比原代码高效，同时代码更简洁：

typedef unsigned __int128 tw_limb_t;

inline __attribute__((always_inline)) mpz_class& operator+=(mpz_class& lhs, const tw_limb_t& rhs) {
    static_assert(sizeof(tw_limb_t) == 2 * sizeof(mp_limb_t), 
                  "tw_limb_t must be two mp_limb_t in size");

    const int LIMB_BITS = sizeof(mp_limb_t) * 8;
    mp_limb_t low = static_cast<mp_limb_t>(rhs);
    mp_limb_t high = static_cast<mp_limb_t>(rhs >> LIMB_BITS);

    // 先加低limb
    mpz_add_ui(lhs.get_mpz_t(), lhs.get_mpz_t(), low);
    // 将高limb左移对应位数后加到结果中
    mpz_t high_mpz;
    mpz_init_set_ui(high_mpz, high);
    mpz_mul_2exp(high_mpz, high_mpz, LIMB_BITS);
    mpz_add(lhs.get_mpz_t(), lhs.get_mpz_t(), high_mpz);
    mpz_clear(high_mpz);

    return lhs;
}

3. 编译期替代运行时检查 #

原代码中用运行时if检查sizeof匹配，改用static_assert可以在编译期就验证平台兼容性，避免运行时的分支和异常抛出开销，因为目标平台的limb大小是固定的，编译期即可确定。

4. 强制内联减少函数调用开销 #

在g++中，除了inline关键字，添加__attribute__((always_inline))可以强制编译器内联该函数，消除函数调用的栈帧开销，进一步提升性能。

内容的提问来源于stack exchange，提问作者Daniel S.