parser: fix quadratic pointer chasing
In the AST, lists (e.g. the list of statements in a file) are kept in
singly-linked lists -- each AST node has a `next` pointer available for
this purpose.
Previously, a node was added to the list by starting from the head,
chasing to the last, and appending. So creating a list of length N would
take ~N^2/2 pointer dereferences.
Now, we always (temporarily) keep the last as well, so appending is O(1)
instead of O(N).
Given a keymap
xkb_keymap {
xkb_keycodes {
minimum = 8;
minimum = 8;
minimum = 8;
minimum = 8;
minimum = 8;
[... repeated N times ...]
};
xkb_types {};
xkb_compat {};
xkb_symbols {};
};
The compilation times are
N | Before | After
--------|----------|-------
10,000 | 0.407s | 0.006s
20,000 | 1.851s | 0.015s
30,000 | 5.737s | 0.021s
40,000 | 12.759s | 0.023s
50,000 | 21.489s | 0.035s
60,000 | 40.473s | 0.041s
70,000 | 53.336s | 0.039s
80,000 | 72.485s | 0.044s
90,000 | 94.703s | 0.048s
100,000 | 118.390s | 0.057s
Another option is to ditch the linked lists and use arrays instead. I
got it to work, but its more involved and allocation heavy so turns out
to be worse without further optimizations.
Signed-off-by: Ran Benita <ran@unusedvar.com>