With large prefix-lists (thousands of rules in one list) every commit, load and boot slows sharply as the list grows: a 2,000-rule list makes each commit take about 1.5 minutes, 4,000 rules about 6.5 minutes. On 1.5.1 a config with lists of 6,000 / 5,000 / 3,000 rules does not boot: the NIC-naming helper parses config.boot once per NIC and runs past udev's time limit, so the interfaces stay unnamed and the boot commit fails.
Root cause. Vytree.merge_children (src/vytree.ml) merges same-named siblings, such as the rule N entries of one list, one at a time, and re-sorts the merged node after every merge. sorted_children_of_node maps each sorted name back to its node with a linear search. Together that is O(n³) in the number of entries; a commit parses about 8 config trees.
Measurements.
| stock | with the fix | |
|---|---|---|
| one parse, 2,000-rule list | 4.61 s | 0.15 s |
| one parse, 4,000-rule list | 36.15 s | 0.64 s |
| one commit, 2,000-rule list | 88.6 s | 51.5 s |
| one commit, 4,000-rule list | about 390 s | about 104 s |
Fix direction. Collect the children of all same-named nodes, concatenate once, sort once; map names back to nodes through a hash table. The tree is unchanged: same order, the first node's data first, and a duplicated name still maps to its first node.