> On 11 Mar 2018, at 17:01, Frank Heckenbach <f.heckenb...@fh-soft.de> 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 old computers, such a limit might have been seen as necessary.

>> 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
> values:
>        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. :)

It is a good chance it varies with the application.

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

Called handles. They may be required if objects pointed to need to move, as in 
a two space copy gc.

Reply via email to