gpt4 book ai didi

c++ - Qi Symbols 性能慢?

转载 作者:塔克拉玛干 更新时间:2023-11-03 00:22:59 27 4
gpt4 key购买 nike

我想提出一个让我陷入困境的主题,并提出了一个关于齐::符号。

这一切都始于我查看新的野兽图书馆并阅读 atutorial example

它以一个从 http 路径猜测 mime 类型的函数开始扩展。我开始仔细观察,看到了这个:

 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,同时声明它为常量。

无论如何,我开始测试这是否会产生任何性能差异将证明可怕的可读性与直接实现相比是合理的。

这样做我开始怀疑这在齐::符号。所以我想出了两个替代实现:

#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;
}

令我惊讶的是,lambda 确实很重要(一点点)。让我吃惊的是更重要的是,qi 的实现速度要慢得多。

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

尝试优化#1

首先,我使用的是这样的符号

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 拷贝所以我改变了它所以它只返回一个索引到静态字符数组:

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 纳秒。 - Qi 实现平均耗时约 7100 纳秒。

现在,这将是我的第一个问题:这是为什么?

“野兽”实现让我印象深刻,因为它经历了所有子字符串,每次都调用 iequals,同时它能够缓存小写。

我认为 qi 肯定会对我添加到符号解析器。但它看起来不像。

尝试优化 #2

所以我想出了我自己的,也是微不足道的实现,并使用静态 map 临时缓存的小写字母(请参阅附加源中的 impl3)。

测试结果:

  • 静态 map 实现平均每次运行约 2400 纳秒

Sooo,我想问题是为什么

我是否以某种方式滥用了 qi::symbols?它实际上进行了二进制搜索但是性能在其他地方丢失了吗?

斯蒂芬¹

(我在 Windows MSVC14 64 位上,boost 1.66)


(¹ 这个问题是从 Spirit General 邮件列表中转述的,它发布于 20180112T14:15CET;online archives 似乎很遗憾地坏掉了)

最佳答案

在 12-01-18 14:15,Stephan Menzel 写道:

So I came up with two different implementations. Please find the source attached.

我看过了。首先进行一些粗略的观察:

  1. 您是在比较苹果和梨,因为 Beast 使用零拷贝字符串 View ,而 Qi 没有。

  2. 此外,样本选择调用 UB 因为 uniform_int_distribution(0,10)超出样本数组的范围(应为 (0, 9) )。

  3. 最后, map 方法没有 .txt 扩展名的映射。

有了这些,我将测试程序简化/结构化为以下内容:

Live On Coliru

在我的系统上打印以下内容:

Lambda runs took 2319 nanoseconds
Qi runs took 2841 nanoseconds
Map runs took 193 nanoseconds

现在,最大的罪魁祸首是(显然?)您每次都在通过循环构建语法(编译规则)。当然,没有必要。删除产量:

Live On Coliru

Lambda runs took 2676 nanoseconds
Qi runs took 98 nanoseconds
Map runs took 189 nanoseconds

这已经更快了,即使您在没有实际需要时仍在复制字符串。使用上面链接的答案的灵感,我可能会这样写:

#include <boost/spirit/include/qi.hpp>
namespace qi_impl {
namespace qi = boost::spirit::qi;

struct mimetype_symbols_type : qi::symbols<char, char const*> {
mimetype_symbols_type() {
auto rev = [](string_view s) -> std::string { return { s.rbegin(), s.rend() }; };

this->add
(rev(".htm"), "text/html")
(rev(".html"), "text/html")
(rev(".php"), "text/html")
(rev(".css"), "text/css")
(rev(".txt"), "text/plain")
(rev(".js"), "application/javascript")
(rev(".json"), "application/json")
(rev(".xml"), "application/xml")
(rev(".swf"), "application/x-shockwave-flash")
(rev(".flv"), "video/x-flv")
(rev(".png"), "image/png")
(rev(".jpe"), "image/jpeg")
(rev(".jpeg"), "image/jpeg")
(rev(".jpg"), "image/jpeg")
(rev(".gif"), "image/gif")
(rev(".bmp"), "image/bmp")
(rev(".ico"), "image/vnd.microsoft.icon")
(rev(".tiff"), "image/tiff")
(rev(".tif"), "image/tiff")
(rev(".svg"), "image/svg+xml")
(rev(".svgz"), "image/svg+xml")
;
}
} static const mime_symbols;

char const* using_spirit(const string_view &n_path) {
char const* result = "application/text";
qi::parse(n_path.crbegin(), n_path.crend(), qi::no_case[mime_symbols], result);
return result;
}
}

不再需要首先寻找“最后一个点”,也不需要“检查匹配项是否在末尾”,您可以直接从符号中获取值。您可以自由分配给 string_viewstd::string随心所欲。

完整 list

