Lately I have being using boost xpressive for parsing files. These files are 10 MB each and there will be several hundred of them to parse.
Xpressive is nice to work and clear syntax, but the problems comes with performance. It is incredible how it crawls in debug versions, while in release version it spends more than a whole second per file. I have tested against old plain get_line(), find() and sscanf() code, and it can beat xpressive easily.
I understand that type checking, backtracking and so have a cost, but this seems excessive to me. How I wonder, I am doing something wrong? Is it any way of optimizing this to run at a decent pace? Should it deserve the effort to migrate code to boost::spirit?
I have prepared a lite version of code with a few lines of a real file embedded in case someone might test and help.
NOTE- As a requirement, VS 2010 must be used (not fully c++11 compliant unfortunately)
#include <boost/xpressive/xpressive.hpp>
#include <boost/xpressive/regex_actions.hpp>
const char input[] = "[2018-Mar-13 13:13:59.580482] - 0.200 s => Driver: 0 - Speed: 0.0 - Road: BTN-1002 - Km: 90.0 - SWITCH_ON: 1\n\
[2018-Mar-13 13:13:59.580482] - 0.200 s => Driver: 0 - Speed: 0.0 - Road: A-11 - Km: 90.0 - SLOPE: 0\n\
[2018-Mar-13 13:14:01.170203] - 1.790 s => Driver: 0 - Speed: 0.0 - Road: A-11 - Km: 90.0 - GEAR: 0\n\
[2018-Mar-13 13:14:01.170203] - 1.790 s => Driver: 0 - Speed: 0.1 - Road: A-11 - Km: 90.0 - GEAR: 1\n\
[2018-Mar-13 13:14:01.819966] - 2.440 s => Driver: 0 - Speed: 0.1 - Road: A-11 - Km: 90.0 - SEQUENCE: 1\n\
[2018-Mar-13 13:14:01.819966] - 2.440 s => Driver: 0 - Speed: 0.2 - Road: A-11 - Km: 90.0 - CLUTCH: 1\n\
[2018-Mar-13 13:14:01.819966] - 2.540 s => Backup to regestry\n\
[2018-Mar-13 13:14:02.409855] - 3.030 s => Driver: 0 - Speed: 0.2 - Road: A-11 - Km: 90.0 - SEQUENCE: 4\n\
[2018-Mar-13 13:14:02.409855] - 3.030 s => Driver: 0 - Speed: 0.3 - Road: A-11 - Km: 90.0 - SEQUENCE: 8\n\
[2018-Mar-13 13:14:01.819966] - 3.110 s => Backup to regestry\n\
[2018-Mar-13 13:14:02.620424] - 3.240 s => Driver: 0 - Speed: 0.4 - Road: A-11 - Km: 90.1 - SEQUENCE: 15\n\
[2018-Mar-13 13:14:02.829983] - 3.450 s => Driver: 0 - Speed: 0.6 - Road: B-302 - Km: 90.1 - SLOPE: -5\n\
[2018-Mar-13 13:14:03.039600] - 3.660 s => Driver: 0 - Speed: 0.8 - Road: B-302 - Km: 90.1 - SEQUENCE: 21\n\
[2018-Mar-13 13:14:03.250451] - 3.870 s => Driver: 0 - Speed: 1.2 - Road: B-302 - Km: 90.2 - GEAR: 2\n\
[2018-Mar-13 13:14:03.460012] - 4.080 s => Driver: 0 - Speed: 1.7 - Road: B-302 - Km: 90.3 - SEQUENCE: 29\n\
[2018-Mar-13 13:14:03.669448] - 4.290 s => Driver: 0 - Speed: 2.2 - Road: B-302 - Km: 90.4 - SEQUENCE: 34\n\
[2018-Mar-13 13:14:03.880066] - 4.500 s => Driver: 0 - Speed: 2.8 - Road: B-302 - Km: 90.5 - CLUTCH: 1\n\
[2018-Mar-13 13:14:04.090444] - 4.710 s => Driver: 0 - Speed: 3.5 - Road: B-302 - Km: 90.7 - SEQUENCE: 45\n\
[2018-Mar-13 13:14:04.300160] - 4.920 s => Driver: 0 - Speed: 4.2 - Road: B-302 - Km: 90.9 - SLOPE: 10\n\
[2018-Mar-13 13:14:04.510025] - 5.130 s => Driver: 0 - Speed: 4.9 - Road: B-302 - Km: 91.1 - GEAR: 3";
const auto len = std::distance(std::begin(input), std::end(input));
struct Sequence
{
int ms;
int driver;
int sequence;
double time;
double vel;
double km;
std::string date;
std::string road;
};
namespace xp = boost::xpressive;
int main()
{
Sequence data;
std::vector<Sequence> sequences;
using namespace xp;
cregex real = (+_d >> '.' >> +_d);
cregex keyword = " - SEQUENCE: " >> (+_d)[xp::ref(data.sequence) = as<int>(_)];
cregex date = repeat<4>(_d) >> '-' >> repeat<3>(alpha) >> '-' >> repeat<2>(_d) >> _s >> repeat<2>(_d) >> ':' >> repeat<2>(_d) >> ':' >> repeat<2>(_d);
cregex header = '[' >> date[xp::ref(data.date) = _] >> '.' >> (+_d)[xp::ref(data.ms) = as<int>(_)] >> "] - "
>> real[xp::ref(data.time) = as<double>(_)]
>> " s => Driver: " >> (+_d)[xp::ref(data.driver) = as<int>(_)]
>> " - Speed: " >> real[xp::ref(data.vel) = as<double>(_)]
>> " - Road: " >> (+set[alnum | '-'])[xp::ref(data.road) = _]
>> " - Km: " >> real[xp::ref(data.km) = as<double>(_)];
xp::cregex parser = (header >> keyword >> _ln);
xp::cregex_iterator cur(input, input + len, parser);
xp::cregex_iterator end;
for (; cur != end; ++cur)
sequences.emplace_back(data);
return 0;
}
Please, mind the VS 2010 constraint.
I see roughly two areas for improvement:
I'd suggest using string views to fix the allocations. Next, you could try to avoid parsing lines that don't match the SEQUENCE pattern. There's no reason in principle why this couldn't be done using Boost Xpressive, but my weapon of choice happens to be Boost Spirit, so I'll include it too.
Being Selective
You can detect interesting lines before spending more effort like this:
This prints
Nothing is allocated. This should be pretty fast.
Reducing Allocations
For this I'm going to switch to Spirit because it will make things easier.
You can use
boost::string_viewwith a trait to "teach" Qi to assign text to it:That way, the Qi grammar could look just like this:
Using it is exceedingly simple, especially if not being "selective".
Benchmark Results: Surprises
Using the selective parsing approach only made the Xpressive approach slower: Interactive
Comparing to Spirit, I had initially started with the selective approach as well (fully anticipating it to be faster). Here's the not-so-encouraging results: Interactive
Oops. The initial Xpressive approach is still superior!
Adjusting The Assumptions
Okay, clearly doing the shallow scan first, and then the "full parse" hurts the performance. Theorizing, this is likely down to cache/prefetch effects. Also, the linear approach may win because it's easier to spot when a line doesn't start with a
'['character, than to see whether it ends with theSEQUENCEpattern.So I decided to adapt the spirit approaches to linear mode too, and see whether the win by reducing allocations is still worth it: Interactive
Now we're getting results. Let's look at the difference between the
std::stringandboost::string_viewapproaches in detail: InteractiveSummary/Conclusions
The reduced allocations are good for 30% more efficiency. In total, an improvement of 10 times over the original approach.
Note that the benchmark code goes out of its way to eliminate unfair differences between the implementations (e.g. by pre compiling everything on both Spirit and Xpressive). See the full benchmark code:
Full Benchmark Code
The benchmarks use Nonius for the measurements and statistical analysis.
-DUSE_NONIUSif you have Nonius available-DVERIFY_OUTPUTfor "correctness" mode: in this case no timings are done but the results of the parse are echoed for validationSample text report: