rules: rewrite
Rewrite the rules file parser for clarity, performance and memory usage
reduction. The previous implementation was quite hard to navigate and
did a lot of unnecessary work and copying.
This implementation keeps along just the state necessary, and doesn't
perform any copying of the file's content (although the entire file is
mmap'ed as before). Hopefully it's also easier to understand, has better
documentation, and better error checking and reporting. We try to
reproduce the previous behavior in every case.
Note: the diff is pretty confusing; it's likely better to look at the
file directly.
Benchmarks:
On an old 32-bit Intel processor.
gcc -O2 -pg
./test/rulescomp bench
grof test/rulescomp
Before:
compiled 1000 keymaps in 14.863564304s
% cumulative self self total
time seconds seconds calls ms/call ms/call name
49.33 4.43 4.43
30610000 0.00 0.00 yylex
17.93 6.04 1.61 31000 0.05 0.22 yyparse
6.57 6.63 0.59 1000 0.59 0.59 load_rules
3.23 6.92 0.29 3637000 0.00 0.00 AppendStmt
2.45 7.14 0.22 472000 0.00 0.00 AddKeySymbols
2.12 7.33 0.19 3591000 0.00 0.00 atom_intern
2.12 7.52 0.19 518000 0.00 0.00 FindNamedKey
2.00 7.70 0.18 230000 0.00 0.00 FreeStmt
1.78 7.86 0.16 1000 0.16 0.17 UpdateModifiersFromCompat
1.34 7.98 0.12 732000 0.00 0.00 AddKeyName
1.34 8.10 0.12 __x86.get_pc_thunk.bx
After:
compiled 1000 keymaps in 13.874666269s
% cumulative self self total
time seconds seconds calls ms/call ms/call name
49.82 4.26 4.26
30610000 0.00 0.00 yylex
22.22 6.16 1.90 31000 0.06 0.22 yyparse
2.92 6.41 0.25 3591000 0.00 0.00 atom_intern
2.57 6.63 0.22 1000 0.22 0.25 xkb_components_from_rules
2.11 6.81 0.18 3637000 0.00 0.00 AppendStmt
2.11 6.99 0.18 230000 0.00 0.00 FreeStmt
1.99 7.16 0.17 518000 0.00 0.00 FindNamedKey
1.99 7.33 0.17 1000 0.17 0.17 UpdateModifiersFromCompat
1.99 7.50 0.17 __x86.get_pc_thunk.bx
1.52 7.63 0.13 150000 0.00 0.00 AddInterp
1.40 7.75 0.12 472000 0.00 0.00 AddKeySymbols
On a newer 64-bit Intel processor.
gcc -O2
./test/rules-file bench
Before:
processed 20000 times in 15.940546625s
After:
processed 20000 times in 5.295026345s
Allocations:
gcc -O2
valgrind test/rulescomp
Before:
total heap usage: 257,519 allocs, 257,519 frees, 14,766,529 bytes allocated
After:
total heap usage: 240,756 allocs, 240,756 frees, 14,007,886 bytes allocated
Signed-off-by: Ran Benita <ran234@gmail.com>