Hans Åberg wrote:

> > Here's an example which springs to mind: deeply nested right-associative
> > operators. As you will see if you follow the link, the issue showed up in a
> > real application and the problem was not obvious to the person it affected.
> > 
> > https://unix.stackexchange.com/questions/185923/eval-limitation-with-piped-commands/186446
> This in fact a very good example in the context, as the parser
> stack may not be reduced in some cases.

I admit it is an example, but I don't agree it's very practical.
What they're doing there borders on shell abuse IMHO -- just because
you can do something in the shell doesn't mean you should start
thousands of processes for what a single grep (using a series of
"-e" options, or probably better reading the REs from a file with
"-f") can do much more efficiently (avoid writing and reading back
each non-matching line thousands of times).

> In the case of the C parser, the limit is set by YYMAXDEPTH with
> default 10000 as the link notes, which explains why it is the same
> on all platforms; cf. the Bison manual, sec. 5.10, "Memory
> Management". The C++ parser does not have that variable and limit,
> it seems.

Indeed, I checked with the calc++ example (switching to right
associativity for testing) that it can handle at least 10 million
without problems.

So I actually ran some tests and the results are interesting. Even
though vector needs to reallocate a few times (really just a few
times since it grows exponentially), it's still faster, apparently
the double indirection of deque costs more. (I did check capacity()
to make sure it actually grows with %right, not with %left.) These
are the timings on my machine using unique_ptr<int> for the semantic

        vector  deque
%left   7.7s    7.9s
%right  8.9s    9.5s

So go ahead and use deque if you prefer, but now I'm even less
convinced it's worth it. :)

In fact that's interesting to me outside of Bison. In another
program I wrote in a different language long time ago which doesn't
use Bison, I had implemented a double indirect allocation much like
deque. I plan to port it to C++ soon, and I had expected to use
deque for that, but now I wonder if vector won't actually be faster.
Well, at least with C++ containers, I can switch very easily and
test it then ...


Reply via email to