常量数组声明的最佳位置

Question

在尝试编写运行时计算的最快的阶乘函数时，我发现自己怀疑在函数级别还是在单元级别声明常量数组f[]是一个好主意。

#include <stdint.h>
#include <cassert>  
// uint64_t const f[21] = { 1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000 };
const uint64_t factorial(const uint8_t n) {
static uint64_t const f[21] = { 1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000 };
assert(n <= 20);
return f[n];
}

假设f[]将仅由factorial()函数使用，每种放置的优缺点是什么?

是在函数级别声明的常量，每次执行函数时创建和销毁，就像非const变量一样，还是链接器在编译时收集并将所有常量放在.rodata节中?

Answer 1

依我拙见，最好是让编译器决定并使用constexpr做所有事情。编译器会为你做出最好的决定。

由于一个无符号64位值的阶乘数非常少(21)，编译时数组将主要使用21*8 = 168字节。

168字节

这个数字很低，我们可以很容易地构建一个编译时constexpr std::array，并停止所有进一步的考虑。

实际上一切都可以在编译时完成。

首先将计算阶乘的默认方法定义为constexpr函数:

constexpr unsigned long long factorial(unsigned long long n) noexcept {
return n == 0ull ? 1 : n * factorial(n - 1ull);
}

这样，在编译时可以很容易地计算阶乘。然后，我们用所有阶乘填充std::array。我们也使用一个constexpr，并使它成为一个模板，带有可变参数包。

我们使用std::integer_sequence创建索引0、1、2、3、4、5的阶乘，....

这很简单，也不复杂:

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
return std::array<unsigned long long, sizeof...(ManyIndices)>{ { factorial(ManyIndices)... } };
};

这个函数将被输入一个整数序列0,1,2,3,4，…并返回具有相应阶乘的std::array<unsigned long long, ...>。

我们知道最多可以存储21个值。因此，我们创建下一个函数，它将调用上面的整数序列1,2,3,4，…，20,21，像这样:

constexpr auto generateArray()noexcept {
return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

现在，最后，

constexpr auto Factorial = generateArray();

将为我们提供一个编译时的std::array<unsigned long long, 21>，其名称Factorial包含所有阶乘。如果我们需要第i个阶乘，那么我们可以简单地写Factorial[i]。运行时将不进行计算。

我不认为有更快的方法来计算阶乘。

请参阅下面的完整程序:

#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the below will be calculated at compile time
// constexpr factorial function
constexpr unsigned long long factorial(unsigned long long n) noexcept {
return n == 0ull ? 1 : n * factorial(n - 1ull);
}
// We will automatically build an array of factorials at compile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
return std::array<unsigned long long, sizeof...(ManyIndices)>{ { factorial(ManyIndices)... } };
};
// Max index for factorials for an 64bit unsigned value 
constexpr size_t MaxIndexFor64BitValue = 21;
// Generate the required number of elements
constexpr auto generateArray()noexcept {
return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}
// This is an constexpr array of all factorials numbers
constexpr auto Factorial = generateArray();
// All the above was compile time
// ----------------------------------------------------------------------
// Test function
int main() {
for (size_t i{}; i < MaxIndexFor64BitValue; ++i)
std::cout << i << 't' << Factorial[i] << 'n';
return 0;
}

使用Microsoft Visual Studio Community 2019, Version 16.8.2开发、编译、测试

使用gcc 10.2和clang 11.0.1进行编译和测试

语言:C + + 17