c++ - 10 的幂的表查找

Question

我正在从事一个计算速度至关重要的 C++ 项目。任何时候我可以削减，应该被削减。可执行文件的最终大小和内存使用情况并不重要。

话虽如此，创建一个预先计算的 10 次方查找表是否有益？例如，如果我有这个简化的功能:

double powTen(int exponent) {
    return pow(10, exponent);
}

如果我将 pow() 替换为表查找，性能会有(小的)提升吗？值得吗？ pow() 函数似乎相当复杂。还有，GCC有没有专门针对这个优化？

Answer 1

表查找几乎总是有利于提高性能。因此，假设您已将此确定为瓶颈，我会花时间实现生成表格的模板。但是，请进行测量。性能是现代计算机上的怪兽。它可以朝着人们从未相信的方向发展。

我预计实现编译时间表生成的时间确实很短。但事实证明，至少从旧更新 2 开始，Visual C++ 2015 对 constexpr std::array 一点都不满意。在一个类(class)。然而，最后，原始数组起作用了。

代码，使用 MinGW g++ 6.3.0 和 Visual C++ 2015 update 2 编译:

#include <stddef.h>     // size_t, ptrdiff_t
#include <utility>      // std::(make_index_sequence, )

namespace my {
    using std::make_index_sequence;
    using std::index_sequence;

    using Size = ptrdiff_t;

    template< Size n, class Item >
    using raw_array_of_ = Item[n];

    template< class Item, size_t n >
    constexpr
    auto n_items_of( raw_array_of_<n, Item>& )
        -> Size
    { return n; }

    namespace impl {
        constexpr
        auto compile_time_pow_of_10( int const n )
            -> double
        { return (n == 0? 1.0 : 10.0*compile_time_pow_of_10( n - 1 )); }

        template< size_t... indices >
        struct Powers_of_10_
        {
            static constexpr size_t                     n       = sizeof...(indices);
            static constexpr raw_array_of_<n, double>   table   =
            {
                compile_time_pow_of_10( indices )...
            };

            constexpr
            Powers_of_10_() {}
        };

        template< size_t... indices >
        constexpr
        raw_array_of_<Powers_of_10_<indices...>::n, double>
            Powers_of_10_<indices...>::table;

        template< size_t... indices, int n = sizeof...(indices) >
        constexpr
        auto power_of_10_table_helper( index_sequence<indices...> )
            -> const raw_array_of_<n, double>&
        { return Powers_of_10_<indices...>::table; }
    }  // namespace impl

    template< int n >
    constexpr
    auto power_of_10_table()
        -> const raw_array_of_<n, double>&
    { return impl::power_of_10_table_helper( make_index_sequence<n>() ); }

}  // namespace my

#include <iostream>
using namespace std;
auto main()
    -> int
{
    int const n = 7;
    constexpr auto& pow_10 = my::power_of_10_table<n>();

    cout << n << " powers of 10:\n";
    cout << fixed;  cout.precision( 0 );
    for( int i = 0; i < n; ++i )
    {
        cout << pow_10[i] << "\n";
    }
}

---

模板代码可能难以移植。即:Visual C++ 2015拒绝接受std::array在上面的代码中，需要重写以使用原始数组。它也很难维护，因为编译诊断通常过于冗长和神秘。

可以通过将幂表示为 x^{(2n/支持>) 。例如，x42 = x32⋅x8⋅x2，以及 x 的这些更基本的幂，即 2、8 和 32，可以通过重复平方计算x。这将乘法次数从指数中的线性减少到指数中的对数。}

代码:

#include <stddef.h>     // size_t, ptrdiff_t

namespace my {
    using Size = ptrdiff_t;

    template< Size n, class Item >
    using raw_array_of_ = Item[n];

    namespace impl {
        auto positive_integral_power_of( const double x, const int n )
        {
            double result = 1.0;
            double power = x;
            for( unsigned exp = n; ; )
            {
                if( (exp & 1) != 0 )
                {
                    result *= power;
                }
                exp >>= 1;
                if( exp == 0 )
                {
                    break;
                }
                power *= power;
            }
            return result;
        }
    }  // namespace impl

    auto integral_power_of( const double x, const int n )
        -> double
    {
        return
            n > 0? 
                impl::positive_integral_power_of( x, n ) :
            n < 0?
                1.0 / impl::positive_integral_power_of( x, -n ) :
            1.0;
    }
}  // namespace my

#include <iostream>
using namespace std;
auto main()
    -> int
{
    int const n = 7;
    cout << n << " powers of 10:\n";
    cout << fixed;  cout.precision( 0 );
    for( int i = 0; i < n; ++i )
    {
        cout << my::integral_power_of( 10, i ) << "\n";
    }
}