c++ - 以最小的开销编译时生成函数调度程序

Question

我正在尝试使用编译时生成的数组来实现一个快速函数调度程序，以便能够在 O(1) 的运行时使用它。

一些代码行只是为了澄清:

template<int i>
void f()
  {
  // do stuff 
  }

// specialized for every managed integer 
template<>
void f<1>
{
// do stuff
}

Dispatcher<1,5,100,300> dispatcher;  
dispatcher.execute(5); // this should call f<5>()

我们称 N 为调度程序的输入数(在本例中为 4)，M 为调度程序输入的最大值(在本例中为 300)。

我已经能够创建一个大小等于 M 的数组。这利用了这样一个事实，即在运行时你可以做类似的事情:

dispatcher.execute(5) -> internalArray[5]();

这当然可行，但是对于大维度的数组是不可行的。

最好的办法是只生成一个包含 N 个元素的数组，然后使用一些数学技巧将输入索引转换为第二个数组的索引。

在示例中，将 1,5,100,300 分别转换为 0,1,2,3。我已经能够做一种预处理方法来转换它们，但我正在寻找一种方法来避免这一步。

换句话说，我认为我正在寻找某种可以在编译时以非常有效的方式针对我的特定情况使用的最小完美哈希(理想情况下没有任何开销，例如:goto: MyInstruction)。

我不是在寻找使用虚函数、std::map 或复杂操作的替代方案。

有什么不明白的请追问。

PS 我正在使用 C++11，但欢迎任何想法

[编辑] 我知道标签是 GCC 的值语言扩展。有了这些，我也许能够实现我的目标，但需要一个可移植解决方案。

Answer 1

嗯，我不知道你是否能够做你想做的事。编写一个代码，为任何输入创建一个完美的散列函数，在我看来很漂亮......不可行。

无论如何，这是编写代码的简单解决方案。它是 C++17，但可以通过一些技巧使其与 C++11 一起工作。

template<int i> void f();

template <int... Is>
struct Dispatcher
{
    template <int I> constexpr auto execute_if(int i)
    {
        if  (I == i)
            f<I>();
    }

    constexpr auto execute(int i)
    {
        (execute_if<Is>(i), ...);
    }
};

auto test()
{
    Dispatcher<1,5,100,300> dispatcher;  
    dispatcher.execute(5);
}

上面的代码转换为一个简单的跳转，因为 5 是一个编译时间常量:

test():                               # @test()
        jmp     void f<5>()            # TAILCALL

如果参数是一个运行时变量，那么它会进行一系列比较:

auto test(int i)
{
    Dispatcher<1,5,100,300> dispatcher;  
    dispatcher.execute(i);
}

test(int):                               # @test(int)
        cmp     edi, 99
        jg      .LBB0_4
        cmp     edi, 1
        je      .LBB0_7
        cmp     edi, 5
        jne     .LBB0_9
        jmp     void f<5>()            # TAILCALL
.LBB0_4:
        cmp     edi, 100
        je      .LBB0_8
        cmp     edi, 300
        jne     .LBB0_9
        jmp     void f<300>()          # TAILCALL
.LBB0_9:
        ret
.LBB0_7:
        jmp     void f<1>()            # TAILCALL
.LBB0_8:
        jmp     void f<100>()          # TAILCALL

解决方案可以改进以执行二分搜索，但这并不简单。