search

yhirose / cpp-peglib

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

Packrat uses too much memory #256

Closed w4454962 closed 1 year ago

w4454962 commented 1 year ago

Originally, the "peg" algorithm runs at an exponential speed. In order to pursue linear speed, packrat uses an exponential memory space, that is, the number of rules * the length of input characters. When the input files are huge, for example, 30 mb files with 100 rules require 3 gb of memory space in theory. With such a large amount of memory, the amount of computation consumed by memory management alone exceeds that of pure deep search, Packrat is not a very rational solution

I just tried to input a 28mb file and let my computer's memory eat up. Then I got stuck directly. I forced the computer to restart to recover.....

yhirose commented 1 year ago

@w4454962, thanks for the feedback and sorry to hear that your machine got frozen caused by this library. Packrat can work on certain type of PEG grammar effectively, but not for all. This is not only a problem with cpp-httplib, but I think any other Packrat parsers have the same issue as well...