Диспетчер сгенерированных по времени компиляции с минимальными издержками - PullRequest
Новая
       45

Диспетчер сгенерированных по времени компиляции с минимальными издержками

0 голосов
/ 14 ноября 2018

Я пытаюсь реализовать быстрый диспетчер функций, используя сгенерированные во время компиляции массивы, чтобы иметь возможность использовать его во время выполнения в 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. С теми, кого я, возможно, смог бы достичь своей цели, но мне нужно портативное решение.

Ответы [ 5 ]

0 голосов
/ 09 мая 2019

Теоретически (!) Вы можете создать идеальную хеш-функцию с использованием шаблонов C ++.

  • Этот вопрос содержит код о том, как создать идеальную хеш-функцию (используя грубую силу, поэтому она работает только для относительно небольших наборов).
  • Этот вопрос показывает, что шаблонирование C ++ завершено по Тьюрингу, поэтому должна быть возможность преобразовать приведенный выше код в шаблоны C ++.
  • Это может быть даже возможно с препроцессором C , поскольку он не нуждается в бесконечном цикле.

Но я предполагаю, что сделать это довольно сложно.

0 голосов
/ 14 ноября 2018

Небольшое улучшение (ИМХО) для решения Болова

Запись 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.

0 голосов
/ 14 ноября 2018

ОП попросил решение на 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; }
0 голосов
/ 14 ноября 2018

Опираясь на ответ @ 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

Live Demo

Edit : согласно запросу 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);
}

Live demo

0 голосов
/ 14 ноября 2018

Ну, я не знаю, сможете ли вы сделать то, что вы хотите. Сделать код, который создает идеальную хеш-функцию для любого ввода, кажется мне довольно ... нереализуемым.

В любом случае, вот простое решение для написания кода. Это 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

Решение может быть улучшено для выполнения двоичного поиска, но оно не является тривиальным.

...