> 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. https://en.wikipedia.org/wiki/Handle_(computing) https://en.wikipedia.org/wiki/Cheney%27s_algorithm