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

[Ondrej Zajicek]

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


-- 
Elen sila lumenn' omentielvo

Ondrej 'Santiago' Zajicek (email: santiago at crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
"To err is human -- to blame it on a computer is even more so."