运行时的动态函数解析

Dynamic function resolution at runtime

我的项目需要在运行时加载很多模块,每个模块包含很多函数,其形式类似于下面的伪代码:

void someFunction(Context &ctx) {
    bool result;
    result = ctx.call("someFunction2")(ctx.arg["arg1"], ctx.arg["arg2"])
             && ctx.call("someFunction3")(ctx.arg["arg1"], ctx.arg["arg3"]);
    ctx.result(result);
} 

其中 ctx.arg["arg1"]ctx.arg["arg2"]ctx.arg["arg3"] 是在运行时传递给 someFunction 的参数。 someFunction2someFunction3 无法在编译时静态解析,但在加载所有模块时会在运行时知道(它们是否已在其他模块中定义)。

现在,一个简单的实现是使用散列映射来存储所有这些函数的函数句柄,但是散列会很慢,因为通常有 10k 个函数要搜索并且 每个函数将在其他函数中多次调用(例如:枚举参数以找到将产生所需结果的正确组合)。

因此,我正在寻找某种解决方案,它将在加载所有模块时对这些 "ctx.call" 执行一次性替换,而不是每次都执行 "hash-and-probe"。当前的主要问题是 "replacing" 操作。我想出了一些想法,但并不完美:


第一个解决方案:创建一个内部函数 inner_func(func_handle1, func_handle2, arg1, arg2, arg3),并使用 std::bind 创建一个外部包装器 outer_wrapper()

问题:用户不友好,必须明确告诉上下文要查找哪些函数和参数。


第二个解决方案:使用元编程+constexpr+宏来自动计算函数和参数名称引用,然后创建一个引用table,然后让上下文在运行时填充每个table。

问题:我无法解决,需要一些帮助。我已经从 facebook 阅读了 Fatal 库的文档,从 boost 阅读了 mpl 和 hana,但似乎没有一个干净的方法来做到这一点。


第三种解决方案:使用 JIT 编译器

问题:C++ JIT 编译器选择有限。 NativeJIT 不够强大,easy::JIT 似乎不可定制且不易分发。 asmjit 不可用。


PS:问题上下文是"automated planners",这些函数用于构造谓词。 Context ctx只是一个例子,如果需要你可以使用其他合适的语法,只要它们易于被用来表示下面的lisp表达式:

(and (at ?p ?c1)
(aircraft ?a)
(at ?a ?c3)
(different ?c1 ?c3))

PPS:更具体地说,我正在考虑如下内容:

用户将定义如下所示的函数:

void module_init() {
    FUNC ("someFunction")("p", "a", "c1", "c3") (
        bool result;
        result = CALL("at")("p", "c1") 
                 && CALL("aircraft")("a")
                 && CALL("at")("a", "c3")
                 && CALL("different")("c1", "c3")

        /// Users should also be able to access arguments as a "Variable" 
        /// class using ARG["p"]
        return result;
    )
}

然后通过某种方式,FUNC() 将被转换为类似于以下的函子:

struct func_someFunction {
    some_vector<std::function<bool()>> functions;
    some_vector<Variable*> args;
    some_vector<std::string> func_name;
    some_vector<std::string> arg_name;

    bool operator()() {
       /// above representation of Func(), but function and args are pointers in "functions" and "args"
    }
}

然后当所有模块都加载完成后,系统会读取func_namearg_name,并分别填充相应的函数指针和变量指针到functionsargs

状态:先用hashmap,完成后我会post更新

状态:自己想出了一个解决方案,还测试了哈希实现,post编辑如下。

如有任何想法,我们将不胜感激。谢谢!

Now, a naive implementation would be using a hash map to store a function handle to all of these functions, but hashing would be slow as there are typically 10k functions to search for [...]

哈希表的查找成本为 O(1)。您是否尝试过针对此问题的这种广泛使用的解决方案并进行了性能分析?您是否尝试过使用不同的散列算法来减少散列时间和冲突?

如果您需要在整个程序生命周期中根据 运行time 字符串键不断找到 运行 的正确函数,那么使用哈希映射是没有办法的。 (保罗的回答)

但是,如果您在 运行 时间初始化一个函数列表,并且在程序持续时间内不会更改(即您不需要在初始阶段后执行任何 "find" 操作),那么您可以将这些函数放在一个连续的容器中(例如 std::vector)以改善访问时间和缓存利用率:

