函数列表和包装 [英] Function tabulation and wrapping
问题描述
我正在使用 C++ 编写的求解器进行 [非常] 与物理相关的密集数值计算.在我的 PC 上运行一次最多可能需要几个小时，而一个需要几十个小时.我发现，如果将平滑函数制表并使用制表值，则几乎可以显着(2-5 倍)减少时间而不会损失准确性.下面的代码说明了我的意思:
I'm doing [very] intense numerical calculations related to physics using solvers written in C++. A single run can take up to few hours on my PC, and one need dozens. I've found that it is possible to significantly (2-5x) decrease the time almost without losing accuracy, if one tabulates smooth functions and uses tabulated values instead. The code below illustrates what do I mean:
main.h
#pragma once
#include <iostream>
#include <chrono>
#include <math.h>
#include <memory>
typedef double(*fnc)(const double T);
//helper function
constexpr uint32_t GetNumOfPoints(const uint32_t _start, const uint32_t _end, const uint32_t _splitParameter)
{
return (_end - _start)*_splitParameter;
}
//================================//
//CPP-style runtime tabulation with member function
class TabulatedArrayRTMember
{
public:
inline TabulatedArrayRTMember(const uint32_t _start, const uint32_t _end, const double _splitParameter, double(_Func)(const double T) ) :
Start{ _start }, End{_end}, SplitParameter{ _splitParameter }, calculatedValues{ new double[GetNumOfPoints(_start,_end,_splitParameter)] }
{
for (auto ii = 0; GetNumOfPoints(Start, End, SplitParameter) > ii; ++ii)
calculatedValues[ii] = _Func((ii + Start) / SplitParameter);
}
inline double GetValue(const double T)
{
return calculatedValues[(int)(T * SplitParameter - Start)];
}
private:
const uint32_t Start;
const uint32_t End;
const double SplitParameter;
std::unique_ptr<double[]> calculatedValues;
};
template<TabulatedArrayRTMember* x>
double callWrapper(const double T)
{
return (*x).GetValue(T);
}
main.cpp
//whatever routine accepting some fnc
double calc(fnc Func)
{
double sum=0.0;
for (auto ii=0u; 1<<27 > ii; ++ii)
sum+=Func(rand() % 100 + 40);
return sum;
}
//original function
constexpr double foo(const double T)
{
return 12. + T;
}
//================================//
//https://stackoverflow.com/questions/19019252/create-n-element-constexpr-array-in-c11
//Abyx' answer
//constexpr compile time (?) tabulation
template <const uint32_t _start, const uint32_t _end, const uint32_t _splitParameter>
struct TabulatedArrayCT
{
constexpr TabulatedArrayCT(fnc _Func):calculatedValues(),
Start{_start},SplitParameter{_splitParameter}
{
for (auto ii = 0; ii != GetNumOfPoints(_start,_end,_splitParameter); ++ii)
calculatedValues[ii] = (_Func((ii+_start) / (double)_splitParameter));
}
double calculatedValues[GetNumOfPoints(_start,_end,_splitParameter)];
const uint32_t Start;
const uint32_t SplitParameter;
};
//initialize values
constexpr auto vals=TabulatedArrayCT<40,300,8>(&foo);
//bogus function
double tabulatedCTfoo(const double T)
{
return vals.calculatedValues[(int)((T-vals.Start) * vals.SplitParameter)];
}
//================================//
//CPP-style runtime tabulation
//struct to keep it together
struct TabulatedArrayRT
{
TabulatedArrayRT(const uint32_t _start, const uint32_t _end, const uint32_t _splitParameter, fnc _Func):
Start{_start},SplitParameter{_splitParameter},calculatedValues{new double[GetNumOfPoints(_start,_end,_splitParameter)]}
{
for (auto ii = 0; ii > GetNumOfPoints(_start,_end,_splitParameter) ; ++ii)
calculatedValues[ii] = (_Func((ii+_start) / (double)_splitParameter));
}
const uint32_t Start;
const uint32_t SplitParameter;
std::unique_ptr<double[]> calculatedValues;
};
//initialize values
auto vals2=TabulatedArrayRT(40,300,8,&foo);
//bogus function
double tabulatedRTfoo(const double T)
{
return vals2.calculatedValues[(int)((T-vals2.Start) * vals2.SplitParameter)];
}
//================================//
//C-style (naive) runtime tabulation
//allocate values
double vals3[GetNumOfPoints(40,300,8)];
//initialize values
void initvals()
{
auto np = GetNumOfPoints(40,300,8);
for (auto ii = 0; ii > np ; ++ii)
vals3[ii] = foo((ii+40.0) / 8.0);
}
//bogus function
double simpleTabulation(const double T)
{
return vals3[(int)((T-40)*8)];
}
//================================//
//initialize class with member function to be wrapped later
auto vals4 = TabulatedArrayRTMember(40, 300, 8, &foo);
int main()
{
auto start = std::chrono::steady_clock::now();
calc(&foo);
auto end = std::chrono::steady_clock::now();
std::cout << "Pristine. Elapsed time in mseconds : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " sec\n";
start = std::chrono::steady_clock::now();
calc(&tabulatedCTfoo);
end = std::chrono::steady_clock::now();
std::cout << "CTT. Elapsed time in mseconds : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " sec\n";
start = std::chrono::steady_clock::now();
calc(&tabulatedRTfoo);
end = std::chrono::steady_clock::now();
std::cout << "RTT. Elapsed time in mseconds : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " sec\n";
start = std::chrono::steady_clock::now();
calc(&simpleTabulation);
end = std::chrono::steady_clock::now();
std::cout << "C-style. Elapsed time in mseconds : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " sec\n";
start = std::chrono::steady_clock::now();
calc(&callWrapper<&vals4>);
end = std::chrono::steady_clock::now();
std::cout << "CPP+helper template style. Elapsed time in mseconds : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " sec\n";
return 0;
}
运行代码，一键搞定
Pristine. Elapsed time in mseconds : 690 sec
CTT. Elapsed time in mseconds : 613 sec
RTT. Elapsed time in mseconds : 628 sec
C-style. Elapsed time in mseconds : 615 sec
CPP+helper template style. Elapsed time in mseconds : 632 sec
我想知道的:
- 编译时制表总是比其他制表快吗?方法?
- 从编程的角度来看，是否存在水下岩石"?
- 是否可以避免使用全局变量来存储值?
- 鉴于我们现在有 20 多个功能，而且还会有更多功能，有没有办法让所有功能都更整洁?
在你问之前:
- 我不能/不允许更改大部分现有代码库以接受除了
double(*)(const double T, const void* params).我能够/允许添加新方法. - 我想避免使用外部库，但这并不严格.
- 代码必须是可移植的(至少可以在带有 i686 架构的 Windows 7-10 和 Ubuntu 16.04-18.04 机器上运行)并且具有合理的可读性/可维护性.
- 我考虑过使用 class(es) + std::bind &std::function，但是当某些东西需要指向原始"函数的指针时，似乎无法将成员函数用作非成员函数.
- I'm not able/allowed to change the most of existing codebase to accept
anything but
double(*)(const double T, const void* params). I'm able/allowed to add new methods. - I would like to avoid external libraries, but this is not strict.
- The code must be portable (to run at least on Windows 7-10 and Ubuntu 16.04-18.04 machines with i686 arch) and reasonably readable/maintanable.
- I considered using class(es) + std::bind & std::function, but it looks like there is no way to use member-function as non-member function when something expects a pointer to a "raw" function.
非常感谢！
编辑 #1:当发现 constexpr 不是根据 C++ 标准接受的 std::exp 定义的一部分时，用更简单的函数替换 foo 函数.然后我会坚持使用运行时制表，因为数学被广泛使用.
Edit #1: Replaced foo function with simpler one, when found that constexpr is not part of the accepted definition of the std::exp according to the C++ standard. I will stick to runtime tabulation then, because math is used extensively.
编辑 #2:添加了使用 n314159 的答案进行呼叫包装的方法.
Edit #2: Added an approach to call wrapping using n314159's answer.
推荐答案
这不是关于您的整个问题的答案，而是讨论将成员函数转换为函数指针.
This is not an answer regarding your whole question but rather will talk about converting member functions to function pointers.
先验这不是一个大问题，如果你允许一个函数 af(b) 被转换为 f(a,b)，那么下面将完美工作:
A priori this is not a great problem, if you allow that a function a.f(b) is converted to f(a,b), then the following will work flawlessly:
template<class X, double (X::* f)(const double)>
double easy(X &x, const double t) {
return (x.*f)(t);
}
但是您想从函数签名中消除调用对象，而函数仍然依赖于该对象.这就是为什么您需要全局对象的原因(而且我认为没有办法在某些地方必须依赖这些对象).对于他们，您可以执行以下操作:
But you want to eliminate the calling object from the function signature while the function still depends on the object. That is why you need the global objects (and I do not see a way without, somewhere the dependance on these objects has to be). For them you can do something like this:
#include <iostream>
typedef double(*fnc)(const double T);
double calc(fnc Func){
return Func(0.0);
}
struct S {
double f(const double T) {
return d;
}
double d;
};
static S s{3.0};
template<class X, X* x, double (X::* f) (const double)>
double helper(const double T) {
return (*x).f(T);
}
int main() {
std::cout << helper<S, &s, &S::f>(0.0) << '\n';
std::cout << calc(&helper<S, &s, &S::f>) << '\n';
}
所以我们需要用模板中的依赖替换函数签名中的依赖.请注意，您只能使用指向 s 的指针作为模板参数，因为它是静态的，因此它的地址(基本上)在编译时是已知的.
So we need replace the dependence in the function signature by a dependence in templating. Note that you can only use a pointer to s as template parameter, since it is static, so its address is (basically) known at compile time.
这篇关于函数列表和包装的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
