RE: Why are LR parsers faster than using if conditions

Clint Olsen said:


> I'll have to second John's assertion that lexing is the most expensive
> phase of parsing. I've profiled quite a few pieces of software that
> have used yacc, bison, lemon, and Parse::Yapp for parsing and lex,
> flex, and re2c for lexing, and the results have been pretty much the
> same.


Here's what the Meta-S parsing engine shows as being the most expensive 15
methods of the test-harness (which exercises 90% of the library's
functionality for regression testing):


"Method Name","% in Method","% with
Children","Called","Average","Minimum","Maximum","Average with Children"
"CShuString::CShuString","0.2","30.7","12,606","1.6","1.0","34.3","304.1"
"CShuString::StringRep::StringRep","0.3","30.3","16,702","2.2","0.6","37.5",
"226.5"
"CShuString::~CShuString","2.1","8.6","197,032","1.3","1.1","40.3","5.5"
"CShuString::destroyString","2.0","7.2","261,184","1.0","0.8","41.9","3.5"
"CShuString::operator+=","0.8","3.3","40,666","2.5","1.8","45.4","10.2"
"CShuString::StringRep::~StringRep","0.5","2.3","30,603","1.9","1.5","44.1",
"9.3"
"CShuString::CShuString","1.0","2.2","111,064","1.2","1.0","38.0","2.5"
"CShuString::operator=","0.4","1.8","45,011","1.1","0.9","48.4","5.0"
"CShuString::CShuString","0.6","1.6","72,442","1.0","0.8","37.6","2.7"
"CShuString::copy","0.9","1.3","117,453","0.9","0.8","39.1","1.3"
"CShuString::StringRep::decr","0.8","0.8","261,184","0.4","0.3","42.4","0.4"
"CShuString::StringRep::incr","0.7","0.7","234,942","0.4","0.3","39.6","0.4"
"CShuString::operator=","0.1","0.6","5,668","2.1","1.6","33.2","13.4"
"CShuString::NULL_STRING","0.5","0.5","117,489","0.6","0.5","41.0","0.6"


In other words -- some 30.7% of of the program's time is spent making
strings out of const char*'s.


That's without memory pooling compiled in.


Here is the same run, with pooling:


"Method Name","% in Method","% with
Children","Called","Average","Minimum","Maximum","Average with Children"
"CShuString::~CShuString","2.7","11.8","282,986","1.3","1.1","71.1","5.8"
"CShuString::destroyString","3.1","10.2","371,879","1.2","0.9","107.0","3.8"
"CShuString::operator+=","1.1","3.9","48,175","3.3","2.6","41.9","11.2"
"CShuString::StringRep::~StringRep","0.7","2.9","48,924","1.9","1.6","47.0",
"8.2"
"CShuString::operator=","0.7","2.8","61,729","1.7","1.4","37.7","6.2"
"CShuString::CShuString","1.4","2.7","145,100","1.3","1.1","70.7","2.6"
"CShuString::CShuString","0.9","2.5","107,430","1.1","0.9","38.1","3.2"
"CShuString::CShuString","0.2","2.4","18,592","1.6","1.3","25.3","17.7"
"CShuString::copy","1.4","2.1","169,159","1.1","0.9","45.1","1.7"
"CShuString::GetLength","1.8","1.8","274,745","0.9","0.8","43.2","0.9"
"CShuString::StringRep::StringRep","0.5","1.7","25,075","2.7","2.2","36.4","
9.4"
"CShuString::StringRep::decr","1.5","1.5","371,879","0.6","0.5","78.7","0.6"
"CShuString::StringRep::incr","1.3","1.3","322,987","0.6","0.5","36.2","0.6"
"CShuString::operator=","0.2","1.1","9,940","2.7","2.1","86.5","15.7"
"CShuString::operator+=","0.3","1.1","7,590","5.0","1.2","46.2","19.6"


With memory pooling -- most of the time is spent adjusting pointers in the
pool as strings get destroyed.


In other words, the great bottleneck of adaptive parsing as implemented in
the Meta-S library's is low-level memory management. Most of it is not being
done by the lexer, but that is only because Meta-S has no traditional lexer.
;-)


Of course, I've optimized this as much as I possibly can while remaining
sane -- new overriden, reference counting schemes everywhere I can put them,
et cetera - before those optimizations -- the situation was even more dire.


--
Quinn

Return to the comp.compilers page.
Search the comp.compilers archives again.