diff options
| author | Andrew Kelley <andrew@ziglang.org> | 2021-06-25 12:50:18 -0700 |
|---|---|---|
| committer | Andrew Kelley <andrew@ziglang.org> | 2021-06-25 12:58:21 -0700 |
| commit | 73f77f30804f3a512fbb35caad3d87ff2778ecc0 (patch) | |
| tree | bcb3f80f6faea5847b83e6ed066c2fc3c4679306 /lib/std | |
| parent | 49b3986417378278cef4157e71c38a817726ddc8 (diff) | |
| download | zig-73f77f30804f3a512fbb35caad3d87ff2778ecc0.tar.gz zig-73f77f30804f3a512fbb35caad3d87ff2778ecc0.zip | |
AstGen: fix O(N^2) perf for many decls with same parent
AstGen was calling findLineColumn() for every sibling Decl, using the
parent Decl as the starting point for the search for newlines. This
resulted in poor performance for large numbers of Decls with the same
parent.
The solution is simple: since AstGen progresses monotonically through
the AST, keep a single cursor into the source file, and whenever
line/column information is needed, advance the cursor. This guarantees
O(N) on the number of bytes in the file.
Perf:
As an example I ran ast-check on zigwin32/win32/everything.zig
(a 17 MiB file) in master branch, and after this commit.
With master branch, I killed the process after 17 seconds out of
boredom. With this commit, it completed in 300 milliseconds.
Closes #9234
Diffstat (limited to 'lib/std')
0 files changed, 0 insertions, 0 deletions
