). Производительность, скорее всего, не репрезентативна (она не оптимизируется, возможно, с использованием отладчиков MSVC и т. Д.)
ел поднять тему, которая просто послала меня в кроличью нору и подняла вопрос о символах qi ::.
Все началось, когда я изучал новую библиотеку зверя и читалучебный пример
Он начинается с функции, которая угадывает типы пантомимы из расширений пути http. Я начал присматриваться и увидел это:
auto const ext = [&path]
{
auto const pos = path.rfind(".");
if(pos == boost::beast::string_view::npos)
return boost::beast::string_view{};
return path.substr(pos);
}();
Мне понадобилось время, чтобы понять, что этоIIFE в стиле C ++, и был использован для инициализацииext при объявлении его постоянным.
Во всяком случае, я начал тестировать, если это повлияло на производительность, которая оправдывала бы ужасную читабельность по сравнению с прямой реализацией.
При этом я начал задаваться вопросом, не будет ли это лучше реализовано в символах qi ::. Итак, я придумал две альтернативные реализации:
#include <boost/smart_ptr/scoped_array.hpp>
#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics/stats.hpp>
#include <boost/accumulators/statistics/mean.hpp>
#include <boost/accumulators/statistics/moment.hpp>
#include <boost/chrono.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/qi_parse.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/include/vector.hpp>
#include <boost/spirit/include/karma.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/assign.hpp>
#include <iostream>
#include <string>
#include <vector>
#include <random>
using namespace boost::accumulators;
typedef boost::chrono::duration<long long, boost::micro> microseconds;
namespace qi = boost::spirit::qi;
namespace karma = boost::spirit::karma;
namespace ascii = qi::ascii;
namespace phx = boost::phoenix;
const std::map<const std::string, const std::string> mime_exts = {
{ ".htm", "text/html" },
{ ".html", "text/html" },
{ ".php", "text/html" },
{ ".css", "text/css" },
{ ".js", "application/javascript" },
{ ".json", "application/json" },
{ ".xml", "application/xml" },
{ ".swf", "application/x-shockwave-flash" },
{ ".flv", "video/x-flv" },
{ ".png", "image/png" },
{ ".jpe", "image/jpeg" },
{ ".jpeg", "image/jpeg" },
{ ".jpg", "image/jpeg" },
{ ".gif", "image/gif" },
{ ".bmp", "image/bmp" },
{ ".ico", "image/vnd.microsoft.icon" },
{ ".tif", "image/tiff" },
{ ".tiff", "image/tiff" },
{ ".svg", "image/svg+xml"},
{ ".svgz", "image/svg+xml"}
};
const char *mime_literals[] = {
"text/html",
"text/css",
"text/plain",
"application/javascript",
"application/json",
"application/xml",
"application/x-shockwave-flash",
"video/x-flv",
"image/png",
"image/jpeg",
"image/gif",
"image/bmp",
"image/vnd.microsoft.icon",
"image/tiff",
"image/svg+xml"
};
template <typename Iterator>
struct mimetype_matching_parser : qi::grammar<Iterator, unsigned int()> {
mimetype_matching_parser() : mimetype_matching_parser::base_type(m_start, "mimetype_matching_parser") {
m_mime_extensions.add
(".htm", 0)
(".html", 0)
(".php", 0)
(".css", 1)
(".txt", 2)
(".js", 3)
(".json", 4)
(".xml", 5)
(".swf", 6)
(".flv", 7)
(".png", 8)
(".jpe", 9)
(".jpeg", 9)
(".jpg", 9)
(".gif", 10)
(".bmp", 11)
(".ico", 12)
(".tiff", 13)
(".tif", 13)
(".svg", 14)
(".svgz", 14)
;
using qi::no_case;
m_start %= no_case[m_mime_extensions] >> qi::eoi;
}
qi::symbols<char, unsigned int> m_mime_extensions;
qi::rule<Iterator, unsigned int()> m_start;
};
std::string mime_extension(const std::string &n_path) {
// First locate the extension itself
const std::size_t last_dot = n_path.rfind(".");
if (last_dot == std::string::npos) {
return "application/text";
}
// and now pipe the extension into a qi symbols parser.
// I don't know if this is any faster than a more trivial algorithm::ends_with
// approach but I guess it won't be any slower
const mimetype_matching_parser<std::string::const_iterator> p;
unsigned int result;
std::string::const_iterator begin = n_path.begin() + last_dot;
const std::string::const_iterator end = n_path.end();
try {
if (qi::parse(begin, end, p, result) && (begin == end)) {
return mime_literals[result];
} else {
return "application/text";
}
} catch (const std::exception &) { // asio throws on invalid parse
return "application/text";
}
}
std::string mime_extension2(const std::string &n_path) {
using boost::algorithm::iequals;
auto const ext = [&n_path] {
auto const pos = n_path.rfind(".");
if (pos == std::string::npos)
return std::string{};
return n_path.substr(pos);
}();
// const std::size_t pos = n_path.rfind(".");
// if (pos == std::string::npos) {
// return std::string{};
// }
// const std::string ext = n_path.substr(pos);
if (iequals(ext, ".htm")) return "text/html";
if (iequals(ext, ".html")) return "text/html";
if (iequals(ext, ".php")) return "text/html";
if (iequals(ext, ".css")) return "text/css";
if (iequals(ext, ".txt")) return "text/plain";
if (iequals(ext, ".js")) return "application/javascript";
if (iequals(ext, ".json")) return "application/json";
if (iequals(ext, ".xml")) return "application/xml";
if (iequals(ext, ".swf")) return "application/x-shockwave-flash";
if (iequals(ext, ".flv")) return "video/x-flv";
if (iequals(ext, ".png")) return "image/png";
if (iequals(ext, ".jpe")) return "image/jpeg";
if (iequals(ext, ".jpeg")) return "image/jpeg";
if (iequals(ext, ".jpg")) return "image/jpeg";
if (iequals(ext, ".gif")) return "image/gif";
if (iequals(ext, ".bmp")) return "image/bmp";
if (iequals(ext, ".ico")) return "image/vnd.microsoft.icon";
if (iequals(ext, ".tiff")) return "image/tiff";
if (iequals(ext, ".tif")) return "image/tiff";
if (iequals(ext, ".svg")) return "image/svg+xml";
if (iequals(ext, ".svgz")) return "image/svg+xml";
return "application/text";
}
std::string mime_extension3(const std::string &n_path) {
using boost::algorithm::iequals;
auto ext = [&n_path] {
auto const pos = n_path.rfind(".");
if (pos == std::string::npos) {
return std::string{};
} else {
return n_path.substr(pos);
}
}();
boost::algorithm::to_lower(ext);
const std::map<const std::string, const std::string>::const_iterator i = mime_exts.find(ext);
if (i != mime_exts.cend()) {
return i->second;
} else {
return "application/text";
}
}
const std::string samples[] = {
"test.txt",
"test.html",
"longer/test.tiff",
"www.webSite.de/ico.ico",
"www.websIte.de/longEr/path/ico.bmp",
"www.TEST.com/longer/path/ico.svg",
"googlecom/shoRT/path/index.HTM",
"googlecom/bild.jpg",
"WWW.FLASH.COM/app.swf",
"WWW.FLASH.COM/BILD.GIF"
};
int test_qi_impl() {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 10);
const std::string sample = samples[dis(gen)];
const std::string result = mime_extension(sample);
int ret = dis(gen);
for (const char &c : result) { ret += c; }
return ret;
}
int test_lambda_impl() {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 10);
const std::string sample = samples[dis(gen)];
const std::string result = mime_extension2(sample);
int ret = dis(gen);
for (const char &c : result) { ret += c; }
return ret;
}
int test_map_impl() {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 10);
const std::string sample = samples[dis(gen)];
const std::string result = mime_extension3(sample);
int ret = dis(gen);
for (const char &c : result) { ret += c; }
return ret;
}
int main(int argc, char **argv) {
const unsigned int loops = 100000;
accumulator_set<boost::chrono::high_resolution_clock::duration, features<tag::mean> > times_qi;
accumulator_set<boost::chrono::high_resolution_clock::duration, features<tag::mean> > times_lambda;
accumulator_set<boost::chrono::high_resolution_clock::duration, features<tag::mean> > times_map;
std::cout << "Measure execution times for " << loops << " lambda runs" << std::endl;
for (unsigned int i = 0; i < loops; i++) {
boost::chrono::high_resolution_clock::time_point start = boost::chrono::high_resolution_clock::now();
test_lambda_impl();
boost::chrono::high_resolution_clock::time_point end = boost::chrono::high_resolution_clock::now();
times_lambda(end - start);
}
std::cout << "Measure execution times for " << loops << " qi runs" << std::endl;
for (unsigned int i = 0; i < loops; i++) {
boost::chrono::high_resolution_clock::time_point start = boost::chrono::high_resolution_clock::now();
test_qi_impl();
boost::chrono::high_resolution_clock::time_point end = boost::chrono::high_resolution_clock::now();
times_qi(end - start);
}
std::cout << "Measure execution times for " << loops << " map runs" << std::endl;
for (unsigned int i = 0; i < loops; i++) {
boost::chrono::high_resolution_clock::time_point start = boost::chrono::high_resolution_clock::now();
test_map_impl();
boost::chrono::high_resolution_clock::time_point end = boost::chrono::high_resolution_clock::now();
times_map(end - start);
}
std::cout << "Lambda runs took " << mean(times_lambda) << std::endl;
std::cout << "Qi runs took " << mean(times_qi) << std::endl;
std::cout << "Map runs took " << mean(times_map) << std::endl;
return EXIT_SUCCESS;
}
К моему удивлению, лямбда имеет значение (немного). Еще больше меня удивило то, что реализация ци намного медленнее.
Measure execution times for 100000 lambda runs
Measure execution times for 100000 qi runs
Measure execution times for 100000 map runs
Lambda runs took 12443 nanoseconds
Qi runs took 15311 nanoseconds
Map runs took 10466 nanoseconds
Во-первых, я использовал такие символы
template <typename Iterator>
struct mimetype_matching_parser : qi::grammar<Iterator, std::string()> {
mimetype_matching_parser() : mimetype_matching_parser::base_type(m_start,
"mimetype_matching_parser") {
m_mime_extensions.add
(".htm", "text/html")
(".html", "text/html")
(".php", "text/html")
(".css", "text/css")
(".svg", "whatever...")
;
using qi::no_case;
m_start %= no_case[m_mime_extensions] >> qi::eoi;
}
qi::symbols<char, std::string> m_mime_extensions;
qi::rule<Iterator, std::string()> m_start;
};
Это вернуло строку непосредственно как атрибут. Коллега указал, что это одна дополнительная копия std :: string, поэтому я изменил ее, чтобы она возвращала только индекс статического массива char:
const char *mime_literals[] = {
"text/html",
"text/css",
"text/plain",
// ... and so forth
};
template <typename Iterator>
struct mimetype_matching_parser : qi::grammar<Iterator, unsigned int()> {
mimetype_matching_parser() : mimetype_matching_parser::base_type(m_start, "mimetype_matching_parser")
{
m_mime_extensions.add
(".htm",0)
(".html",0)
(".php",0)
(".css",1)
(".svg",... etc.
;
using qi::no_case;
m_start %= no_case[m_mime_extensions] >> qi::eoi;
}
qi::symbols<char, unsigned int> m_mime_extensions;
qi::rule<Iterator, unsigned int()> m_start;
};
Это было немного быстрее, но не стоит упоминать.
На моем ноутбуке в режиме Release я получаю: - Реализация Beast Tutorial (Lambda) в среднем составляет 6200 наносекунд за цикл. - В среднем реализация ци составляет около 7100 наносекунд.
Теперь это будет мой первый вопрос:Почему это?
Реализация «зверя» кажется мне очень неэффективной, поскольку она проходит через все подстроки, каждый раз вызывает iequals, в то время как она сможет кэшировать строчные буквы.
Я думал, что qi сделает бинарный поиск по ключевым словам, которые я добавил в анализатор символов. Но это не похоже на это.
Попытка оптимизации # 2Поэтому я разработал собственную, тоже тривиальную реализацию, и использую статическую карту с временным кешированием в нижнем регистре (см. Impl3 в прикрепленном источнике).
Тест дал:
Реализация статической карты в среднем составляет около 2400 наносекунд за циклОоо, я думаю, вопросПочему?
Я неправильно используюqi::symbols каким-то образом? Действительно ли он выполняет бинарный поиск, но производительность теряется в другом месте?
Stephan¹
(У меня на windows MSVC14 64 бита с бустом 1,66)
(¹ этот вопрос был перефразирован из списка рассылки Spirit General, где он был опубликован 20180112T14: 15CET;онлайн-архивы кажется грустно сломленным)