ОК, так что я сам нашел решение, близкое к первому решению в моем вопросе, я сделал очень простой пример проблемы, выложенной на github, ссылка ниже:
Демонстрация с использованием таблицы ha sh и указателя соответственно
Примечание: это решение является простой демонстрацией, а не оптимизировано. Дальнейшие возможные оптимизации включают в себя:
Для метода отображения ha sh можно использовать интернирование строки , чтобы уменьшить накладные расходы на конструкцию строки, как предложено Konrad Rudolph и cmaster - восстанавливает monica , это приведет к снижению производительности в среднем (примерно на 50% по сравнению с указателями), но устраняет накладные расходы на динамическое создание c и уменьшает потребление памяти. boost::flyweight - хороший вариант.
Для метода карты ha sh я только что реализовал демонстрацию, используя std::unordered_map, но существуют лучшие заменители, включая google::dense_hash_map, tsl::hop_scotch_map и такие, их стоит попробовать, но согласно эталону Тесиля , я сомневаюсь в их O (s) (где s - средняя длина строки) временная сложность для каждого отдельного поиска может быть быстрее, чем доступ к указателю O (1).
В моем сценарии все функции могут быть однако, найденный после этапа загрузки модуля, вы можете захотеть охватить такой сценарий, как поиск символов в python, тогда hashmap будет лучше, если вы не введете больше ограничений для вашего senario или не обновите разрешенные указатели периодически. Tr ie структура данных может быть хорошим вариантом, если вы вставляете и удаляете объекты в большом масштабе.
Достаточно болтовни, вот результаты и решения :
Производительность
Тест: 1,28e8 возможных комбинаций для смешанных логических и числовых значений c SAT
Платформа: 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_ha sh:
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() будет явно указывать зависимые функции, и будет построена таблица указателей локальной функции.
Вот фактический полученный код после расширения макроса:
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))
По сути, решение с указателем создает таблицу поиска функции func_dep_map, которая позже будет использоваться классом Domain для поиска других функций, зависящих от этой функции, и вектор указателя на функцию func_dep, который будет заполнен их указателями.
enum используется для предоставления элегантного и компактного способа поиска индексов, вместо использования классов карт, предоставляемых библиотеками метапрограммирования, такими как Fatal и boost :: mpl, они не удобны для использования в этом случае .
Эта реализация сильно зависит от boost :: preprocessor, чтобы узнать больше, обратитесь к моему репозиторию github.