C++11快速constexpr整数幂

Question

这里就是在反复强调同一个观点。在C语言中，计算整数次幂的一种典型（且较快）方法如下：

int64_t ipow(int64_t base, int exp){
  int64_t result = 1;
  while(exp){
    if(exp & 1)
      result *= base;
    exp >>= 1;
    base *= base;
  }
  return result;
}

但是我需要一个在编译时计算整数幂的函数，所以我继续使用constexpr实现了一个递归函数：

constexpr int64_t ipow_(int base, int exp){
  return exp > 1 ? ipow_(base, (exp>>1) + (exp&1)) * ipow_(base, exp>>1) : base;
}
constexpr int64_t ipow(int base, int exp){
  return exp < 1 ? 1 : ipow_(base, exp);
}

第二个函数的作用只是以可预测的方式处理小于1的指数。在这种情况下传递exp<0是一个错误。

递归版本要慢4倍

我生成了一个由10E6个随机值为基数和指数组成的向量，并对向量中的两个算法进行计时（之前进行了一次非计时运行以尝试消除任何缓存效应）。没有优化的情况下，递归方法比循环方法快两倍。但是使用-O3（GCC）时，循环方法比递归方法快4倍。

我想问你们的问题是：有人能想出一个更快的ipow()函数，可以处理基数和指数为0的情况，并且可以用作constexpr吗？

（免责声明：我不需要更快的ipow，我只是想看看这里聪明的人能想出什么）。

- Emily L.

---

constexpr函数也可以在运行时进行评估。期望的优化是针对运行时评估的情况。如果递归方法在运行时与循环方法相比速度相当快，则可以在编译时和运行时都使用递归方法，而无需为运行时版本单独定义。请参见@hivert的答案。 - Emily L.

@MikeDunlavey她确实写了一个小程序来完成这个任务：那个ipow函数。;) - Casey

FYI，C++1y在constexpr函数中大幅扩展了您可以执行的操作：详见N3652。您的第一个实现在C++1y中是一个有效的constexpr函数。 - Casey

@MikeDunlavey：正如我在原帖中所说，这个问题纯粹是出于理论/技术兴趣，我并不需要更快的代码。你的回答并不是很建设性。 - Emily L.

重新审视这个问题：现在clang 3.4已经发布并支持c++1y，只需在其声明中添加constexpr关键字，原始函数即可在编译时完美运行。 - Casey

Answer 1

一款优秀的优化编译器可以将尾递归函数转换为与命令式代码一样快速运行。您可以使用pumping将此函数转换为尾递归。GCC 4.8.1编译了这个测试程序：

#include <cstdint>

constexpr int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
}

int64_t foo(int64_t base, int exp) {
  return ipow(base, exp);
}

进入循环（请参见gcc.godbolt.org）：

foo(long, int):
    testl   %esi, %esi
    movl    $1, %eax
    jle .L4
.L3:
    movq    %rax, %rdx
    imulq   %rdi, %rdx
    testb   $1, %sil
    cmovne  %rdx, %rax
    imulq   %rdi, %rdi
    sarl    %esi
    jne .L3
    rep; ret
.L4:
    rep; ret

与 您的 while 循环实现 相比：

ipow(long, int):
    testl   %esi, %esi
    movl    $1, %eax
    je  .L4
.L3:
    movq    %rax, %rdx
    imulq   %rdi, %rdx
    testb   $1, %sil
    cmovne  %rdx, %rax
    imulq   %rdi, %rdi
    sarl    %esi
    jne .L3
    rep; ret
.L4:
    rep; ret

按照指令逐步执行对我来说已经足够好了。

- Casey

---

有趣！我知道尾调用优化可以通过编译器转换为迭代，但我没有预料到它与实际循环的指令一一对应。此外，我可能需要研究一下尾调用优化发生所必需的条件。因为我无法确定为什么它适用于你的 ipow，但不适用于我的。 - Emily L.

尾调用是指在函数调用后直接返回结果，而不对该结果进行任何其他计算。例如，return function(x+2)是一个尾调用，但return 2+function(x)则不是。 - Casey

Answer 2

似乎这是C++中constexpr和模板编程的标准问题。由于编译时间的限制，如果在运行时执行，constexpr版本会比普通版本慢。但重载不允许选择正确的版本。标准化委员会正在解决此问题。例如，参见以下工作文档：http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3583.pdf

- hivert

---

感谢纠正！在我的母语法语中，拼写为“comité”。所以，对于我来说，有两个“m”、“t”和“e”是非常不自然的，而我的拼写检查器却没有问题。 - hivert

区分运行时和编译时对于解决在等效实现之间进行选择的问题并不是必要的。C++14放宽了constexpr函数的要求，允许大多数运行时算法。 - Potatoswatter

等等，我以为它是喜剧？但说真的，主要问题不是constexpr的限制，而是这种限制与允许编译器在运行时评估函数的不健康组合，而程序员无法对此做出太多反应。即使您通过分配给enum来强制进行编译时评估，编译器仍然允许在运行时再次评估后续调用（例如GCC就会这样做！）。这很愚蠢，但完全合法。 - Damon