Símbolos Qi rendimiento lento?

Quería plantear un tema que simplemente me envió por una madriguera de conejo y planteó una pregunta sobre qi :: símbolos.

Todo comenzó mientras miraba la nueva biblioteca de bestias y leíaun ejemplo tutorial

Comienza con una función que adivina los tipos mime de las extensiones de ruta http. Empecé a mirar más de cerca y vi esto:

 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);
    }();

Me tomó un tiempo descubrir que era unIIFE en estilo C ++, y se utilizó para inicializarext mientras lo declaras constante.

De todos modos, comencé a probar si esto marcaba una diferencia en el rendimiento que justificaría la horrible legibilidad frente a la implementación directa.

Al hacerlo, comencé a preguntarme si esto no se implementaría mucho mejor en qi :: symbols. Entonces se me ocurrieron dos implementaciones alternativas:

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

Para mi sorpresa, la lambda sí importa (un poco). Lo que me sorprendió aún más fue que la implementación de qi es mucho más lenta.

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

Intento de optimización # 1

Primero, estaba usando símbolos como este

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

Eso devolvió la cadena directamente como atributo. Un colega señaló que esta es una copia adicional de std :: string, así que la cambié para que solo devuelva un índice a una matriz de caracteres estáticos:

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

Esto fue un poco más rápido pero realmente no vale la pena mencionarlo.

En mi computadora portátil, en modo Release, obtengo: - El promedio de implementación de Beast Tutorial (Lambda) es de 6200 nanosegundos por carrera. - La implementación de Qi promedia alrededor de 7100 nanosegundos.

Ahora, esa sería mi primera pregunta:¿Porqué es eso?

La implementación de 'bestia' me parece muy ineficiente ya que pasa por todas las subcadenas, llama iequals cada vez, mientras que podría almacenar en caché las minúsculas.

Pensé que seguramente qi haría una búsqueda binaria de las palabras clave que agregué a un analizador de símbolos. Pero no se ve como lo hace.

Intento de optimización # 2

Así que se me ocurrió mi propia implementación, también trivial, y utilicé un mapa estático con una temporal en minúscula en caché (ver impl3 en la fuente adjunta).

La prueba arrojó:

La implementación del mapa estático promedia aproximadamente 2400 nanosegundos por carrera

Entonces, supongo que la pregunta espor qué?

¿Estoy haciendo mal usoqi::symbols ¿de alguna manera? ¿Realmente hace una búsqueda binaria pero el rendimiento se pierde en otro lugar?

Stephan¹

(Estoy en Windows MSVC14 64 bits con boost 1.66)

(¹ esta pregunta fue parafraseada de la lista de correo Spirit General, donde fue publicada 20180112T14: 15CET; elarchivos en línea parece tristemente roto)