Re: Why are LR parsers faster than using if conditions

  Quinn Tyler Jackson <quinn-j@shaw.ca> wrote:


> 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.


A recommendation: Verify that your profiling tool is accurate. I have
seen profilers that introduced significant errors when profiling
functions with very short execution time. I'd profile something like


      unsigned int f (unsigned int x) { return x + 1; }
      unsigned int g (unsigned int x) {
            unsigned int i, result;
            for (i = 0, result = 0; i < x; ++i) result += f (i);
            return result; }
      unsigned int h (unsigned int x) {
            unsigned int i, result;
            for (i = 0, result = 0; i < x; ++i) result += g (i);
            return result; }


      int main (void) { h (10000); return 0; }


Make f extern in a separate file so it doesn't get optimised away.
Profile and compare to the real runtime. One profiler that I used added
about 160 cycles to g() for every call to f() that it made, so the
numbers were total nonsense.


And profiling probably prevented inlining - so your actual execution
times might be much less than you thought.

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