search

yhirose / cpp-peglib

A single file C++ header-only PEG (Parsing Expression Grammars) library
MIT License
879 stars 112 forks source link

Severe performance regression in 1.8.6 #294

Closed joankaradimov closed 5 months ago

joankaradimov commented 5 months ago

I'm running this grammar: https://github.com/joankaradimov/Magnetar/blob/master/MagnetarCraft/src/iscript_parser.cpp#L71 ... with this input file: https://raw.githubusercontent.com/neivv/aice/master/test_scripts/vanilla.txt

On v1.8.5 I'm observing parse times of below 1 second. On 1.8.6 it's above 10 seconds.

Similarly -- on the web playgound I was running identical examples for under 150 ms the previous week. I'm assuming the version over there was updated these last couple of days, since the execution times are suddenly 1-2 orders of magnitude worse.

yhirose commented 5 months ago

@joankaradimov I guess this commit causes this problem. I'll take a look at it some time this weekend. Thanks for catching the serious problem!

joankaradimov commented 5 months ago

In that case I think it might be this line. There are multiple std::string constructors being called within a while loop. This line can easily be moved outside the loop. And then the additional std::string allocations can be avoided altogether in the non-case-insensitive case.

This improves the situation a little bit, but it does not resolve it completely. The performance is still worse than 1.8.5.

A much better solution would be to get rid of the ignore_case_ checks in match and tweak the dictionary in the trie...

std::map<std::string, Info, std::less<>> dic_;

... to use case-insensitive comparisons instead of std::less when necessary.

yhirose commented 5 months ago

@joankaradimov could you check performance with the latest peglib.h in the master branch? If you confirm that it fixes the performance regression, I'll bump the version to 1.8.8. Thanks!

joankaradimov commented 5 months ago

@yhirose I can confirm the problem is fixed.

From ~10 seconds previously down to below 50 ms now.

yhirose commented 5 months ago

It's now included in v1.8.8. Thanks for your fine contribution!

joankaradimov commented 5 months ago

Thank you for the quick responses and fixes!

davemcatcisco commented 5 months ago

@yhirose - Thanks for this. Are you responsible for the vcpkg? That's still sitting at 1.8.6.

yhirose commented 5 months ago

@joankaradimov no. I don't know who are working on vcpkg, or other package managers like conan.