// getFuncNames is where you are deciding on the list of functions to run
// funcs is a vector of function handles
// funcMap is a hash map of function names to function handles
for (auto& funcName : getFuncNames())
{
    funcs.push_back(funcMap.at(funcName));
}

这可能有点矫枉过正,但可能是一个有用的想法:

  1. 使用字符串驻留来确保每个 MyString("aircraft") 产生相同的对象。当然,这意味着你的字符串必须是 immutable.

  2. 将创建的每个字符串对象与高质量随机数 (uint64_t) 相关联并将其用作该字符串的 "hash".

由于 "hash" 与字符串一起存储,因此对 "compute" 进行简单的内存加载。并且由于您使用良好的 PRNG 来生成 "hash",它作为散列 table.

的键表现出色

只要将 std::string 转换为内部字符串对象,您仍然需要计算经典哈希以在现有字符串对象的 table 中找到 MyString 对象,但这这是一次性的工作,可以在词法分析器处理配置文件或加载模块时完成。字符串与其各自函数实现等的实际匹配将与经典哈希的计算分离。

好的,所以我自己想出了一个解决方案,接近我问题中的第一个解决方案,我做了一个非常简单的问题示例,发布在github上,下面是link :

Demonstration using hash table and pointer respectively

注意:本方案只是一个简单的演示,并未进行优化。进一步可能的优化包括:

  1. 对于hash map方法,string interning可以减少string构造开销,如Konrad Rudolph and cmaster - reinstate monica所建议,会导致中等(与指针相比降低约 50%)性能下降,但消除了动态字符串创建开销并减少了内存消耗。 boost::flyweight 是个不错的选择。

  2. 对于哈希映射方法,我只是使用 std::unordered_map 实现了演示,但存在更好的替代方法,包括 google::dense_hash_maptsl::hop_scotch_map 等,它们是值得一试,但根据 Tessil's benchmark,我怀疑他们的 O(s)(其中 s 是平均字符串长度)每次搜索的时间复杂度可能比 O(1) 指针访问更快。

  3. 在我的场景中,所有函数都可以在模块加载阶段之后找到,但是,您可能想要涵盖场景,例如 python 中的符号查找,然后 [=74] =]hashmap 会更好,除非您为您的 senario 引入更多约束或定期更新已解析的指针。如果要大规模插入和删除内容,Trie 数据结构可能是一个不错的选择。

废话少说,下面是结果和解决方案:


性能

基准:布尔和数字混合 SAT 问题的 1.28e8 种可能组合

平台:i7 6700HQ,单线程

cmake-build-debug/test_ptr  0.70s user 0.00s system 99% cpu 0.697 total
cmake-build-debug/test_hash  4.24s user 0.00s system 99% cpu 4.241 total

来自 perf 的热点和函数运行时:

test_ptr:

  53.17%  test_ptr  test_ptr       [.] main
  35.38%  test_ptr  test_ptr       [.] module_1_init(Domain&)::__internal_func_some_circuit::operator()
   8.02%  test_ptr  test_ptr       [.] module_2_init(Domain&)::__internal_func_and_circuit::operator()
   1.90%  test_ptr  test_ptr       [.] module_2_init(Domain&)::__internal_func_or_circuit::operator()
   0.18%  test_ptr  libc-2.23.so   [.] _int_malloc
   0.15%  test_ptr  ld-2.23.so     [.] do_lookup_x
   0.15%  test_ptr  test_ptr       [.] module_2_init(Domain&)::__internal_func_xor_circuit::operator()

test_hash:

  33.11%  test_hash  test_hash            [.] Domain::call<char const (&) [11], Domain::Variable&, Domain::Variable&>
  25.37%  test_hash  test_hash            [.] main
  21.46%  test_hash  libstdc++.so.6.0.26  [.] std::_Hash_bytes
   5.10%  test_hash  libc-2.23.so         [.] __memcmp_sse4_1
   4.64%  test_hash  test_hash            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_construct<char const*>
   3.41%  test_hash  test_hash            [.] module_1_init(Domain&)::__internal_func_some_circuit::operator()
   1.86%  test_hash  libc-2.23.so         [.] strlen
   1.44%  test_hash  test_hash            [.] module_2_init(Domain&)::__internal_func_and_circuit::operator()
   1.39%  test_hash  libc-2.23.so         [.] __memcpy_avx_unaligned
   0.55%  test_hash  test_hash            [.] std::_Hash_bytes@plt

hashmap 实现具有非常高的开销,来自重复的哈希和函数查找。


解决方案

