Время компиляции сгенерированного диспетчера функций с минимальными издержками
Я пытаюсь реализовать быстрый диспетчер функций, используя сгенерированные во время компиляции массивы, чтобы иметь возможность использовать его во время выполнения в 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, но любая идея приветствуется
[Edit] Мне известны метки как расширение языка значений GCC. С теми, кого я, возможно, смог бы достичь своей цели, но мне нужно портативное решение.Решение
Ну, я не знаю, сможете ли вы сделать то, что вы хотите. Создайте код, который создает идеальную хэш-функцию для любой ввод кажется мне довольно … не выполнимым.
В любом случае, вот простое решение для написания кода. Это 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
Решение может быть улучшено для выполнения бинарного поиска, но оно не является тривиальным.
Другие решения
Основываясь на ответе @ bolov, можно использовать произвольный алгоритм отправки, когда i не является константой при изменении:
constexpr auto execute(int i)
{
(execute_if<Is>(i), ...);
}
Для того, чтобы:
constexpr auto execute(unsigned i)
{
(execute_if<Is>(i), ...);
}
И затем добавление:
constexpr auto execute (int& i)
{
// Add arbitrary dispatch mechanism here
}
Полный пример, совместимый с C ++ 11 и довольно неуклюжий std::map (сложность журнала наихудшего случая n), когда i не является константой (я бросил constexpr вещи, которые облегчают жизнь в C ++ 11):
#include <map>
#include <iostream>
std::map <int, void (*) ()> map;
template <int i> void f ();
template <> void f <1> () { std::cout << "f1\n"; }
template <> void f <2> () { std::cout << "f2\n"; }
template <> void f <3> () { std::cout << "f3\n"; }
template <> void f <4> () { std::cout << "f4\n"; }
template <> void f <5> () { std::cout << "f5\n"; }
template <int ... Is>
struct Dispatcher
{
template <int first> void execute_if (int i)
{
if (first == i)
{
std::cout << "Execute f" << i << " via template\n";
f <first> ();
}
}
template <int first, int second, int... rest> void execute_if (int i)
{
if (first == i)
{
std::cout << "Execute f" << i << " via template\n";
f <first> ();
}
else
execute_if <second, rest...> (i);
}
void execute (unsigned i)
{
execute_if <Is...> (i);
}
void execute (int& i)
{
std::cout << "Execute f" << i << " via map\n";
map.at (i) ();
}
};
int main()
{
map [1] = f <1>;
map [2] = f <2>;
map [3] = f <3>;
map [4] = f <4>;
map [5] = f <5>;
Dispatcher <1, 2, 4> dispatcher;
dispatcher.execute (2);
int i = 4;
dispatcher.execute (i);
}
Выход:
Execute f2 via template
f2
Execute f4 via map
f4
редактировать: согласно запросу OP, вот версия, использующая бинарный поиск вместо std::map, Ключом к этому является создание массива для поиска в Dispatcher конструктор.
#include <vector>
#include <iostream>
template <int i> void f ();
template <> void f <1> () { std::cout << "f1\n"; }
template <> void f <2> () { std::cout << "f2\n"; }
template <> void f <3> () { std::cout << "f3\n"; }
template <> void f <4> () { std::cout << "f4\n"; }
template <> void f <5> () { std::cout << "f5\n"; }
using ve = std::pair <int, void (*) ()>;
template <int ... Is>
struct Dispatcher
{
template <int first> void execute_if (int i)
{
if (first == i)
{
std::cout << "Execute f" << i << " via template\n";
f <first> ();
}
}
template <int first, int second, int... rest> void execute_if (int i)
{
if (first == i)
{
std::cout << "Execute f" << i << " via template\n";
f <first> ();
}
else
execute_if <second, rest...> (i);
}
void execute (unsigned i)
{
execute_if <Is...> (i);
}
void execute (int& i)
{
std::cout << "Execute f" << i << " via binary search\n";
auto lb = lower_bound (indexes.begin (), indexes.end (), ve (i, nullptr),
[] (ve p1, ve p2) { return p1.first < p2.first; });
if (lb != indexes.end () && lb->first == i)
lb->second ();
}
template <int first> void append_index ()
{
indexes.emplace_back (ve (first, f <first>));
}
template <int first, int second, int... rest> void append_index ()
{
append_index <first> ();
append_index <second, rest...> ();
}
Dispatcher ()
{
append_index <Is...> ();
}
private:
std::vector <ve> indexes;
};
int main()
{
Dispatcher <1, 2, 4> dispatcher;
dispatcher.execute (2);
int i = 4;
dispatcher.execute (i);
}
ОП попросил C ++ 11 решение, которое поддерживает constexpres, следуя примеру решения Болова.
Ну … нет, если это хорошая идея, потому что constexpr Функция / член в C ++ 11 должна быть рекурсивной и возвращать значение. И компиляторы накладывают строгие ограничения на рекурсию шаблона, и это может быть проблемой, если N ( sizeof...(Is)) в приоритете.
Во всяком случае … лучшее, что я могу себе представить, это следующее
template <int... Is>
struct Dispatcher
{
template <typename = void>
constexpr int execute_h (int) const
{ /* wrong case; exception? */ return -1; }
template <int J0, int ... Js>
constexpr int execute_h (int i) const
{ return J0 == i ? (f<J0>(), 0) : execute_h<Js...>(i); }
constexpr int execute (int i) const
{ return execute_h<Is...>(i); }
};
которые могут быть использованы, вычисляя f<>() время компиляции, следующим образом
void test()
{
constexpr Dispatcher<1,5,100,300> dispatcher;
constexpr auto val1 = dispatcher.execute(5);
constexpr auto val2 = dispatcher.execute(6);
std::cout << val1 << std::endl; // print 0 (5 is in the list)
std::cout << val2 << std::endl; // print -1 (6 isn't in the list)
}
также f<>() должно быть constexpr и в C ++ 11 не может вернуться void; Я использовал следующее
template <int i>
constexpr int f ()
{ return i; }
Небольшое улучшение (ИМХО) для решения Болова
Пишу execute_if возвращать true, когда f<I>() выполняется или false, иначе
template <int I>
constexpr auto execute_if (int i) const
{ return I == i ? f<I>(), true : false; }
вместо использования оператора запятой для свертывания шаблона
template <int ... Is>
constexpr auto execute(int i) const
{ (execute_if<Is>(i), ...); }
мы можем использовать или (||) оператор
template <int ... Is>
constexpr auto execute(int i) const
{ (execute_if<Is>(i) || ...); }
Используя запятую, execute_is<Is>(i) призван навсегда Isтакже когда первый Is равно i; с использованием || у нас короткое замыкание, то есть execute_is<Is>(i) называется только до тех пор, пока мы не получим Is это равно i,