О(log n^2) config parser time regression in 2.0.11

[Yanko Kaneti]

On Thu, 2023-04-27 at 23:15 +0200, Ondrej Zajicek wrote:
> On Wed, Apr 26, 2023 at 12:28:59AM +0300, Yanko Kaneti wrote:
> > Hello,
> > 
> > The recent bird1 EOL announcement nudged me to try a 1 to 1 (or close to
> > it) migration of a legacy 1.6 config to 2.0. Without using any of the
> > fancy new 2.0 features to keep things lazy.
> > 
> > The old config has a giant 100M generated case statement in a function.
> > Turns out with 2.0.11 and later (bisected to 
> > 
> >     1ac8e11b: Filter: Implement mixed declarations of local variables
> > 
> > ) the config parser of the entire config couldn't finish in reasonable
> > time.
> 
> 
> Hello
> 
> This was particularly interesting issue, caused by two long-term bugs
> triggered by an unrelated change (1ac8e11b):
> 
> 1) Symbol hash table used only symbol name and not symbol scope as a hash
> key, therefore lookup time could be linear in number of different symbols
> of the same name.
> 
> 2) Even keywords like 'if', 'then', 'return' were registered in the
> symbol table as symbols (in particular scope).
> 
> The change 1ac8e11b just caused each switch-case to be a (potentially)
> separate scope, instead of one scope per function, therefore the symbol
> table were filled (due to bug 2) by separate copies of keywords, which
> (due to bug 1) caused quadratic time.
> 
> Note that you could see this quadratic time even in 1ac8e11b^, if you use
> thousands of functions instead of thousands of switch-cases.
> 
> Thanks for troubleshooting!
> 
> Fixed:
> 
> https://gitlab.nic.cz/labs/bird/-/commit/9b471e72d75c154f3b8c4fa134c7c9f1a55fe27f
> https://gitlab.nic.cz/labs/bird/-/commit/a8a64ca0fed41c78376b27880e934296bd3c3a7f

Nice! I've tried those and it helped to get the whole giant config
loaded fast and without problems. 

Thanks Ondrej !

- Yanko