自始至终使用 string_views(支持/显示 std::string_viewboost::string_view)。

Note also this shows a custom comparator being used on the map<> approach, just to prove that indeed there's a benefit from knowing that the map keys are all lower-case. (It's not, in fact, because it "cached the lowercase" since it's only used once!)

Live On Coliru

#include <boost/chrono.hpp>
#include <string>

#ifdef BOOST_STRING_VIEW
#include <boost/utility/string_view.hpp>
using string_view = boost::string_view;
#else
#include <string_view>
using string_view = std::string_view;
#endif

static auto constexpr npos = string_view::npos;

#include <boost/spirit/include/qi.hpp>
namespace qi_impl {
namespace qi = boost::spirit::qi;

struct mimetype_symbols_type : qi::symbols<char, char const*> {
mimetype_symbols_type() {
auto rev = [](string_view s) -> std::string { return { s.rbegin(), s.rend() }; };

this->add
(rev(".htm"), "text/html")
(rev(".html"), "text/html")
(rev(".php"), "text/html")
(rev(".css"), "text/css")
(rev(".txt"), "text/plain")
(rev(".js"), "application/javascript")
(rev(".json"), "application/json")
(rev(".xml"), "application/xml")
(rev(".swf"), "application/x-shockwave-flash")
(rev(".flv"), "video/x-flv")
(rev(".png"), "image/png")
(rev(".jpe"), "image/jpeg")
(rev(".jpeg"), "image/jpeg")
(rev(".jpg"), "image/jpeg")
(rev(".gif"), "image/gif")
(rev(".bmp"), "image/bmp")
(rev(".ico"), "image/vnd.microsoft.icon")
(rev(".tiff"), "image/tiff")
(rev(".tif"), "image/tiff")
(rev(".svg"), "image/svg+xml")
(rev(".svgz"), "image/svg+xml")
;
}
} static const mime_symbols;

char const* using_spirit(const string_view &n_path) {
char const* result = "application/text";
qi::parse(n_path.crbegin(), n_path.crend(), qi::no_case[mime_symbols], result);
return result;
}
}

#include <boost/algorithm/string.hpp>
namespace impl {
string_view using_iequals(const string_view &n_path) {

using boost::algorithm::iequals;

auto const ext = [&n_path] {
auto pos = n_path.rfind(".");
return pos != npos? n_path.substr(pos) : string_view {};
}();

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";
}
}

#include <boost/algorithm/string.hpp>
#include <map>

namespace impl {
struct CiCmp {
template <typename R1, typename R2>
bool operator()(R1 const& a, R2 const& b) const {
return boost::algorithm::ilexicographical_compare(a, b);
}
};

static const std::map<string_view, string_view, CiCmp> s_mime_exts_map {
{ ".txt", "text/plain" },
{ ".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"},
};

string_view using_map(const string_view& n_path) {
auto const ext = [](string_view n_path) {
auto pos = n_path.rfind(".");
return pos != npos? n_path.substr(pos) : string_view {};
};

auto i = s_mime_exts_map.find(ext(n_path));

if (i != s_mime_exts_map.cend()) {
return i->second;
} else {
return "application/text";
}
}
}

#include <random>
namespace samples {

static string_view const s_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"
};

std::mt19937 s_random_generator(std::random_device{}());
std::uniform_int_distribution<> s_dis(0, boost::size(s_samples) - 1);

string_view random_sample() {
return s_samples[s_dis(s_random_generator)];
}
}

#include <boost/functional/hash.hpp>
#include <iostream>
template <typename F>
int generic_test(F f) {
auto sample = samples::random_sample();
string_view result = f(sample);

//std::cout << "DEBUG " << sample << " -> " << result << "\n";

return boost::hash_range(result.begin(), result.end());
}

#include <boost/serialization/array_wrapper.hpp> // missing include in boost version on coliru
#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics.hpp>

template <typename F>
auto benchmark(F f) {
using C = boost::chrono::high_resolution_clock;
using duration = C::duration;

const unsigned int loops = 100000;

namespace ba = boost::accumulators;
ba::accumulator_set<duration, ba::features<ba::tag::mean>> times;

for (unsigned int i = 0; i < loops; i++) {
auto start = C::now();
generic_test(f);
times(C::now() - start);
}

return ba::mean(times);
}


int main() {
std::cout << std::unitbuf;
std::cout << "Lambda runs took " << benchmark(impl::using_iequals) << std::endl;
std::cout << "Qi runs took " << benchmark(qi_impl::using_spirit) << std::endl;
std::cout << "Map runs took " << benchmark(impl::using_map) << std::endl;
}

打印

Lambda runs took 2470 nanoseconds
Qi runs took 119 nanoseconds
Map runs took 2239 nanoseconds // see Note above

关于c++ - Qi Symbols 性能慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48235133/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com