Отвечая на этот вопрос обзора кода, я придумал способ преобразовать уравнение, заданное во время выполнения, в std::function<double(double)> который оценил бы это уравнение в данной точке. Предполагая, что уравнение уже было разбито на токены и преобразовано в постфиксная запись, это выполняется путем оценки этих токенов, как если бы вы это делали в обычной реализации калькулятора RPN, поддерживая стек промежуточных результатов, но вместо того, чтобы просто сохранять значения, в стеке хранятся лямбда-выражения, которые могут вычислять эти значения. Таким образом, в конце оценки стек должен содержать одно лямбда-выражение, реализующее желаемое уравнение. Вот упрощенная версия парсера, которая поддерживает только несколько операций:
#include <cmath>
#include <functional>
#include <iostream>
#include <numbers>
#include <stack>
#include <string>
#include <string_view>
std::function<double(double)> build_function(const std::vector<std::string_view> &rpn_tokens) {
std::stack<std::function<double(double)>> subexpressions;
for (const auto &token: rpn_tokens) {
if (token.empty())
throw std::runtime_error("empty token");
if (token == "x") { // Variable
subexpressions.push([](double x){
return x;
});
} else if (isdigit(token[0])) { // Literal number
double value = std::stof(token.data());
subexpressions.push([=](double /* ignored */){
return value;
});
} else if (token == "sin") { // Example unary operator
if (subexpressions.size() < 1) {
throw std::runtime_error("invalid expression");
}
auto operand = subexpressions.top();
subexpressions.pop();
subexpressions.push([=](double x){
return std::sin(operand(x));
});
} else if (token == "+") { // Example binary operator
if (subexpressions.size() < 2) {
throw std::runtime_error("invalid expression");
}
auto right_operand = subexpressions.top();
subexpressions.pop();
auto left_operand = subexpressions.top();
subexpressions.pop();
subexpressions.push([=](double x){
return left_operand(x) + right_operand(x);
});
} else {
throw std::runtime_error("invalid token");
}
}
if (subexpressions.size() != 1) {
throw std::runtime_error("invalid expression");
}
return subexpressions.top();
}
int main() {
auto function = build_function({"1", "x", "2", "+", "sin", "+"}); // 1 + sin(2 + x)
for (double x = 0; x < 2 * std::numbers::pi; x += 0.1) {
std::cout << x << ' ' << function(x) << 'n';
}
}
Я называю это JIT для бедняков, потому что, хотя похоже, что мы получаем объект функции, который, казалось бы, создается во время выполнения, в основном это набор предварительно скомпилированных функций (по одной для каждого тела лямбда в приведенном выше коде), связанных вместе с помощью захватов лямбда. Таким образом, при вызове вышеуказанного function() чем если бы можно было написать следующее:
auto function = [](double x){
return 1 + sin(2 + x);
}
Но это все равно должно быть намного быстрее, чем анализ множества токенов, составляющих уравнение, каждый раз, когда вы хотите его оценить.
Некоторые вопросы:
- Есть лучший способ сделать это?
- Эта техника уже реализована в какой-нибудь библиотеке?
- Аргумент результирующей функции должен быть передан большинству лямбда-выражений (исключение составляет тот, который возвращает буквальные числа). Есть лучший способ сделать это?
- Как обрабатывать создание функции, которая принимает несколько аргументов? Можем ли мы сделать
build_functionшаблон каким-то образом может вернутьstd::functionс переменным количеством аргументов?
Измерения производительности на AMD Ryzen 3900X, код, скомпилированный с GCC 10.2.1 с -O2после разминки 60 миллионов вызовов, в среднем более 60 миллионов вызовов function():
- Простая лямбда: 10 нс на оценку
- Приведенный выше код: 21 нс на оценку
- Исходный ответ дедупликатора: 77 нс на оценку
- Добавление
stack.reserve(): 39 нс на оценку - Изготовление
stackstatic: 26 нс на оценку
- Добавление
2 ответа
Есть лучший способ сделать это?
Что ж, у вас есть динамическая диспетчеризация и еще один разбросанный остров памяти для каждый жетон. Это очень неэффективно.
Простой способ повысить эффективность — написать собственную мини-виртуальную машину для выполнения выражений. Вам все равно нужно будет выполнить синтаксический анализ только один раз, но теперь вся память находится в одном компактном фрагменте, который будет использоваться линейно, и компилятор может видеть весь код.
Операторы switch с одним компактным диапазоном допустимых значений сами по себе просты, и вы избегаете перетасовки аргументов, сохранения регистров и всех других накладных расходов, связанных с динамическим вызовом произвольных функций.
Следующим шагом для повышения эффективности будет компиляция в собственный код.
Кроме того, простой модификацией должно быть помещение всех аргументов в массив, а затем использование инструкции с операндом или последовательных простых инструкций для их получения.
Я также добавил обширные X-макросы, чтобы уменьшить повторение и избежать определения всех применимых преобразований повсюду.
Адаптированный пример жить на колиру:
#include <iostream>
#include <numbers>
#include <charconv>
#include <cmath>
#include <exception>
#include <memory>
#include <span>
#include <string_view>
#include <string>
#include <vector>
#define XX()
X("x", x, 0, 1, *p = x)
X("sin", sin, 1, 1, *p = std::sin(*p))
X("+", plus, 2, 1, *p += p[1])
enum class instruction : unsigned char {
end,
push,
#define X(a, b, c, d, e) b,
XX()
#undef X
};
auto build_function(std::span<const std::string_view> rpn_tokens) {
std::vector<char> bin;
double temp;
unsigned count = 0;
auto process = [&](instruction id, unsigned take, unsigned give) {
if (count < take)
throw std::runtime_error("invalid expression: underflow");
bin.push_back((char)id);
count += give - take;
};
for (auto token : rpn_tokens) {
#define X(a, b, c, d, e)
if (token == a)
process(instruction::b, c, d);
else
XX()
#undef X
// if (auto [p, ec] = std::from_chars(token.begin(), token.end(), temp); !ec && p = token.end()) {
// process(instruction::push, 0, 1);
// bin.insert(bin.end(), (char*)&temp, (char*)(&temp + 1));
// } else
// throw std::runtime_error("invalid token");
try {
temp = std::stod(std::string(token));
process(instruction::push, 0, 1);
bin.insert(bin.end(), (char*)&temp, (char*)(&temp + 1));
} catch(...) {
std::throw_with_nested(std::runtime_error("invalid token"));
}
}
process(instruction::end, 1, 0);
if (count)
throw std::runtime_error("invalid expression: overflow");
return [bin = std::move(bin)](double x) {
std::vector<double> stack;
for (std::size_t n = 0;;) {
switch(bin[n++]) {
case (char)instruction::end:
return stack[0];
case (char)instruction::push: {
double temp;
std::copy_n(&bin[n], sizeof temp, (char*)&temp);
stack.push_back(temp);
n += sizeof temp;
break;
}
#define X(a, b, c, d, e)
case (char)instruction::b: {
auto p = stack.end() - c;
if (d > c) stack.resize(stack.size() + d - c);
e;
if (d < c) stack.resize(stack.size() + d - c);
break;
}
XX()
#undef X
default:
throw std::runtime_error("unexpected");
}
}
};
}
#undef XX
int main() {
std::string_view rpn[] = {"1", "x", "2", "+", "sin", "+"}; // 1 + sin(2 + x)
auto function = build_function(rpn);
for (double x = 0; x < 2 * std::numbers::pi; x += 0.1) {
std::cout << x << ' ' << function(x) << 'n';
}
}
Технически isdigit(token[0]):
- Потребности
#include <cctype>. - Должно быть
std::isdigit(static_cast<unsigned char>(token[0])).
Я думаю, проходя мимо std::map<std::string_view, double> const& дает нам гибкость в аргументации.
Я сравнил ваш код с моим и был удивлен, что мой код был примерно в 3,7 раза быстрее! Конечно, эти числа могут быть бессмысленными, так как этот код — всего лишь очень упрощенный синтаксический анализатор выражений, я должен проверить его, добавив больше функций и пытаясь вычислить более сложные уравнения.
— Г. Сон
Вы тестировали синтаксический анализ, вызов или и то, и другое? В любом случае, похоже, что заменителя измерения нет. Я думаю, что большая часть проблемы — это динамическое распределение во время выполнения. Надо поэкспериментировать.
— Дедупликатор
Я тестировал только вызов. В самом деле, я тоже буду экспериментировать, может просто
reserve()места в стеке будет достаточно, чтобы ускорить его.— Г. Сон
Кажется,
stackдействительно большая часть проблемы. Сstaticstackон снижается до 26 нс, что очень близко к моему решению. Думаю, стек не нужен; порядок и количество операций со стеком всегда одинаковы для каждого вызова возвращаемой функции, мое решение — это «жесткие коды», но я не вижу, как это сделать с вашим, сохраняяbinтакой компактный, как он …— Г. Сон
Многопоточный код может быть удивительно быстрым и одновременно удивительно плотным. Существует множество историй о программистах встраиваемых систем, которые обнаружили, что интерпретатор FORTH и программа FORTH быстрее и компактнее, чем оптимизированная вручную программа на языке C для решения той же проблемы. И если вам нужно решить больше, чем одну единственную задачу, преимущество в плотности только возрастет, потому что вам понадобится только одна копия интерпретатора FORTH.
— Йорг В полдень