大量使用宏来使用户更容易定义函数(谓词):

in test_ptr:

void module_1_init(Domain &d) {
    FUNC(some_circuit, d,
         DEP(and_circuit, or_circuit, xor_circuit, not_circuit),
         ARG(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10),
         BODY(
             return CALL(and_circuit, a1, a2)
                 && CALL(or_circuit, a3, a4)
                 && CALL(xor_circuit, a5, a6)
                 && CALL(not_circuit, a7)
                 && a8.value >= R1 && a9.value >= R2 && a10.value >= R3;
         )
    );
}
in test_hash:

void module_1_init(Domain &d) {
    FUNC(some_circuit, d,\
         ARG(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10), \
         BODY(
             return CALL(and_circuit, a1, a2)
                 && CALL(or_circuit, a3, a4)
                 && CALL(xor_circuit, a5, a6)
                 && CALL(not_circuit, a7)
                 && a8.value >= R1 && a9.value >= R2 && a10.value >= R3;
         )
    );
}

主要区别在于指针解决方案中的DEP()宏,DEP()将显式指定依赖函数,并构造一个局部函数指针table。

下面是宏展开后实际生成的代码:

in test_ptr:

void module_1_init(Domain &d) {
    class __internal_func_some_circuit : public Domain::Function { 
    public: 
        enum func_dep_idx { 
            and_circuit, 
            or_circuit, 
            xor_circuit, 
            not_circuit, 
            __func_dep_idx_end }; 
    Domain::Variable a1; 
    Domain::Variable a2;
    ...
    Domain::Variable a10; 
    explicit __internal_func_some_circuit(Domain &d) : 
    a1(), a2(), a3(), a4(), a5(), a6(), a7(), a8(), a9(), a10(),
    Domain::Function(d) { 
        arg_map = {{"a1", &a1}, {"a2", &a2}, {"a3", &a3} ..., {"a10", &a10}}; 
        arg_pack = { &a1, &a2, &a3, &a4, &a5, &a6, &a7, &a8, &a9, &a10}; 
        func_dep_map = {{"and_circuit", func_dep_idx::and_circuit}, 
                        {"or_circuit", func_dep_idx::or_circuit},
                        {"xor_circuit", func_dep_idx::xor_circuit} , 
                        {"not_circuit", func_dep_idx::not_circuit}}; 
        func_dep.resize(__func_dep_idx_end); 
    } 

    bool operator()() override { 
        return func_dep[func_dep_idx::and_circuit]->call(a1, a2) && 
               func_dep[func_dep_idx::or_circuit]->call(a3, a4) && 
               func_dep[func_dep_idx::xor_circuit]->call(a5, a6) && 
               func_dep[func_dep_idx::not_circuit]->call(a7) && 
               a8.value >= 100 && a9.value >= 100 && a10.value >= 100; 
    } 
}; 
d.registerFunction("some_circuit", new __internal_func_some_circuit(d))
in test_hash:

class __internal_func_some_circuit : public Domain::Function { 
public: 
    Domain::Variable a1; 
    Domain::Variable a2; 
    ...
    Domain::Variable a10; 
    explicit __internal_func_some_circuit(Domain &d) : 
    a1() , a2(), a3(), a4(), a5(), a6(), a7(), a8(), a9(), a10(), 
    Domain::Function(d) { 
        arg_map = {{"a1", &a1}, {"a2", &a2} ..., {"a10", &a10}}; 
        arg_pack = {&a1, &a2, &a3, &a4, &a5, &a6, &a7, &a8, &a9, &a10}; 
    } 

    bool operator()() override { 
        return domain.call("and_circuit", a1, a2) && 
               domain.call("or_circuit", a3, a4) && 
               domain.call("xor_circuit", a5, a6) && 
               domain.call("not_circuit", a7) && 
               a8.value >= 100 && a9.value >= 100 && a10.value >= 100; } 
}; 
d.registerFunction("some_circuit", new __internal_func_some_circuit(d))

基本上,指针解决方案创建了一个函数查找 table func_dep_map,稍后 Domain class 将使用它来搜索由 table class 所依赖的其他函数这个函数,以及一个函数指针向量 func_dep,将用它们的指针填充。

enum用于提供一种优雅简洁的索引查找方式,而不是使用Fatal和[=96=等元编程库提供的mapclasses,它们是在这种情况下不方便使用。

此实现严重依赖 boost::preprocessor,要查看更多详细信息,请参阅我的 github 存储库。